Cryptographie RSA démontrer une relation
Utilisateur anonyme
-
greg6614 Messages postés 592 Date d'inscription Statut Membre Dernière intervention -
greg6614 Messages postés 592 Date d'inscription Statut Membre Dernière intervention -
Bonjour,
Je ne sais pas trop où poster ma question alors je tente dans cette catégorie ^^
On a deux nombres premiers p et q, soit n le produit p.q.
On a e tel que e est premier avec (p-1)(q-1) et e est inférieur à (p-1)(q-1).
d est l'inverse de e modulo (p-1)(q-1) c'est-à-dire : d.e = 1 mod((p-1)(q-1)).
Le message a crypté est m qui devient c (c=message m crypté).
On sait que :
c = m^e mod(n).
m = c^d mod(n).
Dans l'exercice on a :
d1 = d mod(p-1).
d2 = d mod (q-1).
m1 = c^(d1) mod(p).
m2 = c^(d2) mod(q).
Montrer que :
m = m1 mod(p)
m = m2 mod(q)
On doit utiliser le petit théorème de Fermat et l'exponentiation binaire mais je ne vois pas comment aboutir.
Quelqu'un a-t-il une piste pour m'aider ? Merci :)
Je ne sais pas trop où poster ma question alors je tente dans cette catégorie ^^
On a deux nombres premiers p et q, soit n le produit p.q.
On a e tel que e est premier avec (p-1)(q-1) et e est inférieur à (p-1)(q-1).
d est l'inverse de e modulo (p-1)(q-1) c'est-à-dire : d.e = 1 mod((p-1)(q-1)).
Le message a crypté est m qui devient c (c=message m crypté).
On sait que :
c = m^e mod(n).
m = c^d mod(n).
Dans l'exercice on a :
d1 = d mod(p-1).
d2 = d mod (q-1).
m1 = c^(d1) mod(p).
m2 = c^(d2) mod(q).
Montrer que :
m = m1 mod(p)
m = m2 mod(q)
On doit utiliser le petit théorème de Fermat et l'exponentiation binaire mais je ne vois pas comment aboutir.
Quelqu'un a-t-il une piste pour m'aider ? Merci :)
A voir également:
- Cryptographie RSA démontrer une relation
- Une erreur est survenue lors de la création de la page. veuillez vous assurer de respecter les règles relatives aux pages. - Forum Facebook
- La base de données de sécurité du serveur n'a pas de compte d'ordinateur pour la relation - Forum Windows serveur
- Forfait internet rsa orange - Accueil - Box & Connexion Internet
- La relation d'approbation entre cette station de travail... - Forum Réseau
2 réponses
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
Utilisateur anonyme
Merci beaucoup pour tout ça, je savais déjà comment utiliser l'exponentiation binaire ^^' mais le problème c'est qu'ici je ne connais ni m, ni m1, ni m2 donc je ne peux pas faire un calcul pratique mais je dois bien faire une démonstration. Or je ne sais pas comment commencer.