Go further · Chapter 13 · 13a · Real-world case
How does public-key encryption work?
The short answer (tap to open)
Public-key encryption gives you two keys: a public one anyone can use to lock a message, and a private one only you can use to unlock it. RSA's security rests on how hard it is to split a huge number into its two prime factors. Elliptic-curve keys rest on a similar one-way problem. Shor's algorithm undoes both.
What problem does public-key encryption solve?
Two strangers on the internet need to share a secret key without ever meeting. Before the 1970s you needed a courier with a locked briefcase. Public-key encryption does it with maths: like an open padlock you hand out freely. Anyone can snap it shut on a message; only you have the key that opens it.
How does RSA work, with tiny numbers?
- Pick two primes. Toy version: 3 and 11. Multiply them: 33. That's part of the public key.
- Pick a public "locking" number: 3.
- Work out a private "unlocking" number that undoes it. For these numbers it's 7. Finding it is easy if you know 3 and 11, and very hard if you only know 33.
- Lock a message, say 4: multiply 4 by itself 3 times (64) and keep the remainder after dividing by 33: 31.
- Unlock: multiply 31 by itself 7 times and keep the remainder after dividing by 33: you get back 4.
Real RSA uses primes hundreds of digits long. Multiplying them is instant; splitting the product back into its primes would take ordinary computers far longer than the age of the universe. That gap is the whole of RSA's security.
Public: 33 and 3. Private: 7.
Checking every possible factor at a billion tries a second: instantly
Illustrative: real attacks are cleverer than checking every factor, but real RSA numbers have hundreds of digits.
The worked example, in words
- Pick two primes, 3 and 11. Multiply them: 33. That's part of the public key.
- The public locking number is 3. The private unlocking number is 7.
- Lock the message 4: 4 × 4 × 4 = 64, which leaves 31 after dividing by 33.
- Unlock: multiply 31 by itself 7 times and keep the remainder after dividing by 33: 4 again.
- Digits in the public number: 4. Checking every possible factor at a billion tries a second: instantly.
- Digits in the public number: 20. Checking every possible factor at a billion tries a second: 10 seconds.
- Digits in the public number: 40. Checking every possible factor at a billion tries a second: 3,170 years.
- Digits in the public number: 617. Checking every possible factor at a billion tries a second: longer than the age of the universe.
Illustrative: real attacks are cleverer than checking every factor, but real RSA numbers have hundreds of digits.
What are elliptic-curve keys?
Elliptic-curve cryptography uses points on a special curve. Starting from a fixed point, you "add" it to itself a secret number of times by hopping across the curve in a precise way. Hopping forward is easy; working out how many hops someone made, from where they landed, is very hard. It gives the same security as RSA with much smaller keys, so it's everywhere: secure websites, phones, messaging apps and cryptocurrencies such as Bitcoin.
What does a quantum computer change?
Both hard problems hide a repeating pattern, and Shor's algorithm finds such patterns using interference (page 7a). So a large enough error-corrected quantum computer would break both RSA and elliptic-curve keys. Chapter 13 covers how large, how soon, and the switch to new maths that quantum computers can't break.
Check
Two quick ones
Collect
Your aha card
Padlocks made of maths.
Easy to snap shut, hard to open without the key, until a large quantum computer finds the hidden pattern.
Next optional page · 13b
What is post-quantum cryptography, and when must we switch?
Next optional page