Public-Key Cryptography: RSA

RSA is simply a way to let anyone send you a secret message without the two of you ever meeting to agree on a password. The name is just the initials of its inventors, Rivest, Shamir and Adleman, who published it in 1977. Think of it as handing out open padlocks: anyone can snap one shut on a box (that's the public key), but only you have the key that opens it. The formulas look like a lot, but there are only three pieces: $c = m^e \bmod n$ (lock the message $m$ by raising it to the power $e$), $m = c^d \bmod n$ (unlock it with a different power $d$) and $ed \equiv 1 \pmod{(p-1)(q-1)}$ (the rule that makes $d$ undo $e$). Everything else in this lesson is a tool you already built in this unit.

This is where the whole unit pays off. Primes, Euclid's algorithm, modular powers and inverses each play a part.

Key generation.

1. Pick two large primes $p$ and $q$ and compute $n = pq$.
2. Compute $\varphi = (p - 1)(q - 1)$.
3. Choose $e$ with $\gcd(e, \varphi) = 1$, and let $d = e^{-1} \bmod \varphi$.
4. Publish $(n, e)$; keep $d$ (and $p$, $q$) secret.

Step 3 is the inverse from the last lesson, found with the extended Euclidean algorithm, and it exists because we chose $e$ to share no factor with $\varphi$.

Why decryption works. Remember how $3^6 \equiv 1 \pmod 7$ made big powers easy? Euler's theorem says the same kind of thing always happens: $m^{\varphi} \equiv 1 \pmod n$ when $\gcd(m, n) = 1$. So exponents only matter mod $\varphi$. Since $ed = 1 + k\varphi$, we get $c^d = m^{ed} = m \cdot (m^{\varphi})^k \equiv m \pmod n$. (It works for the other messages too, by the Chinese remainder theorem.) Euler's theorem generalizes Fermat's little theorem: $a^{p-1} \equiv 1 \pmod p$ for a prime $p$ not dividing $a$.

Toy example. $p = 5$, $q = 11$, $n = 55$, $\varphi = 40$, $e = 3$, $d = 27$ (since $3 \cdot 27 = 81 \equiv 1 \pmod{40}$). The message $m = 9$ encrypts to $9^3 = 729 \equiv 14 \pmod{55}$, and $14^{27} \equiv 9 \pmod{55}$ brings it back.

Security. Think about what an eavesdropper would need. Anyone can compute $d$ from $e$ if they know $\varphi$, and $\varphi$ is easy given $p$ and $q$. So RSA is only as strong as the difficulty of factoring $n$. Multiplying two primes is quick, but undoing it is believed to be very hard: for 2048-bit moduli it's far beyond any known classical computer.

A common mistake. It's tempting to think the secret is the exponent $e$, or the modulus $n$, since those are what you compute with. It isn't: both are published for the whole world to see. The only secrets are $d$ and the primes $p$ and $q$ it came from.

Browsers use RSA or its relatives to set up secure connections and to check that software updates really come from their publishers.