Not to be confused with
ECDSA.
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.[1]
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.[2]
The reference implementation is public-domain software.[3]
Quick Facts General, Designers ...
Close
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]
An EdDSA signature scheme is a choice:[4]: 1–2 [2]: 5–6 [1]: 5–7
- of finite field
over odd prime power
;
- of elliptic curve
over
whose group
of
-rational points has order
, where
is a large prime and
is called the cofactor;
- of base point
with order
; and
- of cryptographic hash function
with
-bit outputs, where
so that elements of
and curve points in
can be represented by strings of
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
curve additions before it can compute a discrete logarithm,[5] so
must be large enough for this to be infeasible, and is typically taken to exceed 2200.[6]
The choice of
is limited by the choice of
, since by Hasse's theorem,
cannot differ from
by more than
. The hash function
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
, encoded in
bits.
- Signature verification
- An EdDSA signature on a message
by public key
is the pair
, encoded in
bits, of a curve point
and an integer
satisfying the following verification equation, where
denotes concatenation:
![{\displaystyle 2^{c}SB=2^{c}R+2^{c}H(R\parallel A\parallel M)A.}](//wikimedia.org/api/rest_v1/media/math/render/svg/1ea2e747b8c3d3f2c0625b9ee73ff67b51d07026)
- Private key
- An EdDSA private key is a
-bit string
which should be chosen uniformly at random. The corresponding public key is
, where
is the least significant
bits of
interpreted as an integer in little-endian.
- Signing
- The signature on a message
is deterministically computed as
where
for
, and
This satisfies the verification equation
![{\displaystyle {\begin{aligned}2^{c}SB&=2^{c}(r+H(R\parallel A\parallel M)s)B\\&=2^{c}rB+2^{c}H(R\parallel A\parallel M)sB\\&=2^{c}R+2^{c}H(R\parallel A\parallel M)A.\end{aligned}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/e2a722d639564569495b31fad8127ea5d6e19d8e)
Ed25519 is the EdDSA signature scheme using SHA-512 (SHA-2) and Curve25519[2] where
![{\displaystyle q=2^{255}-19,}](//wikimedia.org/api/rest_v1/media/math/render/svg/efb5112630883ccb8eddbdc762c54696bc78abc3)
is the twisted Edwards curve
![{\displaystyle -x^{2}+y^{2}=1-{\frac {121665}{121666}}x^{2}y^{2},}](//wikimedia.org/api/rest_v1/media/math/render/svg/fba95de67402303aa1144563437f5e4a310422fb)
and ![{\displaystyle c=3}](//wikimedia.org/api/rest_v1/media/math/render/svg/da6c3ad0b12414cdd2dad18f1ebd555f89ae5ece)
is the unique point in
whose
coordinate is
and whose
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)
is SHA-512, with
.
The curve
is birationally equivalent to the Montgomery curve known as Curve25519. The equivalence is[2][7]
![{\displaystyle x={\frac {u}{v}}{\sqrt {-486664}},\quad y={\frac {u-1}{u+1}}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/22ae119857d41ca599eedc32fdcacb844236cece)
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.[8]
Public keys are 256 bits long and signatures are 512 bits long.[9]
Secure coding
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 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.[10][11][12][13]
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
Standardization and implementation inconsistencies
Note that there are two standardization efforts for EdDSA, one from IETF, an informational RFC 8032 and one from NIST as part of FIPS 186-5.[14] The differences between the standards have been analyzed,[15][16] and test vectors are available.[17]
Software
Notable uses of Ed25519 include OpenSSH,[18] GnuPG[19] and various alternatives, and the signify tool by OpenBSD.[20] Usage of Ed25519 (and Ed448) in the SSH protocol has been standardized.[21] In 2023 the final version of the FIPS 186-5 standard included deterministic Ed25519 as an approved signature scheme.[14]
Ed448 is the EdDSA signature scheme using SHAKE256 and Curve448 defined in RFC 8032. It has also been approved in the final version the FIPS 186-5 standard.[14]
"Software". 2015-06-11. Retrieved 2016-10-07. The Ed25519 software is in the public domain.
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. Bernstein, Daniel J.; Lange, Tanja. "ECDLP Security: Rho". SafeCurves: choosing safe curves for elliptic-curve cryptography. Retrieved 2016-11-16. Bernstein, Daniel J. (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.
Konstantinos Chalkias, Francois Garillot and Valeria Nikolaenko (2020-10-01). Taming the many EdDSAs. Security Standardisation Research Conference (SSR 2020). Retrieved 2021-02-15.