Chapter 20 — Elliptic curve cryptography

In one sentence

Elliptic-curve cryptography gives the same security as RSA with far smaller keys and faster operations, by replacing "multiply big primes" with arithmetic on points of a curve.

Why bother — the size argument

   Security level     RSA / finite-field DH      Elliptic curve
   --------------     ---------------------      --------------
      ~80 bits              1024-bit                  160-bit
     ~112 bits              2048-bit                  224-bit
     ~128 bits              3072-bit                  256-bit      <- the sweet spot
     ~192 bits              7680-bit                  384-bit
     ~256 bits             15360-bit                  512-bit

A 256-bit ECC key matches a 3072-bit RSA key. Smaller keys mean smaller certificates, less bandwidth in every handshake, less storage on constrained devices, and much faster key generation and signing. On the modern web, most new certificates and virtually all key exchange are elliptic-curve.

The idea in plain language

An elliptic curve is the set of points satisfying an equation like y^2 = x^3 + ax + b. There's a way to "add" two points on the curve to get a third point on the curve (draw a line through them; where it hits the curve again, reflect over the x-axis).

   "Adding" a point P to itself k times is called SCALAR MULTIPLICATION:  k*P

   FORWARD:   given k and P, computing Q = k*P is fast.
   REVERSE:   given P and Q, finding k is the ELLIPTIC-CURVE DISCRETE
              LOGARITHM PROBLEM (ECDLP) -- and the best known attack is
              roughly the square root of the group size, nothing better.

   That "nothing better" is why ECC keys can be small: no sub-exponential
   factoring-style shortcut is known, unlike RSA and finite-field DH.

Your private key is the scalar k (a random ~256-bit number). Your public key is the point Q = k*P, where P is a fixed base point in the curve's published parameters.

The curves you'll actually meet

Curve	Also called	Use	Notes
P-256	secp256r1, prime256v1	ECDSA signatures, ECDH	NIST curve; ubiquitous in TLS certs
P-384	secp384r1	Higher-security ECDSA/ECDH	NSA "CNSA" suite
Curve25519	via X25519 (ECDH), Ed25519 (signatures)	Modern default	Designed by Bernstein; fast, misuse-resistant, no parameter mystery
Curve448	X448 / Ed448	Higher-security modern	Less common
secp256k1	—	Bitcoin, Ethereum	Rare outside blockchain

   For NEW systems, the simple advice:
     Key exchange  -> X25519      (fall back to P-256 for compatibility)
     Signatures    -> Ed25519     (fall back to ECDSA P-256)

Why prefer 25519 over the NIST P-curves? The NIST curves have unexplained "random" constants, which fed (largely unproven) worry after the Dual_EC_DRBG backdoor. More concretely, the P-curves are hard to implement in constant time and have sharp edges (point validation, the k in ECDSA). Curve25519 was engineered so the safe implementation is the natural one.

ECDH — elliptic-curve Diffie–Hellman

Exactly the Chapter 18 protocol, with scalar multiplication instead of modular exponentiation:

   Alice: private a, public A = a*P
   Bob:   private b, public B = b*P
   Shared: a*B = a*(b*P) = b*(a*P) = b*A       -> same point, both sides

Ephemeral ECDH is ECDHE — the key exchange in every modern TLS and SSH session, providing the forward secrecy from Chapter 18.

ECDSA — and its one deadly footgun

ECDSA (the elliptic-curve signature algorithm) requires a random per-signature value k (a "nonce", confusingly — nothing to do with AEAD nonces).

   +--------------------------------------------------------------+
   |  If k is EVER reused for two different messages, OR if k is   |
   |  even slightly predictable, THE PRIVATE KEY CAN BE COMPUTED    |
   |  with simple algebra from the two signatures.                 |
   +--------------------------------------------------------------+

   Real incidents:
     * Sony PlayStation 3 (2010) -- Sony used a FIXED k. The ECDSA
       code-signing key was extracted. Total, permanent compromise.
     * Numerous Bitcoin wallet thefts from bad RNGs producing repeated k.
     * Android SecureRandom bug (2013) drained Bitcoin wallets.

The fix: deterministic ECDSA (RFC 6979) derives k from the private key and the message hash via HMAC, so it's unique and unpredictable without needing a good RNG at signing time. Use a library that does this. Or — better — use Ed25519, which is deterministic by construction and has no k to leak.

Ed25519 — the one to reach for

   + Deterministic       -> no RNG-at-signing footgun, no k reuse possible
   + Fast                 -> ~15,000+ sign/verify per second, easily
   + Small               -> 32-byte public key, 64-byte signature
   + Misuse-resistant     -> no parameter choices, no point-validation traps
   + Built-in hashing     -> you sign the message directly, not a pre-hash

   Used by: OpenSSH (default keytype since 2014), Signal, WireGuard, age,
            Tor, TLS 1.3 (Ed25519 certs), most Linux package signing,
            most modern language stdlibs.

Worked example (run it)

cd ~/sec-lab/scratch

# --- Ed25519 with OpenSSL 3.x (works even on LibreSSL for Ed25519 gen/sign) ---
openssl genpkey -algorithm ed25519 -out ed.pem
openssl pkey -in ed.pem -pubout -out ed.pub
wc -c ed.pem ed.pub                       # tiny compared to RSA

echo "ship release v2.1.0" > release.txt
openssl pkeyutl -sign   -inkey ed.pem  -rawin -in release.txt -out release.sig
openssl pkeyutl -verify -pubin -inkey ed.pub -rawin -in release.txt \
        -sigfile release.sig              # -> "Signature Verified Successfully"

# tamper
echo "ship release v2.1.0 (backdoored)" > release.txt
openssl pkeyutl -verify -pubin -inkey ed.pub -rawin -in release.txt \
        -sigfile release.sig              # -> verification fails

# --- the k-reuse catastrophe, demonstrated ---
.venv/bin/python - <<'PY'
# Toy ECDSA over a small curve to show: reuse k -> recover the private key.
# Curve: y^2 = x^3 + 2x + 2 mod 17,  base point G=(5,1), order n=19
p, a, n = 17, 2, 19
G = (5, 1)

def inv(x, m): return pow(x, -1, m)
def add(P, Q):
    if P is None: return Q
    if Q is None: return P
    if P[0] == Q[0] and (P[1] + Q[1]) % p == 0: return None
    if P == Q:
        l = (3*P[0]*P[0] + a) * inv(2*P[1], p) % p
    else:
        l = (Q[1] - P[1]) * inv((Q[0] - P[0]) % p, p) % p
    x = (l*l - P[0] - Q[0]) % p
    return (x, (l*(P[0] - x) - P[1]) % p)
def mul(k, P):
    R = None
    while k:
        if k & 1: R = add(R, P)
        P = add(P, P); k >>= 1
    return R

priv = 7
pub  = mul(priv, G)

def sign(z, k):
    x1, _ = mul(k, G)
    r = x1 % n
    s = inv(k, n) * (z + r*priv) % n
    return r, s

k = 5                       # THE BUG: same k for both messages
z1, z2 = 3, 11              # two different message hashes
r1, s1 = sign(z1, k)
r2, s2 = sign(z2, k)
print(f"sig1 = (r={r1}, s={s1})")
print(f"sig2 = (r={r2}, s={s2})   note r1 == r2 -> k was reused")

# attacker's algebra:  k = (z1 - z2) / (s1 - s2) mod n
k_rec    = (z1 - z2) * inv((s1 - s2) % n, n) % n
priv_rec = (s1 * k_rec - z1) * inv(r1, n) % n
print(f"\nrecovered k    = {k_rec}   (real: {k})")
print(f"recovered priv = {priv_rec}   (real: {priv})")
print("PRIVATE KEY STOLEN from two signatures. This is the PS3 bug.")
PY

Practice (35 min)

Generate an Ed25519 key, sign a file, verify it, tamper with the file, watch verification fail.
Compare sizes: Ed25519 vs RSA-2048 vs RSA-4096 public keys and signatures. Tabulate.
Run openssl speed ecdsap256 ed25519 rsa2048 and compare sign/verify rates.
Run the k-reuse demo. Then, in notes.md, state in one sentence why Ed25519 makes this attack structurally impossible.
Read the P-256 vs Curve25519 argument (further reading) and write two sentences on why you'd pick 25519 for a new system.

Common confusions

"ECC is newer and less trusted than RSA." ECC has been standardised since the mid-2000s and is now the default across TLS, SSH, and code signing. It is at least as trusted.
"ECDSA and EdDSA are the same." Both are elliptic-curve signatures. ECDSA needs a random k per signature (footgun). EdDSA/Ed25519 is deterministic (no footgun).
"X25519 and Ed25519 are interchangeable keys." No. X25519 is for key exchange (ECDH), Ed25519 for signatures. They use the same underlying curve but different key encodings; don't cross-use them.
"Smaller keys mean less security." For ECC vs RSA, no — the maths is harder to attack, so less key achieves the same strength.
"ECC is quantum-safe." No — Shor's algorithm breaks ECDLP too, and ECC keys are smaller, so arguably fall first. (Part 6.)

Check yourself

What RSA key size does a 256-bit elliptic-curve key match?
What's the hard problem underneath ECC?
What is the deadly footgun in ECDSA, and name a real incident it caused.
How does Ed25519 avoid that footgun?
Which primitive for key exchange, which for signatures, in the Curve25519 family?
Is ECC post-quantum secure?