Ed25519 Signatures

Ed25519 Signatures

Introduction

A digital signature proves that a message came from the owner of a private key, and that nobody changed it afterwards. Ed25519 is a widely used signature scheme. A private key is 32 bytes, a public key is 32 bytes, and a signature is 64 bytes. Signing needs no random numbers, because the nonce is derived from the key and the message by a hash.

Ed25519 is one concrete choice inside the family called EdDSA. The family is described in the EdDSA guide. This guide is about the concrete scheme, with every constant in place: the curve, the hash function, the encoding, and the checks. It follows RFC 8032, and it is verified against the test vectors of that RFC and against OpenSSL.

The curve behind Ed25519 is the twisted Edwards form of Curve25519. That is the same group that X25519 uses for key exchange, seen through a change of coordinates. Ed25519 signs, and X25519 agrees on keys. Both are built on the prime 2^255 - 19.

Table of Contents

• History and Standards
• The Curve and Its Parameters
• Keys
• Signing
• Verifying
• Why the Nonce Is Derived
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Where It Is Used
• Limitations
• Security Status
• FAQ
• References

History and Standards

EdDSA was introduced by Bernstein, Duif, Lange, Schwabe, and Yang, in the paper “High-speed high-security signatures”, which appeared in 2011. RFC 8032, by Simon Josefsson and Ilari Liusvaara, standardized it in January 2017. The RFC describes EdDSA as a variant of Schnorr’s signature system with possibly twisted Edwards curves.

The RFC lists the advantages in its introduction. EdDSA has high performance on many platforms, and it does not need a unique random number for each signature. It is more resilient to side-channel attacks, and its public keys and signatures are small: 32 and 64 bytes for Ed25519. Its formulas are complete, with no exceptions, which makes expensive validation of untrusted public values unnecessary. And it offers collision resilience, meaning that hash collisions do not break it. The RFC says this holds for the pure variant.

RFC 8032 defines three variants of Ed25519. Ed25519 is the pure scheme and has no context. Ed25519ctx adds a context string, and Ed25519ph signs a SHA-512 hash of the message instead of the message. The rest of this guide covers the pure variant, which is the one people mean by “Ed25519”.

The Curve and Its Parameters

The curve is the twisted Edwards curve -x^2 + y^2 = 1 + d*x^2*y^2 over the field with p = 2^255 - 19 elements. The RFC lists the parameters of Ed25519 in a table:

• Prime p. The prime is 2^255 - 19.
• Key and signature size. The number b is 256, so a public key has 256 bits and a signature has 512 bits.
• Hash function. The hash is SHA-512.
• Cofactor. The base-2 logarithm of the cofactor is 3, so the cofactor is 8, and secret scalars are multiples of 8.
• Scalar size. The number n is 254, so a secret scalar has 255 bits, with the top one set.
• Curve constant d. The constant is -121665 / 121666 mod p, which is 37095705934669439343138083508754565189542113879843219016388785533085940283555.
• Coefficient a. The coefficient is -1.
• Base point B. The point has y = 4/5 mod p, and its x is the root with an even last bit. Its 32-byte encoding is 5866666666666666666666666666666666666666666666666666666666666666.
• Order L. The order of the base point is 2^252 + 27742317777372353535851937790883648493.

The two key facts about the group are these. First, the curve is equivalent to Curve25519 under a change of coordinates, so the discrete logarithm problem is as hard as for X25519. The RFC says so, and I checked it: for 40 random scalars, the Edwards point maps to the same u coordinate that my X25519 code returns. Second, the addition formulas are complete. One formula adds two different points, doubles a point, and adds the neutral point (0, 1), with no special cases. RFC 8032 gives the formulas for extended coordinates (X, Y, Z, T), where x = X/Z, y = Y/Z, and x*y = T/Z.

Keys

A private key is a seed of 32 random bytes. The seed is not used as a number. It is hashed with SHA-512 into 64 bytes h, and the two halves have different jobs.

1. The first 32 bytes become the secret scalar a. They are clamped: the three lowest bits of the first byte are cleared, the highest bit of the last byte is cleared, and the second highest bit of the last byte is set. They are then read as a little-endian number. This is the same clamping as in X25519.
2. The last 32 bytes are the prefix. It stays secret, and it feeds the nonce of every signature.

The public key is the point A = a * B, which is the base point multiplied by the secret scalar. It is encoded as 32 bytes. The y coordinate is written as 255 bits in little-endian order, and the low bit of x goes into the top bit of the last byte. The sign bit is enough to tell the two x values for a given y apart.

Hashing the seed has a benefit that RFC 8032 mentions. A few missing bits of entropy in the seed do not make it a disaster, because the seed is hashed before use.

Signing

To sign a message M, the signer computes five values:

r = SHA-512(prefix || M)  mod L          the nonce
R = r * B                                the commitment, encoded as 32 bytes
k = SHA-512(R || A || M)  mod L          the challenge
S = (r + k * a)  mod L                   the response
signature = R || S                       64 bytes

The nonce r is a hash of the secret prefix and the message. The commitment R is the public half of the nonce. The challenge k is a hash that ties the signature to R, to the public key A, and to the message. The response S combines the nonce with the secret scalar, and only the owner of a can compute it. The whole signature is the 32 bytes of R followed by the 32 bytes of S, written as a little-endian number.

This is a Schnorr signature. The equation S * B = R + k * A holds, because S * B = r * B + k * a * B = R + k * A.

Verifying

To verify a signature on a message M under a public key A, the RFC says to proceed as follows.

1. Split the signature into R and S. Decode R and the public key as points. Decode S as an integer. If any decoding fails, or if S is not smaller than L, the signature is invalid.
2. Compute the challenge, which is k = SHA-512(R || A || M) mod L.
3. Check the group equation [8][S]B = [8]R + [8][k]A.

Two details deserve attention.

The range check on S. Without the check that S < L, a valid signature could be changed into a different valid one. Adding a multiple of L to S does not change S * B, because L * B is the neutral point. RFC 8032 says that Ed25519 signatures are not malleable because of this check. My code and OpenSSL both reject a signature with S + L.

The cofactor. The RFC checks the equation after multiplying all points by 8. It says that multiplying is not strictly necessary for security, and that any signature that meets the plain equation [S]B = R + [k]A also meets the multiplied one. But the two checks do not accept exactly the same signatures. A signer who adds a point of order 8 to R creates a signature that passes the multiplied equation, since 8 times that point is the neutral element, and fails the plain one. RFC 8032 section 8.8 notes that implementations may disagree about the exact set of valid signatures, and that this can open fingerprinting attacks.

I built such a signature and tried it. My code, which uses the equation of the RFC with the cofactor, accepts it. Node.js 24 with OpenSSL 3.5.8 rejects it. Both follow a valid reading of the standard. For ordinary signatures made with an honest key, they always agree.

Why the Nonce Is Derived

In classic DSA and ECDSA, each signature needs a fresh random number. If it repeats, or is predictable, or even leaks a few bits, the private key can be recovered. RFC 8032 notes that there have been numerous security failures related to random numbers.

Ed25519 removes the risk. The nonce is a hash of a secret prefix and the message. It is different for every message and unpredictable to anyone without the key, so no random number generator is involved. RFC 8032 says that EdDSA signatures are deterministic, and that this protects against attacks that arise from signing with bad randomness, which can range up to full private key compromise.

A side effect is that signing the same message twice gives the same signature, byte for byte. The tests below confirm that. The RFC notes one more point: verification is also deterministic, although some speedups for verifying many signatures at once do need random numbers.

Interactive Visualizer

The visualizer above runs this exact scheme with real keys. It has four variants. Two sign a message, with the message entered as text or as hexadecimal bytes. Two verify a signature in the same two ways. The defaults are the second test vector of RFC 8032, whose message is the single byte 72, which is the letter r.

The signing log shows the SHA-512 of the seed, the clamped secret scalar, the nonce prefix, and the public key with the number of doublings and additions that it took. It continues with the nonce r, the commitment R, the challenge k, the response S, and the signature, and it ends with a self-check of the equation. The verification log shows the range check on S, the decoding of both points, the challenge, and the two sides of the equation. Change one digit of the signature to see it fail.

A Worked Example

The second test vector of the RFC uses the seed 4ccd089b28ff96da9db6c346ec114e0f5b8a319f35aba624da8cf6ed4fb8a6fb and the one-byte message 72. These are the values that the code computes.

h = SHA-512(seed)
  = 6ebd9ed75882d52815a97585caf4790a7f6c6b3b7f821c5e259a24b02e502e114566848291dacaf225cc63deb348da318e2c2e17b00b8160f9ce6bfa0472911d
a = 512e502eb0249a255e1c827f3b6b6c7f0a79f4ca8575a91528d58258d79ebd68
prefix = 4566848291dacaf225cc63deb348da318e2c2e17b00b8160f9ce6bfa0472911d
A = 3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c

The scalar a has 255 bits, and 126 of them are set. The simple double-and-add loop used here does one doubling for each bit and one addition for each set bit, so computing A = a * B takes 255 doublings and 126 additions. The signature values follow.

r = 08332edb9e5d3ac8522a07b5a1857169a67e6509ab59af23ccdb039970ffbf8f
R = 92a009a9f0d4cab8720e820b5f642540a2b27b5416503f8fb3762223ebdb69da
k = 035ce307f6524510110b4ea1c8af0e81fb705118ebcf886912f8d2d87b5776b3
S = 085ac1e43e15996e458f3613d0f11d8c387b2eaeb4302aeeb00d291612bb0c00

The signature is R followed by S:

92a009a9f0d4cab8720e820b5f642540a2b27b5416503f8fb3762223ebdb69da085ac1e43e15996e458f3613d0f11d8c387b2eaeb4302aeeb00d291612bb0c00

For the first test vector of the RFC, the message is empty. The public key is d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a, and the signature begins with e5564300c360ac72. A signature is defined for an empty message, and nothing special is needed.

Python Implementation

This is a complete Ed25519. It has the point arithmetic, the encoding and decoding, key generation, signing, and verification.

# ed25519.py
# Ed25519 (RFC 8032): the EdDSA signature scheme on the twisted Edwards curve
#     -x^2 + y^2 = 1 + d*x^2*y^2     over GF(2^255 - 19),   d = -121665 / 121666
# Teaching code. It is not constant time. Real code must not branch on secret values.

import hashlib

P = 2 ** 255 - 19
L = 2 ** 252 + 27742317777372353535851937790883648493  # the order of the base point
COFACTOR = 8


def inverse(x):
    return pow(x, P - 2, P)


D = -121665 * inverse(121666) % P
SQRT_MINUS_ONE = pow(2, (P - 1) // 4, P)


def sha512(data):
    return hashlib.sha512(data).digest()


# ---------- points ----------
# A point (x, y) is stored as (X, Y, Z, T) with x = X/Z, y = Y/Z and x*y = T/Z.
# The formulas have no special cases, so the same code adds, doubles, and adds zero.

IDENTITY = (0, 1, 1, 0)  # the neutral point (0, 1)


def add(p1, p2):
    a = (p1[1] - p1[0]) * (p2[1] - p2[0]) % P
    b = (p1[1] + p1[0]) * (p2[1] + p2[0]) % P
    c = 2 * D * p1[3] * p2[3] % P
    d = 2 * p1[2] * p2[2] % P
    e, f, g, h = b - a, d - c, d + c, b + a
    return (e * f % P, g * h % P, f * g % P, e * h % P)


def multiply(scalar, point):
    """scalar * point by double-and-add."""
    result = IDENTITY
    while scalar:
        if scalar & 1:
            result = add(result, point)
        point = add(point, point)
        scalar >>= 1
    return result


def equal(p1, p2):
    return (p1[0] * p2[2] - p2[0] * p1[2]) % P == 0 and (p1[1] * p2[2] - p2[1] * p1[2]) % P == 0


def recover_x(y, sign):
    """The x with the given low bit that fits y on the curve, or None."""
    if y >= P:
        return None
    x2 = (y * y - 1) * inverse(D * y * y + 1) % P  # from the curve equation
    if x2 == 0:
        return None if sign else 0
    x = pow(x2, (P + 3) // 8, P)  # a candidate root, because P = 5 mod 8
    if (x * x - x2) % P:
        x = x * SQRT_MINUS_ONE % P
    if (x * x - x2) % P:
        return None  # y is not on the curve
    if (x & 1) != sign:
        x = P - x
    return x


BASE_Y = 4 * inverse(5) % P
BASE_X = recover_x(BASE_Y, 0)
BASE = (BASE_X, BASE_Y, 1, BASE_X * BASE_Y % P)


def encode(point):
    """32 bytes: y little-endian, with the low bit of x in the top bit."""
    zinv = inverse(point[2])
    x = point[0] * zinv % P
    y = point[1] * zinv % P
    return (y | ((x & 1) << 255)).to_bytes(32, "little")


def decode(data):
    """The point for 32 bytes, or None if they are not a valid point."""
    if len(data) != 32:
        return None
    value = int.from_bytes(data, "little")
    sign = value >> 255
    y = value & ((1 << 255) - 1)
    x = recover_x(y, sign)
    return None if x is None else (x, y, 1, x * y % P)


# ---------- keys, signing, verifying ----------

def hash_to_scalar(data):
    return int.from_bytes(sha512(data), "little") % L


def expand_seed(seed):
    """Hash the 32-byte seed. The first half becomes the secret scalar, the second half is the nonce prefix."""
    digest = sha512(seed)
    scalar = int.from_bytes(digest[:32], "little")
    scalar &= (1 << 254) - 8  # clear the 3 lowest bits and the top bit
    scalar |= 1 << 254        # set bit 254
    return scalar, digest[32:]


def public_key(seed):
    scalar, _ = expand_seed(seed)
    return encode(multiply(scalar, BASE))


def sign(seed, message):
    scalar, prefix = expand_seed(seed)
    public = encode(multiply(scalar, BASE))
    r = hash_to_scalar(prefix + message)          # the nonce comes from the key and the message
    r_point = encode(multiply(r, BASE))
    k = hash_to_scalar(r_point + public + message)  # the challenge
    s = (r + k * scalar) % L
    return r_point + s.to_bytes(32, "little")


def verify(public, message, signature):
    if len(public) != 32 or len(signature) != 64:
        return False
    a_point = decode(public)
    r_point = decode(signature[:32])
    if a_point is None or r_point is None:
        return False
    s = int.from_bytes(signature[32:], "little")
    if s >= L:  # a larger S would make the signature malleable
        return False
    k = hash_to_scalar(signature[:32] + public + message)
    left = multiply(COFACTOR * s, BASE)
    right = add(multiply(COFACTOR, r_point), multiply(COFACTOR * k, a_point))
    return equal(left, right)


if __name__ == "__main__":
    # The second test vector of RFC 8032, section 7.1
    seed = bytes.fromhex("4ccd089b28ff96da9db6c346ec114e0f5b8a319f35aba624da8cf6ed4fb8a6fb")
    message = bytes.fromhex("72")
    public = public_key(seed)
    signature = sign(seed, message)
    print("public key:", public.hex())
    print("signature: ", signature.hex())
    print("valid:     ", verify(public, message, signature))
    print("altered:   ", verify(public, b"s", signature))

Running it produces this output:

public key: 3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c
signature:  92a009a9f0d4cab8720e820b5f642540a2b27b5416503f8fb3762223ebdb69da085ac1e43e15996e458f3613d0f11d8c387b2eaeb4302aeeb00d291612bb0c00
valid:      True
altered:    False

I checked this code against several independent sources before writing it up. It reproduces all five test vectors of section 7.1 of RFC 8032, for the public key, the signature, and the verification, and the test code reads them from the text of the RFC. The vectors have messages of 0, 1, 2, 1023, and 64 bytes. The base point lies on the curve, equals the X(P) printed in RFC 7748, and has order L. For 40 random scalars, the point maps to the same u coordinate as my X25519 code, so the two curves behave as one group.

On 200 random keys and messages, the signatures verify and are identical when repeated. Every changed message, signature, or public key is rejected, and so is a signature with S + L. Decoding rejects y = p, an x of zero with the sign bit set, and points that are not on the curve. In Node.js, which uses OpenSSL, 500 random keys and messages give identical public keys and signatures, byte for byte, and OpenSSL accepts all of my signatures and rejects every changed message.

The visualizer’s SHA-512 is a separate implementation in JavaScript. It matches Node.js on 1523 random inputs, with every padding length at the block edges. The visualizer code matches all 620 test vectors computed by this Python code, which include valid signatures, altered ones, and malformed keys, and I ran its page in a simulated browser.

Where It Is Used

• TLS 1.3. RFC 8446 lists ed25519 and ed448 as signature algorithms, and says that they correspond to the pure algorithms and not to the prehash variants. The TLS guide covers the handshake.
• SSH. RFC 8709 describes the use of Ed25519 and Ed448 as public key algorithms in the Secure Shell protocol.
• X.509 certificates. RFC 8410 defines algorithm identifiers and encodings for Ed25519, Ed448, X25519, and X448 in the Internet X.509 public key infrastructure.

Limitations

This is a faithful teaching version of the scheme, not a production one:

• Not constant time. The code branches on the bits of secret scalars. RFC 8032 section 8.1 explains how a side-channel silent implementation avoids data-dependent branches, and it states that its own example code does not try to be one.
• No key generation. The code takes the seed as given. Real code must draw 32 bytes from a secure random source.
• Pure variant only. The code does not implement the context or prehash variants.
• One reading of the cofactor. The code uses the equation with the cofactor. Another library may use the plain equation and differ on signatures that contain small-order points.
• No batch verification. Real libraries can verify many signatures faster together, which needs random numbers.
• Messages are signed whole. RFC 8032 section 8.7 warns against signing very large amounts of data at once, because the verifier must hold the whole message and then process it twice.

Security Status

RFC 8032 says that Ed25519 is intended to operate at around the 128-bit security level. It adds that a sufficiently large quantum computer would break it, and that reasonable projections of the abilities of classical computers conclude that it is perfectly safe. In its guidance on choosing a primitive, the RFC says that if a 128-bit security level is enough, Ed25519 is recommended, and otherwise Ed448 is recommended. It also says that Ed25519ph and Ed448ph should not be used.

The scheme removes several classical pitfalls: no random nonce, no special cases in the formulas, and no malleability when the check on S is performed. What remains is the care of the implementation: constant-time arithmetic, a good source for the seed, and agreement between signer and verifier about the cofactor.

FAQ

What is the difference between EdDSA and Ed25519?

EdDSA is a family of signature schemes with parameters: the curve, the hash function, and the encodings. Ed25519 is the member of the family with Curve25519’s Edwards form and SHA-512. Ed448 is another member. The EdDSA guide explains the family.

Why does the signature contain R and not just S?

Because the verifier needs the nonce commitment to recompute the challenge k. The equation S * B = R + k * A ties S, R, k, and the public key together. The challenge hashes R, so R cannot be changed after the fact.

Can two different signatures be valid for the same message?

For an honest signer, there is only one. Ed25519 is deterministic, so the same key and message always give the same 64 bytes. Other byte strings can pass in edge cases. A signature with a larger S is rejected by the range check. A signature with a small-order component in R is the case described above, and implementations can disagree on it.

Is Ed25519 the same as the signature that Signal uses?

No, it is not. The X3DH specification of Signal calls for signatures of a related scheme, XEdDSA. That is a different construction, and this guide does not cover it.

Should I use Ed25519 or ECDSA?

Ed25519 avoids the risk of a bad nonce, and its formulas have no special cases. ECDSA is still required in places: RFC 8446 says that a compliant TLS 1.3 application must support the signature algorithm ecdsa_secp256r1_sha256. Which one to choose depends on the protocol that you work with.

Does a quantum computer break Ed25519?

Yes, it does break it. RFC 8032 says that a sufficiently large quantum computer would be able to break both Ed25519 and Ed448. Post-quantum signatures, such as the ones in the Dilithium guide, address that threat.

References

1. Josefsson, Simon, and Liusvaara, Ilari. “Edwards-Curve Digital Signature Algorithm (EdDSA).” RFC 8032, Internet Research Task Force, January 2017. Available at: https://www.rfc-editor.org/rfc/rfc8032

2. Bernstein, Duif, Lange, Schwabe, and Yang. “High-speed high-security signatures.” September 2011, DOI 10.1007/978-3-642-23951-9_9. Available at: https://ed25519.cr.yp.to/ed25519-20110926.pdf

3. Langley, Adam, Hamburg, Mike, and Turner, Sean. “Elliptic Curves for Security.” RFC 7748, January 2016. Available at: https://www.rfc-editor.org/rfc/rfc7748

4. Rescorla, Eric. “The Transport Layer Security (TLS) Protocol Version 1.3.” RFC 8446, August 2018. Available at: https://www.rfc-editor.org/rfc/rfc8446

5. Harris, Ben, and Velvindron, Logan. “Ed25519 and Ed448 Public Key Algorithms for the Secure Shell (SSH) Protocol.” RFC 8709, February 2020. Available at: https://www.rfc-editor.org/rfc/rfc8709

6. Josefsson, Simon, and Schaad, Jim. “Algorithm Identifiers for Ed25519, Ed448, X25519, and X448 for Use in the Internet X.509 Public Key Infrastructure.” RFC 8410, August 2018. Available at: https://www.rfc-editor.org/rfc/rfc8410