GetWiki

{{Short description|Digital signature scheme}}

factoids

In public-key cryptography, Edwards-curve Digital Signature Algorithm (EdDSA) is a digital signature scheme using a variant of Schnorr signature based on twisted Edwards curves.JOSEFSSON > FIRST1=S. FIRST2=I., January 2017, Edwards-Curve Digital Signature Algorithm (EdDSA)Internet Research Task Force>IRTF, 8032, 2070-1721, 2022-07-11, It is designed to be faster than existing digital signature schemes without sacrificing security. It was developed by a team including Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang.JOURNAL, Daniel J., Bernstein, Daniel J. Bernstein, Niels, Duif, Tanja, Lange, Peter, Schwabe, Bo-Yin Yang, High-speed high-security signatures, 2012,ed25519.cr.yp.to/ed25519-20110926.pdf, Journal of Cryptographic Engineering, 2, 77–89, 2 s2cid=945254, free, The reference implementation is public-domain software.WEB,ed25519.cr.yp.to/software.html, Software, 2015-06-11, The Ed25519 software is in the public domain., 2016-10-07,

Summary

The following is a simplified description of EdDSA, ignoring details of encoding integers and curve points as bit strings; the full details are in the papers and RFC.TECH REPORT, Daniel J. Bernstein, Simon Josefsson, Tanja Lange, Peter Schwabe, Bo-Yin Yang, EdDSA for more curves, 2015-07-04,ed25519.cr.yp.to/eddsa-20150704.pdf, 2016-11-14, An EdDSA signature scheme is a choice:{{rp|1–2}}{{rp|5–6}}{{rp|5–7}}

• of finite field mathbb{F}_q over odd prime power q;
• of elliptic curve E over mathbb{F}_q whose group E(mathbb{F}_q) of mathbb{F}_q-rational points has order E(mathbb{F}_q) = 2^c ell, where ell is a large prime and 2^c is called the cofactor;
• of base point B in E(mathbb{F}_q) with order ell; and
• of cryptographic hash function H with 2b-bit outputs, where 2^{b - 1} > q so that elements of mathbb{F}_q and curve points in E(mathbb{F}_q) can be represented by strings of b bits.

These parameters are common to all users of the EdDSA signature scheme. The security of the EdDSA signature scheme depends critically on the choices of parameters, except for the arbitrary choice of base point—for example, Pollard’s rho algorithm for logarithms is expected to take approximately sqrt{ellpi/4} curve additions before it can compute a discrete logarithm,TECH REPORT, 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/003, 2011-01-01,eprint.iacr.org/2011/003, 2016-11-14, so ell must be large enough for this to be infeasible, and is typically taken to exceed {{math|2200}}.WEB, Daniel J., Bernstein, Tanja, Lange, ECDLP Security: Rho, SafeCurves: choosing safe curves for elliptic-curve cryptography,safecurves.cr.yp.to/rho.html, 2016-11-16, The choice of ell is limited by the choice of q, since by Hasse’s theorem, #E(mathbb{F}_q) = 2^c ell cannot differ from q + 1 by more than 2sqrt{q}. The hash function H is normally modelled as a random oracle in formal analyses of EdDSA’s security.Within an EdDSA signature scheme,

Public key

An EdDSA public key is a curve point A in E(mathbb{F}_q), encoded in b bits.

Signature Verification

An EdDSA signature on a message M by public key A is the pair (R, S), encoded in 2b bits, of a curve point R in E(mathbb{F}_q) and an integer 0

< S < ell satisfying the following verification equation. parallel denotes concatenation.2^c S B = 2^c R + 2^c H(R parallel A parallel M) A

Private key

An EdDSA private key is a b-bit string k which should be chosen uniformly at random. The corresponding public key is A = s B, where s = H_{0,dots,b - 1}(k) is the least significant b bits of H(k) interpreted as an integer in little-endian.

Signing

The signature on a message M is deterministically computed as (R, S) where R = r B for r = H(H_{b,dots,2b - 1}(k) parallel M), and S equiv r + H(R parallel A parallel M) s pmod ell. This satisfies the verification equation:

begin{align}2^c S B &= 2^c (r + H(R parallel A parallel M) s) B end{align}

Ed25519

Ed25519 is the EdDSA signature scheme using SHA-512 (SHA-2) and Curve25519 where

• q = 2^{255} - 19,
• E/mathbb{F}_q is the twisted Edwards curve

-x^2 + y^2 = 1 - frac{121665}{121666}x^2y^2,

• ell = 2^{252} + 27742317777372353535851937790883648493 and c = 3
• B is the unique point in E(mathbb{F}_q) whose y coordinate is 4/5 and whose x coordinate is positive.“positive” is defined in terms of bit-encoding:
  • “positive” coordinates are even coordinates (least significant bit is cleared)
  • “negative” coordinates are odd coordinates (least significant bit is set)
• H is SHA-512, with b = 256.

The curve E(mathbb{F}_q) is birationally equivalent to the Montgomery curve known as Curve25519. The equivalence isCONFERENCE, Daniel J., Bernstein, Daniel J. Bernstein, Tanja, Lange, Faster addition and doubling on elliptic curves, 29–50,eprint.iacr.org/2007/286, 10.1007/978-3-540-76900-2_3, Lecture Notes in Computer Science, Springer, Berlin, Advances in cryptology—ASIACRYPT, 2007, 978-3-540-76899-9, 2565722, 4833, Kaoru doi-access=free, x = frac{u}{v}sqrt{-486664}, quad y = frac{u - 1}{u + 1}.

Performance

The original team has optimized Ed25519 for the x86-64 Nehalem/Westmere processor family. Verification can be performed in batches of 64 signatures for even greater throughput. Ed25519 is intended to provide attack resistance comparable to quality 128-bit symmetric ciphers.WEB,ed25519.cr.yp.to/, Ed25519: high-speed high-security signatures, 2017-01-22last=Bernstein, 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., 2019-09-27, Public keys are 256 bits long and signatures are 512 bits long.WEB,ed25519.cr.yp.to/, Ed25519: high-speed high-security signatures, 2017-01-22last=Bernstein, Signatures fit into 64 bytes. […] Public keys consume only 32 bytes., 2020-06-01,

Secure coding

Ed25519 is designed to avoid implementations that use branch conditions or array indices that depend on secret data,{{rp|2}}{{rp|40}} in order to mitigate side-channel attacks.As with other discrete-log-based signature schemes, EdDSA uses a secret value called a nonce unique to each signature. In the signature schemes DSA and ECDSA, this nonce is traditionally generated randomly for each signature—and if the random number generator is ever broken and predictable when making a signature, the signature can leak the private key, as happened with the Sony PlayStation 3 firmware update signing key.NEWS, Johnston, Casey, PS3 hacked through poor cryptography implementation, Ars Technica, 2010-12-30,arstechnica.com/gaming/2010/12/ps3-hacked-through-poor-implementation-of-cryptography/, 2016-11-15, CONFERENCE, fail0verflow, Console Hacking 2010: PS3 Epic Fail, Chaos Communication Congress, 2010-12-29,events.ccc.de/congress/2010/Fahrplan/attachments/1780_27c3_console_hacking_2010.pdf, 2016-11-15,web.archive.org/web/20181026183945/https://events.ccc.de/congress/2010/Fahrplan/attachments/1780_27c3_console_hacking_2010.pdf, 2018-10-26, dead, WEB,www.cs.cmu.edu/~dst/GeoHot/1780_27c3_console_hacking_2010.pdf access-date=2019-08-04, BUCHANAN >FIRST=BILL TITLE=NOT PLAYING RANDOMLY: THE SONY PS3 AND BITCOIN CRYPTO HACKS. WATCH THOSE RANDOM NUMBER GENERATORS MEDIUM (WEBSITE)>MEDIUM ACCESS-DATE=2024-03-11 ARCHIVE-DATE=2018-11-30, In contrast, EdDSA chooses the nonce deterministically as the hash of a part of the private key and the message. Thus, once a private key is generated, EdDSA has no further need for a random number generator in order to make signatures, and there is no danger that a broken random number generator used to make a signature will reveal the private key.{{rp|8}}

Standardization and implementation inconsistencies

Note that there are two standardization efforts for EdDSA, one from IETF, an informational {{IETF RFC|8032}} and one from NIST as part of FIPS 186-5. The differences between the standards have been analyzed,CONFERENCE, Konstantinos Chalkias, Francois Garillot and Valeria Nikolaenko, Taming the many EdDSAs, Security Standardisation Research Conference (SSR 2020), 2020-10-01,eprint.iacr.org/2020/1244, 2021-02-15, CONFERENCE, 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,eprint.iacr.org/2020/823, 2021-02-15,

Software

Notable uses of Ed25519 include OpenSSH,WEB,www.openssh.com/txt/release-6.5, Changes since OpenSSH 6.4, 2014-01-03, 2016-10-07, GnuPGWEB,gnupg.org/faq/whats-new-in-2.1.html, What’s new in GnuPG 2.1, 2016-07-14, 2016-10-07, and various alternatives, and the signify tool by OpenBSD.WEB,ianix.com/pub/ed25519-deployment.html, Things that use Ed25519, 2016-10-06LAST2=VELVINDRON DATE=FEBRUARY 2020 PUBLISHER=INTERNET ENGINEERING TASK FORCE >RFC=8709 ACCESS-DATE=2022-07-11, In 2023 the final version of the FIPS 186-5 standard included deterministic Ed25519 as an approved signature scheme.

• Apple Watch and iPhone use Ed25519 keys for IKEv2 mutual authenticationWEB, System security for watchOS,support.apple.com/guide/security/system-security-for-watchos-secc7d85209d/, 2021-06-07,
• Botan
• Crypto++
• CryptoNote cryptocurrency protocol
• Dropbear SSHWEB, Matt Johnston, 2013-11-14, DROPBEAR_2013.61test,secure.ucc.asn.au/hg/dropbear/rev/DROPBEAR_2013.61test, 2019-08-05, 2019-08-05,web.archive.org/web/20190805012812/https://secure.ucc.asn.au/hg/dropbear/rev/DROPBEAR_2013.61test, dead,
• I2Pd implementation of EdDSAJOURNAL, 2015, Heuristic Algorithms and Distributed Computing,algorithms.samsu.ru/-tom2-nom4.pdf, dead, Èvrističeskie Algoritmy I Raspredelennye Vyčisleniâ, ru, 55–56, 2311-8563,algorithms.samsu.ru/-tom2-nom4.pdf," title="web.archive.org/web/20161020120014algorithms.samsu.ru/-tom2-nom4.pdf,">web.archive.org/web/20161020120014algorithms.samsu.ru/-tom2-nom4.pdf, 2016-10-20, 2016-10-07,
• Java Development Kit 15
• Libgcrypt
• MinisignWEB, Frank Denis, Minisign: A dead simple tool to sign files and verify signatures.,jedisct1.github.io/minisign, 2016-10-07,

• NaCl / libsodiumWEB,github.com/jedisct1/libsodium/blob/a162c09b69075c467dfa985cd605a80955512c48/ChangeLog, libsodium/ChangeLog, Frank Denis, GitHub, 2016-06-29, 2016-10-07,
• OpenSSL 1.1.1WEB, July 31, 2019, OpenSSL CHANGES,www.openssl.org/news/cl111.txt, August 5, 2019, May 18, 2018,web.archive.org/web/20180518200747/https://www.openssl.org/news/cl111.txt, dead,
• Python - A slow but concise alternate implementation,WEB, 2011-07-06, python/ed25519.py: the main subroutines,ed25519.cr.yp.to/python/ed25519.py, 2016-10-07, does not include side-channel attack protectionWEB, 2015-06-11, Software: Alternate implementations,ed25519.cr.yp.to/software.html, 2016-10-07,
• Supercop reference implementationWEB, 2016-09-10, eBACS: ECRYPT Benchmarking of Cryptographic Systems: SUPERCOP,bench.cr.yp.to/supercop.html, 2016-10-07, (C language with inline assembler)
• Virgil PKI uses Ed25519 keys by defaultWEB, Virgil Security Crypto Library for C: Library: Foundation,github.com/VirgilSecurity/virgil-crypto-clibrary-foundation, 2019-08-04, GitHub,
• wolfSSLWEB,www.wolfssl.com/wolfSSL/Products-wolfssl.html, wolfSSL Embedded SSL Library (formerly CyaSSL), 2016-10-07,

Ed448

Ed448 is the EdDSA signature scheme using SHAKE256 and Curve448 defined in {{IETF RFC|8032}}. It has also been approved in the final version the FIPS 186-5 standard.BOOK, FIPS 186-5: Digital Signature Standard (DSS), 2023-02-03, NIST, 10.6028/NIST.FIPS.186-5, Dustin, Moody,csrc.nist.gov/publications/detail/fips/186/5/final, 2023-03-04, 256480883,

References

{{reflist}}

External links

• Ed25519 home page

{{Cryptography public-key}}