Ed25519 & X25519

What is 25519?

25519 refers to the number \(2^{255}-19\). \(2^{255}-19\) is a large prime number and we use it to define a prime field \(\mathbb{F}(p)\). In this prime field, take an elliptic curve as:

$$-x^2+y^2=1-\frac{121665}{121666}x^2y^2$$

The selected base point is B=(15112 22134 95354 007725 011514 09588 531511 454012 69304 18572 06046 11328 39498 47762 202, 46316 83569 49264 781694 28394 003475 16314 13079 93866 25622 56157 830336 03165 25185 5960), and the corresponding order is \(L = 2^{252}+27742317777372353535851937790883648493\).

The private key and the public key of Ed25519

The private key of Ed25519 is a 32-byte data sk. The public key is calculated as follows:

1. Calculate SHA2-512(sk), get the 64-byte digest result, and take the first 32 bytes as k';
2. Modify the value of k' as follows: k'[0] &= 248,k'[31] &= 127,k'[31] |= 64, then treat k' as a little-endian number (s);
3. Calculate the point \(\text{P}=s\text{B}\) and note that the horizontal and vertical coordinates of \(\text{P}\) are \(x_p\) and respectively \(y_p\);
4. Replace the highest bit of \(y_p\) with the lowest bit of \(x_p\), and then save \(y_p\) in little endian, which is the final public key.

The signature in Ed25519

The process of signing is as follows:

1. Still use sk to represent the private key, calculate SHA2-512(sk), get the 64-byte digest result, get the number \(s\) according to the method of generating the public key, and record the remaining 32 bytes as the prefix;
2. Denote the data to be signed as M, and compute SHA2-512(prefix || M), where a||b means string a concatenated with string b, and then the digest value is regarded as a little-endian number \(r\);
3. Calculate the point \(\text{P}=r\text{B}\), and use the same encoding method of the public key to represent this point, denoted as R;
4. Calculate SHA2-512(R || pk || M), where pk represents the encoded public key, and then interpret the digest result as a little-endian number \(k\);
5. Calculate \(S = (r + k \cdot s)~\text{mod}~L\) and interpret it in little endian;
6. Use R || S as the final signature.

Calculation example

Let's take the test data in RFC 8032 as an example to show the calculation process:

• Input data:

  • Private key: sk=4c cd 08 9b 28 ff 96 da 9d b6 c3 46 ec 11 4e 0f 5b 8a 31 9f 35 ab a6 24 da 8c f6 ed 4f b8 a6 fb
  • Data to be signed: 72

• Calculation:

  • Public key
  • Signature

First look at the public key:

1. SHA2-512(sk) = 6e bd 9e d7 58 82 d5 28 15 a9 75 85 ca f4 79 0a 7f 6c 6b 3b 7f 82 1c 5e 25 9a 24 b0 2e 50 2e 11 45 66 84 82 91 da ca f2 25 cc 63 de b3 48 da 31 8e 2c 2e 17 b0 0b 81 60 f9 ce 6b fa 04 72 91 1d
2. k' = 68 bd 9e d7 58 82 d5 28 15 a9 75 85 ca f4 79 0a 7f 6c 6b 3b 7f 82 1c 5e 25 9a 24 b0 2e 50 2e 51, s = 0x51 2e 50 2e b0 24 9a 25 5e 1c 82 7f 3b 6b 6c 7f 0a 79 f4 ca 85 75 a9 15 28 d5 82 58 d7 9e bd 68
3. \(\text{P}=r\text{B}=\)`(0x74 ad 28 20 5b 4f 38 4b c0 81 3e 65 85 86 4e 52 80 85 f9 1f b6 a5 09 6f 24 4a e0 1e 57 de 43 ae, 0x0c 66 f4 2a f1 55 cd c0 8c 96 c4 2e cf 2c 98 9c bc 7e 1b 4d a7 0a b7 92 5a 89 43 e8 c3 17 40 3d)
4. Since the lowest bit of \(x_p\) is 0, the final public key is the small endian \(y_p\), ie 3d 40 17 c3 e8 43 89 5a 92 b7 0a a7 4d 1b 7e bc 9c 98 2c cf 2e c4 96 8c c0 cd 55 f1 2a f4 66 0c.

Then the signature:

1. s = 0x51 2e 50 2e b0 24 9a 25 5e 1c 82 7f 3b 6b 6c 7f 0a 79 f4 ca 85 75 a9 15 28 d5 82 58 d7 9e bd 68, prefix = 45 66 84 82 91 da ca f2 25 cc 63 de b3 48 da 31 8e 2c 2e 17 b0 0b 81 60 f9 ce 6b fa 04 72 91 1d;
2. SHA2-512(prefix || M) = d3 ed 25 99 eb 78 01 8f b1 6d f3 66 34 c8 cc 5c 59 25 53 6d 25 8f 8d 67 6a 75 0a 5f 62 bf 0c e3 96 d4 e1 6d c7 01 d6 3e 8b 00 1b cb 90 2f 27 b7 5b ca 85 83 c3 4d ea f3 1a 37 3c df 12 d0 71 4f, then r = 0x4f 71 d0 12 df 3c 37 1a f3 ea 4d c3 83 85 ca 5b b7 27 2f 90 cb 1b 00 8b 3e d6 01 c7 6d e1 d4 96 e3 0c bf 62 5f 0a 75 6a 67 8d 8f 25 6d 53 25 59 5c cc c8 34 66 f3 6d b1 8f 01 78 eb 99 25 ed d3;
3. \(\text{P}=r\text{B}=\)(0x15 7f 73 61 c5 77 aa d3 6f 67 ed 33 e3 8d c7 be 00 01 4f ec c2 16 5c a5 ce e9 ee E1 9f e4 d2 c1, 0x5a 69 db eb 23 22 76 b3 8f 3f 50 16 54 7b b2 a2 40 25 64 5f 0b 82 0e 72 b8 ca d4 f0 a9 09 a0 92), coded as 92 a0 09 a9 f0 d4 Ca b8 72 0e 82 0b 5f 64 25 40 a2 b2 7b 54 16 50 3f 8f b3 76 22 23 eb db 69 da, denoted as R;
4. SHA2-512(R || pk || M) = a2 71 df 0d 2b 0d 03 bd 17 b4 ed 9a 4b 6a fd df 2e 73 28 7f d6 30 f1 a1 37 d8 7c e8 73 a5 91 cc 31 b6 Dd 85 2a 98 b5 dd 12 26 fe 99 3d 82 28 27 8c eb a2 1f 80 b8 fc 95 98 6a 70 d7 1e df 3f af, then k = 0xaf 3f df 1e d7 70 6a 98 95 fc b8 80 1f a2 Eb 8c 27 28 82 3d 99 fe 26 12 dd b5 98 2a 85 dd b6 31 cc 91 a5 73 e8 7c d8 37 a1 f1 30 d6 7f 28 73 2e df fd 6a 4b 9a ed b4 17 bd 03 0d 2b 0d df 71 a2;
5. \(S = (r + k \cdot s)~\text{mod}~L\) = 0x00 0c bb 12 16 29 0d b0 ee 2a 30 b4 ae 2e 7b 38 8c 1d f1 d0 13 36 8f 45 6e 99 15 3e e4 c1 5a 08;
6. The final signature is R spelled S, so it is 92 a0 09 a9 f0 d4 ca b8 72 0e 82 0b 5f 64 25 40 a2 b2 7b 54 16 50 3f 8f b3 76 22 23 eb db 69 da 08 5a c1 e4 3e 15 99 6e 45 8f 36 13 d0 f1 1d 8c 38 7b 2e ae b4 30 2a ee b0 0d 29 16 12 bb 0c 00.

X25519

Since we can use this curve to implement the signature operation, is there any other operation that can be done? The answer is yes. Daniel J. Bernstein used this curve to design an ECDH algorithm called X25519 (also known as Curve25519). The cleverness of this algorithm is that the key is calculated and exchanged using only the x value of the point.

It should be noted that in X25519, the actual curve used is

$$y^2=x^3+486662x^2+x$$

This curve is equivalent to the curve used by Ed25519.

In X25519, Alice and Bob generate two random numbers \(a\) and \(b\) respectively, Alice calculates \(X(aP)\) passed to Bob, and Bob calculates \( X(bP)\) is passed to Alice. Where \(P\) is a point and \(X(P)\) represents the abscissa of the point \(P\). Thus, the public key is \(X(abP)\).

The base point chosen by X25519 is \(X(P)=9\).

For more design considerations for the X25519, please see [In-depth understanding of X25519] (https://github.com/longcpp/CryptoInAction/blob/master/intro-ed25519/190902-intro-x25519.pdf).