Elliptic Curve Operations

In addition to high level operations for signatures, key agreement, and message encryption using elliptic curve cryptography, the library contains lower level interfaces for performing operations such as elliptic curve point multiplication.

All operations described here are constant time (avoiding timing/cache based side channels) unless otherwise documented. Usually this is denoted by including vartime in the name.

Note

Prior to 3.6.0, Botan used BigInt to represent scalar values, and EC_Point for elliptic curve points in Jacobian projective form. EC_Point still exists, but is intentionally undocumented, and will be removed in Botan4.

Warning

The following interfaces are used to implement the elliptic curve signature and key agreement schemes within the library. They are exposed to applications to allow creating custom protocols, such as for example a threshold signature scheme or a PAKE. Ordinary users do not need to use these, outside of perhaps something like deserializing a EC_Scalar and passing it to a constructor.

class EC_Scalar

An elliptic curve scalar; that is, an integer in the range [0,n) where n is size of the prime order subgroup generated by the standard group generator.

Note that while zero is a representable value, some of the deserialization functions reject zero.

static std::optional<EC_Scalar> deserialize(const EC_Group &group, std::span<const uint8_t> buf)

Deserialize a scalar. The bytestring must be exactly the length of the group order; neither inputs with excess leading zero bytes nor short encodings are accepted.

Returns nullopt if the length is incorrect or if the integer is not within the range [1,n) where n is the group order.

static EC_Scalar from_bytes_with_trunc(const EC_Group &group, std::span<const uint8_t> buf)

Convert a bytestring to a scalar using the ECDSA truncation rules. This can return zero.

static EC_Scalar from_bytes_mod_order(const EC_Group &group, std::span<const uint8_t> buf)

Treating the input as the big-endian encoding of an integer, reduce that integer modulo n.

The encoded integer should be no greater than n**2.

static EC_Scalar random(const EC_Group &group, RandomNumberGenerator &rng)

Return a random non-zero scalar value

static EC_Scalar gk_x_mod_order(const EC_Scalar &k, RandomNumberGenerator &rng, std::vector<BigInt> &ws)

Compute the elliptic curve scalar multiplication (g*k) where g is the standard base point on the curve. Then extract the x coordinate of the resulting point, and reduce it modulo the group order.

If k is zero (resulting in the scalar multiplication producing the identity element) then this function returns zero.

size_t bytes() const

Return the byte length of the scalar

void serialize_to(std::span<uint8_t> buf) const

Serialize the scalar to the provided span. It must have length exactly equal to the value returned by bytes.

bool is_zero() const

Returns true if this scalar value is zero

bool is_nonzero() const

Returns true if this scalar value is not zero

EC_Scalar invert() const

Return the multiplicative inverse, or zero if *this is zero

EC_Scalar invert_vartime() const

Same as EC_Scalar::invert, except that the inversion is allowed to leak the value of the scalar to side channels.

EC_Scalar negate() const

Return the additive inverse

EC_Scalar operator+(const EC_Scalar &x, const EC_Scalar &y)

Addition modulo n

EC_Scalar operator-(const EC_Scalar &x, const EC_Scalar &y)

Subtraction modulo n

EC_Scalar operator*(const EC_Scalar &x, const EC_Scalar &y)

Multiplication modulo n

bool operator==(const EC_Scalar &x, const EC_Scalar &y)

Equality test

class EC_AffinePoint

A point on the elliptic curve.

static EC_AffinePoint::generator(const EC_Group &group)

Return the standard generator of the group

static EC_AffinePoint::identity(const EC_Group &group)

Return the identity element of the group (aka the point at infinity)

EC_AffinePoint(const EC_Group &group, std::span<const uint8_t> bytes)

Point deserialization. Throws if invalid, including if the point is not on the curve.

This accepts SEC1 compressed or uncompressed formats

static std::optional<EC_AffinePoint> deserialize(const EC_Group &group, std::span<const uint8_t> bytes)

Point deserialization. Returns nullopt if invalid, including if the point is not on the curve.

This accepts SEC1 compressed or uncompressed formats

bool is_identity() const

Return true if this point is the identity element.

EC_AffinePoint mul(const EC_Scalar &scalar, RandomNumberGenerator &rng, std::vector<BigInt> &ws) const

Variable base scalar multiplication. Constant time. If the rng object is seeded, also uses blinding and point rerandomization.

static EC_AffinePoint g_mul(const EC_Scalar &scalar, RandomNumberGenerator &rng, std::vector<BigInt> &ws)

Fixed base scalar multiplication. Constant time. If the rng object is seeded, also uses blinding and point rerandomization.

static std::optional<EC_AffinePoint> mul_px_qy(const EC_AffinePoint &p, const EC_Scalar &x, const EC_AffinePoint &q, const EC_Scalar &y, RandomNumberGenerator &rng)

Constant time 2-ary multiscalar multiplication. Returns p*x + q*y, or nullopt if the resulting point was the identity element.

static EC_AffinePoint add(const EC_AffinePoint &p, const EC_AffinePoint &q)

Elliptic curve point addition.

Note

This point addition operation is relatively quite expensive since it must convert the point directly from projective to affine coordinates, which requires an expensive field inversion. This is, however, sufficient for protocols which just require a small number of point additions. In the future a public type for projective coordinate points may also be added, to better handle protocols which require many point additions. If you are implementing such a protocol using this interface please open an issue on Github.

EC_AffinePoint negate() const

Return the negation of this point.

static EC_AffinePoint hash_to_curve_ro(const EC_Group &group, std::string_view hash_fn, std::span<const uint8_t> input, std::span<const uint8_t> domain_sep)

Hash to curve (RFC 9380), random oracle variant.

This is currently only supported for a few curves.

static EC_AffinePoint hash_to_curve_nu(const EC_Group &group, std::string_view hash_fn, std::span<const uint8_t> input, std::span<const uint8_t> domain_sep)

Hash to curve (RFC 9380), non-uniform variant.

This is currently only supported for a few curves.

size_t field_element_bytes() const

Return the size of the x and y coordinates, in bytes.

void serialize_x_to(std::span<uint8_t> bytes) const

Serialize the x coordinate to the output span, which must be exactly of the expected size (1 field element)

void serialize_y_to(std::span<uint8_t> bytes) const

Serialize the y coordinate to the output span, which must be exactly of the expected size (1 field element)

void serialize_xy_to(std::span<uint8_t> bytes) const

Serialize the x and y coordinates to the output span, which must be exactly of the expected size (2 field elements)

void serialize_compressed_to(std::span<uint8_t> bytes) const

Serialize the compressed SEC1 encoding to the output span, which must be exactly of the expected size (1 field element plus 1 byte)

void serialize_uncompressed_to(std::span<uint8_t> bytes) const

Serialize the uncompressed SEC1 encoding to the output span, which must be exactly of the expected size (2 field elements plus 1 byte)

class EC_Group::Mul2Table

This class stores precomputed tables for variable time 2-ary multiplications. These are commonly used when verifying elliptic curve signatures.

Mul2Table(const EC_AffinePoint &h)

Set up a table for computing g*x + h*y where g is the group generator.

std::optional<EC_AffinePoint> mul2_vartime(const EC_Scalar &x, const EC_Scalar &y) const

Return g*x + h*y, where it allowed to leak the values of x and y to side channels.

This returns nullopt if the product was the point at infinity.

bool mul2_vartime_x_mod_order_eq(const EC_Scalar &v, const EC_Scalar &x, const EC_Scalar &y) const

Compute g*x + h*y, then extract the x coordinate of that point. Reduce the x coordinate modulo the group order, then check if that value equals v.

This is faster that using EC_Group::Mul2Table::mul2_vartime for this process, because this function can avoid converting the point out of projective coordinates.