Golidocks and the Edwards Bears

Goldilocks and the Edwards Bears

The usage of Curve 25519 is well known in the industry and is used with key exchange methods in SSL, Tor, and many other applications. Overall, Curve 25519 (created by Daniel J Bernstein,) uses a Montgomery curve of y² = x³ + 486662 x² + x with a prime number of 2²⁵⁵-19. In its key exchange mode, it integrates with ECDH (Elliptic Curve Diffie Hellman) and is named X25519.

But, we can also use a twisted Edwards Curve (x²+y²=1−dx²y²) to give us Ed25519. And so while Ed25519 gives 128-bit security, Ed448 enhances Ed25519 with the goldilocks prime (2⁴⁴⁸−2²²⁴−1) and increase the security from around 112 to 224 bits [paper]:

With Ed448, the public and the private keys are the same lengths, but the signature is double this length. In Ed448 we use the goldilocks version of an untwisted Edwards curve with x²+y²=1−39081x²y² and a prime of 2⁴⁴⁸−2²²⁴−1. An EdDSA private key (k) has b bits. We can then create a hash of this — and which is 2b long — to create a number of hash bits (such as using SHAKE256):

H(k)=(h0,h1,…,h2b−1)

We then calculate a value of s:

s=2n+∑2^i×h_i

Now we have a base point on the Edwards 448 curve of B, and determine the public key point (A) of:

A=[s]B

The public key is then:

ENC(A)

and where the ENC(A) encoding format takes an integer (A) which has the length of the prime number p and encodes it into a b length bit-string.

This process generates the public key and private key. In order to produce a signature of the message of M and with a private key of k, we first determine r which takes the hash bits and appends to the message:

r=H(hb||…||h(2b−1)||M)

and then compute R and S :

R=rB

k=H(ENC(R) || ENC(A) || PH(M))

S=(r+k×s)(mod p)

and where p is the Goldilocks prime number.

The EdDSA signature is then:

ENC(R) || ENC(S)

To verify the signature, we recover R and S. As before, we compute a constant value of k (and where A is the public key, R is part of the signature and M is the message):

k=H(ENC(R) || ENC(A) || PH(M))

Now we take B (the base point), S, R and kA, and check that SB is equal to (R + kA):

SB=R+kA

This works because SB=R+kA=rB+ksB=[B]S=[B](r+ks).

Note PM(M) just returns the message in a consistent form.

A sample run gives:

Message: Hello
Context: None

Alice private key: 6a56a7bf8ae2ebf3ac985db1aa55b25f9be38795e53e1ae4bba69d49cdffbd3c8496c1490ceeac29448f6d31b88f91ea985687cdd2f5821302
Alice Public key 9d7b6bc88eb8878c9cf0b3616c885be952dc5464c3f5a01833cfc4f50f471c677cee26a539236de11c531b883c2c0a6cbe098ca06b3a045200

Signature: b2968cc1fd3166a83eacface86116146b02b136a9aa9d94fbe0fd94c78082d24f3d90ce3160eaf1b1edbf3774298691119d6a9d1decf20c7003dd020c7a45878a99d37da4f7acaddd42e5e7a6adde3492cda0a35ac60f8b3e325c3f3f28ba79bb6a1a5c980e3437389d48870d69725b50600

Signature verified

Here is the code:

And here is a demo:

This works because SB = R + kA = rB + ksB = [B] S = [B] (r+ ks)