Ed25519 & X25519 - 有一说一

25519是什么？

25519指的是 $2^{255}-19$ 这个数字。$2^{255}-19$ 是一个很大的素数，我们用它来定义一个素数域 $\mathbb{F}(p)$。在这个素数域下，取一条椭圆曲线为：

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

如果选择基点为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)，则对应的阶数为$L= 2^{252}+27742317777372353535851937790883648493$。

Ed25519的私钥与公钥

Ed25519的私钥是一个32字节的数据sk，公钥计算方法如下：

计算SHA2-512(sk)，得到64字节的摘要值，取前32字节记为k'；
修改k'的值如下：k'[0] &= 248，k'[31] &= 127，k'[31] |= 64，然后把k'当作小端序的数字$s$；
计算点$\text{P}=s\text{B}$，记$\text{P}$的横纵坐标分别为$x_p$和$y_p$；
把$y_p$的最高比特换成$x_p$的最低比特，然后用小端序保存$y_p$，即为最终的公钥。

Ed25519的签名

签名的流程如下：

仍然用sk表示私钥，计算SHA2-512(sk)，得到64字节的摘要值，按照生成公钥的方法得到数$s$，记摘要剩余的32字节为prefix；
记待签名的数据为M，计算SHA2-512(prefix || M)，其中||表示拼接操作，然后把摘要值当作一个小端序的数$r$；
计算点$\text{P}=r\text{B}$，用公钥同样的编码方法表示这个点，记为R；
计算SHA2-512(R || pk || M)，其中pk表示编码后的公钥，然后把摘要值当作一个小端序的数$k$；
计算$S = (r + k \cdot s)~\text{mod}~L$，并用小端序保存；
R || S即为最终的签名。

计算示例

我们以RFC 8032中的测试数据为例展示一下计算过程：

输入数据：
- 私钥：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
- 待签名数据：72
计算：
- 公钥
- 签名

首先来看公钥：

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
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
$\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)
由于$x_p$的最低比特为0，所以最终的公钥即为小端序的$y_p$，即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。

然后是签名：

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；
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, 于是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；
$\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)，编码为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，记为R；
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，于是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；
$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；
最终的签名是R拼上S，所以为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

既然我们用这条曲线能实现签名运算，那还有别的运算能做吗？答案是肯定的。Daniel J. Bernstein使用这个曲线设计了一个ECDH算法，名为X25519（也叫做Curve25519）。这个算法的巧妙之处在于，仅利用点的横坐标来计算和交换密钥。

需要指出的是，在X25519中，实际使用的曲线为

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

而这一曲线与Ed25519使用的曲线是等价的。

在X25519中，Alice和Bob分别生成两个随机数$a$和$b$，Alice计算$X(aP)$传递给Bob，Bob计算$X(bP)$传递给Alice。其中，$P$是一个点，$X(P)$表示点$P$的横坐标。于是，公共的密钥就是$X(abP)$了。

X25519选择的基点是$X(P)=9$。

关于X25519更多的设计考量，请参阅深入理解X25519。