Cryptographie et arithmétique modulaire

L'arithmétique modulaire consiste à travailler avec les restes de la division euclidienne. Deux entiers a et b sont congrus modulo n s'ils ont le même reste dans la division par n. Par exemple, 17 et 5 sont congrus modulo 12 car 17 = 1×12 + 5. Cette notion est naturelle avec une horloge : après 12 heures, on revient à 0. En terminale, on note a ≡ b [n] et on dit que n divise la différence a − b.

Les congruences se comportent bien avec l'addition et la multiplication : si a ≡ b [n] et c ≡ d [n], alors a+c ≡ b+d [n] et a×c ≡ b×d [n]. Cela permet de simplifier les calculs en remplaçant chaque nombre par son reste. Pour les puissances, on peut réduire la base modulo n avant de calculer. Par exemple, pour trouver le chiffre des unités de 7^4, on travaille modulo 10 : 7 ≡ 7 [10], 7^2 ≡ 49 ≡ 9 [10], donc 7^4 ≡ 9^2 ≡ 81 ≡ 1 [10].

Le chiffrement affine code une lettre par un nombre x entre 0 et 25, puis applique la fonction y ≡ ax + b [26]. Pour décoder, il faut inverser cette fonction, donc trouver un entier a^{-1} tel que a×a^{-1} ≡ 1 [26]. Cet inverse n'existe que si a et 26 sont premiers entre eux. Par exemple, avec a = 5 et b = 8, la lettre C (x = 2) devient y ≡ 5×2 + 8 ≡ 18 [26], soit la lettre S. Pour décoder, on utilise x ≡ a^{-1}(y − b) [26].

Le système RSA, utilisé pour sécuriser les transactions en ligne, repose sur la difficulté de factoriser un grand nombre en produit de deux nombres premiers. On choisit deux grands nombres premiers p et q, puis on calcule n = p×q et φ(n) = (p−1)(q−1). La clé publique contient n et un exposant e premier avec φ(n). La clé privée est l'inverse de e modulo φ(n). Coder un message M consiste à calculer C ≡ M^e [n] ; décoder nécessite la clé privée d pour calculer M ≡ C^d [n].