How RSA works
RSA uses two keys. The public key locks a message and anyone can have it. The private key unlocks it, and only the receiver should have it. The two are linked by a calculation that's easy one way and very hard the other.
Making the keys
- Pick two secret prime numbers, p and q, and multiply them: n = p × q. The number n is public.
- Work out φ(n) = (p − 1) × (q − 1), read "phi of n". It's the count of numbers below n that share no factor with it, and it's what lets the two exponents cancel out.
- Pick a public exponent e that shares no factor with φ(n). Almost everyone uses e = 65537. The pair (n, e) is the public key.
- Find the private exponent d: the number where e × d leaves remainder 1 when divided by φ(n). That's written d = e−1 mod φ(n) and called the inverse of e.
Locking and unlocking
- The message is turned into a number m smaller than n.
- Encrypt: c = me mod n. ("mod n" means "the remainder after dividing by n".)
- Decrypt: m = cd mod n. This works because e × d is one more than a multiple of φ(n), and Euler's theorem says raising to a multiple of φ(n) brings you back to 1.
Why it's safe, and why a puzzle isn't
Everyone can see n and e. Getting d needs φ(n), which needs p and q, which means splitting n back into its two primes. For the 600-digit n used in real life, no computer on Earth can do that. For the 40 or 50 digits a puzzle can use, this page does it in about a second, and that's the step that breaks the puzzle open.
The whole thing with tiny numbers
What the puzzle gives you
An RSA puzzle gives a public key, the pair n and e, plus a ciphertext c. Paste each one into its own box. Spaces and line breaks are fine.
Often labelled N, "modulus", or just "public key". It's the two secret primes multiplied together, and usually the longest number in the puzzle.
Almost always short: 65537 is by far the most common, and 3 and 17 turn up too. It's the power the message was raised to.
The locked message, as a number. It's always smaller than n, and usually about as long.
Already know p and q, or d?
Some puzzles hand you part of the private key. Fill in what you have and the worksheet uses it instead of working it out.
Split n into p × q
This is the step RSA is built to make impossible: finding the two primes that multiply to n. At puzzle size, a computer can do it.
How does this page factor n?
First it tries dividing by every small prime, which catches typos fast, since a mistyped n usually has small factors. Then it tries Fermat's method, which is instant when p and q are close together. If neither works, it runs a quadratic sieve. The sieve collects hundreds of numbers made only of small primes, then combines them into a pair of squares that gives up a factor.
The sieve's running time grows fast with the size of n: about a second at 45 digits, tens of seconds at 55, years at 120, and far longer than the age of the universe at real-world sizes.
φ(n): the number that links the keys
With p and q known, Euler's totient is quick: φ(n) = (p − 1) × (q − 1).
φ or λ? Why two people can get different d values
Some write-ups use the Carmichael function λ(n) = lcm(p − 1, q − 1) in place of φ(n). It's a smaller number that does the same job, so the d it gives is smaller too. Both d values decrypt every message to exactly the same answer, so neither one is wrong.
The private exponent d
d is the inverse of e modulo φ(n): the number that makes e × d leave remainder 1 when divided by φ(n). The extended Euclidean algorithm finds it.
Show the extended Euclidean algorithm
Divide, keep the remainder, and repeat until the remainder is 0, the same way you'd find a greatest common divisor. If the last non-zero remainder is 1, e and φ(n) share no factor and d exists. Working back up these rows gives d.
Decrypt: m = cd mod n
Raise the ciphertext to the private exponent and keep the remainder after dividing by n. With numbers this size, the page does it by repeated squaring, which takes a few hundred multiplications instead of an impossible number.
Read the message
m is a number, and the puzzle decides how it turns back into words or coordinates. Try the readings below. If the puzzle says how the message was encoded, use that one.
If none of these look like anything
Decryption scrambles everything when even one digit of an input is off, so a wrong input doesn’t give a slightly wrong answer; it gives noise. Recount the digits of each number against the puzzle (the counts are shown next to every box).
If the inputs are right, the message may use a different encoding: the puzzle text usually says which one. Lining the blocks up from the end, or skipping some digits first, helps when a short message is tacked onto something else.
If every digit matches the puzzle and every reading is still noise, you may be using the wrong system. Check that the puzzle really describes this one: what it calls each number, how many public numbers it gives, and how it says the message was locked.