Inpublic-key cryptography,Edwards-curve Digital Signature Algorithm (EdDSA) is adigital signature scheme using a variant ofSchnorr signature based ontwisted Edwards curves.^[1]It is designed to be faster than existing digital signature schemes without sacrificing security. It was developed by a team includingDaniel J. Bernstein, Niels Duif,Tanja Lange, Peter Schwabe, andBo-Yin Yang.^[2]Thereference implementation ispublic-domain software.^[3]

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.^[4][2][1]

AnEdDSA signature scheme is a choice:^{[4]: 1–2 [2]: 5–6 [1]: 5–7}

• offinite field${\displaystyle {\mathbb{F}}_q}$ over odd prime power${\displaystyle q}$;
• ofelliptic curve${\displaystyle E}$ over${\displaystyle {\mathbb{F}}_q}$ whose group${\displaystyle E({\mathbb{F}}_q)}$ of${\displaystyle {\mathbb{F}}_q}$-rational points has order${\displaystyle \mathrm{\#}E({\mathbb{F}}_q)=2^c\ell }$, where${\displaystyle \ell }$ is a large prime and${\displaystyle 2^c}$ is called the cofactor;
• of base point${\displaystyle B\in E({\mathbb{F}}_q)}$ with order${\displaystyle \ell }$; and
• ofcryptographic hash function${\displaystyle H}$ with${\displaystyle 2b}$-bit outputs, where${\displaystyle 2^{b-1}>q}$ so that elements of${\displaystyle {\mathbb{F}}_q}$ and curve points in${\displaystyle E({\mathbb{F}}_q)}$ can be represented by strings of${\displaystyle 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${\displaystyle \sqrt{\ell \pi /4}}$ curve additions before it can compute a discrete logarithm,^[5] so${\displaystyle \ell }$ must be large enough for this to be infeasible, and is typically taken to exceed2²⁰⁰.^[6]The choice of${\displaystyle \ell }$ is limited by the choice of${\displaystyle q}$, since byHasse's theorem,${\displaystyle \mathrm{\#}E({\mathbb{F}}_q)=2^c\ell }$ cannot differ from${\displaystyle q+1}$ by more than${\displaystyle 2\sqrt{q}}$. The hash function${\displaystyle H}$ is normally modelled as arandom oracle in formal analyses of EdDSA's security.

Within an EdDSA signature scheme,

Public key

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

Signature verification

An EdDSA signature on a message${\displaystyle M}$ by public key${\displaystyle A}$ is the pair${\displaystyle (R,S)}$, encoded in${\displaystyle 2b}$ bits, of a curve point${\displaystyle R\in E({\mathbb{F}}_q)}$ and an integer satisfying the following verification equation, where${\displaystyle \parallel }$ denotesconcatenation:

$${\displaystyle 2^{c}SB=2^{c}R+2^{c}H(R\parallel A\parallel M)A.}$$

Private key

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

Signing

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

Ed25519 is the EdDSA signature scheme usingSHA-512 (SHA-2) and an elliptic curve related toCurve25519^[2] where

• ${\displaystyle q=2^{255}-19,}$
• ${\displaystyle E/{\mathbb{F}}_q}$ is thetwisted Edwards curve

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

• ${\displaystyle \ell =2^{252}+27742317777372353535851937790883648493}$ and${\displaystyle c=3}$
• ${\displaystyle B}$ is the unique point in${\displaystyle E({\mathbb{F}}_q)}$ whose${\displaystyle y}$ coordinate is${\displaystyle 4/5}$ and whose${\displaystyle 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)
• ${\displaystyle H}$ isSHA-512, with${\displaystyle b=256}$.

Thetwisted Edwards curve${\displaystyle E/{\mathbb{F}}_q}$ is known asedwards25519,^[7][1] and isbirationally equivalent to theMontgomery curve known asCurve25519.The equivalence is^[2][7][8]$${\displaystyle x=\frac{u}{v}\sqrt{-486664},y=\frac{u-1}{u+1}.}$$

The original team has optimized Ed25519 for thex86-64Nehalem/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-bitsymmetric ciphers.^[9]

Public keys are 256 bits long and signatures are 512 bits long.^[10]

Ed25519 is designed to avoid implementations that use branch conditions or array indices that depend on secret data,^{[2]: 2 [1]: 40} in order to mitigateside-channel attacks.

As with other discrete-log-based signature schemes, EdDSA uses a secret value called anonce unique to each signature. In the signature schemesDSA andECDSA, 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 theSony PlayStation 3 firmware update signing key.^{[11][12][13][14]}

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.^[2]: 8

Note that there are two standardization efforts for EdDSA, one from IETF, an informationalRFC 8032 and one from NIST as part of FIPS 186-5.^[15] The differences between the standards have been analyzed,^[16][17] and test vectors are available.^[18]

Notable uses of Ed25519 includeOpenSSH,^[19]GnuPG^[20] and various alternatives, and thesignify tool byOpenBSD.^[21] Usage of Ed25519 (and Ed448) in the SSH protocol has been standardized.^[22] In 2023 the final version of theFIPS 186-5 standard included deterministic Ed25519 as an approved signature scheme.^[15]

• Apple Watch andiPhone use Ed25519 keys forIKEv2 mutual authentication^[23]
• Botan
• Crypto++
• CryptoNotecryptocurrencyprotocol
• Dropbear SSH^[24]
• I2Pd implementation of EdDSA^[25]
• Java Development Kit 15
• Libgcrypt
• Minisign^[26] and Minisign Miscellanea^[27] formacOS
• NaCl / libsodium^[28]
• OpenSSL 1.1.1^[29]
• Python - A slow but concise alternate implementation,^[30] does not includeside-channel attack protection^[31]
• Supercop reference implementation^[32] (C language with inlineassembler)
• Virgil PKI uses Ed25519 keys by default^[33]
• wolfSSL^[34]

Ed448 is the EdDSA signature scheme defined inRFC 8032 using the hash functionSHAKE256 and the elliptic curveedwards448, an (untwisted)Edwards curve related toCurve448 inRFC 7748.Ed448 has also been approved in the final version of the FIPS 186-5 standard.^[15]

• Ed25519 home page

• Public-key cryptography
• Elliptic curve cryptography
• Digital signature schemes
• Public-domain software with source code

• CS1 Russian-language sources (ru)
• Articles with short description
• Short description matches Wikidata