Secrets in public: Diffie–Hellman and RSA

Every cipher so far is symmetric: the same key encrypts and decrypts, so the two sides must share it before they can say anything secret. Armies distributed codebooks by courier; banks had key officers carrying sealed envelopes. With $n$ people who all want to talk privately, $n(n-1)/2$ keys are needed. On the Internet, where you want to talk to a shop you have never heard of, it is impossible. The way out came in three steps, between 1974 and 1977, and it changed what cryptography is.

§Merkle's puzzles

In 1974 Ralph Merkle, an undergraduate at Berkeley, proposed a project to agree on a key in public; his professor rejected it. His idea: Bob sends Alice a million puzzles, each a short message encrypted with a deliberately weak key that takes a minute to break. Each puzzle contains a random identifier and a secret key. Alice picks one puzzle at random, breaks it, and announces its identifier; both now share its key. An eavesdropper who does not know which puzzle Alice chose must break, on average, half a million of them. The advantage is only quadratic (a minute for Alice, a year for the eavesdropper), but it was the first proof that a shared secret could be built in public. The paper appeared, after years of rejections, in 1978.

§Diffie–Hellman

In November 1976 Whitfield Diffie and Martin Hellman published New Directions in Cryptography, which begins: “We stand today on the brink of a revolution in cryptography.” Their key agreement uses arithmetic modulo a prime.

Alice and Bob agree in public on a large prime $p$ and a generator $g$. Alice chooses a secret $a$ and sends $A=g^{a}modp$; Bob chooses a secret $b$ and sends $B=g^{b}modp$. Then

and both hold $s=g^{ab}modp$. An eavesdropper sees $p$, $g$, $A$ and $B$. To get $s$ she seems to need $a$ from $A=g^a$: the discrete logarithm. Exponentiation modulo $p$ is fast (see square-and-multiply below); its inverse, for well-chosen 2048-bit primes, is out of reach of every known classical algorithm.

Diffie–Hellman protects against eavesdroppers, not against an active man in the middle who agrees one key with Alice and another with Bob. To defeat her, the public values must be authenticated, which is the job of signatures. With that addition (and with elliptic curves, chapter 09), Diffie–Hellman is how every TLS 1.3 connection starts. Diffie and Hellman received the Turing Award for it in 2015.

§Discovered in secret, first

In 1997 the British signals agency GCHQ revealed that its own mathematicians had got there first. James Ellis had shown in 1970 that “non-secret encryption” was possible in principle; in 1973 Clifford Cocks, a 22-year-old recent recruit, found a practical scheme in an evening, essentially RSA; in 1974 Malcolm Williamson found what amounts to Diffie–Hellman. Classified, none of it was used or published, and the world learned public-key cryptography from the academics.

§The number theory behind RSA

Proof

The numbers $a,2a,\dots ,(p-1)a$ are non-zero and pairwise different modulo $p$ (if $ia\equiv ja$ then $p\mid (i-j)a$, so $i=j$), so they are $1,2,\dots ,p-1$ in some order. Multiplying them all: $a^{p-1}(p-1)!\equiv (p-1)!(\mathrm{mod}p)$, and $(p-1)!$ is invertible modulo $p$.

The proof is the same as Fermat's, applied to the $\phi (n)$ invertible residues; Euler's theorem is Lagrange's theorem for the group ${\mathbb{Z}}_n^{\ast }$.

§RSA

In 1977 three researchers at MIT, Ron Rivest, Adi Shamir and Leonard Adleman, spent a year trying to build a public-key cipher (Rivest and Shamir proposing, Adleman breaking) until, after a Passover evening in April, Rivest wrote down the scheme:

1. Choose two large random primes $p$ and $q$, and let $n=pq$ and $\phi (n)=(p-1)(q-1)$.
2. Choose $e$ coprime with $\phi (n)$ (today almost always $e=65537$) and compute $d=e^{-1}mod\phi (n)$ with the extended Euclidean algorithm.
3. The public key is $(n,e)$; the private key is $d$ (and $p$, $q$).
4. Encrypt a number $0\le m<n$ as $c=m^{e}modn$; decrypt as $m=c^{d}modn$.

Proof

Since $ed\equiv 1(\mathrm{mod}\phi (n))$, write $ed=1+t(p-1)(q-1)$. Modulo $p$: if $p\nmid m$, Fermat gives $m^{ed}=m\cdot (m^{p-1}{)}^{t(q-1)}\equiv m$; if $p\mid m$, both sides are $0$. The same holds modulo $q$. So $p$ and $q$ both divide $m^{ed}-m$, and since they are distinct primes, so does $n=pq$ (this is the Chinese remainder theorem: a residue modulo $pq$ is determined by its residues modulo $p$ and modulo $q$).

Anyone who can factor $n$ computes $\phi (n)$ and then $d$, so RSA is at most as hard as factoring. That August, Martin Gardner's column in Scientific American described RSA and printed a challenge: a message encrypted with a 129-digit modulus, RSA-129, with a $100 prize. The authors estimated it would take 40 quadrillion years. It was factored in 1994 by 600 volunteers coordinated over the Internet; the message read “THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE”.

Square-and-multiply

Computing $m^d$ with $d$ of 3,000 bits by repeated multiplication would take $2^{3000}$ steps. Instead, read the exponent in binary and, for each bit, square the running result and multiply by $m$ if the bit is 1: about ${\log }_{2}d$ squarings and at most as many multiplications, all modulo $n$. This algorithm, known in India over two thousand years ago for computing powers, is what makes RSA (and Diffie–Hellman) practical.

Textbook RSA is not secure

The scheme above, “textbook RSA”, is deterministic (the same $m$ always gives the same $c$, so an attacker can test guesses) and malleable ($c\cdot 2^e$ decrypts to $2m$). Real RSA encrypts a randomly padded message. The old padding of PKCS#1 v1.5 fell to Daniel Bleichenbacher's attack in 1998, a padding oracle like Vaudenay's (chapter 05), which keeps resurfacing in TLS implementations (ROBOT, 2017). OAEP, by Mihir Bellare and Phillip Rogaway (1994), adds randomness through a Feistel-like mixing with a hash, and is provably secure under reasonable assumptions; it is what the desktop app's RSA-OAEP uses, with SHA-256 and 3,072-bit keys. RSA encrypts at most a few hundred bytes, so in practice it encrypts a symmetric key: hybrid encryption.

§How big must the key be?

Factoring has improved steadily: the quadratic sieve (Carl Pomerance, 1981) and the general number field sieve (1990s), whose running time is about

sub-exponential in the number of digits. RSA-768 (232 digits) was factored in 2009; RSA-250 (250 digits, 829 bits) in 2020, with about 2,700 core-years. A 2,048-bit modulus gives about 112 bits of security, 3,072 bits about 128. A large quantum computer running Shor's algorithm would factor in polynomial time and break RSA and Diffie–Hellman at any size; Math of Quantum explains how, and chapter 10 what replaces them.

§Digital signatures

Run RSA backwards and you get a signature: the owner of $d$ computes $s=h^{d}modn$ for the hash $h$ of a message, and anyone can check that $s^e\equiv h(\mathrm{mod}n)$ with the public key. Only the holder of $d$ could have produced $s$, so a signature gives authenticity, integrity and non-repudiation. As with encryption, the hash must be padded: RSA-PSS (Bellare and Rogaway, 1996) randomises it and has a tight security proof; it is one of the desktop app's signature algorithms.

Signatures make the rest of public-key cryptography usable. A certificate is a public key signed by a certificate authority; your browser trusts a few dozen authorities, and they vouch for the keys of millions of websites. When TLS starts, the server's certificate authenticates its Diffie–Hellman share, which defeats the man in the middle. Software updates, passports, e-mail (S/MIME, PGP), Git commits and cryptocurrencies all rest on signatures. The next chapter makes them, and Diffie–Hellman, much smaller.

§Further reading

1. Whitfield Diffie and Martin Hellman, “New Directions in Cryptography”, IEEE Transactions on Information Theory 22(6), 1976.
2. Ron Rivest, Adi Shamir, Leonard Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, Communications of the ACM 21(2), 1978.
3. Ralph Merkle, “Secure Communications over Insecure Channels”, Communications of the ACM 21(4), 1978.
4. James Ellis, “The History of Non-Secret Encryption” (written 1987, published by GCHQ in 1997).
5. Dan Boneh, “Twenty Years of Attacks on the RSA Cryptosystem”, Notices of the AMS 46(2), 1999.