EdDSA

EdDSA

The Edwards-curve Digital Signature Algorithm (EdDSA) is a modern public-key signature scheme. Daniel J. Bernstein and four co-authors introduced it in 2011, building on the Schnorr signature scheme. It runs on twisted Edwards curves, a curve shape chosen for fast, simple arithmetic. The most widely deployed variant, Ed25519, is now standardized in RFC 8032.

EdDSA’s defining feature is determinism. Unlike ECDSA, it needs no random nonce at signing time. That closes off a failure mode that has leaked real private keys in the past.

Table of Contents

• Key Generation
• Signing a Message
• Verifying a Signature
• Python Implementation
• Limitations
• EdDSA vs. ECDSA vs. RSA
• Why Determinism Matters
• Real-World Applications
• FAQ
• References

Key Generation

1. A private key k is a randomly generated integer.
2. The public key A is a curve point. It’s computed as A = k * B, where B is the curve’s base point.

Signing a Message

1. Compute r, deterministically, by hashing the private key and the message: r = hash(k, M). No random number is involved.
2. Compute the curve point R = r * B.
3. Compute a hash h from R, the public key A, and the message: h = hash(R, A, M).
4. The signature is the pair (R, s), where s = r + h * k.

Verifying a Signature

Given a message M, signature (R, s), and public key A:

1. Recompute h = hash(R, A, M).
2. The signature is valid if s * B = R + h * A.

This holds because s * B = (r + hk) * B = rB + h(kB) = R + hA. The verifier confirms the relationship without ever learning k. Security rests on the Elliptic Curve Discrete Logarithm Problem: recovering k from A is computationally infeasible.

Interactive Visualizer

The visualizer above uses your browser’s real Ed25519 implementation, via the WebCrypto API. It’s not a toy stand-in. Clicking “Sign Message” generates a fresh key pair, hashes the message, and signs it.

Python Implementation

This is a genuine, complete Ed25519 implementation. It uses real curve arithmetic over the field mod 2²⁵⁵ − 19. Nonce generation, scalar clamping, and the overall structure follow the original authors’ reference design:

import hashlib

b = 256
q = 2**255 - 19
l = 2**252 + 27742317777372353535851937790883648493

def H(m):
    return hashlib.sha512(m).digest()

def inv(x):
    return pow(x, q - 2, q)

d = (-121665 * inv(121666)) % q
I = pow(2, (q - 1) // 4, q)

def xrecover(y):
    xx = (y * y - 1) * inv(d * y * y + 1)
    x = pow(xx, (q + 3) // 8, q)
    if (x * x - xx) % q != 0:
        x = (x * I) % q
    if x % 2 != 0:
        x = q - x
    return x

By = (4 * inv(5)) % q
Bx = xrecover(By)
B = (Bx % q, By % q)  # the curve's base point

def edwards(P, Q):
    x1, y1 = P; x2, y2 = Q
    x3 = (x1*y2 + x2*y1) * inv(1 + d*x1*x2*y1*y2)
    y3 = (y1*y2 + x1*x2) * inv(1 - d*x1*x2*y1*y2)
    return (x3 % q, y3 % q)

def scalarmult(P, e):
    if e == 0:
        return (0, 1)
    Q = scalarmult(P, e // 2)
    Q = edwards(Q, Q)
    if e & 1:
        Q = edwards(Q, P)
    return Q

def encodeint(y):
    bits = [(y >> i) & 1 for i in range(b)]
    return bytes(sum(bits[i*8+j] << j for j in range(8)) for i in range(b // 8))

def encodepoint(P):
    x, y = P
    bits = [(y >> i) & 1 for i in range(b - 1)] + [x & 1]
    return bytes(sum(bits[i*8+j] << j for j in range(8)) for i in range(b // 8))

def bit(h, i):
    return (h[i // 8] >> (i % 8)) & 1

def clamped_scalar(h):
    """The clamping that makes every private scalar a multiple of the curve's cofactor."""
    return 2**(b - 2) + sum(2**i * bit(h, i) for i in range(3, b - 2))

def public_key(sk):
    a = clamped_scalar(H(sk))
    return encodepoint(scalarmult(B, a))

def Hint(m):
    h = H(m)
    return sum(2**i * bit(h, i) for i in range(2 * b))

def sign(m, sk, pk):
    h = H(sk)
    a = clamped_scalar(h)
    r = Hint(h[b // 8: b // 4] + m)          # deterministic nonce: no RNG needed
    R = scalarmult(B, r)
    S = (r + Hint(encodepoint(R) + pk + m) * a) % l
    return encodepoint(R) + encodeint(S)

def isoncurve(P):
    x, y = P
    return (-x*x + y*y - 1 - d*x*x*y*y) % q == 0

def decodeint(s):
    return sum(2**i * bit(s, i) for i in range(b))

def decodepoint(s):
    y = sum(2**i * bit(s, i) for i in range(b - 1))
    x = xrecover(y)
    if x & 1 != bit(s, b - 1):
        x = q - x
    P = (x, y)
    if not isoncurve(P):
        raise ValueError("decoding point that is not on curve")
    return P

def verify(sig, m, pk):
    if len(sig) != b // 4 or len(pk) != b // 8:
        return False
    R = decodepoint(sig[0:b // 8])
    A = decodepoint(pk)
    S = decodeint(sig[b // 8: b // 4])
    h = Hint(encodepoint(R) + pk + m)
    return scalarmult(B, S) == edwards(R, scalarmult(A, h))

if __name__ == "__main__":
    sk = bytes.fromhex("9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60")
    pk = public_key(sk)
    sig = sign(b"", sk, pk)

    print(f"Public key: {pk.hex()}")
    print(f"Signature:  {sig.hex()}")
    print(f"Verifies:   {verify(sig, b'', pk)}")
    print(f"Tampered:   {verify(sig, b'x', pk)}")

This reproduces RFC 8032’s official Ed25519 test vector 1, for the empty message:

• Public key: d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a
• Signature: e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e065224901555fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b

I cross-checked this against pycryptodome’s own Ed25519 before writing it up. The two agree byte-for-byte on both the public key and the signature.

Limitations

This is a genuine, complete implementation of real Ed25519, not a simplified stand-in. It’s still a teaching artifact:

• Not constant-time. Real implementations use constant-time arithmetic to resist timing side-channels, one of EdDSA’s key selling points. This code’s scalarmult gives no such guarantee.
• Recursive scalarmult. Python’s stack depth isn’t a practical problem for 256-bit scalars. Production code would still use an iterative double-and-add loop instead.
• No batch verification. Some applications verify many signatures at once, far faster, using batch techniques. This code only verifies one at a time.
• Never use this in production. Real applications should use a vetted library’s Ed25519 implementation, like Python’s own cryptography package or pycryptodome.

EdDSA vs. ECDSA vs. RSA

Feature	EdDSA	ECDSA	RSA
Underlying math	Twisted Edwards curves	Elliptic curve cryptography	Integer factorization
Key size	256-bit (Ed25519)	256-bit (typical)	2048+ bit
Signature size	64 bytes (Ed25519)	~70 bytes (P-256)	256 bytes (RSA-2048)
Nonce	Deterministic	Random, per signature	Not applicable
Failure mode on bad nonce	None; no nonce needed	Full key compromise if nonce reused	Not applicable

Why Determinism Matters

ECDSA needs a fresh, secret random number for every single signature. Reuse that nonce once, even partially, and simple algebra recovers the private key. This isn’t theoretical. It’s how the 2010 Sony PlayStation 3 signing key was extracted, among other real-world breaks.

EdDSA sidesteps the problem entirely. It derives its per-signature nonce by hashing the private key and the message. The same input always produces the same signature. There’s no random number to leak or reuse.

EdDSA’s curve arithmetic is also “complete.” Its formulas work for every point on the curve, with no special cases to handle. ECDSA implementations have shipped real vulnerabilities from mishandling exactly these edge cases.

Real-World Applications

• TLS and SSH, both of which support Ed25519 as a modern signature option.
• Cryptocurrencies and blockchain systems, many of which use EdDSA for transaction signing.
• Software and firmware signing, where its speed and small signature size help.
• Secure messaging apps, which use it to authenticate encrypted communications.

FAQ

What are the main variants of EdDSA?

Ed25519 and Ed448 are the two standardized variants. Ed25519 offers roughly 128-bit security; Ed448 offers roughly 224-bit security.

Is EdDSA resistant to quantum computers?

No. EdDSA relies on hardness assumptions, like RSA and ECDSA. Shor’s algorithm breaks all three on a large quantum computer.

Is EdDSA faster than ECDSA?

For popular curves, EdDSA is generally somewhat faster, particularly at verification. Exact numbers depend on the implementation and platform.

Why did it take until 2011 for something this simple to appear?

Schnorr’s patent kept the underlying idea out of open standards for two decades. The Schnorr signatures guide covers that history. EdDSA arrived only after the patent expired.

References

1. Bernstein, D. J., Duif, N., Lange, T., Schwabe, P., & Yang, B-Y. (2011). “High-speed high-security signatures.” Journal of Cryptographic Engineering.
2. RFC 8032: “Edwards-Curve Digital Signature Algorithm (EdDSA).” datatracker.ietf.org/doc/html/rfc8032
3. Wikipedia. “EdDSA.” en.wikipedia.org/wiki/EdDSA
4. PyCryptodome documentation. “EdDSA.” pycryptodome.readthedocs.io