Capstone — Building a Toy RSA Implementation
Number Theory & Cryptographic Math
Chapter 10 · Capstone — Building a Toy RSA Implementation
One continuous project, touching every chapter of this course in the order a real implementation actually needs them: generate real primes, build a real key pair, encrypt and decrypt a real word, measure the real cost of doing it the slow way versus the fast way — then, finally, sit in the attacker's seat and try to break the exact system just built.
| Step | Task | Chapter(s) used |
|---|---|---|
| 1 | Generate and verify two real primes | Ch.6 (primality testing) |
| 2 | Compute the modulus and totient | Ch.2, Ch.8 |
| 3 | Choose a valid public exponent | Ch.4 (GCD check) |
| 4 | Compute the private exponent | Ch.5 (extended Euclidean algorithm) |
| 5-6 | Encrypt and decrypt a real word | Ch.3, Ch.7, Ch.8 (correctness) |
| 7 | Measure fast vs. naive exponentiation, on this exact key | Ch.7 |
| 8 | Attempt to break the system: factor n back into p, q | Ch.1 (the core asymmetry), Ch.6 |
Step 1 — Generate and Verify Two Real Primes
Larger primes than Chapter 9's own toy example (p=11, q=13), still small enough to trace by hand: candidates 211 and 223.
211: no divisor found across 13 trial divisions (up to √211 ≈ 14.5) — prime. 223: no divisor found across 13 trial divisions (up to √223 ≈ 14.9) — prime.
Step 2 — Compute the Modulus and Totient
n = 211 × 223 = 47,053. φ(n) = (211−1)(223−1) = 210 × 222 = 46,620.
Step 3 — Choose a Valid Public Exponent
Testing candidates against Chapter 4's own GCD check, gcd(e, 46620) = 1:
e=7: gcd(7, 46620) = 7 — rejected. e=5: gcd(5, 46620) = 5 — rejected. e=3: gcd(3, 46620) = 3 — rejected. All three fail because 46,620 genuinely is divisible by 3, 5, and 7 — this isn't a contrived example, it's what actually happens when φ(n) is checked against small, tempting exponent choices.
e=17: gcd(17, 46620) = 1 — accepted.
Step 4 — Compute the Private Exponent
Running the extended Euclidean algorithm on (17, 46620):
d = 38,393. Check: 17 × 38393 mod 46620 = 652,681 mod 46620 = 1. Public key: (n=47053, e=17). Private key: (n=47053, d=38393).
Steps 5-6 — Encrypt and Decrypt a Real Word
Encoding "RSA" letter by letter (A=1, B=2, ... Z=26), encrypting each letter's code independently with c = m^e mod n, then decrypting with m = c^d mod n:
R=18 → c=25621 → decrypted=18. S=19 → c=16608 → decrypted=19. A=1 → c=1 → decrypted=1. Reassembled: "RSA" — the exact original word, recovered letter for letter.
A (code 1) encrypted to 1 — completely unchanged. This isn't a bug specific to this key: 1^e mod n = 1 for any public exponent and any modulus, since multiplying 1 by itself never changes it. Real RSA implementations pad messages specifically to avoid ever encrypting a raw, small, predictable value like 1 — a genuine, small weakness this toy version inherits by not bothering with padding, named here rather than swept under the rug.
Step 7 — Fast Exponentiation's Real Payoff, on This Exact Key
Chapter 7 proved O(log b) beats O(b) in the abstract. Here it is, measured on the actual d=38,393 this project just generated:
m^38393 mod n): naive approach needs 38,393 multiplications; fast exponentiation needs 26. Encryption (m^17 mod n): naive needs 17; fast needs 7. This toy key's own private exponent alone would take a naive implementation over a thousand times longer than the fast one to use even once.
Step 8 — The Security Audit: Try to Break What Was Just Built
Switching seats: given only the public key (n=47053, e=17) — exactly what an attacker would see — how much work does factoring n back into p and q actually take, with no shortcuts?
211 × 223 to build n in Step 2: one operation. Trial-dividing 47,053 back down to find its smaller factor, with no prior knowledge: 210 trial divisions, before the factor 211 is finally found. A 210× asymmetry — on a modulus barely five digits long. Real RSA moduli are hundreds of digits long, where this exact same asymmetry, scaled up, is what makes factoring genuinely infeasible rather than merely inconvenient.
What This Course Doesn't Cover
As stated honestly back in Chapter 1: a full academic number theory curriculum, elliptic-curve cryptography, the discrete logarithm problem in depth, and post-quantum cryptography were all named as deliberately out of scope, and stayed out of scope through all ten chapters. This course built the specific number-theoretic machinery RSA needs — divisibility, modular arithmetic, GCDs, modular inverses, primality, fast exponentiation, and the totient/Fermat/Euler theorems — not an exhaustive tour of either field.
Where This Course Connects
This course is the mathematical foundation underneath Security's own crypto1 (Cryptography Fundamentals) and https1 (HTTPS/TLS Fundamentals), both of which use RSA and public-key cryptography operationally without deriving the number theory behind them — this course is that derivation, made concrete on real (if small) numbers throughout. Algorithms & Complexity's own growth-rate and recursion machinery was used directly in Chapters 4 and 7; Discrete Mathematics Fundamentals' own direct-proof style was the template for Chapter 8's Fermat's Little Theorem proof.
Hands-On Exercises
Verify whether 227 is prime using trial division, showing the search bound and the total number of trial divisions needed.
Using this chapter's own φ(n)=46,620, check whether e=19 is a valid public exponent choice. If it is, compute the corresponding private exponent d using the extended Euclidean algorithm, and verify ed ≡ 1 (mod φ(n)).
Explain, in your own words, why m=1 is only one example of a broader category of "predictable" messages a real RSA system needs to guard against — specifically, is m=0 also a problem? What about a value of m equal to the modulus n itself? Reason from first principles (what does m^e mod n actually compute in each case), not just this chapter's own m=1 example.
Chapter 10 Quick Reference
- Full worked project: real verified primes (Ch.6) → n, φ(n) (Ch.2, Ch.8) → a rejected-then-accepted e (Ch.4) → d via extended Euclid (Ch.5) → encrypt/decrypt a real word (Ch.3, Ch.7, Ch.8) → fast-vs-naive cost measured on this exact key (Ch.7) → factor n back to break it (Ch.1, Ch.6)
- Three exponent candidates (3, 5, 7) were genuinely rejected before finding a valid one — a real outcome, not a staged example
1^e mod n = 1always — a real, honestly-named reason production RSA pads messages before encrypting- Fast exponentiation cut this project's own decryption cost from 38,393 multiplications to 26
- Factoring this project's own 5-digit modulus took 210× the work of building it — the exact asymmetry Chapter 1 opened with, now measured on real numbers from this project
- Course complete — Number Theory & Cryptographic Math, 10 chapters, from divisibility to a working (if small) RSA implementation