EdDSA

在公鑰密碼學，愛德華茲曲線數字簽名算法（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$必須足夠大才能使其不可行，並且通常取值超過2200。

$\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 S B = 2^c R + 2^c H(R \parallel A \parallel M) A$$

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

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

$$\begin{align} 2^c S B &= 2^c (r + H(R \parallel A \parallel M) s) B \\ <pre> &= 2^c r B + 2^c H(R \parallel A \parallel M) s B \\ &= 2^c R + 2^c H(R \parallel A \parallel M) A. </pre> \end{align}$$

## 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^2y^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，即資訊性，另一項來自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簽名方式，定義於。其也已被FIPS 186-5標準的最終版本批准。

## 基本資料

- 設計者：Daniel J. Bernstein、Niels Duif、Tanja Lange、Peter Schwabe、Bo-Yin Yang等
- publish date：2011年9月26日
- 結構：橢圓曲線密碼學