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.
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.
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.
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.
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.
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.