EdDSA
概述 | |
---|---|
設計者 | Daniel J. Bernstein、Niels Duif、Tanja Lange、Peter Schwabe、Bo-Yin Yang等 |
首次發佈 | 2011年9月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
這些參數對於使用同一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 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. .
- ^ 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).
- ^ Software. 2015-06-11 [2016-10-07]. (原始內容存檔於2024-04-29).
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]. (原始內容存檔於2023-11-27).
- ^ 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).
- ^ 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.
- ^ 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.
- ^ Johnston, Casey. PS3 hacked through poor cryptography implementation. Ars Technica. 2010-12-30 [2016-11-15]. (原始內容存檔於2024-01-04).
- ^ 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]. (原始內容存檔 (PDF)於2024-01-19).
- ^ 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. (原始內容存檔於2023-05-03).
- ^ 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).
- ^ 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).
- ^ ed25519-speccheck. GitHub. [2021-02-15]. (原始內容存檔於2024-03-24).
- ^ Changes since OpenSSH 6.4. 2014-01-03 [2016-10-07]. (原始內容存檔於2024-05-02).
- ^ What's new in GnuPG 2.1. 2016-07-14 [2016-10-07]. (原始內容存檔於2024-05-12).
- ^ Things that use Ed25519. 2016-10-06 [2016-10-07]. (原始內容存檔於2017-01-22).
- ^ Harris, B.; Velvindron, L.. Ed25519 and Ed448 Public Key Algorithms for the Secure Shell (SSH) Protocol. IETF. February 2020 [2022-07-11]. RFC 8709. .
- ^ 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]. (原始內容存檔於2024-05-08).
- ^ GitHub上的minisign-misc頁面
- ^ Frank Denis. libsodium/ChangeLog. GitHub. 2016-06-29 [2016-10-07]. (原始內容存檔於2022-10-22).
- ^ OpenSSL CHANGES. July 31, 2019 [August 5, 2019]. (原始內容存檔於May 18, 2018).
- ^ python/ed25519.py: the main subroutines. 2011-07-06 [2016-10-07]. (原始內容存檔於2024-03-09).
- ^ Software: Alternate implementations. 2015-06-11 [2016-10-07]. (原始內容存檔於2024-04-29).
- ^ eBACS: ECRYPT Benchmarking of Cryptographic Systems: SUPERCOP. 2016-09-10 [2016-10-07]. (原始內容存檔於2024-03-28).
- ^ Virgil Security Crypto Library for C: Library: Foundation. GitHub. [2019-08-04]. (原始內容存檔於2022-10-22).
- ^ wolfSSL Embedded SSL Library (formerly CyaSSL). [2016-10-07]. (原始內容存檔於2017-09-08).
外部連結
[編輯]
|