Inverse Modulaire et RSA

[invite78f958b1]

Bonjour,
je suis en train de faire des recherches sur ce système de chiffrement. Cependant, je bloque sur le calcul d'inverse Modulaire.

Tout d'abord, le système RSA demande de déterminer l'exposant de chiffrement (la clé publique) E et l'exposant de déchiffrement (clé privée) D.

Je sais que E doit être premier avec (p-1)*(q-1) (p et q étant deux nombres premiers que j'avais choisi au hasard). Avec l'algorithme d'Euclide puis le Théorème de Bézout, je peux déterminer E.

Cependant, je bloque sur D. J'ai lu que D devait vérifier la relation: E*D mod[(p-1)(q-1)]=1
Il faut donc utiliser l'inverse modulaire mais je ne connais pas la méthode pour la déterminer.

Prenons un exemple
Pour E=79, p=47 et q=71

d'où: 79*D mod[(3220)]=1
Je sais que la réponse est D=1019 (et si je tape à la calculatrice, je retrouve bien un reste de 1).
Comment a t-on pû trouver ce nombre ?


Merci de votre aide
-----

[invite6acfe16b]

Salut,

On utilise ce qu'on appelle l'algorithme d'Euclide Etendu.
Etant donné deux nombre a et b, il permet de trouver des entiers x et y t.q.

En particulier, si a et b sont premiers entre eux (dans ton cas : a=e et b=(p-1)(q-1)), on a

Cette équation modulo (p-1)(q-1) donne
et donc x est le d que tu cherches.

Regarde sur Wikipedia pour l'algorithme d'Euclide Etendu. Tu remarqueras que cela se programme presque de la même manière que celui d'Euclide simple, mais que l'on doit faire un retour en arrière à la fin.

[sylvainc2]

Pour l'algo d'Euclide étendu itératif (pas récursif, qui est à éviter si tu veux le programmer sur ordinateur), regarde mon message ici:
http://forums.futura-sciences.com/ma...-spe-math.html

Dans ton exemple, tu voudrais résoudre 3220x + 79y = 1 pour trouver l'inverse de 79 modulo 3220. En suivant la méthode décrite dans le tableau tu devrais trouver 3220*(-25) + 79*1019 = 1 et l'inverse est bien 1019.

[invite78f958b1]

D'accord, je pense avoir compris.
Merci beaucoup !

[A voir en vidéo sur Futura]