Nib asked
How does encryption work with prime numbers?
The primes do not scramble your message. They are a secret ingredient that is easy to multiply together and, for huge ones, practically impossible to pull apart again.
8 steps, drawn by Nib. Read it here, or watch him draw it. Updated .
1the trapdoor
In RSA the two secret primes are multiplied to get a public number n. Anyone can check the product, but recovering the primes from n is the hard part.
Easy to multiply two primes; hard to unmultiply.
a common mix-upPrimes are not the cipher itself. They are the hidden ingredient behind the public number n, and the encryption is arithmetic done with n.
2how big
RSA-250, 829 bits and 250 digits, was factored in February 2020 using about 2,700 core-years. A 2048-bit modulus is about 617 digits, far beyond that.
Record factored: 250 digits. Real keys: 617 digits.
3clock maths
Modular arithmetic means counting around a loop and keeping only the remainder. RSA works on a clock with n positions, here 3233.
Wrap-around arithmetic: 14 mod 12 = 2.
4the n-hour clock
In real R-S-A the clock has n hours: 3233 of them in our toy. Every locking and unlocking is just a jump around that clock.
5key recipe
Choose primes p and q. Publish n = p times q and a number e that shares no factor with (p-1)(q-1). The private number d satisfies e times d leaves remainder 1 when divided by (p-1)(q-1).
The private key is built from (p-1)(q-1), which needs the primes.
6why it works
Because e times d equals 1 plus a multiple of (p-1)(q-1), Euler's theorem makes raising to e then to d return the original message.
7why safe
Eve sees only 3233 and 17. Getting 3120 means knowing 61 and 53, and computing it is as hard as factoring n. That is where the primes protect you.
a common mix-upNobody has proven factoring is hard; it is just that no one has found a fast method in decades of trying.
8the whole idea
So: two secret primes make a public n, clock arithmetic does the locking, and the primes are the trapdoor. A future quantum computer could break it, so new schemes are coming.
a common mix-upRSA's safety is not proven; it rests on no known fast factoring method for ordinary computers. A large quantum computer running Shor's algorithm could break it.
Primes are not the lock, they are the hidden hinge: easy to multiply, practically impossible to pull apart.