GoupillWiki

Outils pour utilisateurs

Outils du site

Piste :
nsi:terminales:chiffrement_modulo

Différences

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

Lien vers cette vue comparative

Les deux révisions précédentesRévision précédente
Prochaine révision		Révision précédente
nsi:terminales:chiffrement_modulo [2021/07/05 18:29] – goupillwikinsi:terminales:chiffrement_modulo [2022/03/29 04:24] (Version actuelle) – ↷ Liens modifiés en raison d'un déplacement. 154.54.249.197
Ligne 3: Ligne 3:
 ===== 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$. 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. 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$$
  
 5 est donc le **reste** de la division entière de 53 par 12 ce qui s'écrit en Python : 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> </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]$.+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 ===== ===== Multiplications modulo =====
  
-<WRAP group> +Le modulo a une propriété intéressante : on peut le distribuer sur l'addition et la multiplication. Voyons sur un exemple :
-<WRAP half column> +
-Le modulo a une propriété intéressante que nous allons voir sur un exemple :+
  
   * $(17 \times 23) \mod 7 = 391 \mod 7 = 6$   * $(17 \times 23) \mod 7 = 391 \mod 7 = 6$
Ligne 47: Ligne 45:
 </code> </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 -- à droite)+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)
  
-> 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> 
-<WRAP half column> 
 <code python> <code python>
->>> 45 % 7 +>>> 45 % 7, 17 % 7, 22 % 7, 16 % 7, 29 % 7, 89 % 7, 12 % 7  
-3 +(3, 3, 1, 2, 1, 5, 5) 
->>> 3 * 17 +>>> 3 * 3 % 7
-51 +
->>> 51 % 7+
 2 2
->>> 2 * 22 +>>> 2 * 1 % 7
-44 +
->>> 44 % 7+
 2 2
->>> 2 * 16 +>>> 2 * 2 % 7
-32 +
->>> 32 % 7+
 4 4
->>> 4 * 29 +>>> 4 * 1 % 7
-116 +
->>> 116 % 7+
 4 4
->>> 4 * 89 +>>> 4 * 5 % 7
-356 +
->>> 356 % 7+
 6 6
->>> 6 * 12 +>>> 6 * 5 % 7
-72 +
->>> 72 % 7+
 2 2
 </code> </code>
-</WRAP>+ 
 + 
 + 
 +<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> </WRAP>
  
Ligne 90: Ligne 77:
 Supposons que je vous dise $d = 5$ puis $d^a = 244140625$, et que je vous demande : que vaut $a$ ? 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)}{\frac{\ln(d)}}$.+Avec les logarithmes, la solution est très simple : $a = \frac{\ln(244140625)}{\ln(d)} = 12$.
  
 <code python> <code python>
Ligne 118: Ligne 105:
 </WRAP> </WRAP>
  
-Les techniques cryptographiques exploitant des formules arithmétiques utilisent ces propriétés de modulo. Vous pouvez voir le cas du [[nsi:projets:elgamal|chiffrement de ElGamal]] et le programme de TNSI prévoit l'étude du [[rsa|chiffrement RSA]].+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> <WRAP tip>
nsi/terminales/chiffrement_modulo.1625502599.txt.gz · Dernière modification : de goupillwiki