Mathématiques expertes (option) · Terminale · Arithmétique

Applications à la cryptographie

• Chiffrer, c'est transformer un message en suite d'entiers, puis appliquer une opération modulaire inversible ; déchiffrer, c'est appliquer l'opération réciproque.
• Chiffrement affine : $y \equiv ax+b \pmod{26}$, réversible si et seulement si $\operatorname{PGCD}(a,26)=1$ ; l'inverse de $a$ se trouve avec l'algorithme d'Euclide étendu (Bézout).
• RSA : $n=pq$, $\varphi(n)=(p-1)(q-1)$, $e$ premier avec $\varphi(n)$, $d$ inverse de $e$ modulo $\varphi(n)$. Clé publique $(n,e)$, clé privée $d$.
• Chiffrer : $c \equiv m^e \pmod n$ ; déchiffrer : $m \equiv c^d \pmod n$. La preuve repose sur le petit théorème de Fermat appliqué modulo $p$ puis modulo $q$.