Nib asked
How does public key encryption work?
Anyone can lock a message with your public key, but only your private key can unlock it, because the maths is easy to do forwards and brutal to undo.
8 steps, drawn by Nib. Read it here, or watch him draw it. Updated .
1the problem
Two people who have never met need to share a secret over a channel an eavesdropper can fully read. Classic ciphers need a shared secret key first, which is the very thing they lack.
Sharing a secret key over a tapped wire looks impossible.
2open padlocks
Picture Bob handing out identical open padlocks. Snapping one shut needs no key, so anyone can do it. Only Bob holds the key that opens them.
A lock anyone can close and only one person can open.
3lock and key
Alice locks her message with Bob's padlock and sends it. Eve holds the same padlock, yet she cannot open it. Only Bob's private key can.
a common mix-upThe public key is not a secret code you reverse. It only locks; it cannot unlock what it locked.
4easy forwards
RSA rests on a one-way street. Multiplying two large primes is quick; recovering the primes from their product is, as far as anyone knows, extremely slow.
Multiplying is easy; un-multiplying is hard.
5huge numbers
With four digits you can still guess the factors. Real keys use a product of about 617 digits, 2048 bits, and no known method on today's ordinary computers can unpick that.
6toy RSA
Take primes 61 and 53, so n is 3233. Pick e as 17. The public key is the pair 3233 and 17. Encrypting 65 means computing 65 to the 17th power, then taking the remainder after dividing by 3233, which gives 2790.
7unlock
Bob's private number d equals 2753 comes from the secret primes 61 and 53. Raise 2790 to that power, take the remainder, and 65 returns.
a common mix-upEve knows n, e and 2790, but getting d means factoring n. The key is not hidden by obscurity; it is hidden by hard maths.
8the whole idea
Browsers use public-key methods to agree on a short session key, then switch to fast symmetric encryption such as AES for the actual data.
Public key delivers a secret; a fast shared key carries the conversation.
a common mix-upPublic-key encryption does not usually encrypt your whole conversation. It hands over a short secret, and fast symmetric encryption does the rest.
Anyone can lock, only you can unlock, and the whole trick is a maths problem that runs easily one way and not the other.