EdDSA

EdDSA

概述
設計者	Daniel J. Bernstein、Niels Duif、Tanja Lange、Peter Schwabe、Bo-Yin Yang等
首次發布	2011年9月26日​（2011-09-26）
細節
結構	橢圓曲線密碼學

在公鑰密碼學，愛德華茲曲線數字簽名算法（EdDSA）是一種數字簽名方式，使用一種基於扭曲的愛德華茲曲線的施諾爾簽名變種。 其被設計為比現有的數字簽名方式更快同時不犧牲安全性。Daniel J. Bernstein、Niels Duif、Tanja Lange、Peter Schwabe 和 Bo-Yin Yang等人的團隊研發了這一算法，並將其參考實現發布為了公有領域軟體。

概要

以下是 EdDSA 的簡化描述，忽略將整數和曲線點編碼為位串的細節。關於完整的細節，請參見論文和RFC。

一種EdDSA 簽名方案是一種下列內容的組合：

• 奇素數冪$q$上的有限域$\mathbb {F} _{q}$
• $\mathbb {F} _{q}$上的橢圓曲線$E$，其$\mathbb {F} _{q}$關係點群$E(\mathbb {F} _{q})$的階數為$\#E(\mathbb {F} _{q})=2^{c}\ell$，其中$\ell$是一個大素數且$2^{c}$被稱為輔因子
• 階數為$\ell$的基點$B\in E(\mathbb {F} _{q})$
• 有$2b$位輸出的密碼學散列函數$H$，其中$2^{b-1}>q$，使得$\mathbb {F} _{q}$的元素和$E(\mathbb {F} _{q})$中的曲線點可以被以$b$位的字符串表示。

這些參數對於使用同一EdDSA簽名方案的所有用戶都是通用的。EdDSA簽名方案的安全性關鍵取決於參數的選擇，除了基點的任意選擇之外，例如，Pollard Rho算法預計需要大約${\sqrt {\ell \pi /4}}$次曲線相加才能計算離散對數， 所以$\ell$必須足夠大才能使其不可行，並且通常取值超過2²⁰⁰。 $\ell$的選擇受限於$q$的選擇，因為根據哈斯定理, $\#E(\mathbb {F} _{q})=2^{c}\ell$不能與$q+1$相差超過$2{\sqrt {q}}$。散列函數$H$在EdDSA安全性的正式分析中通常被建模為隨機預言。

在 EdDSA 簽名方案中，

公鑰

EdDSA公鑰是一個曲線點$A\in E(\mathbb {F} _{q})$，編碼為$b$位。

簽名驗證

公鑰$A$對消息$M$的EdDSA簽名是元組$(R,S)$，編碼為$2b$位，由滿足下面的驗證方程的曲線點$R\in E(\mathbb {F} _{q})$和整數$0<S<\ell$組成。$\parallel$表示串接。

$$2^{c}SB=2^{c}R+2^{c}H(R\parallel A\parallel M)A$$

私鑰

EdDSA私鑰是一個$b$位字符串$k$，其應該被均勻地隨機選擇。對應的公鑰為$A=sB$，其中$s=H_{0,\dots ,b-1}(k)$為通過將$H(k)$的最低有效$b$位解釋為小端字節序的整數得到。

簽名

消息$M$的簽名被確定地計算為$(R,S)$，其中$R=rB$，$r=H(H_{b,\dots ,2b-1}(k)\parallel M)$，且$$S\equiv r+H(R\parallel A\parallel M)s{\pmod {\ell }}$$這滿足驗證方程：

$${\begin{aligned}2^{c}SB&=2^{c}(r+H(R\parallel A\parallel M)s)B\\&=2^{c}rB+2^{c}H(R\parallel A\parallel M)sB\\&=2^{c}R+2^{c}H(R\parallel A\parallel M)A.\end{aligned}}$$

Ed25519

Ed25519是使用SHA-512（SHA-2）和Curve25519的EdDSA簽名方式，其中：

• $q=2^{255}-19,$
• $E/\mathbb {F} _{q}$是扭曲的愛德華茲曲線

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

• $\ell =2^{252}+27742317777372353535851937790883648493$，且$c=3$
• $B$為$E(\mathbb {F} _{q})$中獨特的一點，其$y$坐標為$4/5$，且$x$坐標為正數
  「正數」根據位編碼定義：
  • 「正」坐標是偶數坐標（最低有效位被清除）
  • 「負數」坐標是奇數坐標（最低有效位被設置）
• $H$為SHA-512，其$b=256$。

曲線$E(\mathbb {F} _{q})$與被稱為Curve25519的蒙哥馬利曲線雙有理等價。等價的是： $$x={\frac {u}{v}}{\sqrt {-486664}},\quad y={\frac {u-1}{u+1}}$$

性能

原作團隊將Ed25519針對x86-64 Nehalem、Westmere處理器家族進行了優化x86-64。可以批量執行64個簽名的驗證，以獲得更大的吞吐量。Ed25519 旨在提供與128位對稱密碼質量相當的抗攻擊能力。

公鑰的長度為256位，簽名的長度為512位。

安全編碼

Ed25519旨在避免使用依賴於秘密數據的分支條件或數組索引的實現，以緩解側信道攻擊。

與其他基於離散對數的簽名方案一樣，EdDSA 為每個簽名使用一個唯一的、被稱為「nonce」的秘密值。在DSA和ECDSA簽名方案中，傳統上，這個隨機數是為每個簽名隨機生成的，如果隨機數生成器在簽名時被破壞並且是可預測的，則簽名可能會洩漏私鑰，就像Sony PlayStation 3固件更新簽名密鑰所發生的那樣。

相比之下，EdDSA 確定性地選擇 nonce 作為私鑰和消息的哈希值的一部分。因此，一旦生成私鑰，EdDSA 就不再需要隨機數生成器來進行簽名，並且不存在用於生成簽名的受損隨機數生成器洩露私鑰的風險。

標準化與實施不一致

值得注意的是，EdDSA 有兩項標準化工作，一項來自IETF，即信息性RFC 8032，另一項來自NIST，作為FIPS 186-5的一部分。兩個標準之間的差異已經被分析了，並且有測試向量。

軟體

Ed25519 的顯著用途包括OpenSSH、GnuPG及各種替代方案和OpenBSD的signify工具。SSH協議中的Ed25519和Ed448使用已經得到標準化。在2023年，FIPS 186-5 標準的最終版確定將Ed25519包含為一種批准的簽名方案。

• Apple Watch和iPhone使用Ed25519密鑰進行IKEv2相互認證
• Botan
• Crypto++
• CryptoNote 加密貨幣協議
• Dropbear SSH
• I2Pd的EdDSA實現
• Java Development Kit 15
• Libgcrypt
• Minisign和macOS的Minisign Miscellanea
• NaCl / libsodium
• OpenSSL 1.1.1
• Python的一個緩慢但簡潔的替代實現，不包含側信道攻擊保護
• Supercop參考實現（帶有內聯彙編的C語言）
• Virgil PKI默認使用Ed25519密鑰
• wolfSSL

Ed448

Ed448是使用SHAKE256和Curve448的EdDSA簽名方式，定義於RFC 8032。其也已被FIPE 186-5標準的最終版本批准。

外部連結

• Ed25519主頁 （頁面存檔備份，存於網際網路檔案館）