GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Modulo et chiffrement ======

===== Rappel de ce qu'est modulo =====

{{ :nsi:tds:modulo_points.png?nolink&200|}}

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 :

<code python>
>>> 53 % 12
5
</code>

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

===== Multiplications modulo =====

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$

<code python>
>>> 17 * 23 % 7
6
>>> (17 % 7) * (23 % 7)
6
</code>

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$$

<code python>
>>> 45 * 17 * 22 * 16 * 29 * 89 * 12
8340140160
>>> 8340140160 % 7
2
</code>

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)

<code python>
>>> 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
</code>



<WRAP tip>
  * Ne croyez pas que décomposer est plus long pour la machine : la machine ne sait de toutes façons pas calculer ''%%45 * 17 * 22 * 16 * 29 * 89 * 12%%'', elle fait le calcul par étape.
  * En appliquant modulo progressivement, on n'a jamais de trop grand nombre. C'est important car en cryptographie, on utilise de très grand nombre et on ne veut pas que des calculs intermédiaires fassent apparaître des nombres encore plus grands.
</WRAP>

===== Intérêt pour la cryptographie =====

==== Sans modulo ====

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

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

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

==== Avec modulo ====

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

^ $a$          ^ 1 ^ 2 ^ 3 ^  4 ^  5 ^ 6 ^  7 ^  8 ^  9 ^ 10 ^ 11 ^ 12 ^
| $d^a \mod p$ | 5 | 8 | 6 | 13 | 14 | 2 | 10 | 16 | 12 |  9 | 11 |  4 |

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

<WRAP important>
Dans le cas réel, les nombres utilisés sont extrêmement grands et produire ce tableau peut devenir très très long pour la machine, si long que ça en devient impossible.
</WRAP>

Les techniques cryptographiques exploitant des formules arithmétiques utilisent ces propriétés de modulo. Vous pouvez voir le cas du [[nsi:tds:cryptographie:elgamal|chiffrement de ElGamal]] et le programme de TNSI prévoit l'étude du [[.securite:rsa|chiffrement RSA]].

<WRAP tip>
Dans l'exemple, $p= 17$ est premier. La primalité est un ingrédient très important de ces chiffrements.
</WRAP>