Ed25519 算法介紹

http://ed25519.cr.yp.to/Ed25519

它是一個數(shù)字簽名算法，簽名和驗證的性能都極高， 一個4核2.4GHz 的 Westmere cpu，每秒可以驗證 71000 個簽名，安全性極高，等價于RSA約3000-bit。簽名過程不依賴隨機數(shù)生成器，不依賴hash函數(shù)的防碰撞性，沒有時間通道攻擊的問題，并且簽名很小，只有64字節(jié)，公鑰也很小，只有32字節(jié)。 部署情況http://ianix.com/pub/ed25519-deployment.html

最近看到恒星（Stellar）網(wǎng)絡使用了Ed25519算法作為簽名算法，有點興趣，無奈資料太少，其算法網(wǎng)站也比較簡陋，結(jié)合找到的資料和網(wǎng)站介紹，粗略看了看，25519這個算法很有特點，相比傳統(tǒng)橢圓曲線算法有較大優(yōu)勢，今天簡單介紹給大家

Curve25519/Ed25519/X25519 是著名密碼學家 Daniel J. Bernstein 在 2006 年獨立設計的橢圓曲線加密 /簽名 /密鑰交換算法，和現(xiàn)有的任何橢圓曲線算法都完全獨立，其中Ed25519用于簽名，可在區(qū)塊鏈中進行簽名，Stellar就是使用了Ed25519作為簽名算法的

Daniel J. Bernstein 是世界著名的密碼學家，他在大學曾經(jīng)開設過一門 UNIX 系統(tǒng)安全的課程給學生，結(jié)果一學期下來，發(fā)現(xiàn)了 UNIX 程序中的 91 個安全漏洞；
他早年在美國依然禁止出口加密算法時，曾因為把自己設計的加密算法發(fā)布到網(wǎng)上遭到了美國政府的起訴，他本人抗爭六年，最后美國政府撤銷所有指控，目前另一個非?；鸬母咝阅馨踩髅艽a ChaCha20 也是出自 Bernstein 之手
25519 系列曲線自 2006 年發(fā)表以來，除了學術界無人問津， 2013 年愛德華·斯諾登曝光棱鏡計劃后，該算法突然大火。大量軟件，如 OpenSSH 都迅速增加了對 25519 系列的支持，如今 25519 已經(jīng)是大勢所趨，可疑的 NIST 曲線遲早要退出橢圓曲線的歷史舞臺，目前， RFC 增加了 SSL/TLS 對 X25519 密鑰交換協(xié)議的支持，而新版 OpenSSL 1.1 也加入支持，是擺脫老大哥的第一步，下一步是將 Ed25519 做為可選的 TLS 證書簽名算法，徹底擺脫 NIST 。

根據(jù)其網(wǎng)站介紹，Ed25519算法具有以下優(yōu)勢：

完全開放設計，算法各參數(shù)的選擇直截了當，非常明確，沒有任何可疑之處，相比之下，目前廣泛使用的橢圓曲線是 NIST 系列標準，方程的系數(shù)是使用來歷不明的隨機種子 c49d3608 86e70493 6a6678e1 139d26b7 819f7e90 生成的，至于這個種子的來歷沒有資料介紹；

安全性高，一個橢圓曲線加密算法就算在數(shù)學上是安全的，在實用上也并不一定安全，有很大的概率通過緩存、時間、惡意輸入摧毀安全性，而 25519 系列橢圓曲線經(jīng)過特別設計，盡可能的將出錯的概率降到了最低，可以說是實踐上最安全的加密算法。例如，任何一個 32 位隨機數(shù)都是一個合法的 X25519 公鑰，因此通過惡意數(shù)值攻擊是不可能的，算法在設計的時候刻意避免的某些分支操作，這樣在編程的時候可以不使用 if ，減少了不同 if 分支代碼執(zhí)行時間不同的時序攻擊概率，相反， NIST 系列橢圓曲線算法在實際應用中出錯的可能性非常大，而且對于某些理論攻擊的免疫能力不高。Bernstein 對市面上所有的加密算法使用 12 個標準進行了考察， 25519 是幾乎唯一滿足這些標準的。

以下是評價的截圖，具體可以看網(wǎng)站：https://safecurves.cr.yp.to/index.html

速度快， 25519 系列曲線是目前最快的橢圓曲線加密算法，性能遠遠超過 NIST 系列，而且具有比 P-256 更高的安全性；
以下是其網(wǎng)站的介紹，都是比較簡單的英語描述，最近事情太多，實在來不及翻譯了，偷下懶

Fast single-signature verification.The softwaretakes only 273364 cycles to verify a signature on Intel's widely deployed Nehalem/Westmere lines of CPUs. (This performance measurement is for short messages; for very long messages, verification time is dominated by hashing time.) Nehalem and Westmere include all Core i7, i5, and i3 CPUs released between 2008 and 2010, and most Xeon CPUs released in the same period.

Even faster batch verification.The software performs a batch of 64 separate signature verifications (verifying 64 signatures of 64 messages under 64 public keys) in only 8.55 million cycles, i.e., under 134000 cycles per signature. The software fits easily into L1 cache, so contention between cores is negligible: a quad-core 2.4GHz Westmere verifies 71000 signatures per second, while keeping the maximum verification latency below 4 milliseconds.

Very fast signing.The software takes only 87548 cycles to sign a message. A quad-core 2.4GHz Westmere signs 109000 messages per second.

Fast key generation.Key generation is almost as fast as signing. There is a slight penalty for key generation to obtain a secure random number from the operating system;/dev/urandomunder Linux costs about 6000 cycles.

High security level.This system has a 2^128 security target; breaking it has similar difficulty to breaking NIST P-256, RSA with ~3000-bit keys, strong 128-bit block ciphers, etc. The best attacks known actually cost more than 2^140 bit operations on average, and degrade quadratically in success probability as the number of bit operations drops.

Foolproof session keys.Signatures are generated deterministically; key generation consumes new randomness but new signatures do not. This is not only a speed feature but also a security feature, directly relevant to the recent collapse of the Sony PlayStation 3 security system.

Collision resilience.Hash-function collisions do not break this system. This adds a layer of defense against the possibility of weakness in the selected hash function.

No secret array indices.The software never reads or writes data from secret addresses in RAM; the pattern of addresses is completely predictable. The software is therefore immune to cache-timing attacks, hyperthreading attacks, and other side-channel attacks that rely on leakage of addresses through the CPU cache.

No secret branch conditions.The software never performs conditional branches based on secret data; the pattern of jumps is completely predictable. The software is therefore immune to side-channel attacks that rely on leakage of information through the branch-prediction unit.

Small signatures.Signatures fit into 64 bytes. These signatures are actually compressed versions of longer signatures; the times for compression and decompression are included in the cycle counts reported above.

Small keys.Public keys consume only 32 bytes. The times for compression and decompression are again included.

###################################################

1 基礎參數(shù)

Ed25519采用的曲線方程為 y 2 = x 3 + 486662 x 2 + x y^2 = x^3 + 486662x^2 + x y2=x3+486662x2+x ， m o d u l o   p = 2 255 ? 19 modulo \ p = 2^{255} - 19 modulo p=2255?19 。

私鑰長度：32字節(jié)。

公鑰長度：32字節(jié)，無其它長度。

簽名長度：64字節(jié)。

2 簽名算法2.1 生成密鑰對

私鑰：使用隨機數(shù)發(fā)生器生成隨機數(shù) k k k 作為私鑰。

公鑰生成過程：

1. 計算私鑰哈希值： H ( k ) = ( h 0 , h 1 , . . . , h 2 b ? 1 ) \displaystyle \large H(k)=(h_{0},h_{1},...,h_{2b-1}) H(k)=(h0,h1,...,h2b?1)

2. 生成整數(shù)： a = 2 b ? 2 + ∑ 3 ? i ? b ? 3 2 i h i ∈ { 2 b ? 2 , 2 b ? 2 + 8 , . . . , 2 b ? 1 ? 8 } \displaystyle \large a=2^{b-2}+\sum_{3\leqslant i\leqslant b-3}2^ih_{i}\in \{2^{b-2},2^{b-2}+8,...,2^{b-1}-8\} a=2b?2+3?i?b?3∑2ihi∈{2b?2,2b?2+8,...,2b?1?8}

3. 生成公鑰： A = a B \displaystyle \large A=aB A=aB

在Ed25519中， b b b固定取256。

A A A 就是公鑰。

2.2 生成簽名

1. r = H ( h b , . . . , h 2 b ? 1 , M ) \displaystyle r=H(h_b,...,h_{2b-1},M) r=H(hb,...,h2b?1,M)

2. R = r B \displaystyle R=rB R=rB

3. S = ( r + H ( R , A , M ) a ) m o d   l \displaystyle S=(r+H(R,A,M)a)mod \ l S=(r+H(R,A,M)a)mod l

則簽名就是 ( R , S ) (R,S) (R,S)。

2.3 簽名驗證

只需要檢驗 8 S B = 8 R + 8 H ( R , A , M ) A \displaystyle 8SB=8R+8H(R,A,M)A 8SB=8R+8H(R,A,M)A 是否成立。

2.4 簽名驗證原理分析

簽名驗證原理如下公式：

8 S B = 8 ( r + H ( R , A , M ) a ) B = 8 r B + 8 H ( R , A , M ) a B = 8 R + 8 H ( R , A , M ) A \displaystyle

8SB=8(r+H(R,A,M)a)B=8rB+8H(R,A,M)aB=8R+8H(R,A,M)A

3 參考資料

• High-speed high-security signatures：描述ed25519簽名過程的說明文檔。

• EdDSA：描述EdDSA算法的維基百科主頁。

Ed25519 算法介紹 - 桑中子衿 - 博客園 (cnblogs.com)