In public-key cryptographic systems , the Edwards-curve Digital Signature Algorithm (EdDSA) is a digital signature scheme using a variant of the Shnor scheme based on [1] .
It is designed to be faster than an existing digital signature scheme without compromising its security. It was designed by , Niels Duif, Tanya Lange, Peter Schwabe and Bo-Yin Yang.
Content
Design
Below is a simplified description of EdDSA, which does not include the details of encoding integers and curve points as bit strings. A complete description and details of this digital signature implementation can be found in the documentation and the relevant RFCs [2] [3] [1] .
EdDSA uses the following parameters:
- Selection of the final field q order:
- Selecting an elliptic curve E over a field whose band of rational points of order where l is a large prime number, and 2 ^ c is called a cofactor
- Base point selection with order l
- And the choice of a hash-protected H from collisions with 2b-bit outputs, where 2 ^ (b-1)> q so that the elements of the final field and curve points in could be represented as a string of long b bits.
These parameters are the minimum required for all users of the EdDSA signature scheme. EdDSA signature security is highly dependent on the choice of parameters, with the exception of an arbitrary base point selection. For example , the Polard ro-algorithm for the logarithm should take approximately curves, before being able to calculate the logarithm, [4] therefore l must be large enough that it is not possible and usually must exceed 2 ^ 200. [5] The choice of l is limited by the choice of q, since, according to the Hasse theorem must not differ from q + 1 by more than
As part of the EdDSA signature scheme
- Public key
- EdDSA's public key is a curve point encoded in b bits.
- Signature
- The EdDSA signature in message M by means of the public key A is a pair (R, S) encoded in 2b bits, a curve point and integer satisfying the verification equation
- Private key
- The private key in the EdDSA scheme is a b-bit string k which should be chosen uniformly at random. The corresponding public key in this case is where is the least significant b-bit of H (k) interpreted as an integer in direct byte order. The message signature M is a pair (R, S) where R = rB for and
Ed25519
Ed25519 - EdDSA signature scheme using SHA-512 and Curve25519 [2] where:
- q = 2 ^ 255-19
- - Edwards elliptic curve
- l = 2 ^ 255 + 27742317777372353535851937790883648493 and c = 3
- B - unique point whose y coordinate is 4/5, and the x coordinate is positive (in terms of bit-coding)
H - SHA-512 , with b = 256 Curve birationally equivalent to the Montgomery curve, known as Curve25519. Equivalence [6] [2]
Efficiency
The Bernstein team optimized the Ed25519 for the x86-64 Nehalem / Westmere processor family. Verification can be performed in batches of 64 digital signatures for even greater bandwidth. Ed25519 is designed to provide resistance to attacks comparable to the quality of 128-bit symmetric ciphers . Public keys are 256 bits long, and the signature is twice the size.
Secure coding
As a security feature, the Ed25519 does not use branch operations and array indexing steps that depend on secret data to prevent third-party channel attacks .
Like other discrete-logarithmic signature schemes, EdDSA uses a secret value called a one - time number unique to each signature. In the DSA and ECDSA signature schemes, this one-time number is traditionally randomly generated for each signature, and if the random number generator is broken or predictable during signature generation, the signature can merge the private key, which is what happened to the firmware update key for the Sony PlayStation 3 [7] [8] . Compared to them, EdDSA selects one-time numbers deterministically, like a hash of a private key and a message. Thus, once having generated a private key, the EdDSA no longer needs a random number generator in order to make signatures, and there is no danger that a broken random number generator used to create a digital signature will reveal the private key.
Software
Known uses for Ed25519 include OpenSSH , [9] GnuPG [10] and various alternatives, as well as the value tool from OpenBSD . [eleven]
- Reference implementation of SUPERCOP [12] ( language with a built-in assembler )
- Slow, but laconic alternative implementation, not including protection against attacks on third-party channels ( Python )
- NaCl / libsodium [13]
- CryptoNote Cryptocurrency Protocol
- wolfSSL [14]
- I2Pd has its own implementation of EdDSA [15]
- Minisign and Minisign Miscellanea for macOS [16]
- Virgil PKI uses Ed25519 default keys
- Botan
- Dropbear SSH with test 2013.61
- OpenSSL 1.1.1 (supports TLS 1.3 and SHA3 in addition to X25519 / Ed25519)
- Hashmap Server and Client (Go and Javascript language)
- Libgcrypt
Notes
- ↑ 1 2 Josefsson, S .; Liusvaara, I. (January 2017). Edwards-Curve Digital Signature Algorithm (EdDSA) . Internet Engineering Task Force. doi: 10.17487 / RFC8032. ISSN 2070-1721. RFC 8032. Retrieved 2017-07-31.
- ↑ 1 2 3 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.
- ↑ Daniel J. Bernstein, Simon Josefsson, Tanja Lange, Peter Schwabe, and Bo-Yin Yang (2015-07-04). EdDSA for more curves (PDF) (Technical report). Retrieved 2016-11-14.
- ↑ Daniel J. Bernstein, Tanja Lange, and Peter Schwabe (2011-01-01). Use the map report in the Pollard rho method (Technical report). IACR Cryptology ePrint Archive. 2011/003. Retrieved 2016-11-14.
- ↑ Daniel J. Bernstein and Tanja Lange. "ECDLP Security: Rho". SafeCurves: choosing safe curves for elliptic-curve cryptography. Retrieved 2016-11-16.
- ↑ 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. 4833 . Berlin: Springer. pp. 29-50. doi: 10.1007 / 978-3-540-76900-2_3. ISBN 978-3-540-76899-9. MR 2565722.
- ↑ Johnston, Casey (2010-12-30). "PS3 hacked through poor cryptography implementation". Ars Technica . Retrieved 2016-11-15.
- ↑ fail0verflow (2010-12-29). Console Hacking 2010: PS3 Epic Fail (PDF). 27C3: 27th Chaos Communication Conference. Retrieved 2016-11-15.
- "Changes since OpenSSH 6.4". 2014-01-03. Retrieved 2016-10-07.
- ↑ What's new in GnuPG 2.1 ". 2016-07-14. Retrieved 2016-10-07.
- ↑ "Things that use Ed25519". 2016-10-06. Retrieved 2016-10-07.
- EBACS: ECRYPT Benchmarking of Cryptographic Systems: SUPERCOP. 2016-09-10. Retrieved 2016-10-07.
- ↑ Frank Denis (2016-06-29). "Libsodium / ChangeLog". Retrieved 2016-10-07.
- "WolfSSL Embedded SSL Library (formerly CyaSSL)". Retrieved 2016-10-07.
- Heuristic Algorithms and Distributed Computing (PDF) (in Russian). 2015. pp. 55-56. ISSN 2311-8563. Retrieved 2016-10-07.
- ↑ minisign-misc on GitHub