Lesson 16: Number Theory Recap and the RSA Cryptosystem¶
16.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Apply modular arithmetic, the Euclidean and extended Euclidean algorithms, and compute modular inverses.
- State and use Euler's totient function, Fermat's little theorem and Euler's theorem.
- Perform RSA key generation, encryption and decryption and prove correctness.
- Perform fast modular exponentiation by square-and-multiply.
- State the RSA security assumption and identify precisely what a quantum computer breaks.
16.2 Modular Arithmetic¶
Definition. \(a \equiv b \pmod n\) iff \(n \mid (a-b)\). The set \(\mathbb{Z}_n = \{0,1,\dots,n-1\}\) with addition and multiplication mod \(n\) forms a commutative ring.
Properties. If \(a\equiv b\) and \(c\equiv d \pmod n\) then
Definition (Multiplicative group).
is a group under multiplication mod \(n\). Its order is \(\phi(n)\).
GCD and the Euclidean algorithm¶
Runs in \(O(\log \min(a,b))\) steps — this is the fastest step in RSA and, crucially, it is classically efficient. Shor's algorithm depends on it.
Extended Euclidean algorithm. Finds \(x, y\) with
Modular inverse. If \(\gcd(a,n) = 1\) then \(ax + ny = 1\), so \(ax \equiv 1 \pmod n\), i.e. \(a^{-1} \equiv x \pmod n\).
Euler's totient function¶
| Case | Formula |
|---|---|
| \(n = p\) prime | \(\phi(p) = p - 1\) |
| \(n = p^k\) | \(\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)\) |
| \(n = pq\), \(p\ne q\) prime | \(\phi(pq) = (p-1)(q-1)\) |
| general, multiplicative | \(\phi(mn) = \phi(m)\phi(n)\) when \(\gcd(m,n)=1\) |
This is the trapdoor. Computing \(\phi(n)\) for \(n=pq\) is easy if you know \(p\) and \(q\), and is believed hard otherwise. In fact knowing \(\phi(n)\) and \(n\) lets you recover \(p,q\) by solving a quadratic — so computing \(\phi(n)\) is exactly as hard as factoring.
The two key theorems¶
Fermat's little theorem. For prime \(p\) and \(\gcd(a,p)=1\):
Euler's theorem. For \(\gcd(a,n)=1\):
Definition (Multiplicative order). \(\mathrm{ord}_n(a)\) is the smallest \(r > 0\) with \(a^r \equiv 1\pmod n\). By Lagrange's theorem, \(r \mid \phi(n)\).
Remember this definition — it is the entire target of Shor's algorithm (L17, L20).
16.3 Fast Modular Exponentiation¶
Computing \(a^e \bmod n\) naively by \(e\) multiplications is hopeless when \(e \sim 2^{2048}\). The square-and-multiply algorithm uses the binary expansion of \(e\):
function modexp(a, e, n):
result = 1
base = a mod n
while e > 0:
if e is odd: result = (result * base) mod n
base = (base * base) mod n
e = e >> 1
return result
Cost: \(O(\log e)\) modular multiplications, i.e. \(O(\log^3 n)\) bit operations with schoolbook multiplication.
On a quantum computer this same routine, made reversible, is the dominant cost of Shor's algorithm: modular exponentiation accounts for well over 90 % of the gates, and it is why factoring RSA-2048 is estimated to need millions of physical qubits.
16.4 The RSA Cryptosystem¶
Rivest, Shamir and Adleman, 1977.
Key generation¶
- Choose two large distinct primes \(p, q\) (1024 bits each for RSA-2048).
- Compute the modulus \(n = pq\) and \(\phi(n) = (p-1)(q-1)\).
- Choose a public exponent \(e\) with \(1 < e < \phi(n)\) and \(\gcd(e,\phi(n)) = 1\). (In practice \(e = 65537 = 2^{16}+1\) — few 1-bits, so encryption is fast.)
- Compute the private exponent \(d \equiv e^{-1} \pmod{\phi(n)}\) using the extended Euclidean algorithm.
- Public key: \((n, e)\). Private key: \((n, d)\). Discard \(p\), \(q\) and \(\phi(n)\) — they are as sensitive as \(d\).
Encryption and decryption¶
Proof of correctness¶
We must show \(m^{ed}\equiv m \pmod n\) for all \(m\).
By construction \(ed \equiv 1 \pmod{\phi(n)}\), so \(ed = 1 + k\phi(n)\) for some integer \(k\).
Case 1: \(\gcd(m,n) = 1\). Euler's theorem gives \(m^{\phi(n)}\equiv1\pmod n\), so
Case 2: \(\gcd(m,n) \ne 1\). Then \(p\mid m\) or \(q\mid m\) (not both, unless \(m\equiv0\)). Say \(p\mid m\) and \(q \nmid m\). Then \(m^{ed}\equiv 0 \equiv m\pmod p\). And mod \(q\), Fermat's little theorem gives \(m^{q-1}\equiv1\), and since \((q-1)\mid\phi(n)\),
By the Chinese Remainder Theorem, \(m^{ed}\equiv m \pmod{pq = n}\). \(\blacksquare\)
Digital signatures¶
Signing reverses the roles: \(\sigma = H(m)^{d}\bmod n\) (private key), verified by \(\sigma^{e} \stackrel{?}{=} H(m) \bmod n\) (public key), where \(H\) is a cryptographic hash. Both RSA encryption and RSA signatures fall to the same attack.
16.5 Security¶
The RSA assumption. Given \((n,e)\) and \(c = m^e\bmod n\), it is computationally infeasible to recover \(m\).
Equivalent-difficulty facts.
| Task | Difficulty |
|---|---|
| Factor \(n\) into \(p, q\) | assumed hard classically |
| Compute \(\phi(n)\) from \(n\) | equivalent to factoring |
| Compute \(d\) from \((n,e)\) | equivalent to factoring (randomised reduction) |
| Compute \(\mathrm{ord}_n(a)\) | equivalent to factoring (see L17) |
| Recover \(m\) from \(c\) (the RSA problem) | assumed hard; not proved equivalent to factoring |
Best classical attack. The General Number Field Sieve (GNFS):
— sub-exponential but super-polynomial. RSA-829 (829 bits) was factored in 2020 using about 2700 core-years.
Quantum attack. Shor's algorithm factors \(n\) in \(O((\log n)^3)\) quantum operations (L20). RSA at any key size is broken by a sufficiently large fault-tolerant quantum computer.
"Harvest now, decrypt later." An adversary can record encrypted traffic today and decrypt it once quantum computers mature. Any data that must stay secret for 15+ years should already be protected by post-quantum cryptography (L25). This is why NIST standardised ML-KEM and ML-DSA in August 2024.
16.6 Solved Problems¶
Problem 1 — Complete RSA key generation and message round-trip¶
Let \(p = 11\), \(q = 13\). Choose \(e = 7\). Compute \(n\), \(\phi(n)\), \(d\), then encrypt \(m = 9\) and decrypt the ciphertext.
Solution.
Step 1. \(n = 11\times13 = 143\).
Step 2. \(\phi(n) = (11-1)(13-1) = 10\times12 = 120\).
Step 3. Check \(\gcd(7,120)\): \(120 = 17\cdot7 + 1\), and \(7 = 7\cdot1+0\), so \(\gcd = 1\) ✓.
Step 4 — find \(d = 7^{-1}\bmod 120\) by the extended Euclidean algorithm:
So \(-17\cdot 7 \equiv 1 \pmod{120}\), giving
Verify: \(7\times103 = 721 = 6\times120 + 1\) ✓.
Keys: public \((143, 7)\); private \((143, 103)\).
Step 5 — Encrypt \(m = 9\): \(c = 9^{7}\bmod143\).
Step 6 — Decrypt: \(m = 48^{103}\bmod143\). Use square-and-multiply with \(103 = 1100111_2\).
Now \(103 = 64+32+4+2+1\):
The original message \(m = 9\) is recovered.
Problem 2 — Breaking small RSA by factoring¶
Given the public key \((n,e) = (3233, 17)\), recover the private key \(d\) and decrypt \(c = 2790\).
Solution.
Factor \(n = 3233\). Trial division: \(3233 / 53 = 61\) exactly. So \(p = 53\), \(q = 61\).
Find \(d = 17^{-1}\bmod3120\) by the extended Euclidean algorithm:
Back-substitute:
So \(-367\cdot17\equiv1\pmod{3120}\), giving
Verify: \(17\times2753 = 46801 = 15\times3120 + 1\) ✓.
Decrypt: \(m = 2790^{2753}\bmod 3233\). (This is the standard RSA-3233 textbook example.) Carrying out square-and-multiply gives
The point. The entire break took one factorisation. Everything after it is elementary. A quantum computer supplies exactly that one step.
Problem 3 — Order finding by hand¶
Compute \(\mathrm{ord}_{15}(7)\) and \(\mathrm{ord}_{21}(2)\).
Solution.
(a) \(\mathrm{ord}_{15}(7)\). \(\phi(15) = \phi(3)\phi(5) = 2\times4 = 8\), so \(r \mid 8\): candidates \(1,2,4,8\).
(b) \(\mathrm{ord}_{21}(2)\). \(\phi(21) = 2\times6 = 12\), so \(r\in\{1,2,3,4,6,12\}\).
Why this matters. Shor's algorithm computes exactly these numbers — but for \(n\) with 2048 bits, where classical search over the divisors of \(\phi(n)\) is impossible (you do not even know \(\phi(n)\)).
Problem 4 — Square-and-multiply, step by step¶
Compute \(5^{117}\bmod 19\) using square-and-multiply, and verify with Fermat's little theorem.
Solution.
Fermat's shortcut first. \(19\) is prime, so \(5^{18}\equiv1\pmod{19}\). Reduce the exponent mod 18:
Square-and-multiply on \(5^9\), \(9 = 1001_2\):
Verification. Since \(5^9\equiv1\), we have \(\mathrm{ord}_{19}(5) \mid 9\). Check \(5^3 = 125 = 6\times19 + 11 \equiv 11 \ne 1\), so the order is exactly 9. And \(9 \mid 18 = \phi(19)\) ✓, consistent with Lagrange's theorem.
Problem 5 — Why small primes and reused moduli are fatal¶
Two users share the modulus \(n = 3599\) but have different exponents. User A publishes \(e_A = 31\), user B publishes \(e_B = 37\). Show that either user can read the other's mail, and separately factor \(n\).
Solution.
Factoring \(n = 3599\). Note \(3599 = 3600 - 1 = 60^2 - 1^2 = (60-1)(60+1) = 59\times61\). So \(p = 59\), \(q = 61\).
(This is a Fermat factorisation: when \(p\) and \(q\) are close, \(n = a^2-b^2\) with \(a = \frac{p+q}{2} = 60\) and \(b = \frac{q-p}{2}=1\). Trying \(a = \lceil\sqrt n\rceil, \lceil\sqrt n\rceil+1,\dots\) and testing whether \(a^2 - n\) is a perfect square breaks such moduli instantly. Never choose \(p\) and \(q\) close together.)
The shared-modulus break. User A knows \(d_A\) with \(e_Ad_A \equiv 1\pmod{\phi(n)}\), so \(e_Ad_A - 1\) is a multiple of \(\phi(n)\). From this A can factor \(n\) (standard randomised reduction), recover \(\phi(n)\), and then compute
Here: \(d_B = 37^{-1}\bmod 3480\). Extended Euclid:
Verify: \(37\times1693 = 62641 = 18\times3480 + 1\) ✓.
Three design rules established.
- Never share a modulus between users.
- Never choose \(p, q\) close together (Fermat factorisation).
- \(p\) and \(q\) must be large (≥ 1024 bits each for RSA-2048).
But observe: none of these rules helps against Shor. A perfectly generated RSA-2048 key with distant, huge, unshared primes falls just as easily. Only changing the underlying mathematical problem — as post-quantum cryptography does (L25) — provides a defence.
16.7 Practice Problems¶
- Compute \(\phi(360)\). [Ans: 96]
- Find \(11^{-1}\bmod 26\). [Ans: 19]
- RSA with \(p=7,q=11,e=13\): find \(n\), \(\phi(n)\), \(d\); encrypt \(m=5\). [Ans: \(n=77\), \(\phi=60\), \(d=37\), \(c=26\)]
- Compute \(\mathrm{ord}_{35}(3)\). [Ans: 12]
- Compute \(7^{100}\bmod 13\) using Fermat. [Ans: \(7^{100}=7^{4}\equiv9\)]
- Factor \(n = 8051\) using Fermat's method. [Ans: \(8051 = 90^2 - 7^2 = 83\times97\)]
- Explain why \(e=65537\) is the near-universal choice.
- Why must \(p\) and \(q\) be discarded after key generation?
16.8 Summary¶
- \(\mathbb{Z}_n^*\) has order \(\phi(n)\); for \(n = pq\), \(\phi(n) = (p-1)(q-1)\).
- Euler's theorem: \(a^{\phi(n)}\equiv1\) for \(\gcd(a,n)=1\). Order: the least \(r\) with \(a^r\equiv1\); \(r\mid\phi(n)\).
- RSA: \(n = pq\), \(ed\equiv1\pmod{\phi(n)}\), \(c = m^e\), \(m = c^d\); correctness follows from Euler + CRT.
- Modular exponentiation costs \(O(\log^3 n)\) classically and dominates the gate count of Shor's algorithm quantumly.
- Computing \(\phi(n)\), computing \(d\), and computing \(\mathrm{ord}_n(a)\) are all equivalent to factoring.
- Classical best: GNFS (sub-exponential). Quantum: Shor, polynomial — RSA falls at every key size.
- "Harvest now, decrypt later" makes migration to post-quantum cryptography urgent today.
Next lesson: L17 — The factorisation attack on RSA and the reduction to order finding.
Practise now: unit2-algorithms-lab.html → RSA Workbench: generate keys from primes you
choose, encrypt/decrypt messages, and watch the extended Euclidean algorithm run step by step.