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

  • 奇素数幂 上的有限域 
  •  上的椭圆曲线 ,其 关系点 的阶数为 ,其中 是一个大素数且 被称为辅因子
  • 阶数为 的基点 
  •  位输出的密码学散列函数 ,其中 ,使得 的元素和 中的曲线点可以被以 位的字符串表示。

这些参数对于使用同一EdDSA签名方案的所有用户都是通用的。EdDSA签名方案的安全性关键取决于参数的选择,除了基点的任意选择之外,例如,Pollard Rho算法预计需要大约 次曲线相加才能计算离散对数,[5] 所以 必须足够大才能使其不可行,并且通常取值超过2200[6]  的选择受限于 的选择,因为根据哈斯定理,  不能与 相差超过 。散列函数 在EdDSA安全性的正式分析中通常被建模为随机预言

在 EdDSA 签名方案中,

公钥
EdDSA公钥是一个曲线点 ,编码为 位。
签名验证
公钥 对消息 的EdDSA签名是元组 ,编码为 位,由满足下面的验证方程的曲线点 和整数 组成。 表示串接

 

私钥
EdDSA私钥是一个 位字符串 ,其应该被均匀地随机选择。对应的公钥为 ,其中 为通过将 的最低有效 位解释为小端字节序的整数得到。
签名
消息 的签名被确定地计算为 ,其中  ,且 这满足验证方程:

 

Ed25519

Ed25519是使用SHA-512(SHA-2)和Curve25519的EdDSA签名方式[2],其中:

 

  •  ,且 
  •   中独特的一点,其 坐标为 ,且 坐标为正数
    “正数”根据位编码定义:
    • “正”坐标是偶数坐标(最低有效位被清除)
    • “负数”坐标是奇数坐标(最低有效位被设置)
  •  SHA-512,其 

曲线 与被称为Curve25519蒙哥马利曲线双有理等价。等价的是:[2][7]  

性能

原作团队将Ed25519针对x86-64 NehalemWestmere处理器家族进行了优化x86-64。可以批量执行64个签名的验证,以获得更大的吞吐量。Ed25519 旨在提供与128位对称密码质量相当的抗攻击能力。[8]

公钥的长度为256位,签名的长度为512位。[9]

安全编码

Ed25519旨在避免使用依赖于秘密数据的分支条件或数组索引的实现,[2]:2[1]:40以缓解侧信道攻击

与其他基于离散对数的签名方案一样,EdDSA 为每个签名使用一个唯一的、被称为“nonce”的秘密值。在DSAECDSA签名方案中,传统上,这个随机数是为每个签名随机生成的,如果随机数生成器在签名时被破坏并且是可预测的,则签名可能会泄漏私钥,就像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]

Ed448

Ed448是使用SHAKE256Curve448的EdDSA签名方式,定义于RFC 8032。其也已被FIPE 186-5标准的最终版本批准。[14]

参考文献

  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. . 
  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 [2024-05-05]. S2CID 945254. doi:10.1007/s13389-012-0027-1 . (原始内容存档 (PDF)于2024-05-02). 
  3. ^ Software. 2015-06-11 [2016-10-07]. (原始内容存档于2024-04-29). The Ed25519 software is in the public domain. 
  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]. (原始内容存档于2023-11-27). 
  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 [2024-05-05]. ISBN 978-3-540-76899-9. MR 2565722. doi:10.1007/978-3-540-76900-2_3 . (原始内容存档于2018-12-15). 
  8. ^ Bernstein, Daniel J. Ed25519: high-speed high-security signatures. 2017-01-22 [2019-09-27]. (原始内容存档于2016-11-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]. (原始内容存档于2016-11-27). 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]. (原始内容存档于2024-01-04). 
  11. ^ fail0verflow. 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]. (原始内容存档 (PDF)于2024-01-19). 
  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). 
  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. (原始内容存档于2023-05-03). 
  15. ^ Konstantinos Chalkias, Francois Garillot and Valeria Nikolaenko. Taming the many EdDSAs. Security Standardisation Research Conference (SSR 2020). 2020-10-01 [2021-02-15]. (原始内容存档于2023-11-27). 
  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]. (原始内容存档于2023-12-15). 
  17. ^ ed25519-speccheck. GitHub. [2021-02-15]. (原始内容存档于2024-03-24). 
  18. ^ Changes since OpenSSH 6.4. 2014-01-03 [2016-10-07]. (原始内容存档于2024-05-02). 
  19. ^ What's new in GnuPG 2.1. 2016-07-14 [2016-10-07]. (原始内容存档于2024-05-12). 
  20. ^ Things that use Ed25519. 2016-10-06 [2016-10-07]. (原始内容存档于2017-01-22). 
  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. . 
  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]. (原始内容存档于2024-05-08). 
  26. ^ GitHub上的minisign-misc页面
  27. ^ Frank Denis. libsodium/ChangeLog. GitHub. 2016-06-29 [2016-10-07]. (原始内容存档于2022-10-22). 
  28. ^ OpenSSL CHANGES. July 31, 2019 [August 5, 2019]. (原始内容存档于May 18, 2018). 
  29. ^ python/ed25519.py: the main subroutines. 2011-07-06 [2016-10-07]. (原始内容存档于2024-03-09). 
  30. ^ Software: Alternate implementations. 2015-06-11 [2016-10-07]. (原始内容存档于2024-04-29). 
  31. ^ eBACS: ECRYPT Benchmarking of Cryptographic Systems: SUPERCOP. 2016-09-10 [2016-10-07]. (原始内容存档于2024-03-28). 
  32. ^ Virgil Security Crypto Library for C: Library: Foundation. GitHub. [2019-08-04]. (原始内容存档于2022-10-22). 
  33. ^ wolfSSL Embedded SSL Library (formerly CyaSSL). [2016-10-07]. (原始内容存档于2017-09-08). 

外部链接