RSA (Rivest, Shamir and Adleman, 1977) lets anyone encrypt a message to you with a public key, while only you can decrypt it. It is Euler's theorem plus modular inverses plus one fact: multiplying primes is easy, but factoring their product is hard.
- Setup. Choose primes $p \ne q$. Let $n = pq$ and $\varphi(n) = (p - 1)(q - 1)$.
- Choose $e$ with $\gcd(e, \varphi(n)) = 1$, and compute $d \equiv e^{-1} \pmod{\varphi(n)}$.
- Public key: $(n, e)$. Private key: $d$ (and keep $p$, $q$, $\varphi(n)$ secret).
- Encrypt a message $0 \le m < n$: $c = m^{e} \bmod n$. Decrypt: $m = c^{d} \bmod n$.
Why it works
Since $ed \equiv 1 \pmod{\varphi(n)}$, write $ed = 1 + k\varphi(n)$. If $\gcd(m, n) = 1$, Euler's theorem gives $$c^{d} = m^{ed} = m \cdot \left(m^{\varphi(n)}\right)^{k} \equiv m \cdot 1 = m \pmod{n}.$$ (It also works when $\gcd(m, n) > 1$: check mod $p$ and mod $q$ separately with Fermat, then use the CRT.) Finding $d$ requires $\varphi(n)$, and knowing $\varphi(n) = n - p - q + 1$ is as good as knowing $p$ and $q$. So breaking RSA this way means factoring $n$, which for 600-digit numbers is far out of reach.
Worked example: Making keys
Make RSA keys from $p = 11$, $q = 17$ and $e = 7$.
- $n = 11 \cdot 17 = 187$ and $\varphi(n) = 10 \cdot 16 = 160$.
- $\gcd(7, 160) = 1$. Extended Euclid: $160 = 7 \cdot 22 + 6$, $7 = 6 + 1$, so $1 = 7 - 6 = 7 - (160 - 22 \cdot 7) = 23 \cdot 7 - 160$.
- So $d = 23$. Check: $7 \cdot 23 = 161 = 160 + 1$.
Answer: Public $(187, 7)$, private $d = 23$.
Worked example: Encrypting and decrypting
With $(n, e) = (187, 7)$ and $d = 23$, encrypt $m = 42$, then decrypt.
- $42^{2} = 1764 \equiv 1764 - 9 \cdot 187 = 81$, $\ 42^{4} \equiv 81^{2} = 6561 \equiv 16$.
- $42^{7} = 42^{4} \cdot 42^{2} \cdot 42 \equiv 16 \cdot 81 \cdot 42$: $16 \cdot 81 = 1296 \equiv 174$, then $174 \cdot 42 = 7308 \equiv 15$. So $c = 15$.
- Decrypt: $15^{23} \bmod 187$ by repeated squaring ($23 = 16 + 4 + 2 + 1$) gives $42$, the original message.
Answer: $c = 15$, and $15^{23} \equiv 42$.
Worked example: Breaking a tiny key
Eve sees the public key $(n, e) = (187, 7)$. Show how factoring $n$ gives her the private key.
- Trial division up to $\sqrt{187} \approx 13.7$: $187 = 11 \cdot 17$.
- Then $\varphi(187) = 10 \cdot 16 = 160$, and $d = 7^{-1} \bmod 160 = 23$, exactly Alice's private key.
- For a 600-digit $n$, the best known factoring methods would run for far longer than the age of the universe on ordinary computers. That gap is the whole security of RSA.
Answer: $d = 23$, once $n$ is factored.
Common mistake
Finding $d$ as the inverse of $e$ mod $n$ instead of mod $\varphi(n)$. Here $7^{-1} \bmod 187 = 107$, and decrypting with it gives $15^{107} \equiv 60 \pmod{187}$, not $42$. The exponent identity comes from Euler's theorem, so exponents work mod $\varphi(n) = (p - 1)(q - 1)$.
Real RSA uses primes with hundreds of digits, $e = 65537$, and a padding scheme that randomizes each message; textbook RSA as above is for understanding, not for protecting secrets.
Key idea
RSA: $n = pq$, $d \equiv e^{-1} \pmod{(p - 1)(q - 1)}$. Encrypt $c = m^{e}$, decrypt $m = c^{d}$, both mod $n$. Euler's theorem makes them inverse; the difficulty of factoring $n$ keeps $d$ secret.