04f-rsa-encryption-decryption.ipynb

Kernel: SageMath 10.5

RSA Encryption and Decryption

Module 04 | 04-number-theory-rsa

The climax: everything from Module 04 comes together

---

Motivating Question: You can tell everyone your public key $(n, e)$. Anyone in the world can encrypt a message to you. But only you can decrypt it, using your secret $d$. How is this possible? What mathematical miracle makes one-way encryption a reality?

This notebook is the payoff for everything you have built in Module 04. Every tool you learned --- GCD, extended GCD, Euler's theorem, CRT, primality testing --- was a piece of the RSA puzzle. Now we assemble those pieces into a complete cryptosystem.

Objectives

By the end of this notebook you will be able to:

1. Perform RSA key generation, encryption, and decryption by hand on small examples.

2. Prove why RSA decryption recovers the original message (using Euler's theorem).

3. Identify three concrete attacks on textbook RSA and explain why padding (OAEP) is essential.

4. Implement RSA-CRT decryption and measure the speedup.

5. Apply RSA with realistic key sizes in SageMath.

Prerequisites

This notebook ties together all five previous notebooks in Module 04:

Notebook	What you learned	How RSA uses it
04a	GCD, Euclidean algorithm	Choosing $e$: verify $\gcd(e, \varphi(n)) = 1$
04b	Extended GCD, modular inverse	Computing $d = e^{-1} \bmod \varphi(n)$
04c	Euler's totient, Euler's theorem	Correctness proof: why $m^{ed} \equiv m$
04d	CRT, isomorphism	RSA-CRT optimization (4x decryption speedup)
04e	Primality testing, random_prime()	Generating safe primes $p, q$

If any of these feel shaky, revisit them now. You will need every single one.

Part 1: RSA Key Generation (Step by Step)

We will walk through key generation with small, hand-checkable numbers. The classic textbook example uses $p = 61$ and $q = 53$.

Step 1: Choose two distinct primes $p$ and $q$

In practice, we use random_prime() to find primes of 1024+ bits (notebook 04e). For learning, we pick small primes so you can verify every computation by hand.

# Step 1: Choose primes p and q
p = 61
q = 53

# Verify they are prime (notebook 04e: primality testing)
print(f"p = {p}, is_prime: {is_prime(p)}")
print(f"q = {q}, is_prime: {is_prime(q)}")

Step 2: Compute $n = p \cdot q$

The modulus $n$ is the product of our two primes. This is the number that is public --- everyone knows $n$. The security of RSA rests on the assumption that nobody can factor $n$ back into $p$ and $q$.

# Step 2: Compute the RSA modulus
n = p * q
print(f"n = p * q = {p} * {q} = {n}")

Step 3: Compute $\varphi(n) = (p-1)(q-1)$

Recall from notebook 04c: Euler's totient $\varphi(n)$ counts the integers in $\{1, \ldots, n\}$ that are coprime to $n$. For $n = pq$ with distinct primes:

$$\varphi(n) = \varphi(p) \cdot \varphi(q) = (p-1)(q-1)$$

This value is secret --- anyone who knows $\varphi(n)$ can compute the private key.

# Step 3: Compute Euler's totient (notebook 04c)
phi_n = (p - 1) * (q - 1)
print(f"phi(n) = (p-1)(q-1) = {p-1} * {q-1} = {phi_n}")

# Cross-check with SageMath's euler_phi
assert phi_n == euler_phi(n), "Mismatch!"
print(f"Verified: euler_phi({n}) = {euler_phi(n)}")

Step 4: Choose $e$ coprime to $\varphi(n)$

We need $1 < e < \varphi(n)$ with $\gcd(e, \varphi(n)) = 1$. This ensures $e$ has a modular inverse (notebook 04b: an inverse exists if and only if the GCD is 1). We will use $e = 17$.

In practice, $e = 65537 = 2^{16} + 1$ is the standard choice because it is prime and has only two 1-bits in binary, making modular exponentiation fast.

Bridge to 04a: We verify the coprimality condition using the GCD algorithm you learned in notebook 04a.

# Step 4: Choose e with gcd(e, phi_n) = 1 (notebook 04a: GCD)
e = 17
g = gcd(e, phi_n)
print(f"gcd({e}, {phi_n}) = {g}")
assert g == 1, "e is not coprime to phi(n)!"
print(f"Good: e = {e} is coprime to phi(n) = {phi_n}")

Step 5: Compute $d = e^{-1} \bmod \varphi(n)$

The private exponent $d$ satisfies $ed \equiv 1 \pmod{\varphi(n)}$. We compute it using the extended Euclidean algorithm (notebook 04b).

Bridge to 04b: In that notebook, you learned that xgcd(a, m) returns $(g, s, t)$ with $g = sa + tm$. When $g = 1$, the coefficient $s$ is exactly $a^{-1} \bmod m$.

# Step 5: Compute private exponent d (notebook 04b: extended GCD)

# Method 1: Using xgcd directly (the "from scratch" way)
g, s, t = xgcd(e, phi_n)
d = s % phi_n  # ensure d is positive
print(f"xgcd({e}, {phi_n}) = ({g}, {s}, {t})")
print(f"d = {s} mod {phi_n} = {d}")

# Method 2: Using SageMath's inverse_mod (convenience)
d_check = inverse_mod(e, phi_n)
assert d == d_check

# Verify: e * d = 1 (mod phi_n)
print(f"\nVerification: e * d mod phi(n) = {e} * {d} mod {phi_n} = {(e * d) % phi_n}")

The RSA Key Pair

We now have our complete key pair:

	Key	Value
Public key	$(n, e)$	$(3233, 17)$
Private key	$(n, d)$	$(3233, 2753)$

The public key $(n, e)$ is shared with the world. The private key $d$ (and the factors $p, q$, and $\varphi(n)$) must be kept secret.

Checkpoint: Before running the next cell, compute by hand: what is $e \cdot d \bmod \varphi(n)$? That is, what is $17 \times 2753 \bmod 3120$? (Hint: it had better be 1.)

# Display the complete key pair
print("        RSA KEY PAIR SUMMARY")
print(f"  Primes:      p = {p}, q = {q}  [SECRET]")
print(f"  Modulus:     n = {n}            [PUBLIC]")
print(f"  Totient:     phi(n) = {phi_n}        [SECRET]")
print(f"  Public exp:  e = {e}              [PUBLIC]")
print(f"  Private exp: d = {d}            [SECRET]")
print(f"  Public key:  (n, e) = ({n}, {e})")
print(f"  Private key: (n, d) = ({n}, {d})")

# Sanity check
print(f"\ne * d = {e * d} = {(e*d) // phi_n} * {phi_n} + {(e*d) % phi_n}")
print(f"So e * d mod phi(n) = {(e*d) % phi_n}  (must be 1)")

Part 2: Textbook RSA Encryption

Encryption is remarkably simple. Given a message $m$ (an integer with $0 \le m < n$) and the public key $(n, e)$:

$$c = m^e \bmod n$$

That is it. One modular exponentiation.

Checkpoint: Before running the next cell, try to predict: what is $65^{17} \bmod 3233$? This is hard to compute by hand, but you can use repeated squaring. Or just make a guess and see if you are right.

# RSA Encryption: c = m^e mod n
m = 65  # our message (must be 0 <= m < n)
print(f"Message:    m = {m}")
print(f"Public key: (n, e) = ({n}, {e})")
print()

# Encrypt using power_mod (efficient modular exponentiation)
c = power_mod(m, e, n)
print(f"Ciphertext: c = m^e mod n = {m}^{e} mod {n} = {c}")
print()

# Verify using SageMath's native modular arithmetic
R = IntegerModRing(n)
c_check = R(m)^e
print(f"Verification with IntegerModRing: {c_check}")
assert int(c_check) == c

Part 3: Textbook RSA Decryption

Decryption is the exact same operation, but using the private exponent $d$:

$$m = c^d \bmod n$$

Let us verify that we recover the original message.

# RSA Decryption: m = c^d mod n
print(f"Ciphertext:  c = {c}")
print(f"Private key: (n, d) = ({n}, {d})")
print()

# Decrypt
m_recovered = power_mod(c, d, n)
print(f"Decrypted:   m = c^d mod n = {c}^{d} mod {n} = {m_recovered}")
print()

# Verify
assert m_recovered == m, "Decryption failed!"
print(f"SUCCESS: recovered message {m_recovered} matches original {m}")

Part 4: Why RSA Works (The Proof)

This is the deepest part of the notebook. We need to show that decryption undoes encryption:

$$c^d \equiv (m^e)^d \equiv m^{ed} \equiv m \pmod{n}$$

Why does $m^{ed} \equiv m \pmod{n}$?

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

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

Bridge to 04c: By Euler's theorem (notebook 04c), if $\gcd(m, n) = 1$ then $m^{\varphi(n)} \equiv 1 \pmod{n}$.

So:

$$m^{ed} = m \cdot (m^{\varphi(n)})^k \equiv m \cdot 1^k \equiv m \pmod{n}$$

That is the whole proof. Every tool serves a purpose:

• Euler's theorem (04c) makes $m^{\varphi(n)} = 1$, so the $k\varphi(n)$ part vanishes.

• Extended GCD (04b) lets us find $d$ such that $ed = 1 + k\varphi(n)$.

• GCD (04a) guarantees the inverse exists (because $\gcd(e, \varphi(n)) = 1$).

Technical note: The proof above requires $\gcd(m, n) = 1$. What if $m$ shares a factor with $n$? Since $n = pq$, this means $p | m$ or $q | m$, which happens with negligible probability for random messages. The proof can be extended to cover this case using CRT and Fermat's little theorem on each prime factor separately.

# Let's verify the proof step by step
print("=== Verifying the correctness proof ===")
print()

# Step 1: ed = 1 + k * phi(n)
ed = e * d
k = (ed - 1) // phi_n
print(f"e * d = {ed}")
print(f"e * d = 1 + {k} * {phi_n}")
print(f"Verify: 1 + {k} * {phi_n} = {1 + k * phi_n}  (should equal {ed})")
assert ed == 1 + k * phi_n
print()

# Step 2: m^phi(n) = 1 (mod n)  [Euler's theorem]
euler_check = power_mod(m, phi_n, n)
print(f"m^phi(n) mod n = {m}^{phi_n} mod {n} = {euler_check}")
print(f"Euler's theorem says this should be 1: {'CONFIRMED' if euler_check == 1 else 'FAILED'}")
print()

# Step 3: m^(ed) = m * (m^phi(n))^k = m * 1^k = m
m_ed = power_mod(m, ed, n)
print(f"m^(ed) mod n = {m}^{ed} mod {n} = {m_ed}")
print(f"This equals m = {m}: {'CONFIRMED' if m_ed == m else 'FAILED'}")
print()

# Test with many different messages
print("Testing with 100 random messages...")
all_ok = True
for _ in range(100):
    test_m = randint(2, n-1)
    test_c = power_mod(test_m, e, n)
    test_dec = power_mod(test_c, d, n)
    if test_dec != test_m:
        print(f"FAILED for m = {test_m}")
        all_ok = False
if all_ok:
    print("All 100 tests passed: encrypt then decrypt always recovers the message.")

Part 5: Why Textbook RSA Is INSECURE

Misconception Callout: "RSA is secure because factoring $n$ is hard."

More precisely: RSA is secure if factoring is hard and you use proper padding. Textbook RSA (no padding) is broken even if factoring is hard. Here are three concrete attacks.

Attack 1: Deterministic Encryption (No Semantic Security)

Textbook RSA is deterministic: encrypting the same message twice produces the same ciphertext. This means an attacker who guesses your message can verify the guess.

# Attack 1: Deterministic encryption
# Scenario: Eve intercepts c and wants to know if m = 65 or m = 66

c_intercepted = power_mod(65, e, n)  # the real ciphertext

# Eve tries both candidates
c_guess_65 = power_mod(65, e, n)
c_guess_66 = power_mod(66, e, n)

print(f"Intercepted ciphertext: c = {c_intercepted}")
print(f"Encryption of m=65:     c = {c_guess_65}")
print(f"Encryption of m=66:     c = {c_guess_66}")
print()

if c_intercepted == c_guess_65:
    print("Eve concludes: the message is 65!")
    print("Attack succeeded, no decryption key needed.")
print()
print("This breaks 'semantic security': an attacker can distinguish")
print("between encryptions of two known messages.")

Attack 2: Malleability (Homomorphic Property)

Textbook RSA is multiplicatively homomorphic: given $E(m_1)$ and $E(m_2)$, anyone can compute $E(m_1 \cdot m_2)$ without knowing $m_1$ or $m_2$.

$$E(m_1) \cdot E(m_2) = m_1^e \cdot m_2^e = (m_1 \cdot m_2)^e = E(m_1 \cdot m_2) \pmod{n}$$

An attacker can manipulate ciphertexts in meaningful ways without the private key.

# Attack 2: Malleability
m1 = 42
m2 = 7

c1 = power_mod(m1, e, n)
c2 = power_mod(m2, e, n)

# Attacker multiplies ciphertexts (no private key needed!)
c_product = (c1 * c2) % n

# Decrypt the product ciphertext
m_product = power_mod(c_product, d, n)

print(f"E({m1}) = {c1}")
print(f"E({m2}) = {c2}")
print(f"E({m1}) * E({m2}) mod n = {c_product}")
print(f"Decrypt({c_product}) = {m_product}")
print(f"m1 * m2 = {m1 * m2}")
print(f"Match: {m_product == (m1 * m2) % n}")
print()
print("The attacker manipulated the ciphertext without knowing")
print("the plaintext or the private key. This is devastating in practice:")
print("e.g., an attacker could double an encrypted bank transfer amount.")

Attack 3: Small Message Attack

If the message $m$ is small enough that $m^e < n$ (no modular reduction happens), then the attacker can simply compute the $e$-th root of $c$ over the integers.

With $e = 3$ (common in some implementations), any $m < n^{1/3}$ is vulnerable.

# Attack 3: Small message with small e
# Use e = 3 to make the attack clear
p_demo, q_demo = 1013, 1019
n_demo = p_demo * q_demo  # 1032247
e_demo = 3
phi_demo = (p_demo - 1) * (q_demo - 1)
assert gcd(e_demo, phi_demo) == 1
d_demo = inverse_mod(e_demo, phi_demo)

# A small message: m^3 < n, so no modular reduction occurs
m_small = 50  # 50^3 = 125000 < 1032247
c_small = power_mod(m_small, e_demo, n_demo)
print(f"n = {n_demo}")
print(f"m = {m_small}, m^3 = {m_small^3}, n = {n_demo}")
print(f"Since m^3 = {m_small^3} < n = {n_demo}, no mod reduction!")
print(f"Ciphertext c = {c_small}")
print()

# The attacker just takes the cube root over the integers
m_recovered_attack = Integer(c_small).nth_root(e_demo)
print(f"Attacker computes: c^(1/3) = {m_recovered_attack}")
print(f"Original message was: {m_small}")
print(f"Attack successful: {m_recovered_attack == m_small}")
print()
print("No factoring needed! The attacker just computed an integer root.")

Why Padding Matters: OAEP

All three attacks above are defeated by OAEP (Optimal Asymmetric Encryption Padding, Bellare and Rogaway, 1994). Before encrypting message $m$, OAEP:

1. Adds randomness: Each encryption of the same message produces a different ciphertext (defeats Attack 1).

2. Adds structure: The padded message has algebraic structure that is destroyed by multiplication (defeats Attack 2).

3. Fills the message space: The padded message is always close to $n$ in size (defeats Attack 3).

Rule of practice: Never use textbook RSA. Always use RSA-OAEP (PKCS#1 v2).

Misconception Callout: "I will just add some random bytes myself." Ad-hoc padding schemes have been broken repeatedly. OAEP has a security proof in the random oracle model. Use the standard.

Part 6: RSA-CRT Optimization

Standard RSA decryption computes $c^d \bmod n$. Since $d$ and $n$ are both large (e.g., 2048 bits), this is expensive.

Bridge to 04d: The Chinese Remainder Theorem (notebook 04d) tells us that $\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z}$ when $\gcd(p, q) = 1$. We can decrypt modulo $p$ and modulo $q$ separately, then combine the results with CRT.

RSA-CRT decryption:

1. Precompute $d_p = d \bmod (p-1)$ and $d_q = d \bmod (q-1)$

2. Compute $m_p = c^{d_p} \bmod p$ and $m_q = c^{d_q} \bmod q$

3. Combine: $m = \text{CRT}(m_p, m_q, p, q)$

Why is this faster? Exponentiating a number modulo a $k$-bit number costs roughly $O(k^3)$ using schoolbook arithmetic. Two exponentiations modulo $k/2$-bit numbers cost $2 \cdot O((k/2)^3) = O(k^3/4)$. That is a 4x speedup.

# RSA-CRT Decryption
print("=== RSA-CRT Decryption ===")
print()

# Step 1: Precompute reduced exponents
d_p = d % (p - 1)
d_q = d % (q - 1)
print(f"d_p = d mod (p-1) = {d} mod {p-1} = {d_p}")
print(f"d_q = d mod (q-1) = {d} mod {q-1} = {d_q}")
print()

# Step 2: Decrypt modulo each prime separately
m_p = power_mod(c, d_p, p)
m_q = power_mod(c, d_q, q)
print(f"m_p = c^d_p mod p = {c}^{d_p} mod {p} = {m_p}")
print(f"m_q = c^d_q mod q = {c}^{d_q} mod {q} = {m_q}")
print()

# Step 3: Combine with CRT (notebook 04d)
m_crt = crt(m_p, m_q, p, q)
print(f"CRT({m_p}, {m_q}, {p}, {q}) = {m_crt}")
print(f"Standard decryption gave: {m_recovered}")
print(f"Match: {m_crt == m_recovered}")

# Timing comparison with realistic key sizes

# Generate a 2048-bit RSA key
p_big = random_prime(2^1024)
q_big = random_prime(2^1024)
n_big = p_big * q_big
phi_big = (p_big - 1) * (q_big - 1)
e_big = 65537
d_big = inverse_mod(e_big, phi_big)

# Encrypt a random message
m_big = randint(2, n_big - 1)
c_big = power_mod(m_big, e_big, n_big)

# Standard decryption
t0 = walltime()
for _ in range(10):
    m_std = power_mod(c_big, d_big, n_big)
t_std = (walltime() - t0) / 10

# CRT decryption
d_p_big = d_big % (p_big - 1)
d_q_big = d_big % (q_big - 1)
t0 = walltime()
for _ in range(10):
    mp = power_mod(c_big, d_p_big, p_big)
    mq = power_mod(c_big, d_q_big, q_big)
    m_crt_big = crt(mp, mq, p_big, q_big)
t_crt = (walltime() - t0) / 10

# Verify correctness
assert m_std == m_big == m_crt_big

print(f"2048-bit RSA decryption timing (average of 10 runs):")
print(f"  Standard: {t_std*1000:.2f} ms")
print(f"  CRT:      {t_crt*1000:.2f} ms")
print(f"  Speedup:  {t_std/t_crt:.1f}x")

Part 7: RSA with Realistic Key Sizes

Our toy example used 6-bit primes. In practice, RSA uses 1024-bit primes (for a 2048-bit modulus) or larger. Let us see the full process at scale.

Bridge to 04e: We use random_prime() (notebook 04e) to generate cryptographic-strength primes.

# Full RSA with 2048-bit key (reusing the key from the timing test)
print(f"p has {p_big.nbits()} bits")
print(f"q has {q_big.nbits()} bits")
print(f"n has {n_big.nbits()} bits")
print()

# Encrypt a message (let's encode a string)
message_str = "RSA works!"
m_bytes = message_str.encode('utf-8')
m_int = Integer(int.from_bytes(m_bytes, 'big'))
print(f"Message string: '{message_str}'")
print(f"As integer: m = {m_int}")
print(f"m has {m_int.nbits()} bits (must be < {n_big.nbits()}-bit n)")
print()

# Encrypt
c_real = power_mod(m_int, e_big, n_big)
print(f"Ciphertext c = {c_real}")
print(f"c has {Integer(c_real).nbits()} bits")
print()

# Decrypt
m_dec = power_mod(c_real, d_big, n_big)
m_dec_bytes = int(m_dec).to_bytes((int(m_dec).bit_length() + 7) // 8, 'big')
m_dec_str = m_dec_bytes.decode('utf-8')
print(f"Decrypted integer: {m_dec}")
print(f"Decrypted string: '{m_dec_str}'")
assert m_dec_str == message_str, "Decryption failed!"
print("\nFull RSA round-trip with 2048-bit key: SUCCESS")

Exercises

Exercise 1: Full RSA Round-Trip (Worked Example)

Let us do a complete RSA example with different parameters: $p = 101$, $q = 103$, $e = 7$, and message $m = 42$.

# Exercise 1: FULLY WORKED
# RSA with p=101, q=103, e=7, m=42

# Key generation
p1, q1 = 101, 103
n1 = p1 * q1                          # n = 10403
phi1 = (p1 - 1) * (q1 - 1)            # phi(n) = 10200
e1 = 7
assert gcd(e1, phi1) == 1              # verify e is valid
d1 = inverse_mod(e1, phi1)             # d = 8743

print(f"Key generation:")
print(f"  p = {p1}, q = {q1}")
print(f"  n = {n1}")
print(f"  phi(n) = {phi1}")
print(f"  e = {e1}")
print(f"  d = {d1}")
print(f"  Check: e*d mod phi(n) = {(e1*d1) % phi1}")
print()

# Encryption
m1 = 42
c1 = power_mod(m1, e1, n1)
print(f"Encryption: c = {m1}^{e1} mod {n1} = {c1}")

# Decryption
m1_dec = power_mod(c1, d1, n1)
print(f"Decryption: m = {c1}^{d1} mod {n1} = {m1_dec}")
assert m1_dec == m1
print(f"Round-trip: SUCCESS (recovered m = {m1_dec})")

Exercise 2: RSA-CRT Decryption (Guided)

Using the key from Exercise 1 ($p = 101$, $q = 103$, $d = 8743$, ciphertext from above), perform RSA-CRT decryption. Fill in the TODOs.

# Exercise 2: GUIDED with TODOs
# Perform RSA-CRT decryption on the ciphertext c1 from Exercise 1

# Step 1: Compute reduced exponents
# TODO: compute d_p1 = d1 mod (p1 - 1)
# d_p1 = ???
# TODO: compute d_q1 = d1 mod (q1 - 1)
# d_q1 = ???

# Step 2: Decrypt modulo each prime
# TODO: compute m_p1 = c1^d_p1 mod p1
# m_p1 = ???
# TODO: compute m_q1 = c1^d_q1 mod q1
# m_q1 = ???

# Step 3: Combine with CRT
# TODO: compute m_crt1 = CRT(m_p1, m_q1, p1, q1)
# m_crt1 = ???

# Uncomment to check your answer:
# print(f"d_p = {d_p1}, d_q = {d_q1}")
# print(f"m_p = {m_p1}, m_q = {m_q1}")
# print(f"m_crt = {m_crt1}")
# assert m_crt1 == 42, f"Expected 42, got {m_crt1}"

Exercise 3: Build Your Own RSA (Independent)

Build a complete RSA system from scratch. Choose your own primes (at least 10 digits each), generate a key pair, encrypt and decrypt a message of your choice, and verify the malleability attack. No starter code is provided.

# Exercise 3: INDEPENDENT
# Build a complete RSA system from scratch.
#
# Requirements:
# 1. Choose two primes p, q with at least 10 digits each
#    (Hint: random_prime(10^10) gives primes up to 10 digits)
# 2. Compute n, phi(n), choose e, compute d
# 3. Encrypt a message m of your choice
# 4. Decrypt and verify you recover m
# 5. Demonstrate the malleability attack:
#    - Encrypt m1 and m2 separately
#    - Multiply the ciphertexts
#    - Decrypt the product and show it equals m1*m2 mod n
#
# Write your solution below:

Summary

Concept	Key idea
RSA key generation	Uses GCD (04a) to choose $e$, extended GCD (04b) to compute $d$, and primality testing (04e) to generate $p$ and $q$
Encryption and decryption	Encryption: $c = m^e \bmod n$. Decryption: $m = c^d \bmod n$. One modular exponentiation each way
Correctness proof	Follows from Euler's theorem (04c): $m^{ed} = m^{1+k\varphi(n)} = m \cdot 1^k = m$
Textbook RSA is insecure	Deterministic (no semantic security), multiplicatively malleable, and vulnerable to small-message attacks. Always use RSA-OAEP
RSA-CRT optimization	Uses CRT (04d) to decrypt roughly 4x faster by working modulo $p$ and $q$ separately
Module 04 assembly	Every prior notebook (04a through 04e) contributes a specific piece to the RSA cryptosystem

Crypto Foreshadowing: RSA is being phased out in favor of elliptic curve cryptography (Module 06) and lattice-based cryptography (Module 08). ECC offers the same security with much smaller keys (256-bit ECC $\approx$ 3072-bit RSA). And lattice-based systems are believed to resist quantum computers, which would break RSA entirely via Shor's algorithm. But understanding RSA is essential: it teaches you the paradigm of public-key cryptography that all these newer systems build upon.

Next: Module 05 --- Discrete Logarithm Problem and Diffie-Hellman