Cryptographie : Signature numérique et Chiffrement

Congruences modulo n

Modulo m

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. On peut aussi remplacer tous les résultats intermédiaires par leur reste modulo m. Pour calculer 14×(7+2)¹⁵ modulo 8, on remarque que 7+2=9=1 modulo 8, d'où (7+2)¹⁵=1 modulo 8, et 14×(7+2)¹⁵=14=6 mod 8.

Congruences

On dit que « a est congru à b modulo n » , et l'on note (avec # voulant dire modulo)
```
a # b [ n ]
si a peut s'écrire :
a = n.q + b avec 0 < b < n
```
r est le reste de la division de a par n

q est le quotient

ex: 15 = 7 × 2 + 1 donc 15 # 1 [ 7 ]
Si a # 0 [ n ] alors a est un multiple de n

Exemple 1 :
Dire que A est congru à 30757 modulo 10 c'est dire que si on divise A par 10 et 30757 par 10, le reste est le même.

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é.

Exemple 2 :

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