Walk through a complete RSA computation with small numbers: key generation, encryption, and decryption.

Question

Accepted Answer

Choose $p=11, q=17$. Then $N=187$, $\varphi(N)=160$, choose $e=9$, compute $d=89$. Encrypt $m=5$: $c = 5^9 \mod 187 = 97$. Decrypt: $m = 97^{89} \mod 187 = 5$. ✓

* Squaring and reducing mod 187 at every step keeps the numbers tiny: 5² → 5⁴ → 5⁸ → 5⁹ lands on the ciphertext 97. *
Step 1 — Key Generation:

Choose primes: $p = 11$, $q = 17$
Compute modulus: $N = 11 \cdot 17 = 187$
Compute $\varphi(N) = (11-1)(17-1) = 10 \cdot 16 = 160$
Choose $e = 9$: check $\gcd(9, 160) = 1$ ✓ (160 = $2^5 \cdot 5$, no factor of 3)
Compute $d = e^{-1} \mod 160 = 9^{-1} \mod 160$

Need: $9 \cdot d \equiv 1 \mod 160$
$9 \cdot 89 = 801 = 5 \cdot 160 + 1$ ✓
So $d = 89$

Keys:

Public key: $(N, e) = (187, 9)$
Private key: $d = 89$

Step 2 — Encryption (Bob encrypts $m = 5$):
$$c = m^e \mod N = 5^9 \mod 187$$
Using square-and-multiply, reducing mod 187 at every step so the numbers stay small:

$5^2 = 25$
$5^4 = 25^2 = 625 \equiv 625 - 3 \cdot 187 = 64$
$5^8 = 64^2 = 4096 \equiv 4096 - 21 \cdot 187 = 169$
$5^9 = 5^8 \cdot 5^1 = 169 \cdot 5 = 845 \equiv 845 - 4 \cdot 187 = 97$

$$c = 97$$
Step 3 — Decryption (Alice decrypts $c = 97$):
$$m = c^d \mod N = 97^{89} \mod 187 = 5$$
(In practice computed with SAM; the result recovers the original message.)
Verification: $e \cdot d = 9 \cdot 89 = 801 = 5 \cdot 160 + 1 = 5 \cdot \varphi(N) + 1$ ✓
Common mistakes:

Computing $d \mod N$ instead of $d \mod \varphi(N)$ — the inverse is mod $\varphi(N)$!
Forgetting to check $\gcd(e, \varphi(N)) = 1$ before choosing $e$
Not reducing intermediate results mod $N$ during SAM (numbers explode)

Go deeper:

The RSA Encryption Algorithm — computing an example (Eddie Woo) — a small worked RSA calculation, step by step.
 Exponentiation by squaring (Wikipedia) — the square-and-multiply method used to keep the numbers small.