L'arithmétique modulaire
Il est commode en cryptographie de considérer les entiers modulo m. Deux entiers a et b sont égaux (ou congrus) modulo m si a-b est un multiple de m. On note a=b mod m, et Z/mZ l'ensemble {0,...,m-1} : tout entier est égal modulo m à un unique élément de Z/mZ (son reste dans la division euclidienne par m). Les calculs usuels (addition, multiplication, puissance) peuvent être réalisés modulo m, exactement comme avec les entiers. Il suffit ensuite de réduire le résultat modulo m, c'est-à-dire de prendre le reste modulo m. On peut aussi remplacer tous les résultats intermédiaires par leur reste modulo m. Pour calculer 14×(7+2)15 modulo 8, on remarque que 7+2=9=1 modulo 8, d'où (7+2)15=1 modulo 8, et 14×(7+2)15=14=6 mod 8. L'utilisation des congruences est d'emploi plus courant qu'il n'y parait : s'il est 11H, dans 2H, il est 1H, car 11+2=13=1 mod 12! Le chiffrement de Vigenère peut en particulier être interprété en termes d'arithmétique modulaire. Chaque lettre est codé par un nombre qui correspond à son ordre dans l'alphabet (A->01,B->02,...). Les calculs s'effectuent modulo 26. Si M est l'entier qui correspond à la lettre du mot que l'on est en train de coder, et si K est la lettre de la clé correspondante, C=M+K mod 26 représente la lettre du message codé. Ex :| Mot à chiffrer | E | N | V | E | R | G | U | R | E |
| Clé | M | A | T | H | M | A | T | H | M |
| M | 5 | 14 | 22 | 5 | 18 | 7 | 21 | 18 | 5 |
| K | 13 | 1 | 20 | 8 | 13 | 1 | 20 | 8 | 13 |
| C | 18 | 15 | 16 | 13 | 5 | 8 | 15 | 26 | 18 |
| Mot codé | R | O | P | M | E | H | O | Z | R |
Consulter aussi