This page aims to be a semi-formal specification of the Ed448-Goldilocks curve and its implementation. Ed448-Goldilocks' specification consists of three components:
Each number or variable in this specification is an element of a particular ring or field. Arithmetic operations are the operations in the appropriate field.
Let Z denote the ring of integers, and Z/pZ denote the field of integers modulo the prime number p.
For a group G and integer n, let nG denote the subgroup of elements which are n times an element of G.
The symbol √x will only be applied to x which are elements of a field Z/pZ, where p ≡ 3 mod 4. It always means the principal square root of x, namely x(p+1)/4. This principal square root is always square (i.e. a quadratic residue). It will be used only with a defense of why x must be square, or what to do if it is not.
For an element x of Z/pZ, let L(x) denote the Legendre symbol of x, which is 0 if x = 0, 1 if x is a nonzero square, and -1 otherwise. This can be computed as
Likewise, use of the field division operator / will be justified with an explanation of why the divisor cannot be zero, or what to do if it is.
The symbol || denotes concatenation of byte sequences.
Let HASH(x) denote a hash function suitable for use as a random oracle. For example, HASH() may be implemented as SHA512. Let PRF(k,v) denote a pseudorandom function which takes as input a pseudorandom key and an arbitrary-length value, and outputs 512 bits. For example, PRF may be implemented as HMAC-SHA512.
The elliptic curve Ed448-Goldilocks is the set of pairs
It supports a group operation
The identity point for the group operation is (0,1).
The order of the curve E is 4q, where
The base point g is the point in 4E with the least y-coordinate, namely:
Most ECC protocols use only the prime-order subgroup of the curve. That is, legitimate users should only compute elements of the q-order group 4E. However, it is computationally expensive to restrict inputs to this subgroup. But as we will see, it is cheap to restrict them to 2E. Therefore, all Goldilocks input and output formats are restricted to elements of 2E, and internal routines will generally only have to handle elements of 2E. (Aside: this is also useful for implementors who will use the isogenous twisted Edwards curve, because the addition formulas on that curve are complete for 2E, but not for all of E.)
Additional descriptions will be given to various sections for how to keep points within these subgroups.
An element x of the field Z/pZ is to be serialized as the least positive representative in little-endian form, that is, as a sequence of bytes SERp(x) := [bi],
For any sequence of bytes, the function DESERMODp deserializes them to a number x as above, and then returns x reduced modulo p.
For Goldilocks' base field, and for elements modulo its group order, the size of a serialized element is exactly 56 bytes.
The wire format of a point is designed to be compatible with a Montgomery ladder for simple and fast implementations of ECDH. Furthermore, it is a single-coordinate format in order to minimize the size of the public and private keys.
The wire format of a point (x,y) ∈ 4E is
To deserialize a point from binary form, let t := DESERp([b]), and let
A Goldilocks private key consists of k||s, where:
The corresponding public key is SERPT(2sg). The 2 here is chosen for consistency with other operations, which will need to clear the cofactor 2 of 2E.
The implementation stores the public key along with the private key, because it needs to hash the public key sometimes.