Cairn
algorithms · cryptography · O(log n) time for key generation/exchange, O(1) space; recovering a secret from the public values has no known polynomial algorithm

↩ back to Cryptography

Diffie–Hellman Key Exchange

This is the site's first entry in a new Cryptography category, and it's built entirely out of two things already on this site. Modular Exponentiation computes gx mod p cheaply, in O(log x). Baby-Step Giant-Step explains why reversing that — the discrete logarithm problem, recovering x from g, p, and gx mod p — has no known general algorithm that's fast in the number of digits of p, the way the forward direction is. Diffie–Hellman key exchange, published by Whitfield Diffie and Martin Hellman in 1976, is the payoff: two people who have never met, talking over a channel anyone can listen to, end up agreeing on a shared secret number that an eavesdropper — who hears every single message — cannot feasibly compute, as long as the modulus is large enough that the discrete log problem stays hard.

Small enough, though, and it isn't hard at all. The demo below runs the real protocol with a modulus small enough to see every number involved — and then lets a third party, Eve, who only ever sees what actually crosses the wire, break it live using the exact same baby-step giant-step algorithm from that other page, not a stand-in for it.

Try it

Alice and Bob each pick a secret number from 1 to 21 (or click Randomize) and never say it out loud. Run exchange walks through what each side actually computes and sends. Then click Eve: crack it — Eve never saw either secret, only the public modulus, generator, and the two values that crossed the wire — and watch her recover Alice's secret with the same meet-in-the-middle search Baby-Step Giant-Step uses, then compute the identical shared secret from it.

p = 23 (public), g = 5 (public) — a primitive root mod 23, the same pair Baby-Step Giant-Step uses.
Pick two secrets and run the exchange.

Why it works

Everyone — Alice, Bob, and any eavesdropper — knows a public prime p and a public generator g. Alice picks a secret a and sends A = ga mod p. Bob picks a secret b and sends B = gb mod p. Neither secret itself ever crosses the wire — only the two public values. Alice then computes Ba mod p; Bob computes Ab mod p. Both land on the same number, because exponents of the same base compose by multiplication regardless of which one is applied first:

Ba = (gb)a = gba = gab = (ga)b = Ab (mod p)

Alice never needs to know b to compute this — she only ever uses the public B and her own secret a. The shared secret K = gab mod p is a number neither side could have landed on without combining one real secret with the other side's public value — and it's also the one number an eavesdropper, who sees p, g, A, and B but neither a nor b, would need the discrete logarithm problem solved to reach directly.

Reference implementation

The demo above runs exactly this — three-step public exchange, then each side folding in its own secret — against p = 23, g = 5:

function modpow(base, exp, mod) {
  base = base % mod;
  let result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % mod;
    base = (base * base) % mod;
    exp = Math.floor(exp / 2);
  }
  return result;
}

// Public: p, g. Secret: a (Alice), b (Bob). Nothing but A and B crosses the wire.
const A = modpow(g, a, p);   // Alice sends A
const B = modpow(g, b, p);   // Bob sends B

const sharedByAlice = modpow(B, a, p);
const sharedByBob   = modpow(A, b, p);
// sharedByAlice === sharedByBob, both equal g^(ab) mod p

Eve's crack button runs the same baby-step giant-step search as that page's own reference implementation, against A instead of a hand-picked target — she only needs to recover one secret (either one) to compute the same shared key either original party could.

Pitfalls

A small enough modulus makes the "hard" direction cheap — demonstrated, not just asserted. Checked exhaustively across every one of the 441 possible secret pairs (a, b each 1–21) at this page's own p = 23: the shared secret Alice and Bob land on always matches (0 mismatches), and Eve's baby-step giant-step crack always recovers a secret that reproduces A and the correct shared key (0 failures, 0 wrong answers). Every one of those 441 exchanges is breakable in at most 5 giant steps — p has only 2 digits. Real deployments use primes with hundreds of digits specifically so that same O(√p) search, exponential in the digit count, stays computationally infeasible rather than instantaneous; the math doesn't change between the two cases, only the size of p does.

Diffie–Hellman alone authenticates no one. Nothing in the protocol lets Alice confirm the B she received actually came from Bob, or vice versa — it secures the exchange against someone who can only listen, not against someone who can also intercept and substitute. An active attacker sitting between them can run one exchange with Alice (pretending to be Bob) and a separate exchange with Bob (pretending to be Alice), landing on two different shared secrets, one with each victim, and silently decrypt-and-re-encrypt everything that flows through in either direction — a classic man-in-the-middle attack that the math here does nothing to prevent. This isn't a flaw to fix in the arithmetic; it's a missing piece the protocol was never designed to supply. Real systems (TLS, for instance) layer authentication — certificates, digital signatures — on top of this exact exchange rather than changing it.

A generator that isn't a primitive root shrinks the keyspace, the same subgroup pitfall Baby-Step Giant-Step already documents. This page's g = 5 is a primitive root mod 23 — it generates all 22 nonzero residues, so every secret from 1 to 21 produces a distinct public value. A generator with smaller order only reaches a subset of those residues: fewer possible public values, and in the worst case, a shared secret confined to a small subgroup an attacker can exhaust directly rather than search. Real protocols fix g as a known full-order generator specifically so this can't arise, the same reason that page gives for why its own subgroup-confinement pitfall "rarely bites" in practice.

Complexity

Time: each side's own work is one modular exponentiation, O(log a) multiplications via the same square-and-multiply technique Modular Exponentiation uses — cheap even for the hundreds-of-digit numbers real deployments use. Space: O(1) beyond the numbers themselves. The asymmetry that makes the whole scheme work is the reverse direction: the best known general attack against a safely-sized prime-modulus group is sub-exponential (index calculus and its descendants), far short of polynomial, and even the simpler O(√p) baby-step giant-step search this page's own Eve uses is still exponential in the number of digits of p — the reason a 2-digit demo cracks in milliseconds while a real 600-digit deployment doesn't crack at all with any algorithm known today.