EdDSA

維基百科，自由的百科全書
跳至導覽 跳至搜尋
EdDSA
概述
設計者Daniel J. Bernstein、Niels Duif、Tanja Lange、Peter Schwabe、Bo-Yin Yang等
首次發布2011年9月26日​（14年前）​（2011-09-26）
細節
結構橢圓曲線密碼學

在公鑰密碼學，愛德華茲曲線數位簽章算法（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 

  • 奇素數冪<math>q</math>上的有限域<math>\mathbb{F}_q</math>
  • <math>\mathbb{F}_q</math>上的橢圓曲線<math>E</math>，其<math>\mathbb{F}_q</math>關係點群<math>E(\mathbb{F}_q)</math>的階數為<math>\#E(\mathbb{F}_q) = 2^c \ell</math>，其中<math>\ell</math>是一個大素數且<math>2^c</math>被稱為輔因子
  • 階數為<math>\ell</math>的基點<math>B \in E(\mathbb{F}_q)</math>
  • 有<math>2b</math>位輸出的密碼學散列函數<math>H</math>，其中<math>2^{b - 1} > q</math>，使得<math>\mathbb{F}_q</math>的元素和<math>E(\mathbb{F}_q)</math>中的曲線點可以被以<math>b</math>位的字符串表示。

這些參數對於使用同一EdDSA簽名方案的所有用戶都是通用的。EdDSA簽名方案的安全性關鍵取決於參數的選擇，除了基點的任意選擇之外，例如，Pollard Rho算法預計需要大約<math>\sqrt{\ell\pi/4}</math>次曲線相加才能計算離散對數，[5] 所以<math>\ell</math>必須足夠大才能使其不可行，並且通常取值超過2200。[6] <math>\ell</math>的選擇受限於<math>q</math>的選擇，因為根據哈斯定理, <math>\#E(\mathbb{F}_q) = 2^c \ell</math>不能與<math>q + 1</math>相差超過<math>2\sqrt{q}</math>。散列函數<math>H</math>在EdDSA安全性的正式分析中通常被建模為隨機預言。

在 EdDSA 簽名方案中，

公鑰
EdDSA公鑰是一個曲線點<math>A \in E(\mathbb{F}_q)</math>，編碼為<math>b</math>位。
簽名驗證
公鑰<math>A</math>對消息<math>M</math>的EdDSA簽名是元組<math>(R, S)</math>，編碼為<math>2b</math>位，由滿足下面的驗證方程的曲線點<math>R \in E(\mathbb{F}_q)</math>和整數<math>0 < S < \ell</math>組成。<math>\parallel</math>表示串接。

<math display="block">2^c S B = 2^c R + 2^c H(R \parallel A \parallel M) A</math>

私鑰
EdDSA私鑰是一個<math>b</math>位字符串<math>k</math>，其應該被均勻地隨機選擇。對應的公鑰為<math>A = s B</math>，其中<math>s = H_{0,\dots,b - 1}(k)</math>為通過將<math>H(k)</math>的最低有效<math>b</math>位解釋為小端字節序的整數得到。
簽名
消息<math>M</math>的簽名被確定地計算為<math>(R, S)</math>，其中<math>R = r B</math>，<math>r = H(H_{b,\dots,2b - 1}(k) \parallel M)</math>，且<math display="block">S \equiv r + H(R \parallel A \parallel M) s \pmod \ell</math>這滿足驗證方程：

<math display="block"> \begin{align} 2^c S B &= 2^c (r + H(R \parallel A \parallel M) s) B \\ 

       &= 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.

\end{align} </math>

Ed25519[編輯]

Ed25519是使用SHA-512（SHA-2）和Curve25519的EdDSA簽名方式[2]，其中：

<math display="block">-x^2 + y^2 = 1 - \frac{121665}{121666}x^2y^2,</math>

  • <math>\ell = 2^{252} + 27742317777372353535851937790883648493</math>，且<math>c = 3</math>
  • <math>B</math>為<math>E(\mathbb{F}_q)</math>中獨特的一點，其<math>y</math>坐標為<math>4/5</math>，且<math>x</math>坐標為正數
    「正數」根據位編碼定義：
    • 「正」坐標是偶數坐標（最低有效位被清除）
    • 「負數」坐標是奇數坐標（最低有效位被設置）
  • <math>H</math>為SHA-512，其<math>b = 256</math>。

曲線<math>E(\mathbb{F}_q)</math>與被稱為Curve25519的蒙哥馬利曲線雙有理等價。等價的是：[2][7] <math display="block"> x = \frac{u}{v}\sqrt{-486664}, \quad y = \frac{u - 1}{u + 1} </math>

性能[編輯]

原作團隊將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]

Ed448[編輯]

Ed448是使用SHAKE256和Curve448的EdDSA簽名方式，定義於RFC 8032。其也已被FIPS 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.
    ISSN 2070-1721
    .     
  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.
    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]. （原始內容存檔於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）. 

外部連結[編輯]

取自「https://arolstar52-zhtest.hf.space/index.php?title=EdDSA&oldid=4433456」