ed25519-ssh.ipynb

Kernel: SageMath 10.0

Connect: Ed25519 in SSH

Module 06 | Real-World Connections

When you run ssh-keygen -t ed25519, you generate a key pair on a twisted Edwards curve. EdDSA is deterministic by design, immune to the nonce-reuse attack that broke the PS3.

Introduction

Ed25519 is the recommended algorithm for SSH keys. It is an instance of EdDSA (Edwards-curve Digital Signature Algorithm) on the twisted Edwards curve Edwards25519, which is birationally equivalent to Curve25519.

$ ssh-keygen -t ed25519
Generating public/private ed25519 key pair.
Your identification has been saved in ~/.ssh/id_ed25519
Your public key has been saved in ~/.ssh/id_ed25519.pub

What makes EdDSA special compared to ECDSA?

• Deterministic: No random nonce is needed. The nonce is derived from the message and private key.

• Fast: Complete addition formulas with no edge cases.

• Immune to nonce-reuse: The PS3 attack (Break notebook) is impossible by construction.

Edwards Curves: A Different Form

A twisted Edwards curve has the equation:

$$ax^2 + y^2 = 1 + dx^2y^2$$

For Ed25519: $a = -1$, so the curve is $-x^2 + y^2 = 1 + dx^2y^2$ over $\mathbb{F}_p$ with $p = 2^{255} - 19$.

This is a different form of elliptic curve (not Weierstrass, not Montgomery), but it is still an elliptic curve with the same group structure. There is an explicit birational equivalence between Edwards25519 and Curve25519.

The Edwards form has a remarkable property: the addition law is complete, meaning the same formula works for all inputs (no special cases for doubling, adding inverses, or the identity). This simplifies implementation and side-channel protection.

# === A small twisted Edwards curve for demonstration ===
# We work over F_1009 with a = -1 (twisted Edwards)
# -x^2 + y^2 = 1 + d*x^2*y^2
p_ed = 1009
F_ed = GF(p_ed)

# Choose d such that the curve is non-singular
# d must not be 0 or 1, and a*d must not be a square (for completeness)
a_ed = F_ed(-1)
d_ed = F_ed(100)  # chosen so a*d = -100 is not a square mod 1009

print(f"Twisted Edwards curve: -x^2 + y^2 = 1 + {Integer(d_ed)}*x^2*y^2  over F_{p_ed}")
print(f"a = {Integer(a_ed)}, d = {Integer(d_ed)}")
print(f"a*d = {Integer(a_ed * d_ed)}")
print(f"a*d is a square? {kronecker(Integer(a_ed * d_ed), p_ed) == 1}")
print(f"(For complete addition formulas, we need a*d to be a non-square.)")

# === Edwards curve point operations ===

def edwards_add(P, Q, a, d, p):
    """Add two points on a twisted Edwards curve.
    P, Q are tuples (x, y).
    Curve: a*x^2 + y^2 = 1 + d*x^2*y^2
    
    The UNIFIED addition formula (works for all cases including doubling!):
    x3 = (x1*y2 + y1*x2) / (1 + d*x1*x2*y1*y2)
    y3 = (y1*y2 - a*x1*x2) / (1 - d*x1*x2*y1*y2)
    """
    F = GF(p)
    x1, y1 = F(P[0]), F(P[1])
    x2, y2 = F(Q[0]), F(Q[1])
    
    denom_common = F(d) * x1 * x2 * y1 * y2
    x3 = (x1 * y2 + y1 * x2) / (1 + denom_common)
    y3 = (y1 * y2 - F(a) * x1 * x2) / (1 - denom_common)
    return (Integer(x3), Integer(y3))

def edwards_scalar_mul(k, P, a, d, p):
    """Scalar multiplication on a twisted Edwards curve (double-and-add)."""
    identity = (0, 1)  # The neutral element on Edwards curves
    result = identity
    base = P
    k = Integer(k)
    while k > 0:
        if k % 2 == 1:
            result = edwards_add(result, base, a, d, p)
        base = edwards_add(base, base, a, d, p)
        k //= 2
    return result

def on_edwards_curve(P, a, d, p):
    """Check if a point lies on the twisted Edwards curve."""
    F = GF(p)
    x, y = F(P[0]), F(P[1])
    return F(a) * x^2 + y^2 == 1 + F(d) * x^2 * y^2

# Find points on our Edwards curve
edwards_points = []
for x in range(p_ed):
    for y in range(p_ed):
        if on_edwards_curve((x, y), a_ed, d_ed, p_ed):
            edwards_points.append((x, y))

print(f"Number of points on the Edwards curve: {len(edwards_points)}")
print(f"Identity element: (0, 1)")
print(f"Is (0, 1) on curve? {on_edwards_curve((0, 1), a_ed, d_ed, p_ed)}")

# Test addition: P + identity = P
P_test = edwards_points[5]
P_plus_id = edwards_add(P_test, (0, 1), Integer(a_ed), Integer(d_ed), p_ed)
print(f"\nP = {P_test}")
print(f"P + (0,1) = {P_plus_id}")
print(f"P + identity = P? {P_plus_id == P_test}")

# Find a generator of large order
# Test points until we find one with large order
def edwards_point_order(P, a, d, p, max_order):
    """Compute the order of a point on an Edwards curve."""
    identity = (0, 1)
    current = P
    for i in range(1, max_order + 1):
        if current == identity:
            return i
        current = edwards_add(current, P, a, d, p)
    return None

# Find a point with large prime order
num_points = len(edwards_points)
G_ed = None
G_ed_order = 0
for P_cand in edwards_points[1:20]:  # skip identity
    ord_P = edwards_point_order(P_cand, Integer(a_ed), Integer(d_ed), p_ed, num_points + 1)
    if ord_P is not None and ord_P > G_ed_order:
        G_ed = P_cand
        G_ed_order = ord_P

print(f"Generator G = {G_ed}")
print(f"Order of G = {G_ed_order}")
print(f"Order is prime? {is_prime(G_ed_order)}")
print(f"Cofactor = {num_points // G_ed_order}")

EdDSA: Deterministic Signatures

EdDSA signing differs from ECDSA in a crucial way: the nonce $k$ is deterministic.

ECDSA: $k$ is random. Reuse $\Rightarrow$ catastrophe (PS3 hack).

EdDSA: $k = H(\text{prefix} \| m)$ where prefix is derived from the private key. Same $(\text{key}, \text{message})$ always produces the same $k$, but different messages produce different $k$ values.

The signing algorithm:

1. Private key: seed $s$ (32 bytes). Compute $H(s) = (a \| \text{prefix})$. The scalar $a$ is the actual private key; the prefix is used for nonce generation.

2. Public key: $A = aG$.

3. Nonce: $r = H(\text{prefix} \| m)$ (deterministic!).

4. Nonce point: $R = rG$.

5. Challenge: $k = H(R \| A \| m)$.

6. Signature response: $S = r + k \cdot a \pmod{n}$.

7. Signature: $(R, S)$.

Verification: check $SG = R + kA$ where $k = H(R \| A \| m)$.

# === Simplified EdDSA on our small Edwards curve ===
import hashlib

n_ed = G_ed_order  # order of our generator

def simple_hash(*args):
    """Simple hash function for our toy example."""
    data = ":".join(str(a) for a in args).encode()
    return int(hashlib.sha256(data).hexdigest(), 16)

# Key generation
seed = 12345  # In real Ed25519, this is 32 random bytes
# Derive private scalar and prefix from seed
h_seed = simple_hash("keygen", seed)
a_priv = (h_seed % (n_ed - 1)) + 1  # private scalar
prefix = simple_hash("prefix", seed)  # nonce-generation prefix

# Public key
A_pub = edwards_scalar_mul(a_priv, G_ed, Integer(a_ed), Integer(d_ed), p_ed)

print(f"=== EdDSA Key Generation ===")
print(f"Seed: {seed}")
print(f"Private scalar a = {a_priv}")
print(f"Public key A = aG = {A_pub}")
print(f"On curve? {on_edwards_curve(A_pub, a_ed, d_ed, p_ed)}")

# === EdDSA Signing ===
def eddsa_sign(message, a_priv, prefix, A_pub, G, a_curve, d_curve, p, n):
    """Simplified EdDSA signing."""
    # Step 1: Deterministic nonce (THIS IS THE KEY DIFFERENCE FROM ECDSA)
    r = simple_hash("nonce", prefix, message) % n
    if r == 0:
        r = 1
    
    # Step 2: Nonce point
    R = edwards_scalar_mul(r, G, a_curve, d_curve, p)
    
    # Step 3: Challenge
    k = simple_hash("challenge", R[0], R[1], A_pub[0], A_pub[1], message) % n
    
    # Step 4: Response
    S = (r + k * a_priv) % n
    
    return (R, S)

def eddsa_verify(message, sig, A_pub, G, a_curve, d_curve, p, n):
    """Simplified EdDSA verification.
    Check: S*G == R + k*A
    """
    R, S = sig
    
    # Recompute challenge
    k = simple_hash("challenge", R[0], R[1], A_pub[0], A_pub[1], message) % n
    
    # Left side: S * G
    lhs = edwards_scalar_mul(S, G, a_curve, d_curve, p)
    
    # Right side: R + k * A
    kA = edwards_scalar_mul(k, A_pub, a_curve, d_curve, p)
    rhs = edwards_add(R, kA, a_curve, d_curve, p)
    
    return lhs == rhs

# Sign a message
msg = "SSH session authentication"
sig = eddsa_sign(msg, a_priv, prefix, A_pub, G_ed,
                 Integer(a_ed), Integer(d_ed), p_ed, n_ed)
R_sig, S_sig = sig

print(f"Message: '{msg}'")
print(f"\n=== EdDSA Signature ===")
print(f"R = {R_sig} (nonce point)")
print(f"S = {S_sig} (response scalar)")

# Verify
valid = eddsa_verify(msg, sig, A_pub, G_ed,
                     Integer(a_ed), Integer(d_ed), p_ed, n_ed)
print(f"\nVerification: S*G == R + k*A? {valid}")

# === The key property: deterministic signatures ===
# Signing the same message twice produces the SAME signature
sig1 = eddsa_sign(msg, a_priv, prefix, A_pub, G_ed,
                  Integer(a_ed), Integer(d_ed), p_ed, n_ed)
sig2 = eddsa_sign(msg, a_priv, prefix, A_pub, G_ed,
                  Integer(a_ed), Integer(d_ed), p_ed, n_ed)

print("=== Deterministic Signatures ===")
print(f"Sig 1: R={sig1[0]}, S={sig1[1]}")
print(f"Sig 2: R={sig2[0]}, S={sig2[1]}")
print(f"Same? {sig1 == sig2}")
print(f"\nThis is BY DESIGN. In ECDSA, signing the same message twice")
print(f"would produce DIFFERENT signatures (random nonce each time).")
print(f"\nConsequence: nonce reuse is IMPOSSIBLE in EdDSA.")
print(f"The PS3 hack CANNOT happen with Ed25519.")

# Different messages produce different signatures
msg2 = "Different SSH session"
sig3 = eddsa_sign(msg2, a_priv, prefix, A_pub, G_ed,
                  Integer(a_ed), Integer(d_ed), p_ed, n_ed)
print(f"\nSig for different message: R={sig3[0]}, S={sig3[1]}")
print(f"Different from original? {sig3 != sig1}")

# Tampered message fails verification
valid_tampered = eddsa_verify("Tampered SSH session", sig, A_pub, G_ed,
                              Integer(a_ed), Integer(d_ed), p_ed, n_ed)
print(f"\nTampered message valid? {valid_tampered}")

Ed25519 vs ECDSA: Side-by-Side

Property	ECDSA (secp256k1/P-256)	EdDSA (Ed25519)
Curve form	Weierstrass: $y^2 = x^3 + ax + b$	Twisted Edwards: $-x^2 + y^2 = 1 + dx^2y^2$
Nonce	Random (or RFC 6979)	Deterministic: $r = H(\text{prefix} | m)$
Nonce reuse	Catastrophic (PS3 hack)	Impossible by construction
Addition formula	Different cases for add/double	Unified (complete) formula
Side-channel resistance	Implementation-dependent	Easier by design
Signature size	64 bytes	64 bytes
Key size	32 bytes private, 33/65 bytes public	32 bytes private, 32 bytes public
Speed	Moderate	Fast
Used in	Bitcoin, Ethereum, TLS	SSH, Signal, Tor, TLS

Concept Map: Module 06 Concepts in SSH/Ed25519

Module 06 Concept	Ed25519 / SSH Application
Point addition	Edwards unified addition formula
Scalar multiplication $aG$	Key generation: public key $A = aG$
ECDLP hardness	Cannot recover private key from public key
Nonce-reuse vulnerability (Break)	Deterministic nonce eliminates the risk
Curve arithmetic	EdDSA sign: $S = r + ka$, verify: $SG = R + kA$
Curve form choice	Edwards form enables complete, constant-time formulas

Summary

Concept	Key idea
Edwards25519	A twisted Edwards curve $-x^2 + y^2 = 1 + dx^2y^2$ over $\mathbb{F}_{2^{255}-19}$, birationally equivalent to Curve25519.
Deterministic nonce	EdDSA computes $r = H(\text{prefix} | m)$ from the private key and message, making nonce reuse impossible by construction.
Complete addition formula	The Edwards addition law has no edge cases, which simplifies constant-time implementation.
EdDSA verification	The verifier checks $SG = R + kA$ where $k = H(R | A | m)$, binding the signature to both the message and public key.
Compact representation	Signatures are 64 bytes, keys are 32 bytes, and signing/verification is fast.
Lesson from ECDSA	Instead of relying on implementers to generate good nonces, Ed25519 eliminates the vulnerability at the design level.

Ed25519 represents the lessons learned from ECDSA's operational fragility: instead of relying on implementers to generate good nonces, the protocol eliminates the vulnerability at the design level.

---

Back to Module 06: Elliptic Curves