Revision control
Copy as Markdown
Other Tools
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 :cpp:class:`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.
.. cpp: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.
.. cpp:function:: 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.
.. cpp:function:: 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.
.. cpp:function:: 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``.
.. cpp:function:: static EC_Scalar random(const EC_Group& group, RandomNumberGenerator& rng)
Return a random non-zero scalar value
.. cpp:function:: static EC_Scalar gk_x_mod_order(const EC_Scalar& k, RandomNumberGenerator& rng)
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.
.. cpp:function:: size_t bytes() const
Return the byte length of the scalar
.. cpp:function:: 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 :cpp:func:`bytes`.
.. cpp:function:: bool is_zero() const
Returns true if this scalar value is zero
.. cpp:function:: bool is_nonzero() const
Returns true if this scalar value is not zero
.. cpp:function:: EC_Scalar invert() const
Return the multiplicative inverse, or zero if `*this` is zero
.. cpp:function:: EC_Scalar invert_vartime() const
Same as :cpp:func:`EC_Scalar::invert`, except that the inversion is
allowed to leak the value of the scalar to side channels.
.. cpp:function:: EC_Scalar negate() const
Return the additive inverse
.. cpp:function:: EC_Scalar operator+(const EC_Scalar& x, const EC_Scalar& y)
Addition modulo `n`
.. cpp:function:: EC_Scalar operator-(const EC_Scalar& x, const EC_Scalar& y)
Subtraction modulo `n`
.. cpp:function:: EC_Scalar operator*(const EC_Scalar& x, const EC_Scalar& y)
Multiplication modulo `n`
.. cpp:function:: bool operator==(const EC_Scalar& x, const EC_Scalar& y)
Equality test
.. cpp:class:: EC_AffinePoint
A point on the elliptic curve.
.. cpp:function:: static EC_AffinePoint::generator(const EC_Group& group)
Return the standard generator of the group
.. cpp:function:: static EC_AffinePoint::identity(const EC_Group& group)
Return the identity element of the group (aka the point at infinity)
.. cpp:function:: 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
.. cpp:function:: 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
.. cpp:function:: bool is_identity() const
Return true if this point is the identity element.
.. cpp:function:: EC_AffinePoint mul(const EC_Scalar& scalar, RandomNumberGenerator& rng) const
Variable base scalar multiplication. Constant time. If the rng object is
seeded, also uses blinding and point rerandomization.
.. cpp:function:: static EC_AffinePoint g_mul(const EC_Scalar& scalar, RandomNumberGenerator& rng)
Fixed base scalar multiplication. Constant time. If the rng object is
seeded, also uses blinding and point rerandomization.
.. cpp:function:: 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.
.. cpp:function:: 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.
.. cpp:function:: EC_AffinePoint negate() const
Return the negation of this point.
.. cpp:function:: 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.
.. cpp:function:: 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.
.. cpp:function:: size_t field_element_bytes() const
Return the size of the ``x`` and ``y`` coordinates, in bytes.
.. cpp:function:: 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)
.. cpp:function:: 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)
.. cpp:function:: 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)
.. cpp:function:: 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)
.. cpp:function:: 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)
.. cpp:class:: EC_Group::Mul2Table
This class stores precomputed tables for variable time 2-ary multiplications.
These are commonly used when verifying elliptic curve signatures.
.. cpp:function:: Mul2Table(const EC_AffinePoint& h)
Set up a table for computing ``g*x + h*y`` where ``g`` is the group generator.
.. cpp:function:: 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.
.. cpp:function:: 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 :cpp:func:`EC_Group::Mul2Table::mul2_vartime`
for this process, because this function can avoid converting the point out
of projective coordinates.