Quiz Entry - updated: 2026.10.26
Summarize the complete RSA encryption protocol between Alice and Bob, including the security basis.
Alice generates keys, publishes $(N, e)$. Bob encrypts $m$ as $c = m^e \mod N$. Alice decrypts as $m = c^d \mod N$. Security relies on the factoring problem.
* Only the public key crosses the insecure channel; the private exponent $d$ never leaves Alice, so only she can recover $m$. *
The complete protocol:
| Alice | Unsecure Channel | Bob |
|---|---|---|
| Generates primes $p, q$ | ||
| $N = p \cdot q$ (~$10^{1000}$ ~3000 bit) | ||
| $\varphi(N) = (p-1)(q-1)$ | ||
| Chooses $e$ with $\gcd(e, \varphi(N)) = 1$ | ||
| $d \equiv e^{-1} \mod \varphi(N)$ | ||
| → Sends $(N, e)$ to Bob | ||
| Encrypts: $c = m^e \mod N$ | ||
| ← Sends $c$ | ||
| Decrypts: $m = c^d \mod N$ |
Security relies on two assumptions:
- $N = p \cdot q$ cannot be factored (if it could → compute $\varphi(N)$ → compute $d$)
- The $e$-th root $\sqrt[e]{c} \mod N$ cannot be directly computed without $d$
Current factoring records: $N \approx 10^{250}$ ≈ 830 bits. So $N \approx 10^{600}$ ≈ 2000 bits would still be safe, but all recommendations require 3000+ bits for long-term security.
Go deeper:
Public Key Cryptography — Computerphile — the padlock intuition behind the whole exchange.
Public-key cryptography (Wikipedia) — the general protocol RSA instantiates.