EdDSA

EdDSA
EdDSA
일반
디자이너다니엘 번스타인, 닐스 뒤프, 타냐 랭, 피터 슈와비, 보-인 양 등
초판2011년 9월 26일
세부 사항
구조.타원곡선암호법

공개키 암호학에서 Edwards-curve Digital Signature Algorithm(EdDSA)비틀린 Edwards [1]곡선을 기반으로 한 Schnorr 서명을 사용하는 디지털 서명 방식입니다.보안을 희생하지 않고 기존 디지털 서명 방식보다 고속으로 설계되어 있습니다.그것은 Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwave, 그리고 Bo-Yin [2]Yang을 포함한 팀에 의해 개발되었다.참조 실장은 퍼블릭 도메인 소프트웨어입니다.[3]

요약

다음으로 EdDSA의 간단한 설명을 나타냅니다.정수와 곡선을 비트 문자열로 인코딩하는 자세한 내용은 무시합니다.자세한 내용은 문서 및 [4][2][1]RFC에 기재되어 있습니다.

EdDSA 시그니처 스킴은 다음과 같이 선택할 수 있습니다.

  • 필드 Fq 홀수 q {\q 위의 값.
  • q \ \displaystyle (\ {F _ _displaystyle \ 그룹(\displaystyle E_ #displaystyle \ell 이고 {\}}는 보조인자라고 .
  • base BE ( q B \ ( \{ F}_ {q } )의 입니다
  • 그래서 Fq의 E(Fq){E(\mathbb{F}_{q})\displaystyle}에 있는 요소(_{q}}과 곡선 포인트 끈으로 표시할 수 있암호화 해시 함수 중 H이 2b− 1>2b{2b\displaystyle}-bit 출력, q{2^{b-1\displaystyle}>, q}과{H\displaystyle}.의 b 비트.

이러한 파라미터는 EdDSA 시그니처 스킴의 모든 사용자에게 공통입니다.그 EdDSA 서명 계획의 보안 결정적으로 매개 변수의 선택에, 기지point—for의 모범이 되는 임의의 선택을 위해, 로그에 폴라드의로 알고리즘기 전에는 이산 logarithm,[5]을 계산할 수 있는 대략ℓ π/4{\displaystyle{\sqrt{\ell \pi /4}}}곡선 추가 사항이 걸릴 것으로 예상되는 것을 제외하고 달려 있다. \ell 이 작업이 불가능할 정도로 커야 하며 일반적으로 2를 [6]초과해야200 합니다. { }의 q { q}의 선택으로 제한됩니다. 왜냐하면 Hasse의 정리에# ( q ) {\ { \ # ( \{ F}_ { q } =^{ } \ ell \ q + 2 q + 1 \ q + 1} } } } } } } + 1 } {\ {\ H H 일반적으로 EdDSA 보안의 공식 분석에서 랜덤 오라클로 모델링됩니다.HashEdDSA 바리안트에서는 추가 내충돌 H { H 필요합니다.

EdDSA 시그니처 스킴 내에서

공개 키
EdDSA 공개키는 AE ( q \ \ E ( \ { F}_ {q )로 b\ b} 부호화되어 있습니다.
서명
∈ E(Fq){R\in E(\mathbb{F}_{q})\displaystyle}과 정수 0<>S<>메시지를 M공개 키 A{A\displaystyle}은 쌍(R, S){\displaystyle(R,S)}에 의해{M\displaystyle}에서 EdDSA 시그니처에 곡선 지점 R에서 2b{2b\displaystyle}, 비트에;ℓ{0<\displaystyle;를 인코딩했다.S<, \ell}sa다음과 같은 검증 방정식을 사용합니다.\displaystyle 연결을 나타냅니다

개인 키
EdDSA 개인 키는 b b 비트 k(\ k 랜덤으로 균일하게 선택해야 합니다.대응하는 공개 키는 { A =} 입니다.서 s , , - ( sH _ , \ , b - 1 ( )는 작은 정수로 해석된H()\ H ( ) 비트입니다. Mdisplaystyle M 시그니처는( { (S){displaystyle ( 입니다.서 R ( b , ..., b- 1 ( ) M)、 \ R ( \ )
이는 검증방정식을 충족합니다.

Ed25519

Ed25519SHA-512(SHA-2) 및 Curve25519[2] 사용하는EdDSA 시그니처 스킴입니다

  • q { E 트위스트 에드워즈 곡선입니다.

  • = 252 + \ 2} + c (\ 3 )
  • BY(\ y 좌표가 4 4이고 x 좌표가 E(\ {q}))의 고유 지점입니다.
    "positive"는 비트 전송의 관점에서 정의됩니다.
    • "양수" 좌표는 짝수 좌표입니다(최소 유의 비트가 지워짐).
    • "음" 좌표는 홀수 좌표입니다(최소 유효 비트가 설정됨).
  • H H SHA-512로 b b입니다.

E q E 곡선 25519로 알려진 Montgomery 곡선과 출생 등가입니다.동등성은[2][7]

성능

오리지널 팀은 x86-64 Nehalem/Westmere 프로세서 패밀리용으로 Ed25519를 최적화했습니다.64개의 시그니처 단위로 검증하면 throughput이 더욱 향상됩니다.Ed25519는 128비트 대칭 [8]암호와 동등한 내공격성을 제공하는 것을 목적으로 하고 있습니다.공개키는 256비트, 시그니처는 [9]512비트입니다.

안전한 코딩

보안 기능으로서 Ed25519는 많은 사이드 채널 공격을 막기 위해 비밀 데이터에 의존하는 브랜치 조작 및 어레이 인덱싱 단계를 사용하지 않습니다.

다른 이산 로그 기반의 시그니처 방식과 마찬가지로 EdDSA는 각 시그니처에 고유한 난스라는 비밀값을 사용합니다.시그니처 스킴 DSA 및 ECDSA에서는 전통적으로 이 난스가 시그니처별로 랜덤하게 생성되어 시그니처 작성 시 난수 발생기가 고장나 예측 가능한 경우 Sony PlayStation 3 펌웨어 업데이트 서명 [10][11][12]키와 마찬가지로 시그니처가 개인 키를 누출할 수 있습니다.반대로 EdDSA는 개인 키와 메시지의 일부 해시로서 난스를 결정적으로 선택합니다.따라서 개인 키가 생성되면 서명을 위해 EdDSA에서 난수 생성기가 더 이상 필요하지 않으며 서명에 사용되는 고장난 난수 생성기가 개인 키를 노출시킬 위험도 없습니다.

표준화 및 구현의 불일치

EdDSA에는 2개의 표준화 작업이 있습니다.하나는 IETF의 정보입니다. RFC8032 및 FIPS 186-5 (2019)[13]의 일부로서 NIST의 RFC8032.표준 간의 차이를 [14][15]분석하여 테스트 벡터를 사용할 [16]수 있습니다.

소프트웨어

Ed25519의 주목할 만한 용도에는 OpenSSH,[17] GnuPG[18] 및 다양한 대체 수단과 OpenBSD[19]시그니처 툴이 있습니다.SSH 프로토콜에서의 Ed25519(및 Ed448) 사용은 [20]표준화되었습니다.2019년 FIPS 186-5 표준의 초안 버전은 승인된 서명 [13]체계로 결정론적 Ed25519를 포함했다.

Ed448

Ed448은 RFC 8032에서 정의SHEC256Curve448을 사용하는EdDSA 시그니처 스킴입니다또한 FIPS 186-5 [13]표준의 초안에서도 승인되었습니다.

레퍼런스

  1. ^ a b Josefsson, S.; Liusvaara, I. (January 2017). Edwards-Curve Digital Signature Algorithm (EdDSA). IRTF. doi:10.17487/RFC8032. ISSN 2070-1721. RFC 8032. Retrieved 2022-07-11.
  2. ^ a b c d Bernstein, Daniel J.; Duif, Niels; Lange, Tanja; Schwabe, Peter; Bo-Yin Yang (2012). "High-speed high-security signatures" (PDF). Journal of Cryptographic Engineering. 2 (2): 77–89. doi:10.1007/s13389-012-0027-1. S2CID 945254.
  3. ^ "Software". 2015-06-11. Retrieved 2016-10-07. The Ed25519 software is in the public domain.
  4. ^ Daniel J. Bernstein; Simon Josefsson; Tanja Lange; Peter Schwabe; Bo-Yin Yang (2015-07-04). EdDSA for more curves (PDF) (Technical report). Retrieved 2016-11-14.
  5. ^ Daniel J. Bernstein; Tanja Lange; Peter Schwabe (2011-01-01). On the correct use of the negation map in the Pollard rho method (Technical report). IACR Cryptology ePrint Archive. 2011/003. Retrieved 2016-11-14.
  6. ^ Daniel J. Bernstein; Tanja Lange. "ECDLP Security: Rho". SafeCurves: choosing safe curves for elliptic-curve cryptography. Retrieved 2016-11-16.
  7. ^ Bernstein, Daniel J.; Lange, Tanja (2007). Kurosawa, Kaoru (ed.). Faster addition and doubling on elliptic curves. Advances in cryptology—ASIACRYPT. Lecture Notes in Computer Science. Vol. 4833. Berlin: Springer. pp. 29–50. doi:10.1007/978-3-540-76900-2_3. ISBN 978-3-540-76899-9. MR 2565722.
  8. ^ Daniel J. Bernstein (2017-01-22). "Ed25519: high-speed high-security signatures". Retrieved 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. ^ Daniel J. Bernstein (2017-01-22). "Ed25519: high-speed high-security signatures". Retrieved 2020-06-01. Signatures fit into 64 bytes. […] Public keys consume only 32 bytes.
  10. ^ Johnston, Casey (2010-12-30). "PS3 hacked through poor cryptography implementation". Ars Technica. Retrieved 2016-11-15.
  11. ^ fail0verflow (2010-12-29). Console Hacking 2010: PS3 Epic Fail (PDF). Chaos Communication Congress. Archived from the original (PDF) on 2018-10-26. Retrieved 2016-11-15.
  12. ^ "27th Chaos Communication Congress: Console Hacking 2010: PS3 Epic Fail" (PDF). Retrieved 2019-08-04.
  13. ^ a b c "FIPS 186-5 (Draft): Digital Signature Standard (DSS)". NIST. October 2019. doi:10.6028/NIST.FIPS.186-5-draft. Retrieved 2022-07-11.
  14. ^ Konstantinos Chalkias, Francois Garillot and Valeria Nikolaenko (2020-10-01). Taming the many EdDSAs. Security Standardisation Research Conference (SSR 2020). Retrieved 2021-02-15.
  15. ^ Jacqueline Brendel, Cas Cremers, Dennis Jackson, and Mang Zhao (2020-07-03). The provable security of ed25519: Theory and practice. IEEE Symposium on Security and Privacy (S&P 2021). Retrieved 2021-02-15.{{cite conference}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  16. ^ "ed25519-speccheck". Retrieved 2021-02-15.
  17. ^ "Changes since OpenSSH 6.4". 2014-01-03. Retrieved 2016-10-07.
  18. ^ "What's new in GnuPG 2.1". 2016-07-14. Retrieved 2016-10-07.
  19. ^ "Things that use Ed25519". 2016-10-06. Retrieved 2016-10-07.
  20. ^ Harris, B.; Velvindron, L. (February 2020). Ed25519 and Ed448 Public Key Algorithms for the Secure Shell (SSH) Protocol. IETF. doi:10.17487/RFC8709. ISSN 2070-1721. RFC 8709. Retrieved 2022-07-11.
  21. ^ "eBACS: ECRYPT Benchmarking of Cryptographic Systems: SUPERCOP". 2016-09-10. Retrieved 2016-10-07.
  22. ^ "python/ed25519.py: the main subroutines". 2011-07-06. Retrieved 2016-10-07.
  23. ^ "Software: Alternate implementations". 2015-06-11. Retrieved 2016-10-07.
  24. ^ Frank Denis (2016-06-29). "libsodium/ChangeLog". Retrieved 2016-10-07.
  25. ^ "wolfSSL Embedded SSL Library (formerly CyaSSL)". Retrieved 2016-10-07.
  26. ^ "Heuristic Algorithms and Distributed Computing" (PDF). Èvrističeskie Algoritmy I Raspredelennye Vyčisleniâ (in Russian): 55–56. 2015. ISSN 2311-8563. Archived from the original (PDF) on 2016-10-20. Retrieved 2016-10-07.
  27. ^ Frank Denis. "Minisign: A dead simple tool to sign files and verify signatures". Retrieved 2016-10-07.
  28. ^ GitHubminisign-misc
  29. ^ "Virgil Security Crypto Library for C: Library: Foundation". Retrieved 2019-08-04.
  30. ^ "System security for watchOS". Retrieved 2021-06-07.
  31. ^ Matt Johnston (2013-11-14). "DROPBEAR_2013.61test".
  32. ^ "OpenSSL CHANGES". July 31, 2019.

외부 링크