Key generation
public (n, e) · private (n, d)
p
17
q
11
n = p·q
187
φ(n) = (p−1)(q−1)
160
e
7
d ≡ e⁻¹ mod φ(n)
23
Extended Euclidean · finding s so that e·s + φ(n)·t = 1, then d = s mod φ(n)
| i | aᵢ | bᵢ | qᵢ = ⌊aᵢ/bᵢ⌋ | rᵢ = aᵢ − qᵢ·bᵢ | sᵢ | tᵢ |
|---|---|---|---|---|---|---|
| 0 | 7 | 160 | 0 | 7 | 1 | 0 |
| 1 | 160 | 7 | 22 | 6 | -22 | 1 |
| 2 | 7 | 6 | 1 | 1 | 23 | -1 |
| 3 | 6 | 1 | 6 | 0 | -160 | 7 |
Bézout: 7 · 23 + 160 · -1 = 1. Reducing s mod φ(n) gives d = 23.
Encrypt · decrypt
c = m^e mod n · m = c^d mod n
m (plaintext)
88
c = m^e mod n
11
c^d mod n
88
Square-and-multiply · Encrypt · 88^7 mod 187
| bit # | bit | square (acc²) | multiply? | accumulator |
|---|---|---|---|---|
| 2 | 1 | 1 | × base | 88 |
| 1 | 1 | 77 | × base | 44 |
| 0 | 1 | 66 | × base | 11 |
Square-and-multiply · Decrypt · 11^23 mod 187
| bit # | bit | square (acc²) | multiply? | accumulator |
|---|---|---|---|---|
| 4 | 1 | 1 | × base | 11 |
| 3 | 0 | 121 | — | 121 |
| 2 | 1 | 55 | × base | 44 |
| 1 | 1 | 66 | × base | 165 |
| 0 | 1 | 110 | × base | 88 |
Round trip OK · c^d mod n = 88 = m
Try as text · each letter is one RSA block
Letters a–z are encoded as 1–26. With small primes this is just a demonstration — the encoding is deterministic so the same plaintext always gives the same ciphertext (no padding), which is why real RSA uses OAEP and 2048-bit moduli.
| char | m | c = m^e mod n | c^d mod n | back |
|---|---|---|---|---|
| r | 18 | 171 | 18 | r |
| s | 19 | 145 | 19 | s |
| a | 1 | 1 | 1 | a |
«rsa» → «rsa»