Nib asked, and Nib — askNib's tutor — drew the answer live at a whiteboard. This is the spoken transcript; enable JavaScript to watch it drawn.
how does public key encryption work
Alice wants to send Bob a secret, but they have never met, and every wire between them can be tapped. How do they agree on a secret in the open?
Here is the trick. Bob mails out open padlocks, as many copies as anyone wants. Anyone can snap one shut, but only Bob owns the 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.
Real padlocks are a picture. The maths version needs a trapdoor: easy in one direction, hopeless backwards. Multiplying two primes is easy.
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.
A toy version: the public key is n equals 3233 and e equals 17. Message 65 goes through a modular power and comes out as 2790.
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.
In practice, public-key maths is slow, so it only delivers a short fresh secret key. Then fast shared-key encryption handles the whole conversation.
Anyone can lock, only you can unlock, and the whole trick is a maths problem that runs easily one way and not the other.