How two mathematicians solved a cryptography mystery

On October 30, 1942, a group of destroyer warships from the British Royal Navy hunted down a Nazi submarine near the Nile Delta. The warships pounded the submarine with underwater explosions until it floated to the surface, where it started filling with water and sinking. As its German crew scrambled to escape, three British heroes—Lieutenant Anthony Fasson, sailor Colin Grazier and 16-year-old canteen assistant Tommy Brown—did something that defied all instinct. They jumped from their ship onto the sinking vessel and climbed inside.

They were after the sub’s most valuable cargo: not weapons, not prisoners, but books. The pages contained codes for tuning the Nazi “Enigma machine” that allowed the German forces to communicate in secret. Deep inside the flooding commanding officers’ quarters, the men seized the volumes before the water-soluble ink dissolved into the sea. Only the teenager made it out alive. Less than two months later English mathematician Alan Turing’s team of code breakers used the codes to decipher Nazi messages, an effort estimated to have shortened the war by two years, saving millions of lives.

Cryptography is the math of communicating in secret, and it’s as high stakes as math gets. The submarine story and dozens more like it highlight a catch-22 that plagued cryptography for millennia: to speak in code, you must first agree on a code. If I want to send you a letter but distrust my mail carrier, I can encrypt my message with a cipher. Snoops won’t be able to read it, but neither will you. If I send a follow-up note explaining the cipher, the mail carrier can intercept that, too—we’re right back where we started. Called the key-distribution problem, this cryptography pitfall seems to imply that to establish a private communication channel, we effectively need privacy to begin with.

On supporting science journalism

If you’re enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.

This conundrum is why the history of cryptography reads less like a math textbook and more like a spy thriller. Lacking a mathematical solution to the key-distribution problem, the world relied on physical ones: clandestine meetings, armed couriers and occasional heists on sinking submarines. Then, in 1976, Stanford University researchers Whitfield Diffie and Martin Hellman proposed a solution that seemed to defy logic. Their method allowed two strangers to agree on a shared secret even when all their communications were out in the open for anybody to intercept and read. Their protocol, now known as Diffie-Hellman key exchange, has become a security workhorse of the modern Internet. Every time you check your bank balance, shop online, send a WhatsApp message or visit any “https” website, some version of Diffie-Hellman is probably securing the connection.

By the time of Diffie and Hellman, cryptographers knew how to encrypt documents by scrambling messages so they looked like gibberish to anyone who didn’t possess a secret key consisting of a large random number. So the objective for Diffie and Hellman’s scheme, including in present-day uses, is to generate a single large random number that only the sender and receiver know. With that number, they can use known methods to encrypt and decrypt messages.

Diffie-Hellman’s critical trick relies on a mathematical “one-way function,” an operation that is easy to perform but computationally infeasible to reverse. Consider Coca-Cola’s famously secret formula. Mixing ingredients is easy, but even with access to the finished product, chemists have trouble reconstructing a perfect copy of the beverage. Here’s how you and I can ensure that the secret chemical concoctions we cook up in our homes are identical to one another, assuming we are communicating only via mail with snooping postal workers inspecting our shipments:

1. Public base: We agree on a common starting liquid, say, one liter of carbonated water mixed with a cola syrup. We announce this publicly, so eavesdroppers know the base liquid, too.

2. Private mixtures: I choose a homemade cherry flavoring as my secret ingredient, and I tell no one about it. I mix it with the base liquid to make a cherry cola. You also choose a secret ingredient: a homemade vanilla flavoring. You mix it with the base in your kitchen to make vanilla cola.

3. Exchange: We mail our mixtures to each other. Eavesdroppers are free to inspect them, but they probably can’t unmix the liquids. Even if they detect cherry or vanilla, they cannot extract or identify the exact composition of the flavorings we used without investing prohibitive time and resources.

4. Shared secret: I take the vanilla cola you sent to me and add the correct amount of my secret cherry flavoring. You take the cherry cola I sent to you and add your secret amount of vanilla flavoring.

Because the order in which we mix liquids doesn’t matter, we end up with identical final beverages: cherry-vanilla cola. We now have a shared secret formula. Eavesdroppers have full access to the base liquid, my cherry cola and your vanilla cola, but no trivial combination of these liquids can create our exact formula. They could try to mix the cherry cola and vanilla cola, but the proportions won’t be right. A vanilla flavoring–base liquid mix blended with a cherry flavoring–base liquid mix does not have the same proportions as the secret recipe, which is vanilla flavoring + cherry flavoring + base liquid. Note that we don’t even know each other’s private ingredients, yet we now share a common secret.

Instead of shipping sloshing liquids, computers use mathematical operations that are easy to compute yet difficult to reverse. Imagine that we publicly share some base number called b (akin to the carbonated water with cola syrup). Then I pick a secret number called n (my cherry flavoring), and you pick your own secret number called m (vanilla). I compute bⁿ, and you compute b^m. We send these numbers to each other (akin to our cherry cola and vanilla cola, respectively). I receive b^m and raise that number to the nth power, whereas you receive bⁿ and raise it to the mth power. Both actions result in the same number: b^nm. So we have agreed on a final number without sharing our private numbers directly.

There’s a problem with this method, however: if an eavesdropper sees the two numbers b and bⁿ, that person could simply pull out a calculator and plug them into the logarithm function to compute the exponent n, blowing all the secrecy. Exponentiation (raising one number to the power of another) is not a one-way function, because logarithms (the inverse of exponentiation) are easy to compute. Diffie and Hellman’s insight was that logarithms are not necessarily easy to compute for modular arithmetic, the math of remainders. If c and p are both whole numbers, then the expression c (mod p) is equal to the remainder after you divide c by p. For instance, if c = 15 and p = 12, then c (mod p) is 3 because 15 divided by 12 equals 1 with a remainder of 3. It’s sometimes called clock math because we encounter it when we compute times. If it’s 10:00 on a standard 12-hour clock, and then five hours pass, the time doesn’t become 15:00. It wraps around the 12-hour circle to 3:00. When doing arithmetic with times, you always compute the result mod 12, and 15 (mod 12) is 3.

Diffie-Hellman’s key-exchange method runs this kind of exponentiation protocol, with all the operations conducted in this way using a large prime number in the mod operation. Here’s how it works:

1. Public base: We publicly announce a prime number p and a base number b.

2. Private computations: I pick a secret number n and compute bⁿ (mod p), or the remainder after raising b to the power of n and then dividing it by the large prime number p. Separately, you pick a secret number m and compute b^m (mod p).

3. Exchange: We send the results of our calculations to each other. Eavesdroppers are free to inspect them.

4. Shared secret: I raise what you sent me to the nth power, and you raise what I sent you to the mth power. We both compute the result mod p, or the remainder after dividing by that prime number. Our calculations will yield the same number: b^nm (mod p), our shared secret.

Now eavesdroppers will have a hard time deducing our result, b^nm (mod p), given the public information: p, b, bⁿ (mod p) and b^m (mod p). The task of deducing n when given b, p and bⁿ (mod p) is called the discrete logarithm problem, and it’s an entirely different beast from standard logarithms. For an intuitive sense of why, notice that the function 5^x behaves in predictable ways as we plug in values for x: 5² = 25, 5³ = 125, 5⁴ = 625. As we increment x, the output grows by exactly five times. In modular arithmetic, the “wrapping around” adds a chaotic element that’s much harder to understand. Here are the results using mod 17: 5² (mod 17) = 8, 5³ (mod 17) = 6, 5⁴ (mod 17) = 13. The outputs seem to bounce around randomly with no particular ties to their inputs. To the best of our knowledge, this aspect makes the discrete logarithm problem prohibitively time-consuming to solve when n, m and p are huge (in practice, n and m run about 80 digits long, and the prime p comes in at around 600 digits).

Diffie-Hellman rests on one of the few candidates that computer scientists have for a one-way function—an operation that is easy to compute but hard to reverse. Yet, remarkably, the difficulty of solving the discrete logarithm problem remains unproven. The fastest known method for solving it would take supercomputers many millennia to complete, and eavesdroppers don’t have that kind of time. But perhaps people just haven’t been clever enough to devise a faster solution. The whole of modern Internet security rests on unproven assumptions. Despite the trillions of dollars in banking transactions and government secrets protected by Diffie-Hellman, no hacker or intelligence agency has found a shortcut.

There is a looming exception, however. We know how to break it in theory with quantum computers. In 1994 theoretical computer scientist Peter Shor, then a researcher at AT&T, discovered an algorithm that exploits the strange properties of quantum mechanics to crack the discrete logarithm problem in hours rather than eons. The only thing preventing it is engineering. Humanity hasn’t yet built a quantum computer stable and powerful enough to run the code. Conversions to “postquantum cryptography” are underway, but until they’re complete, Diffie-Hellman will still protect your secrets.