EdDSA

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

EdDSA

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

概要

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

一種EdDSA 簽名方案是一種下列內容的組合：^{[4]:1–2[2]:5–6[1]:5–7}

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

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

在 EdDSA 簽名方案中，

公鑰

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

簽名驗證

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

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

私鑰

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

簽名

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

$${\displaystyle {\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簽名方式^[2]，其中：

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

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

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

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

性能

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

公鑰的長度為256位，簽名的長度為512位。^[9]

安全編碼

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

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

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

標準化與實施不一致

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

軟體

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

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

Ed448

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