Why do prime numbers keep your bank account safe?

The full story

This is the episode's narration, word for word. Headings jump to that point in the video.

Two halves of a puzzle 0:00

Last time we ended on a lock anyone can check but only you can close. To see how it works, start with a puzzle in two halves. First: what's 47 times 59? With a pencil, you'll have 2773 inside a minute. Second: two whole numbers, neither of them one, multiply to make 2773, so what are they? Same sum, run backwards, and suddenly you're guessing. That lopsided feeling is the idea that first put locks on the internet.

Numbers that won't split 0:37

It's 47 and 59, and both are prime. A prime divides only by one and itself, like 2, 3, 5 and 7, and one doesn't count. Every other whole number breaks into primes: 60 is two times two times three times five. And it breaks apart in exactly one way, which is called the fundamental theorem of arithmetic.

A one-way street 1:04

So 2773 hides exactly one pair. To find it, you divide by every prime up to its square root, and only the fifteenth you try, 47, works. But in 1977, using the fastest method its authors knew, at a million steps a second, a number 200 digits long would have taken about 3.8 billion years. Testing whether a number is prime is far quicker, so making locks is easy and picking them is hard. One honest catch: nobody has ever proved factoring is hard. It's a bet, backed by centuries of failed attempts.

The oldest problem in secrecy 1:49

For almost all of history, a secret message needed a secret key that both people shared first, often by courier. In 1976, at Stanford, Whitfield Diffie and Martin Hellman saw that problem growing. Cheap electronics were putting cryptography into what they called remote cash dispensers, or as we'd say, ATMs. How do two strangers agree on a key when anyone could be listening?

Split the key in two 2:19

Their paper, New Directions in Cryptography, opens: we stand today on the brink of a revolution in cryptography. The idea was to split the key in two: a locking key you print in a public directory, and a different unlocking key you keep. They didn't yet know how to build that. Ralph Merkle had found a different, partial answer. But Diffie and Hellman showed two people how to agree a shared secret in public, using powers on a kind of clock.

Clock arithmetic 2:52

Ten o'clock plus five hours is three o'clock: go round past twelve and keep what's left over. Now take powers of four on a 33-hour clock. Four, sixteen, then sixty-four, which wraps round to 31, then 25, then 1, and the cycle repeats. On a number line, powers climb smoothly, so you can work backwards; on the clock they jump around, and the trail goes cold.

Padlocks, and where the picture breaks 3:23

Picture it as padlocks. You hand out open padlocks and keep the only key: anyone can lock a box for you, but only you can open it. But the picture breaks. A real padlock can be cut, while this lock is only as strong as the bet that nobody finds a shortcut. A padlock can't sign anything, but this key, used the other way round, can. That's last episode's signature. And it's slow, so it was only ever meant to set up a small key, which then drives a fast, ordinary cipher.

Three at MIT 3:58

The paper set three researchers at MIT to work: Ron Rivest, Adi Shamir and Leonard Adleman. Their answer reached the journal on the fourth of April, 1977. The recipe: multiply two big secret primes and publish the product. To lock a message, raise it to a public power on a clock that size. To unlock, you need a secret power, and working it out needs the two primes. Their worked example used 47 and 59.

Toy keys 4:35

Take the primes 3 and 11; multiply them, and our clock has 33 hours. Take one less than each, 2 and 10, and multiply those: 20. Pick a locking power with no factor in common with 20, say 3. The unlocking power, times three, must land one past a multiple of 20, and three times seven is twenty-one, so it's 7. So your public key is 33 and 3, and your private key is 7.

Lock and unlock 5:09

Someone sends you the message 4. They cube it to get 64, which wraps round the 33-hour clock to 31, so they send 31. You raise 31 to the power of 7, which is over twenty-seven billion, and on the clock it lands on 4.

Why the lock opens 5:27

But why? On this clock, every number's powers cycle in a loop that fits evenly into 20, the number we built from the primes. Twenty-one is twenty, a whole number of laps, plus one step, right back where you started. That's Fermat's little theorem, extended by Euler. And to find 7 you needed 20, and for 20 you needed 3 and 11. Whoever can factor the clock size can make the private key.

A secret in Cheltenham 5:59

The twist: Britain's own code-makers had found much of this first, and kept it secret. James Ellis, who had Australian roots and grew up in London's East End, worked for GCHQ, Britain's signals agency. In January 1970 he wrote it up as a secret report, showing public-key encryption could exist, but not how to build it.

Half an hour 6:25

In September 1973, the mathematician Clifford Cocks joined GCHQ. As he later put it, from start to finish, it took me no more than half an hour. His note of November 1973 was, in Ellis's words, essentially the RSA algorithm. Early in 1974, by his own account, his colleague Malcolm Williamson found the way to agree a key that Diffie and Hellman would publish. Ellis said the two were identical, though Williamson only wrote it up in August 1976. By Simon Singh's account, computers then were too slow to make it practical.

Twenty-seven years of silence 7:09

On the eighteenth of December, 1997, Cocks finally told the story at a maths conference in Cirencester, England. Ellis had died a month earlier. So who gets the credit? Honestly, both teams. The British trio got there first on most of it, in secret, and in 2010 the engineers' body, the IEEE, honoured them. Diffie, Hellman and the MIT trio found it independently and published, so theirs is the version the world built on.

What your bank actually uses 7:46

So does your bank lock your login with RSA? In the newest version of the standard, no: TLS version 1.3, from 2018, dropped RSA for agreeing keys. Your browser and the bank do a Diffie–Hellman exchange instead, and every browser must be able to do it on an elliptic curve, a different kind of clock with a different hard problem. The certificate that proves the site really is your bank carries a signature, and the standard still requires browsers to check RSA signatures, alongside elliptic-curve ones. Then a fast cipher, usually one called AES, scrambles the actual data.

How big is big enough? 8:31

In 2020, a team of six researchers factored a challenge number 250 digits long, using about 2,700 years of computer-core time. The 200 digits the RSA paper recommended had already fallen, in 2005. Today's minimum is 2048 bits, about 617 digits, and Australia's cyber security guidance prefers 3072. An elliptic curve matches that with a key of just 256 bits.

Shor's shortcut 9:08

In 1994, Peter Shor showed that a quantum computer, a machine that didn't exist yet, could factor in a manageable number of steps. His trick uses clock cycles. On a 15-hour clock, powers of 7 go 7, 4, 13, 1, a cycle of four. Half of four is two, and 7 squared is 49. Its neighbours, 48 and 50, share the factors 3 and 5 with 15. The quantum part only finds the cycle length, which nobody knows how to do quickly on ordinary computers.

How worried should we be? 9:49

How close is that machine? In a 2024 draft, NIST, the American standards body, said no such machine exists yet. But estimates keep falling. In 2019, breaking a 2048-bit RSA key was estimated to need 20 million noisy qubits for 8 hours. By 2025, it was under a million, for under a week. Shor's method breaks elliptic curves too. The real worry is harvest now, decrypt later: record locked traffic today, and open it once the machine exists.

New locks 10:28

On the thirteenth of August, 2024, NIST published its first three post-quantum standards. The main one for agreeing keys, ML-KEM, uses lattice maths, and is believed secure even against a quantum computer. Believed, again, not proved. Australia's signals directorate says that, because of expected advances in quantum computing, RSA won't be approved beyond 2030. Caution pays: in 2022, a fourth-round candidate called SIKE was broken, its basic version in about ten minutes on a single processor core. So a new internet standard, published in August 2026, pairs both kinds of lock, safe as long as either one holds.

So why primes? 11:19

So why do primes keep your bank account safe? Because multiplying them is easy, splitting the product seems hard, and clock arithmetic hides the trail. That one-way street, found twice, once in secret, built the locks of the internet. Now the locks are moving to new maths, on the same bet: that nobody finds a shortcut. Primes are whole numbers that refuse to break down. But some numbers can't even be written down in full. So why does pi never end?

Sources

Every factual claim in the episode is tied to one of these. Spotted an error? Tell us.

1. R. L. Rivest, A. Shamir and L. Adleman, "A Method for Obtaining Digital Signatures and… — people.csail.mit.edu
2. OpenStax, Contemporary Mathematics, section 3.1 "Prime and Composite Numbers" — openstax.org
3. P. W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete… — arxiv.org
4. W. Diffie and M. E. Hellman, "New Directions in Cryptography", IEEE Transactions on… — ee.stanford.edu
5. E. Rescorla, RFC 8446, "The Transport Layer Security (TLS) Protocol Version 1.3",… — rfc-editor.org
6. J. J. O'Connor and E. F. Robertson, "Prime numbers", MacTutor History of Mathematics,… — mathshistory.st-andrews.ac.uk
7. J. H. Ellis, "The history of Non-Secret Encryption", CESG (released after the 1997… — cryptocellar.org
8. Simon Singh, "The Alternative History of Public-Key Cryptography", excerpt from The… — cryptome.org
9. IEEE History Center, "Milestones: Invention of Public-key Cryptography, 1969-1975",… — ethw.org
10. P. Sawer, "The unsung genius who secured Britain's computer defences and paved the way… — web.archive.org
11. E. Barker, NIST Special Publication 800-57 Part 1 Revision 5, "Recommendation for Key… — nvlpubs.nist.gov
12. Paul Zimmermann, "Integer factoring records" — members.loria.fr
13. F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann,… — caramba.loria.fr
14. Australian Signals Directorate, Information Security Manual, "Guidelines for… — cyber.gov.au
15. NIST IR 8547 (initial public draft), "Transition to Post-Quantum Cryptography… — csrc.nist.gov
16. NIST CSRC, publication page for NIST IR 8547 (Initial Public Draft), "Transition to… — csrc.nist.gov
17. C. Gidney and M. Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20… — arxiv.org
18. C. Gidney, "How to factor 2048 bit RSA integers with less than a million noisy… — arxiv.org
19. NIST news, "NIST Releases First 3 Finalized Post-Quantum Encryption Standards", 13… — nist.gov
20. NIST FIPS 203, "Module-Lattice-Based Key-Encapsulation Mechanism Standard", 13 August 2024 — csrc.nist.gov
21. W. Castryck and T. Decru, "An efficient key recovery attack on SIDH", IACR ePrint… — eprint.iacr.org
22. K. Kwiatkowski, P. Kampanakis, B. E. Westerbaan and D. Stebila, RFC 10024,… — rfc-editor.org

Researched and scripted with AI assistance, fact-checked claim by claim, with synthetic narration and diagrams drawn in code. How we make episodes.