Paillier · Tools of the Trade

How Paillier works two minutes, with tiny numbers

Pascal Paillier's system is built on factoring, like RSA, but it works modulo n², so its ciphertexts are about twice as long as the public key. It has an unusual property: multiplying two ciphertexts gives an encryption of the sum of their messages.

Making the keys

Pick two secret primes p and q, and publish n = p × q.
Publish a base g as well. It's very often just n + 1.
Privately work out λ = lcm(p − 1, q − 1), the least common multiple.

The L function

Decryption uses a small helper: L(u) = (u − 1) / n, an ordinary whole-number division. Raising anything to the power λ modulo n² always leaves a number that's 1 more than a multiple of n, so the division comes out exact, and the answer carries the message.

Locking and unlocking

Encrypt: pick a random r and send c = g^m × rⁿ mod n².
Work out μ = L(g^λ mod n²)⁻¹ mod n, the inverse modulo n.
Decrypt: m = L(c^λ mod n²) × μ mod n. Raising to λ wipes out the random r completely, which is why it never needs to be known.

The whole thing with tiny numbers

p = 7, q = 11 → n = 77, n² = 5929, g = n + 1 = 78 λ = lcm(6, 10) = 30 L(g^λ mod n²) = 30, μ = 30⁻¹ mod 77 = 18 (30 × 18 = 540 = 7 × 77 + 1) encrypt m = 42 with r = 23: c = 78^42 × 23^77 mod 5929 = 3840 decrypt: L(3840^30 mod 5929) = 28, m = 28 × 18 mod 77 = 42 ✓

Step 1

What the puzzle gives you

A Paillier puzzle gives a public key (n, g) 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

The private key: `λ` and `μ`

λ is the least common multiple of p − 1 and q − 1. μ undoes the effect of g.

Step 4

Decrypt: `m = L(c^λ mod n²) × μ mod n`

Raise c to λ modulo n², apply L, and multiply by μ.

Step 5

Read the message

m is a number, and the puzzle decides how it turns back into words or coordinates. If the puzzle says how the message was encoded, use that reading.

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.