Rabin

A guided worksheet for Michael O. Rabin’s cryptosystem. Paste the numbers in, and it explains what each one is, checks it fits, and does the big-number math, from factoring to the four candidate messages. Nothing leaves this page; your work is saved in this browser only.

How the Rabin cryptosystem works two minutes, with tiny numbers

Michael O. Rabin's system is about the simplest public-key system there is: to lock a message you square it. Unlocking means finding a square root, which is easy only if you know how the public number splits into primes.

Making the keys

  1. Pick two secret primes, p and q. They're usually chosen so each leaves remainder 3 when divided by 4, because that makes square roots easy later.
  2. Multiply them: n = p × q. The number n is the whole public key. There's no exponent to choose.

Locking and unlocking

  1. Encrypt: c = m2 mod n. ("mod n" means "the remainder after dividing by n".)
  2. Decrypt by working modulo each prime separately. Modulo p, a square root of c is c(p+1)/4 mod p. That shortcut comes from Euler's criterion: since c is a square, c(p−1)/2 is 1, so (c(p+1)/4)2 = c × c(p−1)/2 = c. Do the same modulo q.
  3. Each prime gives two roots, a value and its negative. The Chinese Remainder Theorem (CRT) glues one root from each prime into a number modulo n, so there are four possible messages.
  4. Only one is the real message. Senders usually make it recognizable, for example with an agreed start. In a puzzle, it's normally the only one that reads as anything.

Why it's safe, and why a puzzle isn't

Taking square roots modulo n is exactly as hard as factoring n. For real key sizes nobody can do it. For a 40- or 50-digit n, this page factors it in about a second.

The whole thing with tiny numbers

p = 7, q = 11 → n = 77 (7 and 11 both leave remainder 3 when divided by 4) encrypt m = 20: c = 20² mod 77 = 400 mod 77 = 15 root mod 7: 15^((7+1)/4) mod 7 = 1 → ±1 → 1 or 6 root mod 11: 15^((11+1)/4) mod 11 = 9 → ±9 → 9 or 2 CRT: −3 × 7 + 2 × 11 = 1 (Euclid finds −3 and 2) r = (−3·7·9 + 2·11·1) mod 77 = 64 s = (−3·7·9 − 2·11·1) mod 77 = 20 candidates: 64, 77 − 64 = 13, 20, 77 − 20 = 57 → the message is 20 ✓
Step 1

What the puzzle gives you

A Rabin puzzle gives one public number n and a ciphertext c. Paste each one into its own box. Spaces and line breaks are fine.

Already know p and q?

If the puzzle hands you the private primes, fill them in and the worksheet uses them instead of factoring.

Step 2

Split n into p × q

This is the step the system is built to make impossible. At puzzle size, a computer can do it.

    Step 3

    A square root of c for each prime

    Working modulo one prime at a time turns a hard square root into an easy one.

      Step 4

      Combine them: four candidates

      The Chinese Remainder Theorem builds the numbers modulo n that match one root modulo p and one root modulo q. Two choices for each prime make four candidates.

      Show the extended Euclidean algorithm for p and q

      Euclid's algorithm finds whole numbers yp and yq with yp × p + yq × q = 1. Those two numbers are what the CRT step uses.

        Step 5

        Read the candidates

        Pick a candidate and try the readings. Only one candidate is the message. The puzzle should say how the message was encoded, and the right candidate is usually the only one that reads as anything.

        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.