EdDSA

在公钥密码学，爱德华兹曲线数字签名算法（EdDSA）是一种数字签名方式，使用一种基于扭曲的爱德华兹曲线的施诺尔签名变种。^[1] 其被设计为比现有的数字签名方式更快同时不牺牲安全性。Daniel J. Bernstein、Niels Duif、Tanja Lange、Peter Schwabe 和 Bo-Yin Yang等人的团队研发了这一算法^[2]，并将其参考实现发布为了公有领域软件。^[3]

概要

以下是 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。其也已被FIPE 186-5标准的最终版本批准。^[14]

参考文献

外部链接

• Ed25519主页