Cryptographie RSA démontrer une relation
Fermé
Utilisateur anonyme
-
Modifié par raminoudoudou2 le 17/03/2016 à 17:13
greg6614 Messages postés 592 Date d'inscription vendredi 7 août 2009 Statut Membre Dernière intervention 3 juin 2017 - 18 mars 2016 à 09:20
greg6614 Messages postés 592 Date d'inscription vendredi 7 août 2009 Statut Membre Dernière intervention 3 juin 2017 - 18 mars 2016 à 09:20
A voir également:
- Cryptographie RSA démontrer une relation
- La base de données de sécurité du serveur n'a pas de compte d'ordinateur pour la relation ✓ - Forum Bases de données
- Relation d'approbation et un seul domaine - Forum Logiciels
- La partie de l'image avec l'id de relation rid2 n'a pas été trouvé dans le fichier - Forum Word
- La partie de l'image avec l'ID de relation rId2 n'a pas été trou - Forum Powerpoint
- La relation d'approbation entre cette station de travail... - Forum Réseau
2 réponses
greg6614
Messages postés
592
Date d'inscription
vendredi 7 août 2009
Statut
Membre
Dernière intervention
3 juin 2017
107
Modifié par greg6614 le 17/03/2016 à 18:37
Modifié par greg6614 le 17/03/2016 à 18:37
Salut,
Prenons un exemple simple avec
Pour utiliser le théorème de Fermat tu convertis déjà ton exposant, ici 6, en base 2, soit 110.
Ensuite pour chaque bit de ton exposant tu fais (103^2)^0 mod (35) avec 0 étant l'indice de de ton bit. Soit donc ici :
Pour rappel le bit avec le poids le plus faible et donc le plus petit indice est à droite et les indices commencent toujours à 0.
Or il se trouve que si l'on note ces trois fromule A,B et C on constate que
Soit le résultat précédent élevé au carré modulo 35.
Ce que nous donne :
Et maintenant pour finir pour chaque indice de ton exposant où ton bit vaut 1 tu fais un le produit de tes résultats. Exemple ici le bit le plus à droite, donc celui avec l'indice 0, vaut 0. Il ne sera donc pas compté.
Cela nous donne alors :
Un vérification rapide à la calculatrice montre que c'est bien le bon résultat. Évidement pour une petite valeur comme ici le théorème de Fermat n'est pas le plus court bien que l'on ne soit pas loin du débordement sur la calculatrice.
Voilà j’espère avoir était clair. Expliquer de l'arithmétique à l'écrit n'est pas très simple. Si tu as des soucis ou des questions n'hésite pas.
En espérant t'avoir aidé
Greg
Prenons un exemple simple avec
103^6 mod (35).
Pour utiliser le théorème de Fermat tu convertis déjà ton exposant, ici 6, en base 2, soit 110.
Ensuite pour chaque bit de ton exposant tu fais (103^2)^0 mod (35) avec 0 étant l'indice de de ton bit. Soit donc ici :
(103^2)^0 mod (35)
(103^2)^1 mod (35)
(103^2)^2 mod (35)
Pour rappel le bit avec le poids le plus faible et donc le plus petit indice est à droite et les indices commencent toujours à 0.
Or il se trouve que si l'on note ces trois fromule A,B et C on constate que
B = A^2 mod (35)
C = B^2 mod (35)
Soit le résultat précédent élevé au carré modulo 35.
Ce que nous donne :
(103^2)^0 mod (35) = 103 mod (35) = 33
(103^2)^1 mod (35) = 33^2 mod (35) = 4
(103^2)^2 mod (35) = 4^2 mod (35) = 16
Et maintenant pour finir pour chaque indice de ton exposant où ton bit vaut 1 tu fais un le produit de tes résultats. Exemple ici le bit le plus à droite, donc celui avec l'indice 0, vaut 0. Il ne sera donc pas compté.
Cela nous donne alors :
103^6 mod (35) = 4 * 16 mod (35) = 64 mod (35) = 29
Un vérification rapide à la calculatrice montre que c'est bien le bon résultat. Évidement pour une petite valeur comme ici le théorème de Fermat n'est pas le plus court bien que l'on ne soit pas loin du débordement sur la calculatrice.
Voilà j’espère avoir était clair. Expliquer de l'arithmétique à l'écrit n'est pas très simple. Si tu as des soucis ou des questions n'hésite pas.
En espérant t'avoir aidé
Greg
greg6614
Messages postés
592
Date d'inscription
vendredi 7 août 2009
Statut
Membre
Dernière intervention
3 juin 2017
107
17 mars 2016 à 19:06
17 mars 2016 à 19:06
Autant pour moi j'avais lu trop vite, tu veux donc démontrer que
m1 mod(p) = m2 mod(q) c'est bien ça ?
m1 mod(p) = m2 mod(q) c'est bien ça ?
greg6614
Messages postés
592
Date d'inscription
vendredi 7 août 2009
Statut
Membre
Dernière intervention
3 juin 2017
107
17 mars 2016 à 19:12
17 mars 2016 à 19:12
As-tu essayé de faire un calcul avec tes valeurs trouvé pour vérifier l'égalité ? A partir de là tu pourrai plus facilement remonter pour démontrer l'égalité.
17 mars 2016 à 18:43