Toy RSA - p=11, q=13

A tiny numerical example shows all the steps of RSA with computations you can do by hand.

Example — Toy RSA $p=11$, $q=13$

$n = 143$, $\varphi(n) = 10\cdot 12 = 120$. We choose $e=7$ (coprime with $120$). The inverse of $7$ modulo $120$ is found with the extended Euclidean algorithm: $7\cdot 103 = 721 = 6\cdot 120 + 1$, hence $d=103$.

Encoding the message $m=9$: $c = 9^7\bmod 143$. Computation: $9^2 = 81$, $9^4 = 81^2 = 6561 = 45\cdot 143 + 126\equiv 126$, hence $9^7 = 9^4\cdot 9^2\cdot 9 = 126\cdot 81\cdot 9 \pmod{143}.$ One finds $c \equiv 48\pmod{143}$.

Decoding: $48^{103}\bmod 143$. One verifies numerically (fast exponentiation) that it returns $9$. ✓

The message $\boxed{m=9}$ is encrypted into $c=48$ with the public key $(n,e)=(143,7)$ and recovered with the private key $d=103$: it is the whole mechanism of RSA on a toy scale.

Links

Topics: Distribuzioni probabilita
Concepts: Aritmetica modulare · Crittografia rsa
Methods: Rsa cifratura
Skills: Calcolare · Usare formule