RSA: prime numbers
13 × 17 = 221. You work that out in your head. Get handed 221 and the question which two primes those were, and you have to try: 3? 7? 11? 13, got it. A minute's work. Make them numbers of 300 digits and that minute becomes longer than the universe is old — while the multiplication still takes a fraction of a second. RSA is built on that lopsidedness.
Words you might need
- Prime number
- A number that is only divisible by 1 and by itself: 2, 3, 5, 7, 11, 13… The further you look, the rarer they get, but they never stop — Euclid proved that well over two thousand years ago.
- Factorising
- Breaking a number back down into the primes it is built from. 221 becomes 13 × 17. That's the sum RSA has to make impossible.
- Trapdoor function
- A calculation that goes easily forwards and impossibly backwards — unless you know a secret, and then it works after all. Like a trapdoor: straight in, never out again, except if you know where the latch is.
- OAEP
- The padding that gets put with the message before encrypting: random bytes according to a fixed recipe. Without that padding the same message always gives the same ciphertext, and that's a leak — the same problem as a missing IV in chapter 4.
How it works, without the formulas
- Your computer picks two enormous primes and keeps them secret.
- It multiplies them. Everyone may see that product; it sits in your public key.
- Encrypting is a calculation with that product — clock arithmetic, as in chapter 5, but on a clock with hundreds of digits round its face.
- Decrypting is the same kind of calculation, but for it you need the two primes themselves. You have those, and nobody else.
So whoever has your public key has the product. To decrypt, he has to factorise it. That's possible — in theory. It just takes too long, and that is the entire security. No lock at all, only a sum that nobody can finish.
Try it yourself
The key pair is made in your browser and disappears as soon as you close this tab. You're welcome to look at the private key here: it was made for this page and isn't used for anything. With a real key you never do that.
- Click Make a key pair. That takes a moment: your computer is looking for two primes. You'll see your public key — that block of text you may give to anyone.
- Click Show the private key. Compare the two blocks: the private one is well over four times as long. Below it are p and q, the two primes from step 1, and the product that sits in your public key.
- Click Encrypt with the public key. The ciphertext is always exactly 256 bytes, however short your message is.
- Click Decrypt with the private key. Your message comes back.
- Now paste a long text into the message field — a couple of paragraphs — and encrypt. It won't work. Read why.
Why you ran into a wall
RSA with a 2048-bit key can only encrypt 190 bytes. That isn't a setting you can turn up: the message has to stay smaller than the number being calculated with. A bigger key barely helps and makes everything slower. So asymmetric encryption is not made for sending messages.
What is it for, then? For two things: sending someone a fresh AES key without arranging anything beforehand, and signing. That second one is what chapter 7.1 is about. How it all comes together, chapter 7.3.
But first something nicer. RSA calculates with primes of 600 digits. There's a more elegant way that achieves the same thing with far smaller numbers: calculating with points on a curved line. It's in your ID card, in your browser, and in Bitcoin. The next chapter lets you click on it.
How big does such a key have to be
| Key | That's a number of | Verdict |
|---|---|---|
| RSA-1024 | 309 digits | too small, advised against for years |
| RSA-2048 | 617 digits | today's standard |
| RSA-4096 | 1234 digits | roomier, and noticeably slower |
That slowness is no detail. Making a key pair takes a noticeably long time — you saw that with the first button — because your computer has to keep searching until it finds two primes. And every doubling of the key length makes the arithmetic about eight times heavier. That's exactly why the world is moving to curves, and that's chapter 6.2.
This is math: prime numbers as a one-way street
Multiplying and factorising are each other's opposite, and yet one direction is trivial and the other impassable. The best algorithm we know for factorising a 617-digit number — the number field sieve — would keep every computer in the world together busy for longer than the universe has existed. Not because it can't be done, but because it takes too long.
And note what that says: the best algorithm we know. Nobody has proved that factorising is hard. If a fast way is found tomorrow, RSA falls over the same day. That's not doom-mongering but how the field works: the security of the internet rests on problems of which we only know that an awful lot of clever people failed to solve them. This is number theory, the subject that for centuries was called "useless but beautiful".