How Two Mathematicians Solved A Cryptography Mystery

On October 30, 1942, a group of destroyer warships from nan British Royal Navy hunted down a Nazi submarine adjacent nan Nile Delta. The warships pounded nan submarine pinch underwater explosions until it floated to nan surface, wherever it started filling pinch h2o and sinking. As its German unit scrambled to escape, 3 British heroes—Lieutenant Anthony Fasson, sailor Colin Grazier and 16-year-old canteen adjunct Tommy Brown—did thing that defied each instinct. They jumped from their vessel onto nan sinking alloy and climbed inside.

They were aft nan sub’s astir valuable cargo: not weapons, not prisoners, but books. The pages contained codes for tuning nan Nazi “Enigma machine” that allowed nan German forces to pass successful secret. Deep wrong nan flooding commanding officers’ quarters, nan men seized nan volumes earlier nan water-soluble ink dissolved into nan sea. Only nan teen made it retired alive. Less than 2 months later English mathematician Alan Turing’s squad of codification breakers utilized nan codes to decipher Nazi messages, an effort estimated to person shortened nan warfare by 2 years, redeeming millions of lives.

Cryptography is nan mathematics of communicating successful secret, and it’s arsenic precocious stakes arsenic mathematics gets. The submarine communicative and dozens much for illustration it item a catch-22 that plagued cryptography for millennia: to speak successful code, you must first work together connected a code. If I want to nonstop you a missive but distrust my message carrier, I tin encrypt my connection pinch a cipher. Snoops won’t beryllium capable to publication it, but neither will you. If I nonstop a follow-up statement explaining nan cipher, nan message bearer tin intercept that, too—we’re correct backmost wherever we started. Called nan key-distribution problem, this cryptography pitfall seems to connote that to found a backstage connection channel, we efficaciously request privateness to statesman with.

On supporting subject journalism

If you're enjoying this article, see supporting our award-winning publicity by subscribing. By purchasing a subscription you are helping to guarantee nan early of impactful stories astir nan discoveries and ideas shaping our world today.

This conundrum is why nan history of cryptography sounds little for illustration a mathematics textbook and much for illustration a spy thriller. Lacking a mathematical solution to nan key-distribution problem, nan world relied connected beingness ones: clandestine meetings, equipped couriers and occasional heists connected sinking submarines. Then, successful 1976, Stanford University researchers Whitfield Diffie and Martin Hellman proposed a solution that seemed to defy logic. Their method allowed 2 strangers to work together connected a shared concealed moreover erstwhile each their communications were retired successful nan unfastened for anybody to intercept and read. Their protocol, now known arsenic Diffie-Hellman cardinal exchange, has go a information workhorse of nan modern Internet. Every clip you cheque your slope balance, shop online, nonstop a WhatsApp connection aliases sojourn immoderate “https” website, immoderate type of Diffie-Hellman is astir apt securing nan connection.

By nan clip of Diffie and Hellman, cryptographers knew really to encrypt documents by scrambling messages truthful they looked for illustration gibberish to anyone who didn’t person a concealed cardinal consisting of a ample random number. So nan nonsubjective for Diffie and Hellman’s scheme, including successful present-day uses, is to make a azygous ample random number that only nan sender and receiver know. With that number, they tin usage known methods to encrypt and decrypt messages.

Diffie-Hellman’s captious instrumentality relies connected a mathematical “one-way function,” an cognition that is easy to execute but computationally infeasible to reverse. Consider Coca-Cola’s famously concealed formula. Mixing ingredients is easy, but moreover pinch entree to nan vanished product, chemists person problem reconstructing a cleanable transcript of nan beverage. Here’s really you and I tin guarantee that nan concealed chemic concoctions we navigator up successful our homes are identical to 1 another, assuming we are communicating only via message pinch snooping postal workers inspecting our shipments:

1. Public base: We work together connected a communal starting liquid, say, 1 liter of carbonated h2o mixed pinch a cola syrup. We denote this publicly, truthful eavesdroppers cognize nan guidelines liquid, too.

2. Private mixtures: I take a homemade cherry flavoring arsenic my concealed ingredient, and I show nary 1 astir it. I operation it pinch nan guidelines liquid to make a cherry cola. You besides take a concealed ingredient: a homemade vanilla flavoring. You operation it pinch nan guidelines successful your room to make vanilla cola.

3. Exchange: We message our mixtures to each other. Eavesdroppers are free to inspect them, but they astir apt can’t unmix nan liquids. Even if they observe cherry aliases vanilla, they cannot extract aliases place nan nonstop creation of nan flavorings we utilized without investing prohibitive clip and resources.

4. Shared secret: I return nan vanilla cola you sent to maine and adhd nan correct magnitude of my concealed cherry flavoring. You return nan cherry cola I sent to you and adhd your concealed magnitude of vanilla flavoring.

Because nan bid successful which we operation liquids doesn’t matter, we extremity up pinch identical last beverages: cherry-vanilla cola. We now person a shared concealed formula. Eavesdroppers person afloat entree to nan guidelines liquid, my cherry cola and your vanilla cola, but nary trivial operation of these liquids tin create our nonstop formula. They could effort to operation nan cherry cola and vanilla cola, but nan proportions won’t beryllium right. A vanilla flavoring–base liquid operation blended pinch a cherry flavoring–base liquid operation does not person nan aforesaid proportions arsenic nan concealed recipe, which is vanilla flavoring + cherry flavoring + guidelines liquid. Note that we don’t moreover cognize each other’s backstage ingredients, yet we now stock a communal secret.

Instead of shipping sloshing liquids, computers usage mathematical operations that are easy to compute yet difficult to reverse. Imagine that we publically stock immoderate guidelines number called b (akin to nan carbonated h2o pinch cola syrup). Then I prime a concealed number called n (my cherry flavoring), and you prime your ain concealed number called m (vanilla). I compute bn, and you compute bm. We nonstop these numbers to each different (akin to our cherry cola and vanilla cola, respectively). I person bm and raise that number to nan nth power, whereas you person bn and raise it to nan mth power. Both actions consequence successful nan aforesaid number: bnm. So we person agreed connected a last number without sharing our backstage numbers directly.

There’s a problem pinch this method, however: if an eavesdropper sees nan 2 numbers b and bn, that personification could simply propulsion retired a calculator and plug them into nan logarithm usability to compute nan exponent n, blowing each nan secrecy. Exponentiation (raising 1 number to nan powerfulness of another) is not a one-way function, because logarithms (the inverse of exponentiation) are easy to compute. Diffie and Hellman’s penetration was that logarithms are not needfully easy to compute for modular arithmetic, nan mathematics of remainders. If c and p are some full numbers, past nan look c (mod p) is adjacent to nan remainder aft you disagreement c by p. For instance, if c = 15 and p = 12, past c (mod p) is 3 because 15 divided by 12 equals 1 pinch a remainder of 3. It’s sometimes called timepiece mathematics because we brushwood it erstwhile we compute times. If it’s 10:00 connected a modular 12-hour clock, and past 5 hours pass, nan clip doesn’t go 15:00. It wraps astir nan 12-hour circle to 3:00. When doing arithmetic pinch times, you ever compute nan consequence mod 12, and 15 (mod 12) is 3.

Diffie-Hellman’s key-exchange method runs this benignant of exponentiation protocol, pinch each nan operations conducted successful this measurement utilizing a ample premier number successful nan mod operation. Here’s really it works:

1. Public base: We publically denote a premier number p and a guidelines number b.

2. Private computations: I prime a concealed number n and compute bn (mod p), aliases nan remainder aft raising b to nan powerfulness of n and past dividing it by nan ample premier number p. Separately, you prime a concealed number m and compute bm (mod p).

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

4. Shared secret: I raise what you sent maine to nan nth power, and you raise what I sent you to nan mth power. We some compute nan consequence mod p, aliases nan remainder aft dividing by that premier number. Our calculations will output nan aforesaid number: bnm (mod p), our shared secret.

Now eavesdroppers will person a difficult clip deducing our result, bnm (mod p), fixed nan nationalist information: p, b, bn (mod p) and bm (mod p). The task of deducing n erstwhile fixed b, p and bn (mod p) is called nan discrete logarithm problem, and it’s an wholly different beast from modular logarithms. For an intuitive consciousness of why, announcement that nan usability 5x behaves successful predictable ways arsenic we plug successful values for x: 52 = 25, 53 = 125, 54 = 625. As we increment x, nan output grows by precisely 5 times. In modular arithmetic, nan “wrapping around” adds a chaotic constituent that’s overmuch harder to understand. Here are nan results utilizing mod 17: 52 (mod 17) = 8, 53 (mod 17) = 6, 54 (mod 17) = 13. The outputs look to bounce astir randomly pinch nary peculiar ties to their inputs. To nan champion of our knowledge, this facet makes nan discrete logarithm problem prohibitively time-consuming to lick erstwhile n, m and p are immense (in practice, n and m tally astir 80 digits long, and nan premier p comes successful astatine astir 600 digits).

Diffie-Hellman rests connected 1 of nan fewer candidates that machine scientists person for a one-way function—an cognition that is easy to compute but difficult to reverse. Yet, remarkably, nan trouble of solving nan discrete logarithm problem remains unproven. The fastest known method for solving it would return supercomputers galore millennia to complete, and eavesdroppers don’t person that benignant of time. But possibly group conscionable haven’t been clever capable to devise a faster solution. The full of modern Internet information rests connected unproven assumptions. Despite nan trillions of dollars successful banking transactions and authorities secrets protected by Diffie-Hellman, nary hacker aliases intelligence agency has recovered a shortcut.

There is simply a looming exception, however. We cognize really to break it successful mentation pinch quantum computers. In 1994 theoretical machine intelligence Peter Shor, past a interrogator astatine AT&T, discovered an algorithm that exploits nan unusual properties of quantum mechanics to ace nan discrete logarithm problem successful hours alternatively than eons. The only point preventing it is engineering. Humanity hasn’t yet built a quantum machine unchangeable and powerful capable to tally nan code. Conversions to “postquantum cryptography” are underway, but until they’re complete, Diffie-Hellman will still protect your secrets.