Cryptographie RSA démontrer une relation
Utilisateur anonyme
-
greg6614 Messages postés 629 Statut Membre -
greg6614 Messages postés 629 Statut Membre -
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
- La base de données de sécurité du serveur n'a pas de compte d'ordinateur pour la relation ✓ - Forum Access
- Relation d'approbation - Forum Windows serveur
- La partie de l'image avec l'id de relation rid1 n'a pas été trouvé dans le fichier - Forum Word
- Forum héritage et rsa ✓ - Forum Vos droits sur internet
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.
