Module crrl::ed448

source ·
Expand description

Edwards448 curve implementation.

This module implements generic group operations on the Edwards curve of equation x^2 + y^2 = 1 + d*x^2*y^2, over the finite field GF(2^448 - 2^224 - 1), for the constant d = -39081. This curve is described in [RFC 7748]. The signature algorithm Ed448, which operates on that curve, is described in [RFC 8032].

The curve has order 4*L for a given prime integer L (which is slightly lower than 2^446). A conventional base point is defined, that generates the subgroup of order L. Points used in public keys and signatures are normally part of that subgroup, though this is not verified (the function Point::is_in_subgroup() can be used to validate that a given point is in that subgroup).

A curve point is represented by the Point structure. Point instances can be used in additions and subtractions with the usual + and - operators; all combinations of raw values and references are accepted, as well as compound assignment operators += and -=. Specialized functions are available, in particular for point doubling (Point::double()) and for sequences of successive doublings (Point::xdouble()), the latter using some extra optimizations. Multiplication by an integer (u64 type) or a scalar (Scalar structure) is also accepted, using the * and *= operators. Scalars are integers modulo L. The Scalar structure represents such a value; it implements all usual arithmetic operators (+, -, * and /, as well as +=, -=, *= and /=).

Scalars can be encoded over 56 bytes (using unsigned little-endian convention) and decoded back. Encoding is always canonical, and decoding always verifies that the value is indeed in the canonical range (note: within the context of Ed448, the second half of a signature is an encoded scalar but is represented over 57 bytes, not 56, as per the specification in RFC 8032; the last byte of the signature is then always zero).

Points can be encoded over 57 bytes, and decoded back. As with scalars, encoding is always canonical, and verified upon decoding.

The PrivateKey structure represents a private key for the Ed448 signature algorithm. It is instantiated from a 57-byte seed; the seed MUST have been generated with a cryptographically secure generator (this library does not include provisions for this generation step). Following [RFC 8032], the seed is derived into a secret scalar, and an extra private value used for deterministic signature generation. The private key allows signature generation with the Ed448 and Ed448ph variants (in the latter, the pre-hashed message is provided by the caller). The PublicKey structure represents a public key, i.e. a curve point (and its 57-byte encoding as an additional field). Signature verification functions are available on PublicKey, again for Ed448 and Ed448ph.

Ed448 Edge Cases

Like Ed25519, there exist multiple variants of Ed448 implementations, with regard to the handling of some edge cases, e.g. non-canonical inputs. This implementation follows the strict RFC 8032 rules as follows:

  • Canonical encoding of both points and scalars is enforced. Non-canonical encodings are rejected.

  • The cofactored verification equation is used (i.e. including the multiplication by 4).

  • Points outside of the subgroup of order L, including low-order points and the identity point, are accepted both for the R component of the signatures, and for public keys.

  • The S component of a signature is accepted as long as it is canonically encoded (i.e. in the 0 to L-1 range). Zero is accepted. The full 57 bytes are used: the last byte, and the top two bits of the second to last byte, though always of value 0, are checked.

Structs