EdDSA algorithms – Digital Signatures
9.4.4 EdDSA algorithms
The ed25519 and ed448 algorithms are instantiations of the Edwards-Curve Digital Signature Algorithm (EdDSA) with the elliptic curves edwards25519 and edwards448, respectively. The algorithms are defined in RFC 8032 Edwards-Curve Digital Signature Algorithm (EdDSA).
The ed25519 algorithm offers roughly 128-bit security. This is in line with the security level recommended by common cryptographic guidelines. As an example, Germany’s Federal Office for Information Security Technical Guideline Cryptographic Mechanisms: Recommendations and Key Lengths [64] specifies key lengths for information that requires long-term protection. Such information is defined as ”information whose confidentiality is intended to be maintained significantly longer than the period of time for which the Technical Guideline makes predictions about the suitability of cryptographic mechanisms, that means well beyond 2028”. The Technical Guideline recommends a security level of at least 120 bits.
The ed448 algorithm offers approximately 224-bit security level. While ed25519 offers sufficient security – unless cryptographically relevant quantum computers are invented – the ed448 algorithm is provided for designers looking for ways to hedge the risk of significant cryptanalytic developments in elliptic curve cryptography.
EdDSA is a variant of Schnorr’s signature algorithm with Edwards curves. More precisely, the EdDSA algorithm is defined by 11 parameters, which we list here for completeness:
- An odd prime p defining the finite field 𝔽p over which the elliptic curve used by the EdDSA algorithm is defined.
- An integer 2b−1 > p defining the size of EdDSA public keys and EdDSA signatures. The public keys are exactly b bits long, and the signatures are 2b bits long. Typically, b is a multiple of eight so that both the public keys and the signatures have an integral number of bytes.
- A (b − 1)-bit encoding for elements of the finite field 𝔽p.
- A cryptographic hash function h that generates a 2b-bit hash H.
- An integer c, the base-2 logarithm of the so-called cofactor equal to either two or three. The secret EdDSA scalars are multiples of 2c.
- An integer n where c ≤ n < b. Secret EdDSA scalars have the size of n + 1 bits with the most significant bit always set to 1 and the least significant bit always set to 0.
- A non-square element d from the finite field 𝔽p, typically chosen as the nearest value to 0 that produces an acceptable elliptic curve.
- A second non-square element a from the finite field 𝔽p. To achieve good computational performance, the values typically chosen for a are either -1 (if p mod 4 = 1) or 1 (if p mod 4 = 3).
- An element B from the set E = {(x,y)|x,y ∈ 𝔽p and a ⋅ x2 + y2 = 1 + d ⋅ x2 ⋅ y2}.
- An odd prime l such that the scalar multiple lB equals 0 and 2cl = #E where #E is the number of points on the elliptic curve.
- A so-called prehash function PH. The EdDSA variant PureEdDSA uses the identity function as the prehash function, that is, PH(M) = M for a message M. Another EdDSA variant called HashEdDSA uses a cryptographic hash function to prehash the input message, for example, PH(M) = SHA − 512(M). Note that PureEdDSA is the variant used in TLS 1.3. For collision resistance, it does not rely on the collision resistance of the underlying hash function.