The Math Behind RSA #2: Modular Arithmetic — When Clock Math Becomes Cryptography

This article has a more math-focused version with formal proofs on Folio.

In Part 1, we explored prime numbers — the raw material of RSA. Now we need the machinery that makes RSA work: modular arithmetic.

You already know modular arithmetic. Every time you look at a clock and say "3 hours after 11 is 2," you're doing it. The twist is that this simple idea — numbers that wrap around — turns out to be the foundation of modern cryptography.

The Clock Analogy

On a 12-hour clock, there's no "13 o'clock." After 12, you wrap back to 1. In math, we write:

$$13 \equiv 1 \pmod{12}$$

This reads "13 is congruent to 1, modulo 12." It means 13 and 1 have the same remainder when divided by 12.

# Modular arithmetic in Python is just the % operator
print(13 % 12)  # 1
print(27 % 12)  # 3
print(48 % 12)  # 0  (exactly on the 12)

More formally: $a \equiv b \pmod{n}$ means $n$ divides $(a - b)$ . That's it. That's the whole definition.

The beautiful thing is that modular arithmetic preserves addition and multiplication:

$$(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n$$

$$(a \times b) \bmod n = ((a \bmod n) \times (b \bmod n)) \bmod n$$

# These properties let us keep numbers small during computation
n = 17
a, b = 100, 200

# Direct computation
print((a * b) % n)  # 13

# Reducing first, same result
print(((a % n) * (b % n)) % n)  # 13

This property is critical for RSA. Without it, we'd need to compute numbers with thousands of digits before taking the modulus. Instead, we reduce at every step.

Fast Modular Exponentiation: The Speed Trick

RSA needs to compute things like $m^e \bmod n$ where $e$ might be 65537 and $m$ might be a 2048-bit number. Computing $m^{65537}$ directly? Your computer would run out of memory (and patience).

The trick is repeated squaring. Instead of 65537 multiplications, we need about $\log_2(65537) = 17$ squarings.

def fast_mod_exp(base, exponent, mod):
    """Compute base^exponent mod mod using repeated squaring."""
    result = 1
    base = base % mod
    while exponent > 0:
        # If exponent is odd, multiply result with base
        if exponent % 2 == 1:
            result = (result * base) % mod
        # Square the base, halve the exponent
        exponent = exponent >> 1
        base = (base * base) % mod
    return result

# Python has this built in!
print(pow(7, 65537, 143))  # 7^65537 mod 143 = 123
print(fast_mod_exp(7, 65537, 143))  # Same: 123

The key insight: we never let any intermediate value exceed $n^2$ because we reduce modulo $n$ after every multiplication. This is what makes RSA practical.

One-Way Functions: Easy Forward, Hard Backward

Here's where cryptography enters the picture. Modular exponentiation is a one-way function:

• Forward (easy): Given $m$ , $e$ , and $n$ , compute $c = m^e \bmod n$ . This takes milliseconds.
• Backward (hard): Given $c$ , $e$ , and $n$ , find $m$ . This is the discrete logarithm problem — no efficient algorithm is known.

# Forward: trivial
m, e, n = 42, 65537, 3233
c = pow(m, e, n)
print(f"Encrypted: {c}")  # Encrypted: 2557

# Backward: you'd need to try all possible m values
# For real RSA with 2048-bit n, this is computationally infeasible

RSA's genius is that it finds a trapdoor — a secret piece of information that makes the backward direction easy too. That trapdoor is the modular inverse, and to understand it, we need the Euclidean algorithm.

The Euclidean Algorithm: 2300 Years Old and Still Useful

Euclid's algorithm finds the greatest common divisor (GCD) of two numbers. It's one of the oldest algorithms still in active use today.

The idea is simple: $\gcd(a, b) = \gcd(b, a \bmod b)$ , and $\gcd(a, 0) = a$ .

def gcd(a, b):
    """Euclid's algorithm — over 2300 years old."""
    while b != 0:
        a, b = b, a % b
    return a

print(gcd(48, 18))   # 6
print(gcd(17, 13))   # 1  (coprime — important for RSA!)
print(gcd(65537, 3120))  # 1  (this is a real RSA check)

Two numbers with $\gcd(a, b) = 1$ are called coprime. RSA requires that the public exponent $e$ is coprime with a certain special number. We'll get to that number shortly.

The Extended Euclidean Algorithm: Finding the Trapdoor

The extended version doesn't just find $\gcd(a, b)$ — it finds integers $x$ and $y$ such that:

$$ax + by = \gcd(a, b)$$

This is called Bezout's identity, and it's the key to computing modular inverses.

def extended_gcd(a, b):
    """Returns (gcd, x, y) such that a*x + b*y = gcd(a, b)."""
    if a == 0:
        return b, 0, 1
    gcd_val, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd_val, x, y

g, x, y = extended_gcd(35, 15)
print(f"gcd={g}, 35*({x}) + 15*({y}) = {35*x + 15*y}")
# gcd=5, 35*(1) + 15*(-2) = 5

Modular Inverse: The RSA Private Key

The modular inverse of $a$ modulo $n$ is the number $a^{-1}$ such that:

$$a \cdot a^{-1} \equiv 1 \pmod{n}$$

Think of it as "division in modular arithmetic." It exists if and only if $\gcd(a, n) = 1$ .

Why does the extended Euclidean algorithm give us this? If $\gcd(a, n) = 1$ , then we can find $x, y$ where $ax + ny = 1$ . Taking both sides modulo $n$ , the $ny$ term vanishes:

$$ax \equiv 1 \pmod{n}$$

So $x$ is the modular inverse of $a$ .

def mod_inverse(a, n):
    """Find a^(-1) mod n using extended Euclidean algorithm."""
    g, x, _ = extended_gcd(a % n, n)
    if g != 1:
        raise ValueError(f"No inverse: gcd({a}, {n}) = {g}")
    return x % n

# Example: inverse of 7 mod 26
inv = mod_inverse(7, 26)
print(f"7^(-1) mod 26 = {inv}")        # 15
print(f"Verify: 7 * {inv} mod 26 = {(7 * inv) % 26}")  # 1

# Python 3.8+ has this built in:
print(pow(7, -1, 26))  # 15

This is exactly how RSA computes the private key. Given the public exponent $e$ , the private key $d$ is:

$$d \equiv e^{-1} \pmod{\phi(n)}$$

But what is $\phi(n)$ ? For that, we need two more theorems.

Fermat's Little Theorem: The Warm-Up

Fermat discovered that for any prime $p$ and any $a$ not divisible by $p$ :

$$a^{p-1} \equiv 1 \pmod{p}$$

# Verify Fermat's little theorem
p = 17
for a in range(1, p):
    assert pow(a, p - 1, p) == 1
print(f"Fermat's little theorem holds for all a in [1, {p-1}] mod {p}")

# Useful corollary: a^(-1) ≡ a^(p-2) (mod p)
a, p = 7, 17
print(f"Inverse via Fermat: {pow(a, p - 2, p)}")     # 5
print(f"Inverse via ext GCD: {mod_inverse(a, p)}")    # 5

This gives us a second way to compute modular inverses (when the modulus is prime), but more importantly, it's the stepping stone to Euler's theorem.

Euler's Theorem and the Totient Function

Euler generalized Fermat's result to any modulus, not just primes. First, he defined the totient function $\phi(n)$ : the count of integers from 1 to $n$ that are coprime with $n$ .

def euler_totient(n):
    """Compute phi(n) by counting coprimes (brute force)."""
    from math import gcd
    return sum(1 for k in range(1, n + 1) if gcd(k, n) == 1)

print(f"phi(12) = {euler_totient(12)}")  # 4  (1, 5, 7, 11)
print(f"phi(7) = {euler_totient(7)}")    # 6  (all of 1..6, since 7 is prime)
print(f"phi(15) = {euler_totient(15)}")  # 8

Euler's theorem states: if $\gcd(a, n) = 1$ , then:

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

Notice that when $n = p$ is prime, $\phi(p) = p - 1$ , and this reduces to Fermat's little theorem. Euler's theorem is the engine that makes RSA's encryption-decryption cycle work.

Why $\phi(n) = (p-1)(q-1)$ Is the Secret

Here's where everything clicks. RSA chooses $n = p \cdot q$ for two large primes $p$ and $q$ . The totient has a beautiful property for products of distinct primes:

$$\phi(p \cdot q) = (p - 1)(q - 1)$$

Why? Among the numbers $1, 2, \ldots, pq$ , the ones that are not coprime to $pq$ are exactly the multiples of $p$ (there are $q$ of them) and multiples of $q$ (there are $p$ of them), minus the multiples of both (just $pq$ itself). So:

$$\phi(pq) = pq - p - q + 1 = (p-1)(q-1)$$

# Verify with a small example
p, q = 61, 53
n = p * q  # 3233

phi_brute = euler_totient(n)
phi_formula = (p - 1) * (q - 1)

print(f"n = {n}")
print(f"phi(n) brute force = {phi_brute}")    # 3120
print(f"(p-1)(q-1) = {phi_formula}")          # 3120
assert phi_brute == phi_formula

This is the secret of RSA. Anyone can know $n$ (it's public), but computing $\phi(n)$ requires knowing $p$ and $q$ — which requires factoring $n$ . And factoring large numbers is computationally infeasible.

Putting It All Together: The RSA Key Relationship

Now we can see the full picture. RSA picks primes $p, q$ , computes $n = pq$ and $\phi(n) = (p-1)(q-1)$ , then chooses $e$ coprime to $\phi(n)$ and computes:

$$d \equiv e^{-1} \pmod{\phi(n)}$$

This means $ed \equiv 1 \pmod{\phi(n)}$ , or equivalently $ed = 1 + k\phi(n)$ for some integer $k$ . Now watch the magic of decryption:

$$c^d \equiv (m^e)^d \equiv m^{ed} \equiv m^{1 + k\phi(n)} \equiv m \cdot (m^{\phi(n)})^k \equiv m \cdot 1^k \equiv m \pmod{n}$$

The last step uses Euler's theorem. The message comes back.

# Complete RSA key generation using everything we've learned
p, q = 61, 53
n = p * q                    # 3233 (public)
phi_n = (p - 1) * (q - 1)   # 3120 (secret!)
e = 17                       # public exponent (coprime with phi_n)

assert gcd(e, phi_n) == 1    # Verify e is valid

d = mod_inverse(e, phi_n)    # 2753 (private key!)
print(f"Public key:  (n={n}, e={e})")
print(f"Private key: (n={n}, d={d})")

# Encrypt and decrypt
message = 42
encrypted = pow(message, e, n)
decrypted = pow(encrypted, d, n)
print(f"Message: {message} -> Encrypted: {encrypted} -> Decrypted: {decrypted}")
# Message: 42 -> Encrypted: 2557 -> Decrypted: 42

Recap: The Modular Arithmetic Toolkit for RSA

Concept	Role in RSA
Modular arithmetic	Keeps numbers bounded, enables wrap-around
Fast exponentiation	Makes encryption/decryption practical
One-way functions	Security foundation — easy to encrypt, hard to reverse
Euclidean algorithm	Validates that $e$ is coprime with $\phi(n)$
Extended Euclidean	Computes the private key $d$
Modular inverse	$d = e^{-1} \bmod \phi(n)$ — the private key itself
Fermat's little theorem	Special case that builds intuition
Euler's theorem	Guarantees $m^{ed} \equiv m \pmod{n}$ — why decryption works
Totient function	$\phi(n) = (p-1)(q-1)$ — the trapdoor secret

Every piece of modular arithmetic we covered plays a specific, essential role. Remove any one, and RSA falls apart.

---

Up Next: Part 3 — Building RSA From Scratch

We now have all the mathematical tools. In Part 3, we'll implement RSA end-to-end in Python: key generation, encryption, decryption, and digital signatures. We'll also see where textbook RSA is dangerously insecure and what real implementations do differently.

---

Note: A version of this article with formal theorem/proof environments is available on Folio.