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，公鑰計算方法如下：

1. 計算SHA2-512(sk)，得到64字節的摘要值，取前32字節記爲k'；
2. 修改k'的值如下：k'[0] &= 248，k'[31] &= 127，k'[31] |= 64，然後把k'當作小端序的數字$s$；
3. 計算點$\text{P}=s\text{B}$，記$\text{P}$的橫縱座標分別爲$x_p$和$y_p$；
4. 把$y_p$的最高比特換成$x_p$的最低比特，然後用小端序保存$y_p$，即爲最終的公鑰。

Ed25519的簽名

簽名的流程如下：

1. 仍然用sk表示私鑰，計算SHA2-512(sk)，得到64字節的摘要值，按照生成公鑰的方法得到數$s$，記摘要剩餘的32字節爲prefix；
2. 記待簽名的數據爲M，計算SHA2-512(prefix || M)，其中||表示拼接操作，然後把摘要值當作一個小端序的數$r$；
3. 計算點$\text{P}=r\text{B}$，用公鑰同樣的編碼方法表示這個點，記爲R；
4. 計算SHA2-512(R || pk || M)，其中pk表示編碼後的公鑰，然後把摘要值當作一個小端序的數$k$；
5. 計算$S = (r + k \cdot s)~\text{mod}~L$，並用小端序保存；
6. 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
• 計算：
  • 公鑰
  • 簽名

首先來看公鑰：

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. 由於$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。

然後是簽名：

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, 於是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)，編碼爲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；
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，於是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. 最終的簽名是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。