EdDSA

**EdDSA**
概述
设计者	Daniel J. Bernstein、Niels Duif、Tanja Lange、Peter Schwabe、Bo-Yin Yang等
首次发布	2011年9月26日（12年前）
细节
结构	椭圆曲线密码学

在公钥密码学，爱德华兹曲线数字签名算法（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

奇素数幂 $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}}$ 次曲线相加才能计算离散对数，^[5] 所以 $\ell$ 必须足够大才能使其不可行，并且通常取值超过 $2200$ 。^[6] $\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签名方式^[2]，其中：

$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$ $B$ 为 $E(\mathbb {F} _{q})$ $E(\mathbb {F} _{q})$ 中独特的一点，其 $y$ $y$ 坐标为 $4/5$ $4/5$ ，且 $x$ $x$ 坐标为正数
“正数”根据位编码定义：
- “正”坐标是偶数坐标（最低有效位被清除）
- “负数”坐标是奇数坐标（最低有效位被设置）
$H$ 为SHA-512，其 $b=256$ 。

曲线 $E(\mathbb {F} _{q})$ 与被称为Curve25519的蒙哥马利曲线双有理等价。等价的是：^[2]^[7]

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]

参考文献[编辑]

^ ^1.0 ^1.1 ^1.2 ^1.3 Josefsson, S.; Liusvaara, I.. Edwards-Curve Digital Signature Algorithm (EdDSA). IRTF. January 2017 [2022-07-11]. RFC 8032.
ISSN 2070-1721
.
^ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 Bernstein, Daniel J.; Duif, Niels; Lange, Tanja; Schwabe, Peter; Bo-Yin Yang. High-speed high-security signatures (PDF). Journal of Cryptographic Engineering. 2012, 2 (2): 77–89. S2CID 945254. doi:10.1007/s13389-012-0027-1 .
^ Software. 2015-06-11 [2016-10-07]. The Ed25519 software is in the public domain.
^ ^4.0 ^4.1 Daniel J. Bernstein; Simon Josefsson; Tanja Lange; Peter Schwabe; Bo-Yin Yang. EdDSA for more curves (PDF) (技术报告). 2015-07-04 [2016-11-14].
^ Daniel J. Bernstein; Tanja Lange; Peter Schwabe. On the correct use of the negation map in the Pollard rho method (技术报告). IACR Cryptology ePrint Archive. 2011-01-01 [2016-11-14]. 2011/003.
^ Bernstein, Daniel J.; Lange, Tanja. ECDLP Security: Rho. SafeCurves: choosing safe curves for elliptic-curve cryptography. [2016-11-16].
^ Bernstein, Daniel J.; Lange, Tanja. Kurosawa, Kaoru , 编. Faster addition and doubling on elliptic curves. Advances in cryptology—ASIACRYPT. Lecture Notes in Computer Science 4833. Berlin: Springer: 29–50. 2007. ISBN 978-3-540-76899-9. MR 2565722. doi:10.1007/978-3-540-76900-2_3 .
^ Bernstein, Daniel J. Ed25519: high-speed high-security signatures. 2017-01-22 [2019-09-27]. This system has a 2^128 security target; breaking it has similar difficulty to breaking NIST P-256, RSA with ~3000-bit keys, strong 128-bit block ciphers, etc.
^ Bernstein, Daniel J. Ed25519: high-speed high-security signatures. 2017-01-22 [2020-06-01]. Signatures fit into 64 bytes. […] Public keys consume only 32 bytes.
^ Johnston, Casey. PS3 hacked through poor cryptography implementation. Ars Technica. 2010-12-30 [2016-11-15].
^ fail0verflow. Console Hacking 2010: PS3 Epic Fail (PDF). 混沌通讯大会. 2010-12-29 [2016-11-15]. （原始内容 (PDF)存档于2018-10-26）.
^ 27th Chaos Communication Congress: Console Hacking 2010: PS3 Epic Fail (PDF). [2019-08-04].
^ Buchanan, Bill. Not Playing Randomly: The Sony PS3 and Bitcoin Crypto Hacks. Watch those random number generators. Medium. 2018-11-12 [2024-03-11]. （原始内容存档于2018-11-30）.
^ ^14.0 ^14.1 ^14.2 Moody, Dustin. FIPS 186-5: Digital Signature Standard (DSS). NIST. 2023-02-03 [2023-03-04]. S2CID 256480883. doi:10.6028/NIST.FIPS.186-5.
^ Konstantinos Chalkias, Francois Garillot and Valeria Nikolaenko. Taming the many EdDSAs. Security Standardisation Research Conference (SSR 2020). 2020-10-01 [2021-02-15].
^ Jacqueline Brendel, Cas Cremers, Dennis Jackson, and Mang Zhao. The provable security of ed25519: Theory and practice. IEEE Symposium on Security and Privacy (S&P 2021). 2020-07-03 [2021-02-15].
^ ed25519-speccheck. GitHub. [2021-02-15].
^ Changes since OpenSSH 6.4. 2014-01-03 [2016-10-07].
^ What's new in GnuPG 2.1. 2016-07-14 [2016-10-07].
^ Things that use Ed25519. 2016-10-06 [2016-10-07].
^ Harris, B.; Velvindron, L.. Ed25519 and Ed448 Public Key Algorithms for the Secure Shell (SSH) Protocol. IETF. February 2020 [2022-07-11]. RFC 8709.
ISSN 2070-1721
.
^ System security for watchOS. [2021-06-07].
^ Matt Johnston. DROPBEAR_2013.61test. 2013-11-14 [2019-08-05]. （原始内容存档于2019-08-05）.
^ Heuristic Algorithms and Distributed Computing (PDF). Èvrističeskie Algoritmy I Raspredelennye Vyčisleniâ. 2015: 55–56 [2016-10-07]. ISSN 2311-8563. （原始内容 (PDF)存档于2016-10-20）（俄语）.
^ Frank Denis. Minisign: A dead simple tool to sign files and verify signatures.. [2016-10-07].
^ GitHub上的minisign-misc頁面
^ Frank Denis. libsodium/ChangeLog. GitHub. 2016-06-29 [2016-10-07].
^ OpenSSL CHANGES. July 31, 2019 [August 5, 2019]. （原始内容存档于May 18, 2018）.
^ python/ed25519.py: the main subroutines. 2011-07-06 [2016-10-07].
^ Software: Alternate implementations. 2015-06-11 [2016-10-07].
^ eBACS: ECRYPT Benchmarking of Cryptographic Systems: SUPERCOP. 2016-09-10 [2016-10-07].
^ Virgil Security Crypto Library for C: Library: Foundation. GitHub. [2019-08-04].
^ wolfSSL Embedded SSL Library (formerly CyaSSL). [2016-10-07].

外部链接[编辑]

Ed25519主页

[RFC8032-1] 1.0 ^1.1 ^1.2 ^1.3 Josefsson, S.; Liusvaara, I.. Edwards-Curve Digital Signature Algorithm (EdDSA). IRTF. January 2017 [2022-07-11]. RFC 8032.
ISSN 2070-1721
.

[DJB-2] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 Bernstein, Daniel J.; Duif, Niels; Lange, Tanja; Schwabe, Peter; Bo-Yin Yang. High-speed high-security signatures (PDF). Journal of Cryptographic Engineering. 2012, 2 (2): 77–89. S2CID 945254. doi:10.1007/s13389-012-0027-1 .

[3] Software. 2015-06-11 [2016-10-07]. The Ed25519 software is in the public domain.

[bjlsy2015eddsamorecurves-4] 4.0 ^4.1 Daniel J. Bernstein; Simon Josefsson; Tanja Lange; Peter Schwabe; Bo-Yin Yang. EdDSA for more curves (PDF) (技术报告). 2015-07-04 [2016-11-14].

[5] Daniel J. Bernstein; Tanja Lange; Peter Schwabe. On the correct use of the negation map in the Pollard rho method (技术报告). IACR Cryptology ePrint Archive. 2011-01-01 [2016-11-14]. 2011/003.

[6] Bernstein, Daniel J.; Lange, Tanja. ECDLP Security: Rho. SafeCurves: choosing safe curves for elliptic-curve cryptography. [2016-11-16].

[7] Bernstein, Daniel J.; Lange, Tanja. Kurosawa, Kaoru , 编. Faster addition and doubling on elliptic curves. Advances in cryptology—ASIACRYPT. Lecture Notes in Computer Science 4833. Berlin: Springer: 29–50. 2007. ISBN 978-3-540-76899-9. MR 2565722. doi:10.1007/978-3-540-76900-2_3 .

[8] Bernstein, Daniel J. Ed25519: high-speed high-security signatures. 2017-01-22 [2019-09-27]. This system has a 2^128 security target; breaking it has similar difficulty to breaking NIST P-256, RSA with ~3000-bit keys, strong 128-bit block ciphers, etc.

[9] Bernstein, Daniel J. Ed25519: high-speed high-security signatures. 2017-01-22 [2020-06-01]. Signatures fit into 64 bytes. […] Public keys consume only 32 bytes.

[10] Johnston, Casey. PS3 hacked through poor cryptography implementation. Ars Technica. 2010-12-30 [2016-11-15].

[11] 0verflow. Console Hacking 2010: PS3 Epic Fail (PDF). 混沌通讯大会. 2010-12-29 [2016-11-15]. （原始内容 (PDF)存档于2018-10-26）.

[12] 27th Chaos Communication Congress: Console Hacking 2010: PS3 Epic Fail (PDF). [2019-08-04].

[13] Buchanan, Bill. Not Playing Randomly: The Sony PS3 and Bitcoin Crypto Hacks. Watch those random number generators. Medium. 2018-11-12 [2024-03-11]. （原始内容存档于2018-11-30）.

[FIPS_186-5-14] 14.0 ^14.1 ^14.2 Moody, Dustin. FIPS 186-5: Digital Signature Standard (DSS). NIST. 2023-02-03 [2023-03-04]. S2CID 256480883. doi:10.6028/NIST.FIPS.186-5.

[15] Konstantinos Chalkias, Francois Garillot and Valeria Nikolaenko. Taming the many EdDSAs. Security Standardisation Research Conference (SSR 2020). 2020-10-01 [2021-02-15].

[16] Jacqueline Brendel, Cas Cremers, Dennis Jackson, and Mang Zhao. The provable security of ed25519: Theory and practice. IEEE Symposium on Security and Privacy (S&P 2021). 2020-07-03 [2021-02-15].

[17] 25519-speccheck. GitHub. [2021-02-15].

[18] Changes since OpenSSH 6.4. 2014-01-03 [2016-10-07].

[19] What's new in GnuPG 2.1. 2016-07-14 [2016-10-07].

[20] Things that use Ed25519. 2016-10-06 [2016-10-07].

[21] Harris, B.; Velvindron, L.. Ed25519 and Ed448 Public Key Algorithms for the Secure Shell (SSH) Protocol. IETF. February 2020 [2022-07-11]. RFC 8709.
ISSN 2070-1721
.

[22] System security for watchOS. [2021-06-07].

[23] Matt Johnston. DROPBEAR_2013.61test. 2013-11-14 [2019-08-05]. （原始内容存档于2019-08-05）.

[24] Heuristic Algorithms and Distributed Computing (PDF). Èvrističeskie Algoritmy I Raspredelennye Vyčisleniâ. 2015: 55–56 [2016-10-07]. ISSN 2311-8563. （原始内容 (PDF)存档于2016-10-20）（俄语）.

[25] Frank Denis. Minisign: A dead simple tool to sign files and verify signatures.. [2016-10-07].

[26] GitHub上的minisign-misc頁面

[27] Frank Denis. libsodium/ChangeLog. GitHub. 2016-06-29 [2016-10-07].

[28] OpenSSL CHANGES. July 31, 2019 [August 5, 2019]. （原始内容存档于May 18, 2018）.

[29] ython/ed25519.py: the main subroutines. 2011-07-06 [2016-10-07].

[30] Software: Alternate implementations. 2015-06-11 [2016-10-07].

[31] BACS: ECRYPT Benchmarking of Cryptographic Systems: SUPERCOP. 2016-09-10 [2016-10-07].

[32] Virgil Security Crypto Library for C: Library: Foundation. GitHub. [2019-08-04].

[33] wolfSSL Embedded SSL Library (formerly CyaSSL). [2016-10-07].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]