Ed25519, in depth: the curve, clamping, deterministic Schnorr signing, verification edge cases and the mistakes that leak keys

The curve and its group

Ed25519 works in the group of points on a twisted Edwards curve, -x^2 + y^2 = 1 + d*x^2*y^2, over the prime field of integers modulo p = 2^255 - 19, with d = -121665/121666 mod p. It is birationally equivalent to Curve25519, the Montgomery curve used by X25519 key exchange, which is why the two share a name and a field.

Three facts about this group drive everything below. First, its size is 8 * L, where L = 2^252 + 27742317777372353535851937790883648493 is prime. The factor 8 is the cofactor. The base point B generates the subgroup of order L, which is where all honest keys and signatures live; the other components are small-order points of order dividing 8, and they are the source of most verification subtleties.

Second, the Edwards addition formula is complete: the same formula adds any two points, including a point to itself and the identity (0, 1). Weierstrass curves such as P-256 need separate doubling code and special cases for the point at infinity, and every branch is a chance for a timing leak or a bug. With Edwards curves, a constant-time scalar multiplication is a loop of identical operations.

Third, a point is encoded in 32 bytes: the y coordinate as a little-endian 255-bit integer, with the low bit of x stored in the top bit. Decoding recovers x by solving the curve equation, a square root mod p, and must reject y values that are not below p and x values that have no square root.

Scalar multiplication, [n]P, is repeated addition done by double-and-add; it is the same building block that modular exponentiation uses with multiplication in place of point addition, and its cost dominates both signing and verification.

Keys and clamping

The private key is 32 random bytes, the seed. Everything else is derived from it:

1. Compute h = SHA-512(seed), 64 bytes.
2. Take the low 32 bytes as a little-endian integer and clamp it: clear the lowest three bits, clear bit 255 and set bit 254. The result is the secret scalar s.
3. Keep the high 32 bytes as the prefix, a secret used only to derive nonces.
4. The public key is A = [s]B, encoded in 32 bytes.

Clamping is often presented as magic. Clearing the low three bits makes s a multiple of 8, so multiplying any point by s wipes out a small-order component; that property matters for X25519 and for the cofactored verification equation. Setting bit 254 fixes the position of the top bit, which historically let Montgomery-ladder implementations run a fixed number of iterations. Neither step reduces security meaningfully: the scalar keeps about 251 bits of entropy and the scheme targets roughly 128-bit security.

Signing and verification

To sign a message M:

1. Compute the nonce r = SHA-512(prefix || M) mod L.
2. Compute R = [r]B and encode it.
3. Compute the challenge k = SHA-512(R || A || M) mod L.
4. Compute S = (r + k*s) mod L. The signature is the 32 bytes of R followed by the 32 little-endian bytes of S.

Verification recomputes k from the signature's R, the public key and the message, then checks [S]B = R + [k]A. It holds for an honest signature because [S]B = [r + k*s]B = [r]B + [k]([s]B) = R + [k]A. This is a Schnorr signature: a commitment R, a challenge bound to the commitment and the message by a hash, and a response that only someone who knows s can compute.

Two design choices separate it from ECDSA. The nonce r is derived from a secret and the message, so a bad or reused nonce cannot leak the key, the failure that exposed the PlayStation 3 signing key. And hashing A into k binds each signature to one public key.

A reference implementation

The code below is a complete Ed25519 in about forty lines of Python, using extended coordinates (X, Y, Z, T) so that addition needs no inversions. It is for learning only: the scalar multiplication branches on secret bits and Python integers are not constant time.

import hashlib
p = 2**255 - 19
L = 2**252 + 27742317777372353535851937790883648493
d = -121665 * pow(121666, -1, p) % p
SQRT_M1 = pow(2, (p - 1) // 4, p)
H = lambda m: hashlib.sha512(m).digest()

def add(P, Q):                       # complete twisted Edwards addition
    A = (P[1] - P[0]) * (Q[1] - Q[0]) % p
    B = (P[1] + P[0]) * (Q[1] + Q[0]) % p
    C = 2 * P[3] * Q[3] * d % p
    D = 2 * P[2] * Q[2] % p
    E, F, G, K = B - A, D - C, D + C, B + A
    return (E * F % p, G * K % p, F * G % p, E * K % p)

def mul(n, P):                       # double-and-add; NOT constant time
    Q = (0, 1, 1, 0)
    while n:
        if n & 1: Q = add(Q, P)
        P, n = add(P, P), n >> 1
    return Q

def encode(P):
    zi = pow(P[2], p - 2, p)
    x, y = P[0] * zi % p, P[1] * zi % p
    return (y | (x & 1) << 255).to_bytes(32, "little")

def decode(b):
    y = int.from_bytes(b, "little"); sign = y >> 255; y &= (1 << 255) - 1
    if y >= p: return None
    x2 = (y * y - 1) * pow(d * y * y + 1, p - 2, p) % p
    x = pow(x2, (p + 3) // 8, p)
    if (x * x - x2) % p: x = x * SQRT_M1 % p
    if (x * x - x2) % p or (x == 0 and sign): return None
    if x & 1 != sign: x = p - x
    return (x, y, 1, x * y % p)

B = decode((4 * pow(5, p - 2, p)).to_bytes(32, "little"))

def expand(seed):
    h = H(seed)
    s = int.from_bytes(h[:32], "little") & ((1 << 254) - 8) | (1 << 254)
    return s, h[32:]

def sign(seed, msg):
    s, prefix = expand(seed)
    A = encode(mul(s, B))
    r = int.from_bytes(H(prefix + msg), "little") % L
    R = encode(mul(r, B))
    k = int.from_bytes(H(R + A + msg), "little") % L
    return R + ((r + k * s) % L).to_bytes(32, "little")

def verify(A_bytes, msg, sig):
    A, R = decode(A_bytes), decode(sig[:32])
    S = int.from_bytes(sig[32:], "little")
    if len(sig) != 64 or A is None or R is None or S >= L:
        return False
    k = int.from_bytes(H(sig[:32] + A_bytes + msg), "little") % L
    lhs, rhs = mul(8 * S, B), mul(8, add(R, mul(k, A)))
    return (lhs[0] * rhs[2] - rhs[0] * lhs[2]) % p == 0 and \
           (lhs[1] * rhs[2] - rhs[1] * lhs[2]) % p == 0

Worked example: the RFC test vector and a forgery attempt

RFC 8032 section 7.1 publishes test vectors, and the first one signs the empty message. Its seed is 9d61b19d...1cae7f60. Feeding the full seed through expand and mul above produces the public key d75a9801...f707511a, and sign(seed, b"") produces a signature beginning e5564300c360ac72 and ending 438e7a100b, byte for byte the values in the RFC. Signing again gives the identical 64 bytes, because nothing random is involved.

Now tamper. Verifying the same signature against the message b"x" fails, because k changes. More instructively, take the signature's S, add L, and re-encode it. Mathematically [S + L]B = [S]B, so the group equation still holds; the only thing that rejects the forgery is the explicit S >= L check. Delete that line and you have signature malleability: an attacker can produce a second valid signature for a message without the key, which breaks any system that uses signature bytes as a unique identifier, as Bitcoin's transaction IDs once did with ECDSA.

In production, use a maintained library. In Python that is the cryptography package:

from cryptography.hazmat.primitives.asymmetric.ed25519 import (
    Ed25519PrivateKey, Ed25519PublicKey)
from cryptography.exceptions import InvalidSignature

sk = Ed25519PrivateKey.generate()
pk_bytes = sk.public_key().public_bytes_raw()        # 32 bytes to publish
sig = sk.sign(b"release v1.4.2 sha256=...")          # 64 bytes

try:
    Ed25519PublicKey.from_public_bytes(pk_bytes).verify(sig, b"release v1.4.2 sha256=...")
except InvalidSignature:
    raise SystemExit("reject: bad signature")

What a verifier must check

RFC 8032 requires the verifier to reject S that is not below L and to reject points that do not decode. It then says the cofactored check [8][S]B = [8]R + [8][k]A is sufficient, and that it is also allowed to check the cofactorless [S]B = R + [k]A instead. Those two equations agree on every honestly generated signature. They disagree when R or A carries a small-order component, which an attacker can arrange deliberately.

The consequence is that two correct, RFC-compliant libraries can disagree on whether a particular signature is valid. A 2020 study, Taming the Many EdDSAs by Chalkias, Garillot and Nikolaenko, tested a range of popular implementations and found them split on exactly these cases, plus non-canonical point encodings. For most applications that is harmless, because an honest signer never produces such signatures. For consensus systems, where every node must reach the same verdict, it is a chain split waiting to happen; Zcash's ZIP-215 exists to pin down one exact set of rules for that reason.

Batch verification sharpens the problem. Checking n signatures at once with a random linear combination is much faster than n separate checks, but the batch equation behaves like the cofactored check. A library that verifies singly with the cofactorless equation and in batches with the cofactored one can accept a batch containing a signature it would reject alone. If you need batches, use the cofactored equation everywhere.

• Reject wrong lengths and S >= L. The S check is mandatory.
• Decide whether to reject non-canonical encodings of R and A, and small-order A. Rejecting small-order public keys at registration time removes a class of trivial signatures.
• If verdicts must match across nodes or languages, write the rule set down and test every implementation against the same edge-case vectors.

Failure modes

• The double public key oracle. Some APIs take the private key and the public key as separate arguments to sign. If a caller can supply a wrong A, the signer computes the same r for the same message but a different k, and two signatures S1 = r + k1*s and S2 = r + k2*s give s = (S1 - S2)/(k1 - k2) mod L. This was disclosed across many libraries in 2022. Derive A from the seed inside sign, or check it matches.
• Fault attacks. Deterministic signing means a glitch during the computation of S, induced by voltage or clock faults on a device, can produce a faulty and a correct signature with the same r, leaking s by similar algebra. Hardware signers verify their own output before releasing it, or mix fresh randomness into r (hedged signing).
• Non-constant-time arithmetic. Code like the reference above leaks bits of s through timing. Real implementations use fixed-window or ladder multiplication with table lookups that do not depend on secret indices.
• Prehash confusion. Ed25519ph signs a SHA-512 digest of the message, with domain separation, and its signatures do not verify as plain Ed25519. Pick one per protocol.
• Key format mix-ups. Libraries store a 32-byte seed, a 64-byte seed plus public key (Go's ed25519.PrivateKey), or the expanded scalar. Import with the library's explicit raw or PKCS#8 functions.

Trade-offs

Ed25519 is the default for new protocol designs that control both ends. Choose ECDSA when hardware or a compliance profile requires P-256. No classical scheme resists a large quantum computer, so long-lived keys need a hybrid or ML-DSA plan. For integrity of many objects under one signature, sign the root of a Merkle tree rather than each object.

What to do next

1. Run the reference code against the RFC 8032 section 7.1 vectors, then delete it and use a maintained library.
2. Audit every sign call site: the public key must come from the private key, never from caller input.
3. Confirm your verifier rejects S >= L by feeding it the S + L tampered signature.
4. If verdicts must agree across services or languages, choose cofactored or cofactorless verification explicitly and add edge-case vectors to CI.
5. Standardise one key storage format and one variant (pure Ed25519 or Ed25519ph) per protocol.
6. For long-lived signing keys, write down a migration path to a hybrid or ML-DSA scheme.