Différences

Ci-dessous, les différences entre deux révisions de la page.

--- nsi:terminales:chiffrement_modulo [2021/07/05 18:10] – créée goupillwiki
+++ nsi:terminales:chiffrement_modulo [2022/03/29 04:24] (Version actuelle) – ↷ Liens modifiés en raison d'un déplacement. 154.54.249.197
@@ Ligne 1: / Ligne 1: @@
 ====== Modulo et chiffrement ======
-==== Rappel de ce qu'est modulo ====
+===== Rappel de ce qu'est modulo =====
-{{ :nsi:projets:modulo_points.png?nolink&200|}}
+{{ :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$.
@@ Ligne 9: / Ligne 9: @@
 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$
+$$53 = 4 \times 12 + 5 \Rightarrow 53\mod 12 = 5$$
 est donc le **reste** de la division entière de 53 par 12 ce qui s'écrit en Python :
@@ Ligne 18: / Ligne 18: @@
 </code>
-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]$.
+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 ====
+===== Multiplications modulo =====
-Le modulo a une propriété intéressante que nous allons voir sur un exemple :
+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 \times 23) \mod 7 = 391 \mod 7 = 6$
   * $(17 \mod 7) \times (23 \mod 7) = 3 \times 2 = 6$
@@ Ligne 48: / Ligne 48: @@
 <code python>
->>> 45 % 7
+>>> 45 % 7, 17 % 7, 22 % 7, 16 % 7, 29 % 7, 89 % 7, 12 % 7
+(3, 3, 1, 2, 1, 5, 5)
->>> 3 * 17
+>>> 3 * 3 % 7
->>> 51 % 7
->>> 2 * 22
+>>> 2 * 1 % 7
->>> 44 % 7
->>> 2 * 16
+>>> 2 * 2 % 7
->>> 32 % 7
->>> 4 * 29
+>>> 4 * 1 % 7
->>> 116 % 7
->>> 4 * 89
+>>> 4 * 5 % 7
->>> 356 % 7
->>> 6 * 12
+>>> 6 * 5 % 7
->>> 72 % 7
 </code>
@@ Ligne 78: / Ligne 66: @@
+<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 ====
-Le résultat est le même et si je vous le mets en avant, c'est parce que ce n'est pas un hasard : C'est toujours le cas. On peut multiplier d'abord puis faire modulo, ou faire modulo d'abord puis multiplier (et éventuellement refaire 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)
+.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>