Ed448-Goldilocks

Fast, strong elliptic curve cryptography

This page aims to be a semi-formal specification of the Ed448-Goldilocks curve and its implementation. Ed448-Goldilocks' specification consists of three components:

Notation

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

L(x) = x(p-1)/2

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 curve

The elliptic curve Ed448-Goldilocks is the set of pairs

E : (x,y) ∈ (Z/pZ)2
where
p := 2448 - 2224 - 1
satisfying
y2 + x2 ≡ 1 - 39081 x2 y2

It supports a group operation

(x1,y1) + (x1,y1) := ( ( x1y2 + y1x2 ) / ( 1 - 39081 x1x2y1y2 ) , ( y1y2 - x1x2 ) / ( 1 + 39081 x1x2y1y2 ) )
Because d = -39081 is not square, this is a complete addition law. In particular, the denominators will never be zero. Practical implementations will use some sort of projective coordinates. Because the curve supports a complete addition formula, these formulas can be arranged to never produce either 1/0 or 0/0.

The identity point for the group operation is (0,1).

The order of the curve E is 4q, where

q := 181709681073901722637330951972001133588410340 \ 171829515070372549795146003961539585716195755 \ 291692375963310293709091662304773755859649779  
is prime.

The base point g is the point in 4E with the least y-coordinate, namely:

g := ( 117812161263436946737282484343310064665180535 \ 357016373416879082147939404277809514858788439 \ 644911793978499419995990477371552926308078495   , 19 )
I minimized the y-coordinate and not the x-coordinate because it is the more significant coordinate on an Edwards curve. For any point P ∈ E, the y-coordinates of P and -P are the same.

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.

Integer wire format

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 i from 0 to ceiling(log p / log 256) - 1
where
x = ∑ 256i bi ∈ [0, p-1]
For any number p, the partial function DESERp([bi]) deserializes ceiling(log p / log 256) bytes [bi] to produce x according to the above formula. It must signal an error and return no result if the bytes encode a number greater or equal to p.

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.

Curve point wire format

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

SERPT((x,y)) := SERp( L(x) ⋅ √((y-1)/(y+1)) )
The denominator cannot be zero because the only point (x,y) ∈ E with y = -1 is the 2-torsion point (0,-1), and this point is not in 4E. Furthermore (y-1)/(y+1) is a quadratic residue for every point (x,y) ∈ 2E except for (0,-1). Therefore, this encoding can encode any point in 2E.

To deserialize a point from binary form, let t := DESERp([b]), and let

m := (d-1) ⋅ (t2 + 1)2 + 4 ⋅ t2
where d = -39081. If m is not square, then the point is invalid. If m is square, then the decoded point is (x,y) where
x = 2t/√m   and   y = (1 + t2) / (1 - t2)
It is algebraically impossible for m to be zero. It is also not possible for (1 - t2) to be zero, because then m would not be square.

Public and private keys

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.

Elliptic-curve Diffie-Hellman

To do

Schnorr signatures

To do

Elligator

To do?

Password-authenticated key exchange

To do?