Botan::Ed448Point Class Reference

Representation of a point on the Ed448 curve. More...

#include <ed448_internal.h>

Public Member Functions
void	ct_conditional_assign (bool cond, const Ed448Point &other)
	Assign other to this if cond is true (constant time)
Ed448Point	double_point () const
	Double a point (RFC 8032 5.2.4)
	Ed448Point (const Gf448Elem &x, const Gf448Elem &y)
	Create a point from its coordinates x, y.
	Ed448Point (const Gf448Elem &x, const Gf448Elem &y, const Gf448Elem &z)
	Create a point from its projective coordinates X, Y, Z.
std::array< uint8_t, ED448_LEN >	encode () const
	Encode the point to its 57-byte representation (RFC 8032 5.2.2)
Ed448Point	operator+ (const Ed448Point &other) const
	Add two points (RFC 8032 5.2.4)
bool	operator== (const Ed448Point &other) const
	Check if two points are equal (constant time)
Ed448Point	scalar_mul (const Scalar448 &scalar) const
	Scalar multiplication.
Gf448Elem	x () const
	Getter for point coordinate x.
Gf448Elem	x_proj () const
	Getter for projective coordinate X.
Gf448Elem	y () const
	Getter for point coordinate y.
Gf448Elem	y_proj () const
	Getter for projective coordinate Y.
Gf448Elem	z_proj () const
	Getter for projective coordinate Z.

Static Public Member Functions
static Ed448Point	base_point ()
	Create the curve's base point ('B' in RFC 8032 5.2)
static Ed448Point	decode (std::span< const uint8_t, ED448_LEN > enc)
	Decode a point from its 57-byte encoding (RFC 8032 5.2.3)
static Ed448Point	identity ()
	Return the identity element.

Detailed Description

Representation of a point on the Ed448 curve.

The point is represented in projective coordinates (X, Y, Z). All operations are constant time.

Definition at line 25 of file ed448_internal.h.

Constructor & Destructor Documentation

Ed448Point() [1/2]

Botan::Ed448Point::Ed448Point ( const Gf448Elem & x, const Gf448Elem & y, const Gf448Elem & z )

inline

Create a point from its projective coordinates X, Y, Z.

Definition at line 34 of file ed448_internal.h.

: m_x(x), m_y(y), m_z(z) {}

References x(), and y().

Referenced by base_point(), ct_conditional_assign(), decode(), double_point(), identity(), operator+(), operator==(), and scalar_mul().

Ed448Point() [2/2]

Botan::Ed448Point::Ed448Point ( const Gf448Elem & x, const Gf448Elem & y )

inline

Create a point from its coordinates x, y.

Definition at line 37 of file ed448_internal.h.

: m_x(x), m_y(y), m_z(1) {}

References x(), and y().

Member Function Documentation

base_point()

Ed448Point Botan::Ed448Point::base_point ( )

static

Create the curve's base point ('B' in RFC 8032 5.2)

Definition at line 123 of file ed448_internal.cpp.

                                  {
   constexpr std::array<const uint64_t, WORDS_448> x = {0x2626a82bc70cc05e,
                                                        0x433b80e18b00938e,
                                                        0x12ae1af72ab66511,
                                                        0xea6de324a3d3a464,
                                                        0x9e146570470f1767,
                                                        0x221d15a622bf36da,
                                                        0x4f1970c66bed0ded};
   constexpr std::array<const uint64_t, WORDS_448> y = {0x9808795bf230fa14,
                                                        0xfdbd132c4ed7c8ad,
                                                        0x3ad3ff1ce67c39c4,
                                                        0x87789c1e05a0c2d7,
                                                        0x4bea73736ca39840,
                                                        0x8876203756c9c762,
                                                        0x693f46716eb6bc24};
   return Ed448Point(Gf448Elem(x), Gf448Elem(y));
}

References Ed448Point(), x(), and y().

Referenced by Botan::create_pk_from_sk(), Botan::sign_message(), and Botan::verify_signature().

ct_conditional_assign()

void Botan::Ed448Point::ct_conditional_assign	(	bool	cond,
		const Ed448Point &	other )

Assign other to this if cond is true (constant time)

Definition at line 214 of file ed448_internal.cpp.

                                                                         {
   m_x.ct_cond_assign(cond, other.m_x);
   m_y.ct_cond_assign(cond, other.m_y);
   m_z.ct_cond_assign(cond, other.m_z);
}

References Ed448Point().

decode()

Ed448Point Botan::Ed448Point::decode ( std::span< const uint8_t, ED448_LEN > enc )

static

Decode a point from its 57-byte encoding (RFC 8032 5.2.3)

Definition at line 73 of file ed448_internal.cpp.

                                                                   {
   // RFC 8032 5.2.3  Decoding
   // 1. First, interpret the string as an integer in little-endian
   //    representation.  Bit 455 of this number is the least significant
   //    bit of the x-coordinate, and denote this value x_0.  The
   //    y-coordinate is recovered simply by clearing this bit.  If the
   //    resulting value is >= p, decoding fails.
   if((enc.back() & 0x7F) != 0) {  // last byte is either 0x00 or 0x80
      throw Decoding_Error("Ed448 point has unacceptable x-distinguisher");
   }
   const bool x_distinguisher = enc.back() != 0;
   const auto y_data = std::span(enc).first<56>();
   if(!Gf448Elem::bytes_are_canonical_representation(y_data)) {
      throw Decoding_Error("Ed448 y-coordinate is not smaller than p");
   }
   const auto y = Gf448Elem(y_data);
 
   // 2. To recover the x-coordinate, the curve equation implies
   //    x^2 = (y^2 - 1) / (d y^2 - 1) (mod p).  The denominator is always
   //    non-zero mod p.  Let u = y^2 - 1 and v = d y^2 - 1.  To compute
   //    the square root of (u/v), the first step is to compute the
   //    candidate root x = (u/v)^((p+1)/4).  This can be done using the
   //    following trick, to use a single modular powering for both the
   //    inversion of v and the square root:
   //                      (p+1)/4    3            (p-3)/4
   //             x = (u/v)        = u  v (u^5 v^3)         (mod p)
   const auto d = -Gf448Elem(MINUS_D);
   const auto u = square(Gf448Elem(y)) - Gf448Elem::one();
   const auto v = d * square(Gf448Elem(y)) - Gf448Elem::one();
   const auto maybe_x = (u * square(u)) * v * root((square(square(u)) * u) * square(v) * v);
 
   // 3. If v * x^2 = u, the recovered x-coordinate is x.  Otherwise, no
   //    square root exists, and the decoding fails.
   if(v * square(maybe_x) != u) {
      throw Decoding_Error("Square root does not exist");
   }
   // 4. Finally, use the x_0 bit to select the right square root.  If
   //    x = 0, and x_0 = 1, decoding fails.  Otherwise, if x_0 != x mod
   //    2, set x <-- p - x.  Return the decoded point (x,y).
   if(maybe_x.is_zero() && x_distinguisher) {
      throw Decoding_Error("Square root of zero cannot be odd");
   }
   bool maybe_x_parity = maybe_x.is_odd();
   std::array<uint64_t, WORDS_448> x_data{};
   CT::Mask<uint64_t>::expand_bool(maybe_x_parity == x_distinguisher)
      .select_n(x_data.data(), maybe_x.words().data(), (-maybe_x).words().data(), WORDS_448);
 
   return {Gf448Elem(x_data), y};
}

References Botan::Gf448Elem::bytes_are_canonical_representation(), Ed448Point(), Botan::CT::Mask< T >::expand_bool(), Botan::Gf448Elem::is_odd(), Botan::Gf448Elem::one(), Botan::root(), Botan::square(), Botan::WORDS_448, and y().

Referenced by Botan::Ed448_PublicKey::check_key(), and Botan::verify_signature().

double_point()

Ed448Point Botan::Ed448Point::double_point

(

)

const

Double a point (RFC 8032 5.2.4)

Definition at line 175 of file ed448_internal.cpp.

                                          {
   // RFC 8032 5.2.4. - Point Addition (Double)
   const Gf448Elem B = square(m_x + m_y);
   const Gf448Elem C = square(m_x);
   const Gf448Elem D = square(m_y);
   const Gf448Elem E = C + D;
   const Gf448Elem H = square(m_z);
   const Gf448Elem J = E - (H + H);
   const Gf448Elem X3 = (B - E) * J;
   const Gf448Elem Y3 = E * (C - D);
   const Gf448Elem Z3 = E * J;
 
   return Ed448Point(X3, Y3, Z3);
}

References Ed448Point(), and Botan::square().

encode()

std::array< uint8_t, ED448_LEN > Botan::Ed448Point::encode

(

)

const

Encode the point to its 57-byte representation (RFC 8032 5.2.2)

Definition at line 141 of file ed448_internal.cpp.

                                                      {
   std::array<uint8_t, ED448_LEN> res_buf = {0};
 
   // RFC 8032 5.2.2
   //    All values are coded as octet strings, and integers are coded using
   //    little-endian convention. [...]
   //    First, encode the y-coordinate as a little-endian string of 57 octets.
   //    The final octet is always zero.
   y().to_bytes(std::span(res_buf).first<56>());
 
   //    To form the encoding of the point, copy the least significant bit of
   //    the x-coordinate to the most significant bit of the final octet.
   res_buf.back() = (static_cast<uint8_t>(x().is_odd()) << 7);
 
   return res_buf;
}

References Botan::Gf448Elem::is_odd(), Botan::Gf448Elem::to_bytes(), x(), and y().

identity()

Ed448Point Botan::Ed448Point::identity ( )

inlinestatic

Return the identity element.

Definition at line 40 of file ed448_internal.h.

{ return Ed448Point(Gf448Elem::zero(), Gf448Elem::one()); }

References Ed448Point(), Botan::Gf448Elem::one(), and Botan::Gf448Elem::zero().

Referenced by scalar_mul().

operator+()

Ed448Point Botan::Ed448Point::operator+

(

const Ed448Point &

other

)

const

Add two points (RFC 8032 5.2.4)

Definition at line 158 of file ed448_internal.cpp.

                                                              {
   // RFC 8032 5.2.4. - Point Addition (Add)
   const Gf448Elem A = m_z * other.m_z;
   const Gf448Elem B = square(A);
   const Gf448Elem C = m_x * other.m_x;
   const Gf448Elem D = m_y * other.m_y;
   const Gf448Elem E = (-Gf448Elem(MINUS_D)) * C * D;
   const Gf448Elem F = B - E;
   const Gf448Elem G = B + E;
   const Gf448Elem H = (m_x + m_y) * (other.m_x + other.m_y);
   const Gf448Elem X3 = A * F * (H - C - D);
   const Gf448Elem Y3 = A * G * (D - C);
   const Gf448Elem Z3 = F * G;
 
   return Ed448Point(X3, Y3, Z3);
}

References Ed448Point(), and Botan::square().

operator==()

bool Botan::Ed448Point::operator==

(

const Ed448Point &

other

)

const

Check if two points are equal (constant time)

Definition at line 206 of file ed448_internal.cpp.

                                                         {
   // Note that the operator== of of Gf448Elem is constant time
   const auto mask_x = CT::Mask<uint8_t>::expand_bool(x() == other.x());
   const auto mask_y = CT::Mask<uint8_t>::expand_bool(y() == other.y());
 
   return (mask_x & mask_y).as_bool();
}

References Ed448Point(), Botan::CT::Mask< T >::expand_bool(), x(), and y().

scalar_mul()

Ed448Point Botan::Ed448Point::scalar_mul

(

const Scalar448 &

scalar

)

const

Scalar multiplication.

Definition at line 190 of file ed448_internal.cpp.

                                                          {
   auto res = Ed448Point::identity();
 
   // Square and multiply (double and add) in constant time.
   // TODO: Optimization potential. E.g. for a = *this precompute
   //       0, a, 2a, 3a, ..., 15a and ct select and add the right one for
   //       each 4 bit window instead of conditional add.
   for(int16_t i = 445; i >= 0; --i) {
      res = res.double_point();
      // Conditional add if bit is set
      auto add_sum = res + *this;
      res.ct_conditional_assign(s.get_bit(i), add_sum);
   }
   return res;
}

References Ed448Point(), Botan::Scalar448::get_bit(), and identity().

Referenced by Botan::operator*().

x()

Gf448Elem Botan::Ed448Point::x ( ) const

inline

Getter for point coordinate x.

Definition at line 64 of file ed448_internal.h.

{ return m_x / m_z; }

Referenced by base_point(), Ed448Point(), Ed448Point(), encode(), and operator==().

x_proj()

Gf448Elem Botan::Ed448Point::x_proj ( ) const

inline

Getter for projective coordinate X.

Definition at line 55 of file ed448_internal.h.

{ return m_x; }

y()

Gf448Elem Botan::Ed448Point::y ( ) const

inline

Getter for point coordinate y.

Definition at line 67 of file ed448_internal.h.

{ return m_y / m_z; }

Referenced by base_point(), decode(), Ed448Point(), Ed448Point(), encode(), and operator==().

y_proj()

Gf448Elem Botan::Ed448Point::y_proj ( ) const

inline

Getter for projective coordinate Y.

Definition at line 58 of file ed448_internal.h.

{ return m_y; }

z_proj()

Gf448Elem Botan::Ed448Point::z_proj ( ) const

inline

Getter for projective coordinate Z.

Definition at line 61 of file ed448_internal.h.

{ return m_z; }

---

The documentation for this class was generated from the following files:

• src/lib/pubkey/curve448/ed448/ed448_internal.h
• src/lib/pubkey/curve448/ed448/ed448_internal.cpp