Goldwasser–Micali

A guided worksheet for the Goldwasser–Micali cryptosystem. Paste the numbers in, and it explains what each one is, checks it fits, and turns the list of ciphertext numbers back into bits and text. Nothing leaves this page; your work is saved in this browser only.

How Goldwasser–Micali works two minutes, with tiny numbers

Shafi Goldwasser and Silvio Micali's system encrypts one bit at a time, so a message turns into a long list of big numbers. Each number hides a single 0 or 1 in whether it's a square modulo the secret primes.

Squares modulo a prime

Modulo a prime p, half the numbers are squares (quadratic residues) and half aren't. Anyone who knows p can tell which in one step, using Euler's criterion: a(p−1)/2 mod p is 1 for a square and p − 1 (that is, −1) for a non-square. Modulo n = p × q, telling squares from non-squares without knowing p and q is believed to be as hard as factoring.

Making the keys

  1. Pick secret primes p and q, and publish n = p × q.
  2. Publish a number x that is not a square modulo p and not a square modulo q. To an outsider it looks like it could be a square.

Locking and unlocking

  1. For each bit, pick a random y. Send y2 mod n for a 0, or y2 × x mod n for a 1.
  2. To decrypt each number, check whether it's a square modulo p: square means 0, non-square means 1.
  3. String the bits together and read them, usually 8 at a time as ASCII.

The whole thing with tiny numbers

p = 7, q = 11 → n = 77. Squares mod 7: 1, 2, 4. Squares mod 11: 1, 3, 4, 5, 9. x = 6 (6 is not a square mod 7, and not a square mod 11) bit 1 with y = 3: c = 3² × 6 mod 77 = 54 bit 0 with y = 5: c = 5² mod 77 = 25 decrypt 54: 54 mod 7 = 5, not a square → 1 decrypt 25: 25 mod 7 = 4, a square → 0 ✓
Step 1

What the puzzle gives you

A Goldwasser–Micali puzzle gives a public key (n, x) and a list of ciphertext numbers, one for each bit of the message.

cipublic

Paste them all, in order. Separate them with spaces, commas, or line breaks. Each one is smaller than n, and there's one per bit, so a 3-letter message in 8-bit ASCII is 24 numbers.

    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

    Knowing p is what lets you tell squares from non-squares.

      Step 3

      Check x

      For the system to work, x must be a non-square modulo both primes.

        Step 4

        One bit per number

        For each ciphertext number c, work out c(p−1)/2 mod p. If it's 1, c is a square and the bit is 0. If it's p − 1, the bit is 1.

          Show every number
          Step 5

          Read the bits

          Group the bits into characters. 8 bits per character (ASCII) is the most common; the puzzle should say if it's different.