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 :)
2 réponses
-
Salut,
Prenons un exemple simple avec103^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 -
Autant pour moi j'avais lu trop vite, tu veux donc démontrer que
m1 mod(p) = m2 mod(q) c'est bien ça ?
