The idea that changed cryptography.

For almost its entire history, cryptography lived by a rule that seemed like a law of nature: to communicate in secret, the two parties first had to share a key. The general and his lieutenant, the bank and its branch, the ambassador and his foreign ministry. Anyone who wanted to talk in secret with a thousand people needed a thousand keys and a thousand trusted couriers to deliver them. And the signature, understood as proof of authorship before a third party, was not even on the table: if both parties know the same key, either of them could have produced the message.

In November 1976, Whitfield Diffie and Martin Hellman published a paper in IEEE Transactions on Information Theory that opened with a deliberately provocative sentence: “We stand today on the brink of a revolution in cryptography.” They were not exaggerating. “New Directions in Cryptography” put forward two ideas that no one had stated in public before: agreeing on a secret key over a completely exposed channel, and signing digitally with something only one person holds but anyone can verify.

One way functions

Everything that follows rests on a notion that is simple to state and hard to prove: a one way function is a function f that is easy to compute, but such that, given y = f(x), finding any x that produces it is infeasible in practice.

“Infeasible” has a precise meaning here. It does not mean impossible, because one can always try every input. It means that the best known method requires a number of operations that grows exponentially (or nearly so) with the size of the input, so that with reasonable parameters it exceeds any conceivable computing capacity. Computing f takes time polynomial in the length of x; inverting it takes time that is not.

A one way function is useful for storing passwords, but it is not enough to encrypt or to sign: if nobody can invert it, neither can the legitimate recipient. Diffie and Hellman proposed a subtler object, the trapdoor one way function: impossible to invert in general, but easy to invert for whoever knows an extra piece of information, the trapdoor. That information is the private key. The function, with everything needed to compute it, is the public key.

Clock arithmetic

The candidate Diffie and Hellman chose comes from modular arithmetic, the arithmetic of clocks. Working “modulo p” means keeping only the remainder after dividing by p: on a 12 hour clock, 9 + 5 = 2. With a prime p, the numbers from 1 to p 1 form a group under multiplication: every number has an inverse, and there are elements called generators whose powers run through the entire group.

Over the real numbers, the logarithm is a smooth function that is easy to approximate: if 2^x = 1000, x is somewhere near 10. In modular arithmetic that intuition vanishes. The powers jump from one place on the clock to another with no visible order, and knowing where one landed says almost nothing about the exponent. The following lab shows this with a clock of 23 positions.

With 23 positions, finding the exponent by trial is trivial. With a 3072 bit prime, the best known algorithm, the number field sieve, needs on the order of 2¹²⁸ operations. That is the same security level offered by a 128 bit symmetric key, which is why NIST pairs the two sizes in its key management recommendation.

The Diffie and Hellman exchange

The first application in the 1976 paper was not the signature but something that seemed even more impossible: two people who have never met agreeing on a secret while talking out loud in front of everyone.

1. Public parameters. Alice and Bob agree, in full view of everyone, on a prime p and a generator g. In the example, p = 23 and g = 5.
2. Private secrets. Alice privately picks a = 6; Bob picks b = 15. They never reveal them.
3. Public values. Alice sends A = 5⁶ mod 23 = 8. Bob sends B = 5¹⁵ mod 23 = 19.
4. Shared secret. Alice computes B^a = 19⁶ mod 23 = 2. Bob computes A^b = 8¹⁵ mod 23 = 2. Both arrive at g^ab without ever having transmitted it.

Anyone who overheard the whole conversation knows 23, 5, 8 and 19. To get the 2 they would need a or b, that is, they would have to solve a discrete logarithm. (Strictly speaking, they need to solve the so called Diffie and Hellman problem, which is not known to be equivalent to the discrete logarithm but is not known to be any easier either.) The protocol has a weakness the paper already sensed: it does not say who you are talking to. An intermediary can run one exchange with each party and read everything. The solution to that problem is, precisely, the digital signature.

The signature as they imagined it

The section of the paper devoted to authentication defines precisely what is wanted: a signed message that the receiver can verify but could not have produced themselves, and that can therefore convince a third party, a judge for instance. This is the property we now call nonrepudiation, and it is what sets a signature apart from a mere message authentication code, where both parties share the key and either could have generated it.

The abstract scheme they proposed is still the one we use today:

What Diffie and Hellman lacked was a concrete trapdoor function to implement it. A few months later, at MIT, Ron Rivest, Adi Shamir and Leonard Adleman found one: integer factorization. Their 1978 paper put the words “digital signatures” in its title ahead of “public key cryptosystems”. RSA is the subject of the next article in this series.

Those who got there first, in silence

The story has a chapter that only came to light in 1997. At GCHQ, the British signals intelligence agency, James Ellis had formulated in 1970 the idea of “nonsecret encryption”. In 1973 Clifford Cocks, newly hired, found in a single afternoon a scheme essentially identical to RSA, and in 1974 Malcolm Williamson arrived at an exchange equivalent to Diffie and Hellman’s. All of it stayed classified. Meanwhile Ralph Merkle, then a student at Berkeley, had proposed in 1974 a key agreement protocol based on “puzzles”, which was not published until 1978 and is now recognized as the first public scheme of its kind.

Three families of problems

Half a century later, the public key cryptography in use rests on very few mathematical problems. They are worth keeping in mind, because they determine what threatens it and how its strength is measured.

The first three fall to the same enemy, Shor’s algorithm on a sufficiently large quantum computer. The last were chosen precisely because no efficient quantum attack against them is known. The whole series comes back, one way or another, to this table.

← All notes