Diffie-Hellman: A Secret over a Public Wire

in reviewThis lesson is complete and being validated before release - details may still change.

Diffie-Hellman key exchange

Loading interactive demo…

Three lanes, Alice, Eve, and Bob, with the messages that cross the wire between Alice and Bob; Eve reads all of them. The chart is the power table of the group, g to the x for every exponent, with the bar Eve is trying lit and the bars equal to the shares marked. The table beneath shows what each party knows as the exchange runs. Tap a message to light it.Take the tour, or press and explore. Legend:

The panel beside the stage is the real DiffieHellman class from the published library executing in your browser, with the current line highlighted.

The message or trial under way.
A share on the wire.
Bars of the power table equal to a share: what Eve is looking for.
A key agreed on both ends.
The key in Eve's hands.
Trials Eve has not made yet, ghosted.

shared key is g to the ab once both parties have it, agree whether both ends got the same, eve's trials how many exponents she has tried, eve whether she recovered the key. The seed draws both secrets; Reseed draws new ones.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The exchange. Public: a prime $p$ and a generator $g$ of the multiplicative group mod $p$ , so that $g, g^2, \ldots, g^{p-1}$ are all the nonzero residues in some order. Alice picks $a$ , Bob picks $b$ , and they send

A = g^a \bmod p, \qquad B = g^b \bmod p .

Alice computes $B^a$ and Bob computes $A^b$ , and both are

g^{ab} \bmod p ,

because $(g^b)^a = g^{ba} = g^{ab} = (g^a)^b$ . The powers are taken by squaring, so each party does about $2 \log_2 p$ multiplications, the modular lesson's loop, and the shared key readout shows the result they never transmitted.

What Eve needs. Eve has $p$ , $g$ , $A$ , and $B$ . The Diffie-Hellman problem is to get $g^{ab}$ from these; the only known route is to find $a$ from $A = g^a$ , the discrete logarithm, and nobody knows how to do that much faster than the stage does it when $p$ is a safe prime. Exponentiation is easy and its inverse is not: a one-way function, which is what every public-key scheme rests on. The stage's Eve walks the power table, $O(p)$ trials; the best general algorithms for prime fields run in time about $\exp(c \sqrt[3]{\ln p\,(\ln \ln p)^2})$ , subexponential but still hopeless at $2048$ bits, and on elliptic curves nothing better than $O(\sqrt{p})$ is known, which is why $256$ -bit curves suffice.

Why a generator. If $g$ had small order, its powers would repeat after a few steps and Eve's table would be short. A generator has order $p - 1$ , so the table is as long as it can be; in practice $p$ is chosen as $2q + 1$ with $q$ prime, so every element has order $2$ , $q$ , or $2q$ and there are no small subgroups to fall into.

Forward secrecy. The secrets $a$ and $b$ can be thrown away after the exchange, and then nothing recorded from the wire can ever be turned into the key, even if every long-term key the parties own leaks later. TLS 1.3 insists on this; the handshake lesson's first two messages are exactly $A$ and $B$ .

What it does not do. Nothing here tells Alice that $B$ came from Bob. If Eve intercepts both shares and replaces each with her own $g^e$ , she agrees one key with Alice and another with Bob and relays between them, reading everything: the man in the middle. The exchange needs authentication, which signatures and certificates supply three lessons from now.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

publish validates the group, prime and generator, with the modular lesson's static checks; a non-generator would shorten Eve's table and a composite modulus would break the arithmetic, so the class refuses both.
keyPair and combine are the same pow on different arguments, taken through the untraced ModularArithmetic instance the constructor holds, so the exchange is two calls per party and nothing else.
discreteLog multiplies by $g$ once per trial rather than taking a fresh power, so each trial is one multiplication and the walk along the table costs what the chart shows.
run caps Eve at MAX_LOG_TRIALS, so the untraced use in the handshake, with a 16-bit prime, gives up quickly and the trace never exceeds a few hundred events.

Before 1976 every cipher needed a key delivered in secret, by courier or in person, which was the hardest part of using one. Whitfield Diffie and Martin Hellman's 'New Directions in Cryptography' showed two strangers could agree a key over a line anyone could tap, using a one-way street in modular arithmetic: powers are cheap and logarithms are not. Malcolm Williamson at GCHQ had found the same scheme in 1974, in secret, and it stayed classified until 1997. The exchange, on primes of thousands of bits or on elliptic curves, now opens nearly every encrypted connection on the internet.

1974Ralph Merkle - Proposes key agreement by puzzles, where the eavesdropper's work grows only quadratically; it is the first public-key idea and the reason Hellman calls the scheme Diffie-Hellman-Merkle.source
1976Whitfield Diffie and Martin Hellman - Publish 'New Directions in Cryptography', with the exchange over powers mod a prime and the idea of public-key cryptography itself.source
1985Taher ElGamal - Turns the exchange into an encryption and signature scheme, and Neal Koblitz and Victor Miller move it onto elliptic curves, where 256 bits do the work of 3072.source
1997GCHQ - Declassifies Malcolm Williamson's 1974 discovery of the exchange, and James Ellis's 1970 idea of non-secret encryption that preceded it.source
2015The Logjam team - Show that a single precomputation on a widely shared 512-bit prime breaks every exchange using it, and that 1024-bit primes are within a state's budget; browsers raise the minimum.source

Used today

TLS key shares - Every TLS 1.3 handshake begins with an elliptic-curve Diffie-Hellman exchange; the handshake lesson runs one in this group.
Messaging - Signal's double ratchet performs a fresh exchange for every message, so compromising one key reveals nothing before or after it.
SSH and VPNs - Each session's key is agreed this way, so a recorded session cannot be read later even if the server's long-term key leaks: forward secrecy.

group

shared key: 12
agree: yes
eve's trials: 15 of 22
eve: found a = 15

diffie-hellman.ts

import { ModularArithmetic } from "../number-theory/modular-arithmetic";import { Mulberry32 } from "../random";import type { Tracer } from "../trace";/** The largest prime below 2^16: the group the handshake lesson uses untraced. */export const MAX_PRIME = 65521;/** Eve's brute force gives up after this many powers, so a trace stays short. */export const MAX_LOG_TRIALS = 128;/** Primes small enough for Eve to finish on the stage, each with a generator. */export const GROUPS: readonly { p: number; g: number }[] = [  { p: 23, g: 5 },  { p: 47, g: 5 },  { p: 97, g: 5 },  { p: 127, g: 3 },];export interface Exchange {  p: number;  g: number;  a: number;  aliceSecret: number;  b: number;  bobSecret: number;  shareA: number;  shareB: number;  sharedA: number;  sharedB: number;  agree: boolean;}export interface LogResult {  target: number;  /** The exponent found, or null when the trials ran out. */  exponent: number | null;  trials: number;  found: boolean;}export interface DhRun {  exchange: Exchange;  eve: LogResult;  /** What Eve computes from the secret she recovered, or null. */  eveShared: number | null;  broken: boolean;}/** * Diffie-Hellman key exchange: everyone agrees on a prime p and a * generator g in public; Alice picks a secret a and sends g to the a, * Bob picks b and sends g to the b, and each raises what they got to * their own secret, so both hold g to the ab while the wire carried * only g to the a and g to the b. Eve, who saw both, needs a or b, * and finding the exponent that gives a known power of g is the * discrete logarithm, for which nothing much better than trying every * exponent is known when p is large. Here Eve tries them, which works * at the stage's sizes and is why real groups have 2048-bit primes. * * Time: O(log p) multiplications per party; O(p) for Eve. Space: O(1). */export class DiffieHellman {  constructor(    private readonly tracer?: Tracer,    private readonly modular: ModularArithmetic = new ModularArithmetic(),  ) {}  /** The public parameters: a prime and a generator of its multiplicative group. */  publish(p: number, g: number): void {    if (!ModularArithmetic.isPrime(p) || p > MAX_PRIME) throw new RangeError(`p must be a prime up to ${MAX_PRIME}, got ${p}`);    if (!ModularArithmetic.isGenerator(g, p)) throw new RangeError(`${g} does not generate the group mod ${p}`);    // ▸ the prime and the generator are agreed in the open    this.tracer?.emit("publish", { p, g });  }  /** A party's secret and the share it publishes, g to the secret. */  keyPair(party: string, p: number, g: number, secret: number): number {    if (!Number.isInteger(secret) || secret < 1 || secret > p - 2) throw new RangeError(`a secret is a whole number from 1 to p - 2, got ${secret}`);    // ▸ each party picks an exponent and tells nobody    this.tracer?.emit("secret", { party, secret });    const share = this.modular.pow(g, secret, p);    // ▸ g to the secret, mod p: safe to show, hard to undo    this.tracer?.emit("share", { party, secret, share });    return share;  }  /** A share crosses the wire, where anyone can read it. */  send(from: string, to: string, value: number): number {    // ▸ the share crosses the wire, where eve reads it    this.tracer?.emit("send", { from, to, value });    return value;  }  /** The received share raised to the party's own secret. */  combine(party: string, p: number, received: number, secret: number): number {    const shared = this.modular.pow(received, secret, p);    // ▸ the other share to your own secret: g to the ab either way    this.tracer?.emit("combine", { party, received, secret, shared });    return shared;  }  /** The whole exchange between Alice with secret a and Bob with secret b. */  exchange(p: number, g: number, a: number, b: number): Exchange {  exchange(p: number, g: number, aliceSecret: number, bobSecret: number): Exchange {    this.publish(p, g);    const shareA = this.keyPair("alice", p, g, a);    const shareA = this.keyPair("alice", p, g, aliceSecret);    const shareB = this.keyPair("bob", p, g, b);    const shareB = this.keyPair("bob", p, g, bobSecret);    const toBob = this.send("alice", "bob", shareA);    const toAlice = this.send("bob", "alice", shareB);    const sharedA = this.combine("alice", p, toAlice, a);    const sharedA = this.combine("alice", p, toAlice, aliceSecret);    const sharedB = this.combine("bob", p, toBob, b);    const sharedB = this.combine("bob", p, toBob, bobSecret);    const agree = sharedA === sharedB;    // ▸ both parties hold the same key, and never sent it    this.tracer?.emit("agree", { sharedA, sharedB, same: agree });    return { p, g, a, b, shareA, shareB, sharedA, sharedB, agree };    return { p, g, aliceSecret, bobSecret, shareA, shareB, sharedA, sharedB, agree };  }  /** Eve's attack: multiply by g until the running power equals the target, or the trials run out. */  discreteLog(p: number, g: number, target: number): LogResult {    let value = 1;    for (let x = 1; x <= Math.min(MAX_LOG_TRIALS, p - 1); x++) {      value = this.modular.mul(value, g, p);      const hit = value === target;      // ▸ try the next exponent: is g to the x the share?      this.tracer?.emit("trial", { x, value, target, hit });      if (hit) return { target, exponent: x, trials: x, found: true };    }    return { target, exponent: null, trials: Math.min(MAX_LOG_TRIALS, p - 1), found: false };  }  /** Secrets from the seed, the exchange, then Eve reads the wire and tries to recover Alice's secret from her share. */  run(p: number, g: number, seed: number): DhRun {    const random = new Mulberry32(seed);    const a = random.intBetween(2, p - 2);    const aliceSecret = random.intBetween(2, p - 2);    const b = random.intBetween(2, p - 2);    const bobSecret = random.intBetween(2, p - 2);    const exchange = this.exchange(p, g, a, b);    const exchange = this.exchange(p, g, aliceSecret, bobSecret);    // ▸ eve has p, g, and both shares, and needs a or b    this.tracer?.emit("eavesdrop", { p, g, shareA: exchange.shareA, shareB: exchange.shareB });    const eve = this.discreteLog(p, g, exchange.shareA);    const eveShared = eve.exponent === null ? null : this.modular.pow(exchange.shareB, eve.exponent, p);    const broken = eveShared === exchange.sharedA;    // ▸ with the exponent, eve computes the key too    this.tracer?.emit("broken", { exponent: eve.exponent, trials: eve.trials, shared: eveShared, found: broken });    return { exchange, eve, eveShared, broken };  }}

shared =: 12
agree =: yes
broken =: yes

Shared key 12, agreed on both ends; Eve recovered it after 15 trials, which is why real primes are far larger.

import { ModularArithmetic } from "../number-theory/modular-arithmetic";import { Mulberry32 } from "../random";import type { Tracer } from "../trace";/** The largest prime below 2^16: the group the handshake lesson uses untraced. */export const MAX_PRIME = 65521;/** Eve's brute force gives up after this many powers, so a trace stays short. */export const MAX_LOG_TRIALS = 128;/** Primes small enough for Eve to finish on the stage, each with a generator. */export const GROUPS: readonly { p: number; g: number }[] = [ { p: 23, g: 5 }, { p: 47, g: 5 }, { p: 97, g: 5 }, { p: 127, g: 3 },];export interface Exchange { p: number; g: number; a: number; aliceSecret: number; b: number; bobSecret: number; shareA: number; shareB: number; sharedA: number; sharedB: number; agree: boolean;}export interface LogResult { target: number; /** The exponent found, or null when the trials ran out. */ exponent: number | null; trials: number; found: boolean;}export interface DhRun { exchange: Exchange; eve: LogResult; /** What Eve computes from the secret she recovered, or null. */ eveShared: number | null; broken: boolean;}/** * Diffie-Hellman key exchange: everyone agrees on a prime p and a * generator g in public; Alice picks a secret a and sends g to the a, * Bob picks b and sends g to the b, and each raises what they got to * their own secret, so both hold g to the ab while the wire carried * only g to the a and g to the b. Eve, who saw both, needs a or b, * and finding the exponent that gives a known power of g is the * discrete logarithm, for which nothing much better than trying every * exponent is known when p is large. Here Eve tries them, which works * at the stage's sizes and is why real groups have 2048-bit primes. * * Time: O(log p) multiplications per party; O(p) for Eve. Space: O(1). */export class DiffieHellman { constructor( private readonly tracer?: Tracer, private readonly modular: ModularArithmetic = new ModularArithmetic(), ) {} /** The public parameters: a prime and a generator of its multiplicative group. */ publish(p: number, g: number): void { if (!ModularArithmetic.isPrime(p) || p > MAX_PRIME) throw new RangeError(`p must be a prime up to ${MAX_PRIME}, got ${p}`); if (!ModularArithmetic.isGenerator(g, p)) throw new RangeError(`${g} does not generate the group mod ${p}`); // ▸ the prime and the generator are agreed in the open this.tracer?.emit("publish", { p, g }); } /** A party's secret and the share it publishes, g to the secret. */ keyPair(party: string, p: number, g: number, secret: number): number { if (!Number.isInteger(secret) || secret < 1 || secret > p - 2) throw new RangeError(`a secret is a whole number from 1 to p - 2, got ${secret}`); // ▸ each party picks an exponent and tells nobody this.tracer?.emit("secret", { party, secret }); const share = this.modular.pow(g, secret, p); // ▸ g to the secret, mod p: safe to show, hard to undo this.tracer?.emit("share", { party, secret, share }); return share; } /** A share crosses the wire, where anyone can read it. */ send(from: string, to: string, value: number): number { // ▸ the share crosses the wire, where eve reads it this.tracer?.emit("send", { from, to, value }); return value; } /** The received share raised to the party's own secret. */ combine(party: string, p: number, received: number, secret: number): number { const shared = this.modular.pow(received, secret, p); // ▸ the other share to your own secret: g to the ab either way this.tracer?.emit("combine", { party, received, secret, shared }); return shared; } /** The whole exchange between Alice with secret a and Bob with secret b. */ exchange(p: number, g: number, a: number, b: number): Exchange { exchange(p: number, g: number, aliceSecret: number, bobSecret: number): Exchange { this.publish(p, g); const shareA = this.keyPair("alice", p, g, a); const shareA = this.keyPair("alice", p, g, aliceSecret); const shareB = this.keyPair("bob", p, g, b); const shareB = this.keyPair("bob", p, g, bobSecret); const toBob = this.send("alice", "bob", shareA); const toAlice = this.send("bob", "alice", shareB); const sharedA = this.combine("alice", p, toAlice, a); const sharedA = this.combine("alice", p, toAlice, aliceSecret); const sharedB = this.combine("bob", p, toBob, b); const sharedB = this.combine("bob", p, toBob, bobSecret); const agree = sharedA === sharedB; // ▸ both parties hold the same key, and never sent it this.tracer?.emit("agree", { sharedA, sharedB, same: agree }); return { p, g, a, b, shareA, shareB, sharedA, sharedB, agree }; return { p, g, aliceSecret, bobSecret, shareA, shareB, sharedA, sharedB, agree }; } /** Eve's attack: multiply by g until the running power equals the target, or the trials run out. */ discreteLog(p: number, g: number, target: number): LogResult { let value = 1; for (let x = 1; x <= Math.min(MAX_LOG_TRIALS, p - 1); x++) { value = this.modular.mul(value, g, p); const hit = value === target; // ▸ try the next exponent: is g to the x the share? this.tracer?.emit("trial", { x, value, target, hit }); if (hit) return { target, exponent: x, trials: x, found: true }; } return { target, exponent: null, trials: Math.min(MAX_LOG_TRIALS, p - 1), found: false }; } /** Secrets from the seed, the exchange, then Eve reads the wire and tries to recover Alice's secret from her share. */ run(p: number, g: number, seed: number): DhRun { const random = new Mulberry32(seed); const a = random.intBetween(2, p - 2); const aliceSecret = random.intBetween(2, p - 2); const b = random.intBetween(2, p - 2); const bobSecret = random.intBetween(2, p - 2); const exchange = this.exchange(p, g, a, b); const exchange = this.exchange(p, g, aliceSecret, bobSecret); // ▸ eve has p, g, and both shares, and needs a or b this.tracer?.emit("eavesdrop", { p, g, shareA: exchange.shareA, shareB: exchange.shareB }); const eve = this.discreteLog(p, g, exchange.shareA); const eveShared = eve.exponent === null ? null : this.modular.pow(exchange.shareB, eve.exponent, p); const broken = eveShared === exchange.sharedA; // ▸ with the exponent, eve computes the key too this.tracer?.emit("broken", { exponent: eve.exponent, trials: eve.trials, shared: eveShared, found: broken }); return { exchange, eve, eveShared, broken }; }}