Sharing a secret in public

Two strangers, talking over a line anyone can tap, can end up holding the same secret number — and the listener, who heard every word, cannot work it out. Nothing is hidden; what protects the secret is that one calculation is easy and its reverse is believed hard.

What it is

A public key distribution system, in Diffie and Hellman's phrase, is a procedure in which two users "communicate back and forth until they arrive at a key in common," while an eavesdropper must find it "computationally infeasible" to compute that key from what was overheard. The key then runs an ordinary cipher. The novelty is its source: not a courier or a prior meeting, but the public conversation itself.

Why it matters

Before this, encryption was, in the paper's words, "a derivative security measure": a secure channel had to deliver the key before the cipher could protect anything, limiting cryptography to people with prior arrangements. The paper notes that n users make (n² − n)/2 potential pairs, and that a prearranged key for every pair, or one sent by secure physical means, is unrealistic for a network of strangers. A key built in the open removes that wall.

The easy direction and the hard one

Fix a prime q and a number α whose powers modulo q run through every value from 1 to q − 1 (a primitive element). From an exponent X, computing Y = α^X mod q is cheap: repeated squaring takes at most 2 log₂ q multiplications. Going backwards — from Y to the X that produced it — is the logarithm of Y modulo q, and the best method the paper knew took on the order of √q operations for a suitably chosen q. Their example: for a 200-bit prime q, the forward computation costs at most 400 multiplications; the logarithm, about 2¹⁰⁰, roughly 10³⁰, operations. The attacker's work grows exponentially relative to the honest users'.

The exchange

Each user i picks a random secret X_i between 1 and q − 1 and publishes Y_i = α^X_i mod q. Users i and j each raise the other's public value to their own secret exponent. User i computes Y_j^X_i; user j computes Y_i^X_j. Both equal α^X_iX_j mod q — same exponent, same number — and that is the shared key K_ij. The eavesdropper holds q, α, Y_i and Y_j; the obvious route to the key is a logarithm — the hard direction.

The hedge

The paper claims no proof. It says the security "depends crucially on the difficulty of computing logarithms mod q," and that if a fast algorithm were found, "our system would be broken." The problem's simplicity might allow such an algorithm, or instead a proof of hardness; "for now we assume that the best known algorithm … is in fact close to optimal." And it admits a gap: no proof that hard logarithms make the system secure — only that they saw no way to compute the key from the public values without first obtaining a secret exponent. The scheme rests on a stated belief about computation.

In short

Each side raises a public base to a private exponent and shares the result, then raises the other's result to its own exponent; because exponents multiply in either order, both land on the same number. A listener has the base and both results, but recovering an exponent is the logarithm problem, believed — not proven — far harder than the forward step. The secret is shared in public because only the easy direction is ever performed there.