Math Detours · Grade 10 · Around the corner · 6

RSA: a lock anyone can close

Encrypt a message with public numbers, decrypt with a private one, and do a whole round by hand with small primes.

Before this sheet: Fermat's little theorem and, if remainders are rusty, grade 6's Clock arithmetic.

Name ____________________Date ____________

Tonight's idea

Every time your phone talks to a bank, two machines that have never met agree on a secret while anyone can listen. The trick is a one-way street in arithmetic: multiplying two primes is easy, but recovering them from the product is slow. \(61 \times 53 = 3233\) takes seconds; factoring a 600-digit product would take longer than the age of the universe.

RSA (Rivest, Shamir and Adleman, 1977) turns that street into a padlock.

Alice publishes (n, e)public key: an open padlockBob sends c = mᵉ mod nanyone can lockAlice: cᵈ mod n = mprivate key d: only Alice opens
Who holds what. The eavesdropper sees n, e and c, never d.
  1. Pick two different primes \(p\) and \(q\). Let \(n = pq\) and \(\varphi = (p-1)(q-1)\).
  2. Pick \(e\) sharing no factor with \(\varphi\). Publish \((n, e)\): the public key, an open padlock.
  3. Find \(d\) with \(ed \equiv 1 \pmod{\varphi}\). Keep \(d\) secret: the private key.
  4. To send \(m \lt n\), anyone computes \(c = m^e \bmod n\). You compute \(c^d \bmod n\), and out comes \(m\).

Why does \(c^d\) give back \(m\)? Because \(ed = 1 + k\varphi\), so \(c^d = m \cdot (m^{p-1})^{k(q-1)}\), and by Fermat's little theorem that is \(\equiv m \pmod p\). The same works mod \(q\), and a number that is \(m\) mod both is \(m\) mod \(pq\) (exercise 4 does this with the numbers from the example). The eavesdropper sees \(n\), \(e\), \(c\). To find \(d\) they need \(\varphi\), and for that they need \(p\) and \(q\): the factoring problem.

Watch one: a round with \(p = 11\), \(q = 13\)

\(n = 143\), \(\varphi = 10 \times 12 = 120\). Choose \(e = 7\).

Find \(d\). \(120 = 17 \times 7 + 1\), so \(1 = 120 - 17 \times 7\), so \(7 \times (-17) \equiv 1 \pmod{120}\) and \(d = -17 \equiv 103\). Check: \(7 \times 103 = 721 = 6 \times 120 + 1\).

Encrypt \(m = 9\). Square and reduce as you go: \(9^2 = 81\); \(9^4 = 6561 \equiv 126\). Then \(9^7 = 9^4 \cdot 9^2 \cdot 9 \equiv 126 \times 81 \times 9\). \(126 \times 81 = 10206 \equiv 53\), and \(53 \times 9 = 477 \equiv 48\). So \(c = 48\).

Decrypt. Compute \(48^{103} \bmod 143\) the same way, squaring six times (up to \(48^{64}\)) and multiplying the pieces you need, and 9 comes back.

Your turn

  1. Verify \(7 \times 103 \equiv 1 \pmod{120}\). Then explain why \(e = 8\) would have been a bad choice.
  2. Encrypt \(m = 5\) with the public key \((143, 7)\). Find \(5^2\) and \(5^4\) mod 143 first, then combine.
  3. Break a weak key. A public key is \((221, 5)\). Factor 221, compute \(\varphi\), and find \(d\). This time the division takes two steps: \(192 = 38 \times 5 + 2\), then \(5 = 2 \times 2 + 1\). Write \(1 = 5 - 2 \times 2\), replace the 2 by \(192 - 38 \times 5\), and collect the 5s.
  4. In the example \(ed = 721 = 1 + 6 \times 120\). Use Fermat's little theorem to show \(m^{721} \equiv m \pmod{11}\) when 11 does not divide \(m\), and likewise mod 13. Why does that force \(m^{721} \equiv m \pmod{143}\)?

Try bigger keys, every squaring shown, at mathdetours.com/demos/rsa.html.

Stretch: agreeing a secret in public

Everyone agrees on \(p = 23\) and \(g = 5\). Alice picks a secret \(a = 6\) and shouts \(A = 5^6 \bmod 23\). Bob picks \(b = 15\) and shouts \(B = 5^{15} \bmod 23\). Compute \(A\) and \(B\). Then show that \(B^a\) and \(A^b\) agree mod 23. Why must they? What would an eavesdropper have to solve?

Answers

  1. \(7 \times 103 = 721 = 6 \times 120 + 1\). With \(e = 8\): \(\gcd(8, 120) = 8\), so \(8d\) is always a multiple of 8 and can never equal \(1 + 120k\), which is odd. No \(d\) exists, so nothing could be decrypted.
  2. \(5^2 = 25\), \(5^4 = 625 = 4 \times 143 + 53 \equiv 53\). \(5^7 \equiv 53 \times 25 \times 5\): \(53 \times 25 = 1325 \equiv 38\); \(38 \times 5 = 190 \equiv 47\). So \(c = 47\).
  3. \(221 = 13 \times 17\), \(\varphi = 12 \times 16 = 192\). \(192 = 38 \times 5 + 2\) and \(5 = 2 \times 2 + 1\). Back-substitute: \(1 = 5 - 2 \times 2 = 5 - 2(192 - 38 \times 5) = 77 \times 5 - 2 \times 192\). So \(d = 77\). Check: \(5 \times 77 = 385 = 2 \times 192 + 1\).
  4. Mod 11: \(m^{721} = m \cdot (m^{10})^{72} \equiv m \cdot 1^{72} = m\) by Fermat. Mod 13: \(m^{721} = m \cdot (m^{12})^{60} \equiv m\). So \(m^{721} - m\) is divisible by 11 and by 13, hence by 143. (If 11 divides \(m\), both sides are 0 mod 11, so it still holds.)

Stretch. \(5^2 \equiv 2\), \(5^4 \equiv 4\), so \(A = 5^6 \equiv 8\). \(5^8 \equiv 16\), so \(B = 5^{15} \equiv 16 \times 4 \times 2 \times 5 = 640 \equiv 19\). Alice: \(19^6 \equiv (-4)^6 = 4096 \equiv 2\) (since \(19 \equiv -4 \pmod{23}\)). Bob: \(8^2 \equiv -5\), \(8^4 \equiv 2\), \(8^8 \equiv 4\), so \(8^{15} \equiv 4 \times 2 \times (-5) \times 8 = -320 \equiv 2\). Same secret, 2, because \(B^a = 5^{ab} = A^b\). The eavesdropper knows \(5^a \equiv 8\) and must find \(a\): the discrete logarithm, which like factoring has no known fast method.

← PreviousNext: Multiplying is rotating →