Modulo et chiffrement

Le modulo suit le principe des points d'une horloge. Prenons les points sur le cercle à droite. Nous avons 12 points sur le cercle, il s'agit donc d'un $\mod 12$.

L'idée est de compter les points dans le sens indiqué et si on dépasse 11, de continuer en boucle. À ce jeu, on réalisera que le nombre 53 tombera en face de 5.

$$53 = 4 \times 12 + 5 \Rightarrow 53\mod 12 = 5$$

5 est donc le reste de la division entière de 53 par 12 ce qui s'écrit en Python :

>>> 53 % 12
5

53 est donc au même endroit que 5 sur notre cercle. Le mathématicien, rigoureux, ne dira pas que 53 est égal à 5. Il dira que ces deux nombres sont équivalents d'un certain point de vue et il pourra l'écrire de cette façon $53 \equiv 5 \, [12]$ ou encore $53 \overset{12}{\equiv} 5$.

Le modulo a une propriété intéressante : on peut le distribuer sur l'addition et la multiplication. Voyons sur un exemple :

• $(17 \times 23) \mod 7 = 391 \mod 7 = 6$
• $(17 \mod 7) \times (23 \mod 7) = 3 \times 2 = 6$

>>> 17 * 23 % 7
6
>>> (17 % 7) * (23 % 7)
6

Voici un autre exemple. Supposons que l'on veuille calculer :

$$(45 \times 17 \times 22 \times 16 \times 29 \times 89 \times 12) \mod 7$$

>>> 45 * 17 * 22 * 16 * 29 * 89 * 12
8340140160
>>> 8340140160 % 7
2

Calculer la multiplication d'abord puis le modulo fait passer par un grand nombre intermédiaire. Voici ce que l'on aurait intérêt à faire (en décomposant)

>>> 45 % 7, 17 % 7, 22 % 7, 16 % 7, 29 % 7, 89 % 7, 12 % 7 
(3, 3, 1, 2, 1, 5, 5)
>>> 3 * 3 % 7
2
>>> 2 * 1 % 7
2
>>> 2 * 2 % 7
4
>>> 4 * 1 % 7
4
>>> 4 * 5 % 7
6
>>> 6 * 5 % 7
2

Supposons que je vous dise $d = 5$ puis $d^a = 244140625$, et que je vous demande : que vaut $a$ ?

Avec les logarithmes, la solution est très simple : $a = \frac{\ln(244140625)}{\ln(d)} = 12$.

>>> d = 5
>>> from math import log
>>> log(244140625)/log(d)
12.000000000000002

Le résultat n'est pas exact mais on trouve sans peine la réponse : $a = 12$.

On introduit le nombre $p = 17$. On a toujours $d = 5$. Maintenant je dis : $d^a \mod p = 4$ et je demande toujours combien vaut $a$ ?

On ne peut plus répondre directement. Le modulo embrouille le calcul. tout ce qu'on peut faire, c'est calculer les $d^a \mod p$ pour tous les $a$.

Par exemple, $d^2 = 5^2 = 25$ donc $d^2 \mod p = 25 \mod 17 = 8$.

On constate que la réponse est $a = 12$.

Les techniques cryptographiques exploitant des formules arithmétiques utilisent ces propriétés de modulo. Vous pouvez voir le cas du chiffrement de ElGamal et le programme de TNSI prévoit l'étude du chiffrement RSA.