Ed25519

Ed25519 is an elliptic curve digital signature algorithm based on the Edwards-form curve Curve25519, designed by Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang in 2011. It is specified in RFC 8032 and is the recommended signature scheme for new applications, replacing ECDSA over NIST curves (P-256, P-384) and RSA signatures. This page covers the curve, the EdDSA algorithm, the security properties, and the production use cases (SSH keys, age encryption, Signal’s XEdDSA).

Why Ed25519 Exists

ECDSA (Elliptic Curve Digital Signature Algorithm) over NIST curves has been the workhorse of public-key signatures since the early 2000s. But it has problems:

1. NIST curves have unexplained parameters. The random seed for the P-256 curve coefficients (c = SHA-1(S) where S is an unexplained constant) raised concerns of NSA backdoors (especially post-DUAL_EC_DRBG). No backdoor was ever found, but the suspicion remains.

2. ECDSA signatures are non-deterministic. Each signing operation generates a fresh random k value; if k is ever reused (or even slightly biased), the private key can be recovered from two signatures. Real-world examples include Sony’s PS3 private key (2010) and Bitcoin’s Android wallet (2013).

3. ECDSA is slow to verify. Verification requires two elliptic curve point multiplications, which are the most expensive EC operations.

4. NIST curves use Weierstrass form, which doesn’t have a unified addition formula — there are special cases for doubling vs. addition, which are bug-prone and slow.

Ed25519 addresses all four:

1. Curve25519 has transparent parameters. The curve’s parameters are derived from the smallest valid constant d that gives a secure curve. There’s no “seed” to question.

2. EdDSA signatures are deterministic. The nonce is derived from the message and the private key via SHA-512, not from a random number generator. Two signatures of the same message by the same key are identical, which eliminates the k-reuse attack class.

3. Ed25519 verification is fast. Optimized verification uses formulas that batch point operations, achieving ~80 µs per verification on a modern CPU (vs ~250 µs for ECDSA P-256).

4. Edwards curves have a unified addition formula — the same code path for adding distinct points and for doubling. This eliminates the special-case bugs.

The Curve25519

The curve used by Ed25519 is the twisted Edwards form:

-y² + x² = 1 + d·x²·y²    (mod p)

where:

• p = 2²⁵⁵ - 19 (a 255-bit prime, hence “25519”)
• d = -121665 / 121666 mod p (the smallest non-negative d that gives a curve with cofactor 8)
• The base point B has a known large prime-order subgroup of order L = 2²⁵² + 2774231777887265569338668668036346433429328634613 (≈ 2²⁵²).

The curve’s order is 8L — the cofactor of 8 means the full group is 8× larger than the prime-order subgroup EdDSA uses. EdDSA implementations handle the cofactor carefully (the signer/verifier reduces to the prime-order subgroup).

The EdDSA Algorithm

Key Generation

private_key_seed = 32 random bytes (sk)
h = SHA-512(sk)        ← 64 bytes
h[0..32] → clamp      ← clamp the lower 32 bytes (set/clear specific bits)
a = clamped scalar (the "scalar half" of the private key)
A = a * B              ← public key (a point on the curve)

The private key is sk (32 random bytes). The public key is A (32 bytes, the y-coordinate of the curve point, with the high bit encoding the sign of x).

Signing

r = SHA-512(h[32..64] || M) mod L   ← deterministic nonce
R = r * B                           ← the "r half" of the signature
k = SHA-512(R || A || M) mod L      ← the challenge
S = (r + k * a) mod L               ← the "s half"
signature = R || S                  ← 64 bytes total

The signature is two parts: R (32 bytes, the curve point) and S (32 bytes, the scalar). Verification reconstructs R, A, M, computes k, and checks S*B == R + k*A.

Verification

Parse signature as R || S
Recompute k = SHA-512(R || A || M) mod L
Verify: S * B == R + k * A

Verification is a single multi-scalar multiplication: S*B - k*A - R == 0. This can be batched — verifying N signatures can be done in ~1.5× the time of one verification (vs N× for serial verification).

Security Properties

• 128-bit security level: breaking Ed25519 is approximately as hard as breaking AES-128.
• No random number dependency in signing: deterministic, k-reuse impossible.
• Side-channel resistant: the algorithm doesn’t branch on secret data (no secret-dependent array indexes, no conditional execution). The verifier also has a constant-time implementation (some implementations skip this for speed).
• Small signatures: 64 bytes. Compare RSA-2048: 256 bytes. ECDSA P-256: 64 bytes (same).
• Small keys: 32 bytes (vs RSA-2048: 256 bytes; ECDSA P-256: 32 bytes).

Production Use Cases

SSH

OpenSSH 6.5+ (2014) supports Ed25519 keys, and they are the recommended key type. To generate:

ssh-keygen -t ed25519 -f ~/.ssh/id_ed25519

The public key is ~/.ssh/id_ed25519.pub, ~80 bytes (starts with ssh-ed25519 ).

Git commit signing

Git supports Ed25519 signing since Git 2.13 (2017). GitHub shows “Verified” badges on commits signed with a key associated with the user’s account.

age (modern encryption tool)

The age tool (Björn Jacke, Filippo Valsorda) uses X25519 (Diffie-Hellman over Curve25519) for key agreement. X25519 is the same curve as Ed25519 but with a different protocol (DH vs. signatures).

Signal’s XEdDSA

Signal’s protocol uses XEdDSA, an extension of EdDSA that supports both signing and Diffie-Hellman key exchange with the same key pair. This is a non-standard but widely-deployed variant.

Tor v3 onion services

Tor’s v3 onion service addresses use Ed25519 keys for service identity. The onion address is derived from the public key.

FIDO2 / WebAuthn

The FIDO2 standard supports Ed25519 as one of the signature algorithms. Hardware keys (YubiKey 5) support Ed25519 since firmware 5.2.

Comparison Table

Notes:

• RSA verification is fast because public exponents are small (typically 65537); signing is slow because the private exponent is large.
• Ed25519 is fastest overall for both sign and verify; the next-fastest is secp256k1 (Bitcoin’s curve, which has the libsecp256k1 highly-optimized library).

Ed25519 vs Ed448

Ed448 is the larger sibling: it uses a 448-bit prime and a different curve (the Goldilocks curve), providing ~224-bit security vs. Ed25519’s ~128-bit. Ed448 is specified in RFC 8032 alongside Ed25519.

Ed448 is recommended by some standards (e.g., the IETF CFRG’s draft recommendations) but is rarely deployed. Ed25519 has won the market for “secure enough, fast, small” signatures.

Common Pitfalls

1. Using the wrong library. Many crypto libraries have multiple Ed25519 implementations; some don’t validate signatures correctly (e.g., don’t check the cofactor). Use libsodium or ed25519-dalek (Rust) which are audited.

2. Confusing Ed25519 with X25519. Ed25519 is for signatures; X25519 is for Diffie-Hellman. The curve is similar but the algorithms are different. You can’t use an Ed25519 key for X25519 directly (Signal’s XEdDSA bridges this).

3. Not validating signatures before trusting them. Some libraries silently accept malformed signatures; verify returns true even for invalid signatures if the implementation is buggy. Test with negative cases.

4. Assuming Ed25519 is quantum-safe. It is not. Quantum computers can break Ed25519 (and ECDSA, RSA, etc.) via Shor’s algorithm. For post-quantum security, use Kyber/Dilithium (NIST PQC standards, 2024).

5. Forgetting that the public key must be the same byte-for-byte for batched verification. Batch verification can only combine signatures for the same public key.

6. Storing the private key insecurely. The 32-byte seed must be kept secret. Use an HSM, OS keyring, or encrypted storage. Don’t write it to a file readable by other users.

References

• RFC 8032: Ed25519 and Ed448
• Bernstein et al., “High-speed high-security signatures” (2011) — the original paper
• Curve25519: first 10 years — D.J. Bernstein’s history
• libsodium Ed25519 documentation
• ed25519-dalek Rust library
• FIPS 186-5: ECDSA, EdDSA, RSA (2023) — EdDSA standardized
• Post-quantum cryptography standards (NIST)