RSA: the math that protects the internet

Every time you visit a site over HTTPS, the padlock in your browser is saying: "the connection is secure." Behind it, at some point, RSA (or something built on it) ran. Two keys: one public, anyone can see it; one private, only the server knows it. One locks, the other unlocks.

This post opens up the math behind that.

The problem

You want to send a secret message to someone you've never met. No meeting up first, no pre-shared password.

With symmetric cryptography, both sides use the same key. Works fine, but there's a catch: how do you agree on that key without someone in the middle intercepting it?

The insight behind asymmetric cryptography: two different keys. One locks, the other unlocks. You publish the locking key for the whole world. Anyone can lock a message for you. But only you have the key that unlocks it.

It's like mailing someone an open padlock. Anyone can snap it shut, but only you have the key to open it.

Prime numbers

RSA starts with two large prime numbers. Primes are numbers divisible only by 1 and themselves: 2, 3, 5, 7, 11, 13...

Why primes? Because multiplying two primes is easy:

61 × 53 = 3233

Any calculator does this. But given 3233, figure out which two primes were multiplied. With a small number, you can brute-force it. With a 600-digit number, every computer on Earth combined can't do it.

Easy one way, impossible the other. That's what RSA relies on.

Modular arithmetic

Before building the keys, you need one operation: $\bmod$ . It's the remainder after division.

17 mod 5 = 2    (17 ÷ 5 = 3, remainder 2)
23 mod 7 = 2    (23 ÷ 7 = 3, remainder 2)

Think of a clock. If it's 10 o'clock and 5 hours pass, it's 15? On a 12-hour clock, it wraps around to 3. That's $15 \bmod 12 = 3$ .

Modular arithmetic is what makes RSA tick. It creates a kind of "one-way box": given $c = m^e \bmod n$ , knowing $c$ , $e$ , and $n$ doesn't give you $m$ back. Not unless you have an extra piece of information (the private key).

Euler's totient — $\varphi(n)$

Given a number $n$ , $\varphi(n)$ counts how many numbers less than $n$ are coprime with $n$ (meaning they share no factors other than 1).

For a prime $p$ , $\varphi(p) = p - 1$ . Every number less than a prime is coprime with it.

For the product of two primes, $n = p \times q$ :

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

This formula only works if you know $p$ and $q$ . If all you have is $n$ , you need to factor it — and that's exactly the hard problem.

Generating the keys

Step by step with small numbers (in practice, primes with hundreds of digits are used):

1. Pick two primes:

$p = 61, \quad q = 53$

2. Compute n:

$n = p \times q = 61 \times 53 = 3233$

3. Compute $\varphi(n)$ :

$\varphi(n) = (p - 1)(q - 1) = 60 \times 52 = 3120$

4. Choose e (public exponent):

$e$ must be coprime with $\varphi(n)$ . A common choice is $e = 17$ .

$\gcd(17, 3120) = 1 \quad \checkmark$

5. Compute d (private exponent):

$d$ is the modular inverse of $e \bmod \varphi(n)$ . That is, the number such that:

$e \times d \equiv 1 \pmod{\varphi(n)}$

$17 \times d \equiv 1 \pmod{3120}$

$d = 2753$

Check: $17 \times 2753 = 46801 = 15 \times 3120 + 1$ . Checks out.

Public key: $(e=17, n=3233)$ — you publish this. Private key: $(d=2753, n=3233)$ — this stays with you.

Encrypting and decrypting

With the keys ready:

Encrypt (anyone can do this with the public key):

$c = m^e \bmod n$

Decrypt (only the private key holder):

$m = c^d \bmod n$

Example with $m = 42$ :

$c = 42^{17} \bmod 3233 = 2557$

$m = 2557^{2753} \bmod 3233 = 42$

The number comes back. Every time.

message (2-3232):

1/5

Why does this work? Because of Fermat's Little Theorem and its generalization by Euler: $m^{\varphi(n)} \equiv 1 \pmod{n}$ when $m$ and $n$ are coprime. Since $e \times d \equiv 1 \pmod{\varphi(n)}$ , the exponentiation "wraps around" and recovers the original value.

Why it's secure

In our example, $n = 3233$ . Factoring that by hand is trivial. But in practice, RSA uses 2048 or 4096-bit keys. The $n$ has over 600 decimal digits.

Factoring a number that size is the bottleneck. The best algorithm anyone has (General Number Field Sieve) is sub-exponential, but still absurdly slow for large numbers.

To get a sense of scale:

RSA-768 (232 digits) was factored in 2009. It took 2 years with hundreds of machines.
RSA-2048 (617 digits) has never been factored. Conservative estimates say millions of years with current technology.

Quantum computers change this picture. Shor's algorithm factors in polynomial time. That's why post-quantum standards (like CRYSTALS-Kyber) already exist. But classical RSA is still secure against conventional computers.

RSA in practice

Nobody encrypts large data with RSA. It's way too slow, orders of magnitude slower than AES.

What actually happens in a TLS connection (simplified):

Your browser and the server do the handshake
RSA (or a variant) encrypts a temporary symmetric key
The rest of the communication uses that symmetric key (AES)

RSA only protects the key exchange. The actual data is encrypted with symmetric cryptography, which is much faster.

Another application: digital signatures. Instead of encrypting the message, you encrypt its hash with your private key. Anyone can verify it with your public key. If the hash matches, the message wasn't tampered with and it came from you.

Multiplying two primes is easy. Figuring out which primes were multiplied is hard. Every HTTPS connection depends on that.