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日
- 结构：椭圆曲线密码学