Ed25519 算法介紹

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

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

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

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

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

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

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

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

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

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

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 基礎(chǔ)參數(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 。

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

公鑰長(zhǎng)度：32字節(jié)，無(wú)其它長(zhǎng)度。

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

2 簽名算法2.1 生成密鑰對(duì)

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

公鑰生成過(guò)程：

1. 計(jì)算私鑰哈希值： 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 簽名驗(yàn)證

只需要檢驗(yàn) 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 簽名驗(yàn)證原理分析

簽名驗(yàn)證原理如下公式：

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簽名過(guò)程的說(shuō)明文檔。

• EdDSA：描述EdDSA算法的維基百科主頁(yè)。

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