101
0/228
Loading content...
RSA is perhaps the most elegant application of abstract mathematics to practical computing in history. Concepts developed by Euclid over 2,300 years ago, refined by Fermat and Euler in the 17th and 18th centuries, and formalized by modern mathematicians, combine to create a cryptosystem that secures trillions of dollars in daily transactions.
This page is not a superficial overview. We will develop a rigorous understanding of the mathematical foundations that make RSA work:
By the end of this page, you won't just know that RSA works—you'll understand why it works, with mathematical certainty.
This page assumes familiarity with: basic arithmetic operations, the concept of divisibility, what prime numbers are, and basic algebra. We will build all necessary number theory from these foundations. No prior number theory knowledge is required—each concept is developed from first principles with full explanations and examples.
RSA operates entirely within the realm of modular arithmetic—a system where numbers "wrap around" after reaching a maximum value. This isn't an arbitrary choice; modular arithmetic is essential for making cryptographic operations computationally tractable and creating the mathematical properties RSA depends on.
Definition: Congruence Modulo n
Two integers a and b are congruent modulo n if they have the same remainder when divided by n. We write:
a ≡ b (mod n)
which means n divides (a - b), or equivalently, a mod n = b mod n.
Examples:
The Clock Analogy:
Modular arithmetic is often called "clock arithmetic." On a 12-hour clock:
In RSA, we work modulo n (the product of two large primes), so all values stay within [0, n-1].
Fundamental Properties of Modular Arithmetic
Modular arithmetic preserves the basic arithmetic operations, which is crucial for RSA:
Addition:
(a + b) mod n = ((a mod n) + (b mod n)) mod n
Subtraction:
(a - b) mod n = ((a mod n) - (b mod n) + n) mod n
Multiplication:
(a × b) mod n = ((a mod n) × (b mod n)) mod n
Exponentiation (by repeated multiplication):
a^k mod n = ((a mod n)^k) mod n
Example: Computing 7^100 mod 13
Without modular reduction: 7^100 is a number with ~85 digits
With modular reduction: We can compute step-by-step, keeping intermediate results small:
7^1 mod 13 = 7
7^2 mod 13 = 49 mod 13 = 10
7^4 mod 13 = 10^2 mod 13 = 100 mod 13 = 9
7^8 mod 13 = 9^2 mod 13 = 81 mod 13 = 3
...
This is the square-and-multiply technique that makes RSA practical—we can compute m^e mod n in O(log e) multiplications, where each intermediate value is at most n².
Modular arithmetic has a remarkable property: computing a^b mod n is easy (polynomial time), but extracting 'a' from the result (the discrete logarithm problem) or extracting the 'b' (in certain contexts) is computationally hard. This asymmetry—easy to compute forward, hard to reverse—is the foundation of all public-key cryptography.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485
# Modular Arithmetic Operations for RSA def mod_add(a: int, b: int, n: int) -> int: """Modular addition: (a + b) mod n""" return (a + b) % n def mod_subtract(a: int, b: int, n: int) -> int: """Modular subtraction: (a - b) mod n, handling negative results""" return ((a - b) % n + n) % n def mod_multiply(a: int, b: int, n: int) -> int: """Modular multiplication: (a × b) mod n""" return (a * b) % n def mod_pow_naive(base: int, exponent: int, modulus: int) -> int: """ Naive modular exponentiation: base^exponent mod modulus O(exponent) multiplications - too slow for large exponents! """ result = 1 for _ in range(exponent): result = (result * base) % modulus return result def mod_pow_square_and_multiply(base: int, exponent: int, modulus: int) -> int: """ Fast modular exponentiation using square-and-multiply. O(log exponent) multiplications - efficient for RSA! Also known as "exponentiation by squaring" or "binary exponentiation". Key insight: Express exponent in binary, then: - For each bit, square the current result - If the bit is 1, multiply by base Example: 3^13 mod 17 13 in binary = 1101 Step 0: result = 1 Step 1 (bit 1): result = 1^2 * 3 = 3 Step 2 (bit 0): result = 3^2 = 9 Step 3 (bit 1): result = 9^2 * 3 = 81 * 3 = 243 mod 17 = 5 Step 4 (bit 1): result = 5^2 * 3 = 25 * 3 = 75 mod 17 = 7 Verify: 3^13 = 1594323 mod 17 = 7 ✓ """ result = 1 base = base % modulus while exponent > 0: # If current bit is 1, multiply result by base if exponent & 1: result = (result * base) % modulus # Move to next bit exponent >>= 1 # Square the base for next iteration base = (base * base) % modulus return result # Python's built-in pow(base, exp, mod) uses optimized modular exponentiation# It's implemented in C and handles arbitrary precision efficiently# Always use pow(m, e, n) for RSA operations # Demonstrationif __name__ == "__main__": # Example: compute 7^100 mod 13 result = pow(7, 100, 13) print(f"7^100 mod 13 = {result}") # Output: 7^100 mod 13 = 9 # Verify our implementation assert mod_pow_square_and_multiply(7, 100, 13) == pow(7, 100, 13) # RSA-scale example: 2048-bit numbers import secrets n = secrets.randbits(2048) # 2048-bit modulus m = secrets.randbits(2047) # Message < n e = 65537 # Public exponent # This is fast even with 2048-bit numbers! c = pow(m, e, n) print(f"Encrypted {m.bit_length()}-bit message in milliseconds")The greatest common divisor (GCD) is central to RSA. It determines when modular inverses exist and helps us understand the structure of the multiplicative group we work in.
Definition: Greatest Common Divisor
The GCD of two integers a and b, denoted gcd(a, b), is the largest positive integer that divides both a and b.
Examples:
Definition: Coprime (Relatively Prime)
Two integers a and b are coprime (or relatively prime) if gcd(a, b) = 1. They share no common factors other than 1.
Coprimality in RSA:
The Euclidean Algorithm
Computing GCD naively by factoring numbers is slow. The Euclidean Algorithm, known for over 2,300 years, provides an elegant and efficient alternative:
gcd(a, b) = gcd(b, a mod b)
with base case gcd(a, 0) = a.
Example: gcd(48, 18)
gcd(48, 18) = gcd(18, 48 mod 18) = gcd(18, 12)
gcd(18, 12) = gcd(12, 18 mod 12) = gcd(12, 6)
gcd(12, 6) = gcd(6, 12 mod 6) = gcd(6, 0)
gcd(6, 0) = 6
Result: gcd(48, 18) = 6
Time Complexity: The Euclidean Algorithm runs in O(log(min(a, b))) iterations, making it extremely efficient even for numbers with thousands of digits. Each iteration reduces the larger number by at least half, guaranteeing logarithmic convergence.
Bézout's Identity states that for any integers a and b, there exist integers x and y such that: ax + by = gcd(a, b). When gcd(a, b) = 1, this becomes ax + by = 1, which means ax ≡ 1 (mod b). Thus x is the modular multiplicative inverse of a modulo b. The Extended Euclidean Algorithm computes not just gcd(a, b) but also the coefficients x and y.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
def gcd(a: int, b: int) -> int: """ Euclidean Algorithm for computing GCD. Based on: gcd(a, b) = gcd(b, a mod b) Base case: gcd(a, 0) = a Time: O(log(min(a, b))) """ while b != 0: a, b = b, a % b return a def extended_gcd(a: int, b: int) -> tuple[int, int, int]: """ Extended Euclidean Algorithm. Returns (gcd, x, y) where gcd = ax + by (Bézout's identity). The coefficients x and y allow us to compute modular inverses: If gcd(a, b) = 1, then x is the modular inverse of a mod b. Derivation: - Base case: gcd(a, 0) = a = a*1 + 0*0, so return (a, 1, 0) - Recursive case: Given gcd(b, a mod b) = bx' + (a mod b)y' We have: a mod b = a - (a // b) * b So: gcd = bx' + (a - (a // b) * b)y' = ay' + b(x' - (a // b) * y') Therefore: x = y', y = x' - (a // b) * y' """ if b == 0: return a, 1, 0 gcd_val, x1, y1 = extended_gcd(b, a % b) x = y1 y = x1 - (a // b) * y1 return gcd_val, x, y def mod_inverse(a: int, n: int) -> int: """ Compute modular multiplicative inverse of a modulo n. Returns x such that (a * x) ≡ 1 (mod n). Requires: gcd(a, n) = 1 (a and n must be coprime). This is how we compute the private exponent d in RSA: d = e^(-1) mod φ(n) """ gcd_val, x, _ = extended_gcd(a % n, n) if gcd_val != 1: raise ValueError(f"Modular inverse doesn't exist: gcd({a}, {n}) = {gcd_val}") # Ensure result is positive return (x % n + n) % n # Demonstrationif __name__ == "__main__": # Example: Find inverse of 17 modulo 3120 (actual RSA example) # This is computing d such that 17*d ≡ 1 (mod 3120) e = 17 phi_n = 3120 # = (61-1)(53-1) for n = 61*53 = 3233 d = mod_inverse(e, phi_n) print(f"e = {e}") print(f"φ(n) = {phi_n}") print(f"d = e^(-1) mod φ(n) = {d}") # Verify: e * d ≡ 1 (mod φ(n)) print(f"Verification: {e} * {d} mod {phi_n} = {(e * d) % phi_n}") # Output: 1 # Extended GCD gives us Bézout coefficients gcd_val, x, y = extended_gcd(e, phi_n) print(f"\nBézout's identity: {e}*{x} + {phi_n}*{y} = {gcd_val}") print(f"Verification: {e}*{x} + {phi_n}*{y} = {e*x + phi_n*y}")Euler's totient function φ(n) is the mathematical heart of RSA. It counts the positive integers up to n that are coprime to n—and this count has a direct relationship to the structure of the multiplicative group modulo n.
Definition: Euler's Totient Function φ(n)
φ(n) = |{k : 1 ≤ k ≤ n, gcd(k, n) = 1}|
In words: φ(n) counts how many integers from 1 to n are coprime to n.
Simple Examples:
φ(6): Numbers from 1-6: {1, 2, 3, 4, 5, 6}
Coprime to 6 (gcd = 1): {1, 5} (2, 3, 4, 6 share factors with 6)
φ(6) = 2
φ(7): Numbers from 1-7: {1, 2, 3, 4, 5, 6, 7}
Coprime to 7: {1, 2, 3, 4, 5, 6} (7 is prime, all smaller numbers are coprime)
φ(7) = 6
φ(12): Numbers from 1-12: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
Coprime to 12: {1, 5, 7, 11}
φ(12) = 4
Computing φ(n): Special Cases
For a prime p:
φ(p) = p - 1
Every number from 1 to p-1 is coprime to p (by definition of prime).
For a prime power p^k:
φ(p^k) = p^k - p^(k-1) = p^(k-1)(p - 1)
The only numbers not coprime to p^k are multiples of p: {p, 2p, 3p, ..., p^(k-1) × p}. There are p^(k-1) such multiples, so φ(p^k) = p^k - p^(k-1).
For a product of two distinct primes n = p × q:
φ(n) = φ(p) × φ(q) = (p - 1)(q - 1)
This is the formula used in RSA! The totient function is multiplicative for coprime arguments: if gcd(a, b) = 1, then φ(ab) = φ(a)φ(b).
Example for RSA: Let p = 61, q = 53, n = 61 × 53 = 3233 φ(n) = (61 - 1)(53 - 1) = 60 × 52 = 3120
| n | Prime Factorization | φ(n) | Formula Used |
|---|---|---|---|
| 7 | 7 (prime) | 6 | p - 1 = 7 - 1 |
| 8 | 2³ | 4 | p^(k-1)(p-1) = 2²(2-1) |
| 10 | 2 × 5 | 4 | (2-1)(5-1) = 1×4 |
| 12 | 2² × 3 | 4 | 2¹(2-1) × (3-1) = 2×2 |
| 15 | 3 × 5 | 8 | (3-1)(5-1) = 2×4 |
| 100 | 2² × 5² | 40 | 2¹(2-1) × 5¹(5-1) = 2×20 |
| 3233 | 61 × 53 | 3120 | (61-1)(53-1) = 60×52 |
In RSA, computing φ(n) = (p-1)(q-1) requires knowing p and q. But finding p and q from n means factoring n, which is computationally infeasible for large n. Thus, only the key creator (who generated p and q) can compute φ(n) and derive the private key d. This is why RSA security reduces to the factoring problem.
Euler's theorem is the mathematical gem that makes RSA work. It establishes a fundamental relationship between the totient function and modular exponentiation—a relationship that RSA exploits for encryption and decryption.
Theorem (Euler's Theorem):
For any integer a and positive integer n with gcd(a, n) = 1:
a^φ(n) ≡ 1 (mod n)
In words: raising a to the power φ(n) and taking the remainder modulo n always yields 1, provided a and n are coprime.
Special Case: Fermat's Little Theorem
When n = p is prime, φ(p) = p - 1, so Euler's theorem becomes:
a^(p-1) ≡ 1 (mod p) for any a not divisible by p
This is Fermat's Little Theorem, discovered a century before Euler's generalization.
Proof Sketch of Euler's Theorem:
Let S = {r₁, r₂, ..., r_φ(n)} be the set of integers from 1 to n that are coprime to n.
(This is the "multiplicative group modulo n," also written (Z/nZ)*.)
For any a coprime to n, multiplying each element of S by a gives: {a×r₁ mod n, a×r₂ mod n, ..., a×r_φ(n) mod n}
Key insight: This new set is a permutation of S. Each product is still coprime to n (since a and each rᵢ are), and all products are distinct (since a is invertible mod n).
Therefore:
(a×r₁)(a×r₂)...(a×r_φ(n)) ≡ r₁×r₂×...×r_φ(n) (mod n)
Simplifying:
a^φ(n) × (r₁×r₂×...×r_φ(n)) ≡ (r₁×r₂×...×r_φ(n)) (mod n)
Since the product (r₁×r₂×...×r_φ(n)) is coprime to n, we can divide both sides by it:
a^φ(n) ≡ 1 (mod n) ∎
RSA uses a powerful consequence of Euler's theorem: a^(kφ(n) + 1) ≡ a (mod n) for any integer k. Here's why: a^(kφ(n) + 1) = a^(kφ(n)) × a = (a^φ(n))^k × a ≡ 1^k × a = a (mod n). If we choose e and d such that ed = kφ(n) + 1 (i.e., ed ≡ 1 mod φ(n)), then (m^e)^d = m^(ed) ≡ m (mod n). This is the RSA encryption-decryption relationship!
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495
def euler_totient(n: int) -> int: """ Compute Euler's totient function φ(n). φ(n) = count of integers in [1, n] that are coprime to n. For n = p × q (two distinct primes): φ(n) = (p-1)(q-1) For general n: Use the product formula over prime factorization. """ result = n p = 2 while p * p <= n: if n % p == 0: # Remove all factors of p while n % p == 0: n //= p # Apply formula: result *= (1 - 1/p) result -= result // p p += 1 # If n > 1, then it's a remaining prime factor if n > 1: result -= result // n return result def verify_euler_theorem(a: int, n: int) -> bool: """ Verify Euler's theorem: a^φ(n) ≡ 1 (mod n) when gcd(a, n) = 1. """ from math import gcd if gcd(a, n) != 1: print(f"gcd({a}, {n}) = {gcd(a, n)} ≠ 1, Euler's theorem doesn't apply") return False phi = euler_totient(n) result = pow(a, phi, n) print(f"a = {a}, n = {n}") print(f"φ({n}) = {phi}") print(f"a^φ(n) mod n = {a}^{phi} mod {n} = {result}") print(f"Euler's theorem verified: {result == 1}") return result == 1 def demonstrate_rsa_relationship(): """ Demonstrate how Euler's theorem leads to RSA. Key relationship: if ed ≡ 1 (mod φ(n)), then m^(ed) ≡ m (mod n) """ # Small RSA example p, q = 61, 53 n = p * q # 3233 phi_n = (p - 1) * (q - 1) # 3120 e = 17 d = pow(e, -1, phi_n) # d = 2753 (Python 3.8+ supports modular inverse with pow) print(f"RSA Setup:") print(f" p = {p}, q = {q}, n = {n}") print(f" φ(n) = {phi_n}") print(f" e = {e}, d = {d}") print(f" e × d mod φ(n) = {(e * d) % phi_n}") # Should be 1 # Test encryption-decryption message = 123 ciphertext = pow(message, e, n) decrypted = pow(ciphertext, d, n) print(f"\nEncryption/Decryption:") print(f" Message: m = {message}") print(f" Ciphertext: c = m^e mod n = {message}^{e} mod {n} = {ciphertext}") print(f" Decrypted: m' = c^d mod n = {ciphertext}^{d} mod {n} = {decrypted}") print(f" Original recovered: {decrypted == message}") # Why it works: m^(ed) = m^(1 + k×φ(n)) = m × (m^φ(n))^k ≡ m × 1^k = m (mod n) ed = e * d k = (ed - 1) // phi_n print(f"\nWhy it works:") print(f" e × d = {ed} = 1 + {k} × {phi_n}") print(f" m^(ed) = m^(1 + k×φ(n)) = m × (m^φ(n))^k ≡ m × 1^k = m (mod n)") if __name__ == "__main__": # Verify Euler's theorem for various values verify_euler_theorem(3, 7) # 3^6 mod 7 = 1 print() verify_euler_theorem(5, 12) # 5^4 mod 12 = 1 print() # Demonstrate RSA relationship print("=" * 60) demonstrate_rsa_relationship()We now present a rigorous proof that RSA correctly recovers the original message after encryption and decryption. This proof addresses all cases, including the edge case where gcd(m, n) ≠ 1.
Theorem (RSA Correctness):
Let n = pq where p and q are distinct primes. Let e and d be positive integers satisfying ed ≡ 1 (mod λ(n)) where λ(n) = lcm(p-1, q-1). Then for all integers m with 0 ≤ m < n:
(m^e)^d ≡ m (mod n)
Proof:
We need to show m^(ed) ≡ m (mod n) for all m ∈ [0, n-1].
Since ed ≡ 1 (mod λ(n)), we have ed = 1 + k×λ(n) for some non-negative integer k.
By the Chinese Remainder Theorem, it suffices to prove:
We prove (1); the proof of (2) is identical with p replaced by q.
Case 1: p does not divide m (gcd(m, p) = 1)
By Fermat's Little Theorem: m^(p-1) ≡ 1 (mod p)
Since λ(n) = lcm(p-1, q-1), we have (p-1) | λ(n), so λ(n) = (p-1)×j for some integer j.
Therefore:
m^(ed) = m^(1 + k×λ(n))
= m × m^(k×λ(n))
= m × m^(k×(p-1)×j)
= m × (m^(p-1))^(kj)
≡ m × 1^(kj) (mod p)
= m ✓
Case 2: p divides m (gcd(m, p) = p)
If p | m, then m ≡ 0 (mod p), so: m^(ed) ≡ 0^(ed) = 0 ≡ m (mod p) ✓
(Note: This case is astronomically rare for random messages, since m would need to be a multiple of a 1024-bit prime.)
By symmetry, the same argument shows m^(ed) ≡ m (mod q).
Combining via CRT:
Since m^(ed) ≡ m (mod p) and m^(ed) ≡ m (mod q), and gcd(p, q) = 1, by the Chinese Remainder Theorem:
m^(ed) ≡ m (mod pq) = m (mod n) ∎
The proof works with either Euler's totient φ(n) = (p-1)(q-1) or Carmichael's totient λ(n) = lcm(p-1, q-1). Since λ(n) | φ(n), any d satisfying ed ≡ 1 (mod φ(n)) also satisfies ed ≡ 1 (mod λ(n)). Using λ(n) produces the smallest valid d, which can improve decryption performance.
Why the Proof Matters
This proof gives us mathematical certainty that RSA works—not just for test cases, but for every possible message and every properly generated key pair. This kind of provable security is rare in computer science; many algorithms are believed to work but lack formal proofs.
The proof also reveals RSA's structure:
This deep mathematical structure is why RSA has remained secure for nearly 50 years—it's built on number theory results that have withstood centuries of mathematical scrutiny.
The Chinese Remainder Theorem (CRT) is both a theoretical tool used in RSA proofs and a practical technique for optimizing RSA operations. Understanding CRT completes our mathematical foundation.
Theorem (Chinese Remainder Theorem):
Let n₁, n₂, ..., nₖ be pairwise coprime positive integers (gcd(nᵢ, nⱼ) = 1 for i ≠ j). Let N = n₁n₂...nₖ. For any integers a₁, a₂, ..., aₖ, there exists a unique integer x with 0 ≤ x < N such that:
x ≡ a₁ (mod n₁)
x ≡ a₂ (mod n₂)
...
x ≡ aₖ (mod nₖ)
In RSA's Context (k = 2):
For n = pq where gcd(p, q) = 1, knowing x mod p and x mod q uniquely determines x mod n.
This allows us to:
Constructive Form: Finding x
Given remainders a₁ (mod n₁) and a₂ (mod n₂), we can construct x explicitly:
For two moduli p and q:
x = a₁ × q × (q⁻¹ mod p) + a₂ × p × (p⁻¹ mod q) (mod pq)
Simplified for RSA decryption:
Let m_p = c^(d mod p-1) mod p and m_q = c^(d mod q-1) mod q.
Then the full decryption m can be computed as:
h = q_inv × (m_p - m_q) mod p
m = m_q + h × q
where q_inv = q⁻¹ mod p.
Why CRT Makes RSA Faster:
Modular exponentiation with k-bit numbers takes O(k³) time (roughly).
Standard RSA: one exponentiation with 2048-bit numbers → O(2048³)
CRT RSA: two exponentiations with 1024-bit numbers → 2 × O(1024³) = O(1024³)/4
CRT provides approximately a 4x speedup for RSA private key operations.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113
def extended_gcd(a: int, b: int) -> tuple[int, int, int]: """Return (gcd, x, y) where ax + by = gcd(a, b).""" if b == 0: return a, 1, 0 gcd, x1, y1 = extended_gcd(b, a % b) return gcd, y1, x1 - (a // b) * y1 def mod_inverse(a: int, m: int) -> int: """Compute a^(-1) mod m.""" gcd, x, _ = extended_gcd(a % m, m) if gcd != 1: raise ValueError(f"No inverse: gcd({a}, {m}) = {gcd}") return (x % m + m) % m def crt_two(a1: int, n1: int, a2: int, n2: int) -> int: """ Chinese Remainder Theorem for two moduli. Find x such that: x ≡ a1 (mod n1) x ≡ a2 (mod n2) Returns x in range [0, n1*n2). Requires gcd(n1, n2) = 1. """ # x = a1 * n2 * (n2^(-1) mod n1) + a2 * n1 * (n1^(-1) mod n2) n1_inv = mod_inverse(n1, n2) # n1^(-1) mod n2 n2_inv = mod_inverse(n2, n1) # n2^(-1) mod n1 N = n1 * n2 x = (a1 * n2 * n2_inv + a2 * n1 * n1_inv) % N return x def crt_general(remainders: list[int], moduli: list[int]) -> int: """ Chinese Remainder Theorem for multiple moduli. Find x such that x ≡ remainders[i] (mod moduli[i]) for all i. Requires all moduli to be pairwise coprime. """ if len(remainders) != len(moduli): raise ValueError("Lengths must match") # Start with first equation, successively combine x = remainders[0] m = moduli[0] for i in range(1, len(remainders)): x = crt_two(x, m, remainders[i], moduli[i]) m *= moduli[i] return x def rsa_decrypt_crt(c: int, p: int, q: int, d: int) -> int: """ RSA decryption using CRT optimization. Instead of computing c^d mod n directly, we: 1. Compute m_p = c^(d mod p-1) mod p 2. Compute m_q = c^(d mod q-1) mod q 3. Combine using CRT This is ~4x faster than direct computation. """ # Precompute CRT parameters dP = d % (p - 1) dQ = d % (q - 1) qInv = mod_inverse(q, p) # Partial decryptions (smaller moduli = faster) m_p = pow(c, dP, p) m_q = pow(c, dQ, q) # Combine using Garner's formula h = (qInv * (m_p - m_q)) % p m = m_q + h * q return m # Demonstrationif __name__ == "__main__": # Basic CRT example # Find x where x ≡ 2 (mod 3) and x ≡ 3 (mod 5) x = crt_two(2, 3, 3, 5) print(f"x ≡ 2 (mod 3) and x ≡ 3 (mod 5)") print(f"Solution: x = {x}") print(f"Verification: {x} mod 3 = {x % 3}, {x} mod 5 = {x % 5}") # x = 8: 8 mod 3 = 2, 8 mod 5 = 3 ✓ print() # RSA with CRT p, q = 61, 53 n = p * q e = 17 d = mod_inverse(e, (p-1)*(q-1)) message = 42 ciphertext = pow(message, e, n) # Standard decryption m_standard = pow(ciphertext, d, n) # CRT decryption m_crt = rsa_decrypt_crt(ciphertext, p, q, d) print(f"RSA with CRT:") print(f" Original message: {message}") print(f" Ciphertext: {ciphertext}") print(f" Decrypted (standard): {m_standard}") print(f" Decrypted (CRT): {m_crt}") print(f" Both match original: {m_standard == m_crt == message}")We've developed a rigorous understanding of the mathematics underlying RSA. These aren't mere abstractions—they're the precise machinery that makes secure internet communication possible.
What's Next:
With the mathematical foundations firmly established, the next page explores the RSA Encryption Process in complete detail. We'll examine how messages are prepared for encryption (padding schemes), the actual encryption computation, and critical considerations for secure implementation including protection against various attack vectors.
You now possess a rigorous understanding of RSA's mathematical foundation: modular arithmetic, the Euclidean algorithm, Euler's theorem, and the Chinese Remainder Theorem. You can prove RSA's correctness and understand why the cryptosystem works at a fundamental level. You're ready to explore the practical details of RSA encryption.