View source for EdDSA

{{Short description|Digital signature scheme}}
{{confused|ECDSA}}
{{Infobox encryption method
| name           = EdDSA
| image          = 
| caption        = 
<!-- General -->
| designers      = [[Daniel J. Bernstein]], Niels Duif, [[Tanja Lange]], Peter Schwabe, Bo-Yin Yang, et al.
| publish date   = {{start date and age|2011|9|26|df=y|paren=y}}
| series         = 
| derived from   = 
| derived to     = 
| related to     = 
| certification  = 
<!-- Detail -->
| digest size    = 
| block size     = 
| structure      = [[Elliptic-curve cryptography]]
| rounds         = 
| cryptanalysis  = 
}}

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 curve]]s.<ref name="RFC8032">{{cite IETF
| last1=Josefsson | first1=S.
| last2=Liusvaara | first2=I.
| date=January 2017
| title=Edwards-Curve Digital Signature Algorithm (EdDSA)
| publisher=[[Internet Research Task Force|IRTF]]
| rfc=8032
| issn=2070-1721
| access-date=2022-07-11
}}</ref>
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.<ref name="DJB">{{cite journal
| first1=Daniel J.
| last1=Bernstein
| author-link1=Daniel J. Bernstein
| first2=Niels
| last2=Duif
| first3=Tanja
| last3=Lange
| first4=Peter
| last4=Schwabe
| author5=Bo-Yin Yang
| title=High-speed high-security signatures
| year=2012
| url=https://ed25519.cr.yp.to/ed25519-20110926.pdf
| journal=Journal of Cryptographic Engineering
| volume=2
| pages=77–89
| issue=2
| doi=10.1007/s13389-012-0027-1| s2cid=945254
| doi-access=free
}}</ref>
The [[reference implementation]] is [[public-domain software]].<ref>{{cite web
| url=https://ed25519.cr.yp.to/software.html
| title=Software
| date=2015-06-11
| quote=The Ed25519 software is in the public domain.
| access-date=2016-10-07}}</ref>

== 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.<ref name="bjlsy2015eddsamorecurves">{{cite tech report |author=Daniel J. Bernstein |author2=Simon Josefsson |author3=Tanja Lange |author4=Peter Schwabe |author5=Bo-Yin Yang|title=EdDSA for more curves|date=2015-07-04|url=https://ed25519.cr.yp.to/eddsa-20150704.pdf|access-date=2016-11-14}}</ref><ref name="DJB"/><ref name="RFC8032"/>

An '''EdDSA signature scheme''' is a choice:<ref name="bjlsy2015eddsamorecurves"/>{{rp|1–2}}<ref name="DJB"/>{{rp|5–6}}<ref name="RFC8032"/>{{rp|5–7}}

* of [[finite field]] <math>\mathbb{F}_q</math> over odd prime power <math>q</math>;
* of [[elliptic-curve cryptography|elliptic curve]] <math>E</math> over <math>\mathbb{F}_q</math> whose group <math>E(\mathbb{F}_q)</math> of [[Rational point|<math>\mathbb{F}_q</math>-rational points]] has order <math>\#E(\mathbb{F}_q) = 2^c \ell</math>, where <math>\ell</math> is a large prime and <math>2^c</math> is called the cofactor;
* of base point <math>B \in E(\mathbb{F}_q)</math> with order <math>\ell</math>; and
* of [[cryptographic hash function]] <math>H</math> with <math>2b</math>-bit outputs, where <math>2^{b - 1} > q</math> so that elements of <math>\mathbb{F}_q</math> and curve points in <math>E(\mathbb{F}_q)</math> can be represented by strings of <math>b</math> 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 <math>\sqrt{\ell\pi/4}</math> curve additions before it can compute a discrete logarithm,<ref>{{cite tech report |author=Daniel J. Bernstein |author2=Tanja Lange |author3=Peter Schwabe|title=On the correct use of the negation map in the Pollard rho method|publisher=IACR Cryptology ePrint Archive|number=2011/003|date=2011-01-01|url=https://eprint.iacr.org/2011/003|access-date=2016-11-14}}</ref> so <math>\ell</math> must be large enough for this to be infeasible, and is typically taken to exceed {{math|2<sup>200</sup>}}.<ref>{{cite web  |first1=Daniel J. |last1=Bernstein |first2=Tanja |last2=Lange |title=ECDLP Security: Rho |series=SafeCurves: choosing safe curves for elliptic-curve cryptography |url=https://safecurves.cr.yp.to/rho.html |access-date=2016-11-16 }}</ref>
The choice of <math>\ell</math> is limited by the choice of <math>q</math>, since by [[Hasse's theorem on elliptic curves|Hasse's theorem]], <math>\#E(\mathbb{F}_q) = 2^c \ell</math> cannot differ from <math>q + 1</math> by more than <math>2\sqrt{q}</math>. The hash function <math>H</math> 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 <math>A \in E(\mathbb{F}_q)</math>, encoded in <math>b</math> bits.
; Signature verification
: An EdDSA signature on a message <math>M</math> by public key <math>A</math> is the pair <math>(R, S)</math>, encoded in <math>2b</math> bits, of a curve point <math>R \in E(\mathbb{F}_q)</math> and an integer <math>0 < S < \ell</math> satisfying the following verification equation, where <math>\parallel</math> denotes [[concatenation]]:
<math display="block">2^c S B = 2^c R + 2^c H(R \parallel A \parallel M) A.</math>
; Private key
: An EdDSA private key is a <math>b</math>-bit string <math>k</math> which should be chosen uniformly at random.  The corresponding public key is <math>A = s B</math>, where <math>s = H_{0,\dots,b - 1}(k)</math> is the least significant <math>b</math> bits of <math>H(k)</math> interpreted as an integer in [[little-endian]]. 
; Signing
: The signature on a message <math>M</math> is deterministically computed as <math>(R, S),</math> where <math>R = r B</math> for <math>r = H(H_{b,\dots,2b - 1}(k) \parallel M)</math>, and <math display="block">S \equiv r + H(R \parallel A \parallel M) s \pmod \ell.</math> This satisfies the verification equation
<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''' is the EdDSA signature scheme using [[SHA-512]] (SHA-2) and an elliptic curve related to [[Curve25519]]<ref name="DJB"/> where

* <math>q = 2^{255} - 19,</math>
* <math>E/\mathbb{F}_q</math> is the [[twisted Edwards curve]]
<math display="block">-x^2 + y^2 = 1 - \frac{121665}{121666}x^2y^2,</math>
* <math>\ell = 2^{252} + 27742317777372353535851937790883648493</math> and <math>c = 3</math>
* <math>B</math> is the unique point in <math>E(\mathbb{F}_q)</math> whose <math>y</math> coordinate is <math>4/5</math> and whose <math>x</math> coordinate is positive.<br />"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)
* <math>H</math> is [[SHA-512]], with <math>b = 256</math>.

The [[twisted Edwards curve]] <math>E/\mathbb{F}_q</math> is known as '''edwards25519''',<ref name="RFC7748">{{cite IETF
| last1=Langley | first1=A.
| last2=Hamburg | first2=M.
| last3=Turner | first3=S.
| date=January 2016
| title=Elliptic Curves for Security
| publisher=[[Internet Engineering Task Force|IETF]]
| rfc=7748
| issn=2070-1721
| access-date=2024-11-12
}}</ref><ref name="RFC8032" /> and is [[birationally equivalent]] to the [[Montgomery curve]] known as [[Curve25519]].
The equivalence is<ref name="DJB" /><ref name="RFC7748" /><ref>{{cite conference
| first1=Daniel J.
| last1=Bernstein
| author-link1=Daniel J. Bernstein
| first2=Tanja
| last2=Lange
| title=Faster addition and doubling on elliptic curves
| pages=29–50
| url=https://eprint.iacr.org/2007/286
| doi=10.1007/978-3-540-76900-2_3
| series=Lecture Notes in Computer Science
| publisher=Springer
| location=Berlin
| conference=Advances in cryptology—ASIACRYPT
| year=2007
| isbn=978-3-540-76899-9
| mr=2565722
| volume=4833
| editor1-first=Kaoru
| editor1-last=Kurosawa| doi-access=free
}}</ref>
<math display="block">
x = \frac{u}{v}\sqrt{-486664}, \quad y = \frac{u - 1}{u + 1}.
</math>

=== Performance ===
The original team has optimized Ed25519 for the [[x86-64]] [[Nehalem (microarchitecture)|Nehalem]]/[[Westmere (microarchitecture)|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-key algorithm|symmetric ciphers]].<ref>{{cite web
| url=https://ed25519.cr.yp.to/
| title=Ed25519: high-speed high-security signatures
| date=2017-01-22
| first=Daniel J. |last=Bernstein
| quote=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.
| access-date=2019-09-27}}</ref>

Public keys are 256 bits long and signatures are 512 bits long.<ref>{{cite web
| url=https://ed25519.cr.yp.to/
| title=Ed25519: high-speed high-security signatures
| date=2017-01-22
| first=Daniel J. |last=Bernstein
| quote=Signatures fit into 64 bytes. […] Public keys consume only 32 bytes.
| access-date=2020-06-01 }}</ref>

=== Secure coding ===
Ed25519 is designed to avoid implementations that use branch conditions or array indices that depend on secret data,<ref name="DJB"/>{{rp|2}}<ref name="RFC8032"/>{{rp|40}} in order to mitigate [[side-channel attack]]s.

As with other discrete-log-based signature schemes, EdDSA uses a secret value called a [[Cryptographic nonce|nonce]] unique to each signature.  In the signature schemes [[Digital Signature Algorithm|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.<ref>{{cite news|last=Johnston|first=Casey|title=PS3 hacked through poor cryptography implementation|newspaper=Ars Technica|date=2010-12-30|url=https://arstechnica.com/gaming/2010/12/ps3-hacked-through-poor-implementation-of-cryptography/|access-date=2016-11-15}}</ref><ref>{{cite conference|author=((fail0verflow))|title=Console Hacking 2010: PS3 Epic Fail|conference=[[Chaos Communication Congress]]|date=2010-12-29|url=https://events.ccc.de/congress/2010/Fahrplan/attachments/1780_27c3_console_hacking_2010.pdf|access-date=2016-11-15|archive-url=https://web.archive.org/web/20181026183945/https://events.ccc.de/congress/2010/Fahrplan/attachments/1780_27c3_console_hacking_2010.pdf|archive-date=2018-10-26|url-status=dead}}</ref><ref>{{cite web
| url=https://www.cs.cmu.edu/~dst/GeoHot/1780_27c3_console_hacking_2010.pdf
| title=27th Chaos Communication Congress: Console Hacking 2010: PS3 Epic Fail | access-date=2019-08-04}}</ref><ref>{{cite news |last=Buchanan |first=Bill |url=https://medium.com/asecuritysite-when-bob-met-alice/not-playing-randomly-the-sony-ps3-and-bitcoin-crypto-hacks-c1fe92bea9bc |title=Not Playing Randomly: The Sony PS3 and Bitcoin Crypto Hacks. Watch those random number generators |work=[[Medium (website)|Medium]] |date=2018-11-12 |access-date=2024-03-11 |archive-url=https://web.archive.org/web/20181130215509/https://medium.com/asecuritysite-when-bob-met-alice/not-playing-randomly-the-sony-ps3-and-bitcoin-crypto-hacks-c1fe92bea9bc |archive-date=2018-11-30}}</ref>

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.<ref name="DJB"/>{{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.<ref name="FIPS 186-5"/> The differences between the standards have been analyzed,<ref>{{cite conference
| author-last1=Chalkias | author-first1=Konstantinos
| author-last2=Garillot | author-first2=Francois
| author-last3=Nikolaenko | author-first3=Valeria
| title=Taming the many EdDSAs
| conference=Security Standardisation Research Conference (SSR 2020)
| date=2020-10-01
| url=https://eprint.iacr.org/2020/1244
| access-date=2021-02-15
}}</ref><ref>{{cite conference
| author-last1=Brendel | author-first1=Jacqueline
| author-last2=Cremers | author-first2=Cas
| author-last3=Jackson | author-first3=Dennis
| author-last4=Zhao | author-first4=Mang
| title=The provable security of ed25519: Theory and practice
| conference=IEEE Symposium on Security and Privacy (S&P 2021)
| date=2020-07-03
| url=https://eprint.iacr.org/2020/823
| access-date=2021-02-15
}}</ref> and test vectors are available.<ref>{{cite web
| url=https://github.com/novifinancial/ed25519-speccheck
| title=ed25519-speccheck
| website=[[GitHub]]
| access-date=2021-02-15
}}</ref>

=== Software ===
Notable uses of Ed25519 include [[OpenSSH]],<ref>{{cite web
| url=http://www.openssh.com/txt/release-6.5
| title=Changes since OpenSSH 6.4
| date=2014-01-03
| access-date=2016-10-07}}</ref> [[GnuPG]]<ref>{{cite web
| url=https://gnupg.org/faq/whats-new-in-2.1.html
| title=What's new in GnuPG 2.1
| date=2016-07-14
| access-date=2016-10-07}}</ref> and various alternatives, and the [[Signify (OpenBSD)|signify]] tool by [[OpenBSD]].<ref>{{cite web
| url=https://ianix.com/pub/ed25519-deployment.html
| title=Things that use Ed25519
| date=2016-10-06
| access-date=2016-10-07}}</ref> Usage of Ed25519 (and Ed448) in the SSH protocol has been standardized.<ref>{{cite IETF |last1=Harris |first1=B. |last2=Velvindron |first2=L. |date=February 2020 |title=Ed25519 and Ed448 Public Key Algorithms for the Secure Shell (SSH) Protocol |publisher=[[Internet Engineering Task Force|IETF]] |rfc=8709 |issn=2070-1721 |access-date=2022-07-11}}</ref> In 2023 the final version of the [[Federal Information Processing Standards|FIPS]] 186-5 standard included deterministic Ed25519 as an approved signature scheme.<ref name="FIPS 186-5"/>

* [[Apple Watch]] and [[iPhone]] use Ed25519 keys for [[IKEv2]] mutual authentication<ref>{{cite web |title=System security for watchOS |url=https://support.apple.com/guide/security/system-security-for-watchos-secc7d85209d/ |access-date=2021-06-07}}</ref>
* [[Botan (programming library)|Botan]]
* [[Crypto%2B%2B|Crypto++]]
* [[CryptoNote]] [[cryptocurrency]] [[Cryptographic protocol|protocol]]
* [[Dropbear (software)|Dropbear SSH]]<ref>{{cite web |author=Matt Johnston |date=2013-11-14 |title=DROPBEAR_2013.61test |url=https://secure.ucc.asn.au/hg/dropbear/rev/DROPBEAR_2013.61test |access-date=2019-08-05 |archive-date=2019-08-05 |archive-url=https://web.archive.org/web/20190805012812/https://secure.ucc.asn.au/hg/dropbear/rev/DROPBEAR_2013.61test |url-status=dead }}</ref>
* I2Pd implementation of EdDSA<ref>{{cite journal |date=2015 |title=Heuristic Algorithms and Distributed Computing |url=http://algorithms.samsu.ru/-tom2-nom4.pdf |url-status=dead |journal=Èvrističeskie Algoritmy I Raspredelennye Vyčisleniâ |language=ru |pages=55–56 |issn=2311-8563 |archive-url=https://web.archive.org/web/20161020120014/http://algorithms.samsu.ru/-tom2-nom4.pdf |archive-date=2016-10-20 |access-date=2016-10-07}}</ref>
* [[Java Development Kit]] 15
* [[Libgcrypt]]
* Minisign<ref>{{cite web |author=Frank Denis |title=Minisign: A dead simple tool to sign files and verify signatures. |url=https://jedisct1.github.io/minisign |access-date=2016-10-07}}
</ref> and Minisign Miscellanea<ref>{{Github|JayBrown/minisign-misc}}</ref> for [[macOS]]
* [[NaCl (software)|NaCl / libsodium]]<ref>{{cite web
| url=https://github.com/jedisct1/libsodium/blob/a162c09b69075c467dfa985cd605a80955512c48/ChangeLog
| title=libsodium/ChangeLog
| author=Frank Denis
| website=[[GitHub]]
| date=2016-06-29
| access-date=2016-10-07}}</ref>
* [[OpenSSL]] 1.1.1<ref>{{cite web |date=July 31, 2019 |title=OpenSSL CHANGES |url=https://www.openssl.org/news/cl111.txt |access-date=August 5, 2019 |archive-date=May 18, 2018 |archive-url=https://web.archive.org/web/20180518200747/https://www.openssl.org/news/cl111.txt |url-status=dead }}</ref>
* [[Python (programming language)|Python]] - A slow but concise alternate implementation,<ref>{{cite web |date=2011-07-06 |title=python/ed25519.py: the main subroutines |url=https://ed25519.cr.yp.to/python/ed25519.py |access-date=2016-10-07}}</ref> does not include [[side-channel attack]] protection<ref>{{cite web |date=2015-06-11 |title=Software: Alternate implementations |url=https://ed25519.cr.yp.to/software.html |access-date=2016-10-07}}</ref> 
* Supercop reference implementation<ref>{{cite web |date=2016-09-10 |title=eBACS: ECRYPT Benchmarking of Cryptographic Systems: SUPERCOP |url=https://bench.cr.yp.to/supercop.html |access-date=2016-10-07}}</ref> ([[C language]] with inline [[assembler (computing)|assembler]])
* Virgil PKI uses Ed25519 keys by default<ref>{{cite web |title=Virgil Security Crypto Library for C: Library: Foundation |url=https://github.com/VirgilSecurity/virgil-crypto-c#library-foundation |access-date=2019-08-04 |website=[[GitHub]]}}</ref>
* [[wolfSSL]]<ref>{{cite web
| url=https://www.wolfssl.com/wolfSSL/Products-wolfssl.html
| title=wolfSSL Embedded SSL Library (formerly CyaSSL)
| access-date=2016-10-07}}</ref>
* [[Nano (cryptocurrency)]] uses ed25519 public keys for addresses
* [[Mainline DHT]] uses ed25519 signing for its extension supporting arbitrary mutable data

== Ed448 ==
'''Ed448''' is the EdDSA signature scheme defined in {{IETF RFC|8032}} using the hash function [[SHAKE256]] and the elliptic curve '''edwards448''', an (untwisted) [[Edwards curve]] related to [[Curve448]] in {{IETF RFC|7748}}.
Ed448 has also been approved in the final version of the FIPS 186-5 standard.<ref name="FIPS 186-5">{{cite book
| title=FIPS 186-5: Digital Signature Standard (DSS)
| date=2023-02-03
| publisher=[[NIST]]
| doi=10.6028/NIST.FIPS.186-5
| doi-access=free
| first=Dustin
| last=Moody
| url=https://csrc.nist.gov/publications/detail/fips/186/5/final
| access-date=2023-03-04
| s2cid=256480883
}}</ref>

== References ==
{{reflist}}

== External links ==
* [https://ed25519.cr.yp.to/ Ed25519 home page]

{{Cryptography public-key}}

[[Category:Public-key cryptography]]
[[Category:Elliptic curve cryptography]]
[[Category:Digital signature schemes]]
[[Category:Public-domain software with source code]]