RSA

MATH 195

Algebraic Setup

We begin with a theorem from group theory:

Theorem (Lagrange). If G is a finite group, #G = n < ∞, then for all g ∈ G, one has g^{n} = e.

Quick proof, G abelian. Fix g ∈ G, then G → G by x ↦ gx is bijective (the map x ↦ g^{−1}x is its inverse. Hence

∏_{y∈G} y = ∏_{x∈G}(gx) = g^{n} ∏_{x∈G} x

so e = g^{n}. □

Special case: Let k be a finite field, #k = q. Then for all α ∈ k^{∗}, α^{q−1} = 1. Apply Lagrange’s theorem to G = k^{∗} = k \ {0}. Including α = 0, we have for all α ∈ k, α^{q} = α.

Example. If k = 𝔽_{p} = ℤ/pℤ, for p prime, then a^{p} = a for all a ∈ ℤ/pℤ, in other words, we have the (little) theorem of Fermat: for all integers a ∈ ℤ, a^{p} ≡ a (mod p) for p prime.

Notice that for all a ∈ (ℤ/pℤ)^{∗}, a^{p−1} = 1, a^{2(p−1)} = 1, and so on, so that a^{ℓ} = 1 if ℓ ≡ 0 (mod p − 1). Then for all a ∈ ℤ, and all m ∈ ℤ_{≥0} such that m ≡ 1 (mod p − 1), a^{m} ≡ a (mod p).

Proposition. Let p and q be two prime numbers, p ≠ q, and put n = pq. Then for all positive integers m ≡ 1 (mod lcm(p − 1, q − 1)) and all a ∈ ℤ/nℤ, one has a^{m} = a (in ℤ/nℤ), which is to say

a^{m} ≡ a (mod n)

for all integers a.

Recall that the least common multiple of integers k and ℓ is the smallest positive integer divisible both by k and by ℓ. For example, lcm(12, 18) = 36. Note that lcm(k, ℓ) = kℓ/ gcd(k, ℓ). Note then that if m ≡ 1 (mod (p−1)(q −1)), then m ≡ 1 (mod lcm(p − 1, q − 1)).

This proposition is the backbone of the RSA cryptosystem.

Proof. Take a ∈ ℤ. Then m ≡ 1 (mod p − 1), since lcm(p − 1, q − 1) | (m − 1) but by definition (p − 1) | lcm(p − 1, q − 1). So by Fermat’s little theorem, a^{m} ≡ a (mod p) which is to say p | (a^{m} − a). The same is true for q, so q | (a^{m} − a). Hence n = pq | (a^{m} − a), since it is divisible by these distinct primes, and hence a^{m} ≡ a (mod n). □

This is some of the material covered February 26, in Math 195: Cryptography, taught by Hendrik Lenstra, prepared by John Voight jvoight@math.berkeley.edu.

Remark. We can get this from Lagrange’s theorem. We take G = (ℤ/nℤ)^{∗}. We have

#G = ϕ(n) = ϕ(pq) = ϕ(p)ϕ(q) = (p − 1)(q − 1).

Therefore for all a ∈ (ℤ/nℤ)^{∗}, a^{(p−1)(q−1)} ≡ 1 (mod pq). But this only gives us the statement for the product (p − 1)(q − 1), and only for elements a ∈ (ℤ/nℤ)^{∗}.

Example. Take p = 5, q = 7, and lcm(p−1, q −1) = lcm(4, 6) = 12. Take m = 13 ≡ 1 (mod 12), and a = 2, then 2^{13} ≡ 2 (mod 35), hence 5 · 7 | 8190 = 2 · 3^{2} · 5 · 7 · 13.

Note that for all m ≡ 1 (mod p − 1), 2^{m} ≡ 2 (mod p), so 2^{13} ≡ 2 (mod p) for every prime p for which (p−1) | 12, i.e. p−1 = 1, 2, 3, 4, 6, 12, or p = 2, 3, 4, 5, 7, 13, but 4 is not prime, so we could have known already that 2 · 3 · 5 · 7 · 13 | 8190.

RSA Cryptosytem

Recall we have Alice sending a message to Bob, with Eve listening.

The RSA-system is a block cipher, P = C = ℤ/nℤ for an integer n = pq, where n (the modulus) is known to everybody, but the prime factors p, q are known only to Bob. We need in practice p and q to be very large (over 100 digits, say). We take K to be the set of positive integers relatively prime to lcm(p − 1, q − 1). The encryption key e ∈ K is known to everyone, but the decryption key d ∈ K is known only to Bob. Then Alice encrypts:

E : P × K → C
E(a, e) = a^{e} (mod n)

Eve knows a^{e}, e, and n, but does not know a.

To decrypt, Bob

D : C × K → P
D(b, e) = b^{d} (mod n)

where ed ≡ 1 (mod lcm(p − 1, q − 1)).

Claim. For all a, e, D(E(a, e), e) = a, since

D(E(a, e), e) = D(a^{e}, e) = (a^{e})^{d} = a^{de} ≡ a (mod n)

by the proposition.

Warning: Given n = pq, and a multiple of lcm(p − 1, q − 1), one can compute p and q. For example, in the special case that we are given ϕ(n) = (p − 1)(q − 1) = pq − p − q + 1, we note that

(x − p)(x − q) = x^{2} − (p + q)x + pq = x^{2} − (n + 1 − ϕ(n))x + n.

is a polynomial which gives the values of p and q by the quadratic formula. Therefore the secrets are in some sense equivalent: knowing p, q is equivalent to knowing ϕ(n), and vice versa.

Why is prime factorization a difficult problem? Only a historical one: it is an age-old problem, for centuries people have been thinking about it, but no fast methods have been arrived upon.