Module 04: Number Theory and RSA

The number theory that makes RSA work, and the attacks that break it when the math is sloppy.

Prerequisites

After completing this module you will:

Implement the extended Euclidean algorithm and use it to compute modular inverses
Apply Euler's theorem and the Chinese Remainder Theorem
Generate RSA keys from first principles (prime selection, key pair computation)
Understand textbook RSA's limitations and why padding is essential

Work through these notebooks in order:

#	Notebook	What You'll Learn
a	Divisibility, GCD, and Euclid	The Euclidean algorithm and its correctness
b	Extended Euclidean Algorithm	Computing Bezout coefficients and modular inverses
c	Euler's Totient and Fermat's Theorem	Why a^phi(n) = 1 mod n and how RSA uses this
d	Chinese Remainder Theorem	Solving simultaneous congruences and CRT based RSA speedup
e	RSA Key Generation	Choosing primes, computing e and d, the full key generation process
f	RSA Encryption and Decryption	Textbook RSA in action and its pitfalls

Build these from scratch in rust/src/lib.rs:

#	Function	Description
1	`extended_gcd`	Extended Euclidean algorithm returning (gcd, x, y)
2	`mod_inverse`	Modular multiplicative inverse via extended GCD
3	`euler_totient`	Compute Euler's totient function for a given n
4	`rsa_keygen`	Generate an RSA key pair (n, e, d) from two primes
5	`rsa_encrypt_decrypt`	Textbook RSA encryption and decryption

Run: cargo test -p number-theory-rsa

Try these attacks in the break/ folder:

Hastad's broadcast attack: recover plaintext from multiple ciphertexts when e is small and no padding is used
Wiener's attack on small d: exploit a small private exponent via continued fractions
Factor N when |p - q| is small using Fermat's factorization method

See where this shows up in practice (in the connect/ folder):

RSA in TLS certificates and PKCS#1, where RSA signs the certificates that authenticate web servers
RSA-OAEP padding in practice, showing why textbook RSA is never used and how OAEP fixes it