rsa-key-generation.ipynb

Kernel: SageMath 10.0

Connect: RSA Key Generation

Module 01 | Real-World Connections

Every concept from this module shows up in RSA. Here's exactly where.

Introduction

You've learned about modular arithmetic, groups, generators, subgroups, and Lagrange's theorem. RSA uses all of these. Let's trace the connections.

$(\mathbb{Z}/n\mathbb{Z})^*$ Is the RSA Group

RSA operates in the multiplicative group of units modulo $n = pq$, where $p$ and $q$ are distinct primes. This is exactly the group $(\mathbb{Z}/n\mathbb{Z})^*$ that we studied in Module 01 --- the set of integers from $1$ to $n-1$ that are coprime to $n$, under multiplication.

# RSA setup: pick two primes
p, q = 61, 53
n = p * q
print(f'RSA modulus n = {p} * {q} = {n}')
print(f'The RSA group is (Z/{n}Z)*, the units mod n')
print(f'Group size: phi({n}) = {euler_phi(n)}')
print(f'Manual: ({p}-1)*({q}-1) = {(p-1)*(q-1)}')

$\varphi(n)$ = Group Size --- The Secret at the Heart of RSA

The order of the RSA group is $\varphi(n) = (p-1)(q-1)$.

This is the secret. Anyone can know $n$ (it's public), but computing $\varphi(n)$ requires knowing the factorization $n = pq$. Without $\varphi(n)$, you cannot compute the private key.

This is why RSA security reduces to the hardness of integer factorization: if you can factor $n$, you learn $p$ and $q$, compute $\varphi(n) = (p-1)(q-1)$, and recover the private key.

Key Generation

The key generation algorithm:

1. Choose $e$ coprime to $\varphi(n)$ --- this uses gcd from Module 01.

2. Compute $d = e^{-1} \bmod \varphi(n)$ --- this is a modular inverse, which exists precisely because $\gcd(e, \varphi(n)) = 1$.

phi_n = (p-1) * (q-1)
e = 17  # public exponent, must be coprime to phi_n
assert gcd(e, phi_n) == 1
d = inverse_mod(e, phi_n)  # private exponent
print(f'Public key:  (n={n}, e={e})')
print(f'Private key: d={d}')
print(f'Verification: e*d mod phi(n) = {(e*d) % phi_n}')

Encryption and Decryption

• Encrypt: $c = m^e \bmod n$

• Decrypt: $m = c^d \bmod n$

Both operations are modular exponentiation --- the same power_mod we used throughout Module 01.

m = 65  # message (must be < n)
c = power_mod(m, e, n)  # encrypt
m_recovered = power_mod(c, d, n)  # decrypt
print(f'Message:    m = {m}')
print(f'Ciphertext: c = m^e mod n = {c}')
print(f'Decrypted:  c^d mod n = {m_recovered}')
print(f'Success: {m == m_recovered}')

Why It Works: Euler's Theorem

Decryption works because of Euler's theorem, which says that for any unit $a \in (\mathbb{Z}/n\mathbb{Z})^*$:

$$a^{\varphi(n)} \equiv 1 \pmod{n}$$

Since $ed \equiv 1 \pmod{\varphi(n)}$, we can write $ed = 1 + k\varphi(n)$ for some integer $k$. Then:

$$c^d = (m^e)^d = m^{ed} = m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^k = m \cdot 1^k = m$$

This is exactly Lagrange's theorem in action: every element of a group, raised to the order of the group, gives the identity.

# Verify Euler's theorem directly
a = 42  # arbitrary unit
print(f'a = {a}')
print(f'a^phi(n) mod n = {power_mod(a, phi_n, n)}  (should be 1)')
print(f'e*d = {e*d} = 1 + {(e*d - 1) // phi_n} * {phi_n}')
print(f'a^(e*d) mod n = {power_mod(a, e*d, n)}  (should be {a})')

Concept Map: Module 01 $\to$ RSA

Module 01 Concept	RSA Application
$\mathbb{Z}/n\mathbb{Z}$	RSA works in $\mathbb{Z}/n\mathbb{Z}$ where $n = pq$
Units and $\varphi(n)$	$\varphi(n)$ determines key generation
Modular exponentiation	Encryption ($m^e$) and decryption ($c^d$)
gcd	Choosing $e$ coprime to $\varphi(n)$
Modular inverse	Computing private key $d = e^{-1} \bmod \varphi(n)$
Euler's theorem	Why decryption reverses encryption

What's Next

Module 04 builds all of this from scratch --- the extended Euclidean algorithm for computing inverses, a full proof of Euler's theorem, and a complete RSA implementation with proper padding and security analysis.

Summary

Concept	Key idea
RSA group	$(\mathbb{Z}/n\mathbb{Z})^*$, the multiplicative group of units mod $n = pq$
Group order $\varphi(n)$	$(p-1)(q-1)$ is the secret that enables key generation
Key generation	Uses gcd (to choose $e$) and modular inverses (to compute $d$)
Encryption and decryption	Both are modular exponentiation: $c = m^e$, $m = c^d$
Correctness	Follows from Euler's theorem: $a^{\varphi(n)} \equiv 1$

Every tool from this module, modular arithmetic, groups, orders, and Euler's theorem, is load-bearing in RSA. None of it was abstract for its own sake.