Skip to content

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:

  1. Apply modular arithmetic, the Euclidean and extended Euclidean algorithms, and compute modular inverses.
  2. State and use Euler's totient function, Fermat's little theorem and Euler's theorem.
  3. Perform RSA key generation, encryption and decryption and prove correctness.
  4. Perform fast modular exponentiation by square-and-multiply.
  5. 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

\[ a+c \equiv b+d, \qquad ac \equiv bd, \qquad a^k \equiv b^k \pmod n . \]

Definition (Multiplicative group).

\[ \mathbb{Z}_n^{*} = \{a \in \mathbb{Z}_n : \gcd(a,n) = 1\} \]

is a group under multiplication mod \(n\). Its order is \(\phi(n)\).

GCD and the Euclidean algorithm

\[ \gcd(a,b) = \gcd(b,\ a \bmod b), \qquad \gcd(a,0) = a . \]

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

\[ ax + by = \gcd(a,b) \qquad \text{(Bézout's identity)} . \]

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

\[ \phi(n) = \big|\{k : 1\le k\le n,\ \gcd(k,n) = 1\}\big| \]
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\):

\[ a^{p-1}\equiv 1 \pmod p . \]

Euler's theorem. For \(\gcd(a,n)=1\):

\[ a^{\phi(n)}\equiv 1 \pmod n . \]

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

  1. Choose two large distinct primes \(p, q\) (1024 bits each for RSA-2048).
  2. Compute the modulus \(n = pq\) and \(\phi(n) = (p-1)(q-1)\).
  3. 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.)
  4. Compute the private exponent \(d \equiv e^{-1} \pmod{\phi(n)}\) using the extended Euclidean algorithm.
  5. Public key: \((n, e)\). Private key: \((n, d)\). Discard \(p\), \(q\) and \(\phi(n)\) — they are as sensitive as \(d\).

Encryption and decryption

\[ \text{Encrypt: } \ c = m^{e} \bmod n \qquad\qquad \text{Decrypt: } \ m = c^{d} \bmod n \]

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

\[ m^{ed} = m^{1+k\phi(n)} = m\cdot\left(m^{\phi(n)}\right)^{k} \equiv m\cdot 1^{k} = m \pmod n . \]

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)\),

\[ m^{ed} = m\cdot\left(m^{q-1}\right)^{k(p-1)} \equiv m \pmod q . \]

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):

\[ \exp\!\left(\left(\sqrt[3]{\tfrac{64}{9}} + o(1)\right)(\ln n)^{1/3}(\ln\ln n)^{2/3}\right) \]

— 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:

\[ 120 = 17\cdot 7 + 1 \quad\Longrightarrow\quad 1 = 120 - 17\cdot 7 \]

So \(-17\cdot 7 \equiv 1 \pmod{120}\), giving

\[ d \equiv -17 \equiv 103 \pmod{120} . \]

Verify: \(7\times103 = 721 = 6\times120 + 1\) ✓.

Keys: public \((143, 7)\); private \((143, 103)\).

Step 5 — Encrypt \(m = 9\): \(c = 9^{7}\bmod143\).

\[ 9^2 = 81 \]
\[ 9^4 = 81^2 = 6561 = 45\times143 + 126 \ \Rightarrow\ 9^4\equiv 126 \equiv -17 \pmod{143} \]
\[ 9^7 = 9^4\cdot9^2\cdot9 \equiv (-17)(81)(9) \pmod{143} \]
\[ (-17)(81) = -1377; \quad -1377 + 10\times143 = -1377+1430 = 53 \]
\[ 53\times9 = 477 = 3\times143 + 48 \ \Rightarrow\ c = \mathbf{48} \]

Step 6 — Decrypt: \(m = 48^{103}\bmod143\). Use square-and-multiply with \(103 = 1100111_2\).

\[ 48^1 \equiv 48 \]
\[ 48^2 = 2304 = 16\times143 + 16 \equiv 16 \]
\[ 48^4 \equiv 16^2 = 256 = 143 + 113 \equiv 113 \]
\[ 48^8 \equiv 113^2 = 12769 = 89\times143 + 42 \equiv 42 \]
\[ 48^{16}\equiv 42^2 = 1764 = 12\times143 + 48 \equiv 48 \]
\[ 48^{32}\equiv 48^2 \equiv 16 \]
\[ 48^{64}\equiv 16^2 \equiv 113 \]

Now \(103 = 64+32+4+2+1\):

\[ 48^{103}\equiv 113\cdot16\cdot113\cdot16\cdot48 \pmod{143} \]
\[ 113\cdot16 = 1808 = 12\times143 + 92 \equiv 92 \]
\[ 92\cdot113 = 10396 = 72\times143 + 100 \equiv 100 \]
\[ 100\cdot16 = 1600 = 11\times143 + 27 \equiv 27 \]
\[ 27\cdot48 = 1296 = 9\times143 + 9 \equiv \mathbf{9} \ \checkmark \]

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\).

\[ \phi(n) = 52\times60 = 3120 \]

Find \(d = 17^{-1}\bmod3120\) by the extended Euclidean algorithm:

\[ 3120 = 183\times17 + 9 \]
\[ 17 = 1\times 9 + 8 \]
\[ 9 = 1\times 8 + 1 \]

Back-substitute:

\[ 1 = 9 - 8 = 9 - (17 - 9) = 2\cdot9 - 17 \]
\[ = 2(3120 - 183\cdot17) - 17 = 2\cdot3120 - 367\cdot17 \]

So \(-367\cdot17\equiv1\pmod{3120}\), giving

\[ d \equiv -367 \equiv 2753 \pmod{3120} . \]

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

\[ m = \mathbf{65} . \]

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\).

\[ 7^1 = 7 \]
\[ 7^2 = 49 = 3\times15 + 4 \equiv 4 \]
\[ 7^4 \equiv 4^2 = 16 \equiv 1 \pmod{15} \]
\[ \boxed{\mathrm{ord}_{15}(7) = 4} \]

(b) \(\mathrm{ord}_{21}(2)\). \(\phi(21) = 2\times6 = 12\), so \(r\in\{1,2,3,4,6,12\}\).

\[ 2^1=2,\quad 2^2=4,\quad 2^3=8,\quad 2^4=16,\quad 2^6 = 64 = 3\times21+1 \equiv 1 \]
\[ \boxed{\mathrm{ord}_{21}(2) = 6} \]

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:

\[ 117 = 6\times18 + 9 \ \Longrightarrow\ 5^{117} \equiv 5^{9}\pmod{19} . \]

Square-and-multiply on \(5^9\), \(9 = 1001_2\):

\[ 5^1 \equiv 5 \]
\[ 5^2 = 25 \equiv 6 \]
\[ 5^4 \equiv 6^2 = 36 \equiv 36-19 = 17 \equiv -2 \]
\[ 5^8 \equiv (-2)^2 = 4 \]
\[ 5^9 = 5^8\cdot5^1 \equiv 4\times5 = 20 \equiv \mathbf{1} \pmod{19} \]

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.)

\[ \phi(n) = 58\times60 = 3480 \]

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

\[ d_B \equiv e_B^{-1} \pmod{\phi(n)} . \]

Here: \(d_B = 37^{-1}\bmod 3480\). Extended Euclid:

\[ 3480 = 94\times37 + 2, \qquad 37 = 18\times2 + 1 \]
\[ 1 = 37 - 18\times2 = 37 - 18(3480 - 94\times37) = 1693\times37 - 18\times3480 \]
\[ d_B \equiv \mathbf{1693} \pmod{3480} \]

Verify: \(37\times1693 = 62641 = 18\times3480 + 1\) ✓.

Three design rules established.

  1. Never share a modulus between users.
  2. Never choose \(p, q\) close together (Fermat factorisation).
  3. \(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

  1. Compute \(\phi(360)\). [Ans: 96]
  2. Find \(11^{-1}\bmod 26\). [Ans: 19]
  3. 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\)]
  4. Compute \(\mathrm{ord}_{35}(3)\). [Ans: 12]
  5. Compute \(7^{100}\bmod 13\) using Fermat. [Ans: \(7^{100}=7^{4}\equiv9\)]
  6. Factor \(n = 8051\) using Fermat's method. [Ans: \(8051 = 90^2 - 7^2 = 83\times97\)]
  7. Explain why \(e=65537\) is the near-universal choice.
  8. 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.