Working Mod n²

Some public-key systems work on a clock of size n² instead of n. This lesson shows the trick that makes that useful: powers of 1 + n, the L function, and how the secret λ wipes out the random part.

1

Why square the modulus?

Most systems work mod n or mod a prime. A few work mod n2 (or mod p2) instead, because that bigger clock hides a neat trick: some powers become easy to undo, but only for someone who knows the secret primes. You can spot these systems by their size. Ciphertexts mod n2 are about twice as long as n.

The trick needs three ideas, one per section below.

2

The shortcut: powers of 1 + n

Multiply out (1 + n)m and every term after the second contains n2 or more, so mod n2 they all vanish:

(1 + n)^m = 1 + m·n + (terms with n², n³, …) ≡ 1 + m·n (mod n²) example, n = 7: 8^3 = 512 = 10 × 49 + 22, and 1 + 3 × 7 = 22 ✓

So a power of 1 + n, which would normally be hard to undo, wears its exponent on the outside: subtract 1, divide by n, and there's m (mod n). This is why the base is so often chosen as g = n + 1.

3

The L function

That “subtract 1, divide by n” step has a name:

L(u) = (u − 1) / n an ordinary whole-number division

It only makes sense when u is 1 more than a multiple of n, and then it reads off the exponent from the previous section: L((1 + n)m mod n2) = m mod n. For n = 7: L(22) = 21 / 7 = 3.

4

Wiping out the random number

Encryption mixes in a random number r as rn, so the same message never gives the same ciphertext twice. The receiver removes it by raising to λ = lcm(p − 1, q − 1), which only someone who knows p and q can work out:

(r^n)^λ = r^(n·λ) ≡ 1 (mod n²)

This is Euler's idea again, on the bigger clock: mod n2, every number that shares no factor with n returns to 1 after n × λ steps (or a divisor of it). So the random part turns into 1 and drops out, and what's left is a power of 1 + n, which section 2 undoes.

Worked example with p = 7, q = 11: n = 77, n2 = 5929, g = 78, λ = lcm(6, 10) = 30. The message m = 42 with random r = 23 encrypts to c = 3840.

23^(77 × 30) mod 5929 = 1 the random part is gone 3840^30 mod 5929 = 2157 = 1 + 28 × 77 so L(c^λ) = 28 28 = 42 × 30 mod 77 that's m × λ (mod n) multiply by λ⁻¹ mod 77 (= 18): 28 × 18 mod 77 = 42 = m ✓

That last multiplier is the μ in the Paillier worksheet. With g = n + 1 it's just λ−1 mod n; with another g it also undoes g's own exponent.

5

The same trick mod p2

The trick also works on a clock of size p2 for a single secret prime p. Raising to p − 1 (Fermat's exponent) leaves a number that's 1 more than a multiple of p, so L(x) = (x − 1) / p reads off an exponent mod p. Anything that was raised to a multiple of p beforehand, like a random hr where h = gn and n is a multiple of p, turns into 1 and drops out.

Worked example with p = 7, p2 = 49, g = 2, and a ciphertext c = 310:

2^6 mod 49 = 15 = 1 + 2 × 7 b = L(15) = 2 310^6 mod 49 = 8 = 1 + 1 × 7 a = L(8) = 1 m = a × b⁻¹ mod 7 = 1 × 4 mod 7 = 4 (2 × 4 = 8 ≡ 1, so b⁻¹ = 4)

Here a message can only be smaller than p, about a third as long as the public key when the key is p2 × q.

Check yourself
  1. Without a calculator, what is 64 mod 25? (6 = 1 + 5.)
    Show answer

    1 + 4 × 5 = 21. Check: 64 = 1296 = 51 × 25 + 21.

  2. With n = 5, what is L(21)?
    Show answer

    (21 − 1) / 5 = 4, the exponent from the first question.

  3. Why can't an eavesdropper just raise c to λ too?
    Show answer

    λ = lcm(p − 1, q − 1) needs the secret primes. Without them, the random part can't be wiped out, so the eavesdropper has to factor n first.