Le protocole RSA

Par construction $ed=1+k\phi (n)$ pour un $k\in \mathbb{N}$. Le théorème d'Euler ($m\wedge n=1$) donne $m^{\phi (n)}\equiv 1[n]$, d'où $${\left(m^e\right)}^d=m^{1+k\phi (n)}=m{\left(m^{\phi (n)}\right)}^k\equiv m[n].$$ Le chiffrement $m\mapsto m^e[n]$ (clef publique $(n,e)$) est inversé par $c\mapsto c^d[n]$ (clef privée $d$) — et calculer $d$ exige $\phi (n)$, donc la factorisation de $n$ : toute la sécurité tient à la difficulté de factoriser.

Exemple : $n=33$, $\phi (33)=2\times 10=20$, $e=3$ ($3\wedge 20=1$), $d=7$ (car $3\times 7=21\equiv 1[20]$). Chiffrement de $m=4$ : $c=4^3=64\equiv 31[33]$. Déchiffrement : $31\equiv -2[33]$, donc $$c^7\equiv (-2{)}^7=-128\equiv -128+4\times 33=4[33]:m\text{ est retrouveˊ.}✓$$ (Le RSA « miniature » entrevu en première année repose donc exactement sur Euler — c'est-à-dire sur Lagrange dans $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ : trois chapitres d'algèbre dans une carte bancaire.)