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.