Problème du cryptage RSA

[invite4b26dc46]

Salut!
J'aurai aimé trouver un peu d'aide sur ce forum en ce qui concerne le cryptage RSA. Le cryptage est très facile en soit:
Pour crypter, je prend p=47, q=71 et n=p*q=3337. Jusque là tout va bien. Je calcule Phi avec la formule d'Euler, ce qui me donne: Phi = (q - 1)*(p - 1) = 3220 dans notre cas. On prend e compris entre 2 et 3220. Je choisis e = 79. Et là commencent les difficultés car on me dit que d*e = 1mod(Phi). Je dois trouver d. Ce que je ne comprend pas c'est qu'on me dit que d = e^-1*mod(Phi) = 79^-1*mod(3220) = 1019! Je ne comprend absolument pas comment ce résultat a pu être trouvé. Si quelqu'un a une idée... Je l'écouterai voluntiers. Merci d'avance.
-----

[invite37968ad1]

Une méthode possible est ce bon algorithme d'Euclide

Il faut trouver d tel que d*e = 1 modulo phi
en valeur numérique, il faut trouver d et k tels que 79*d = 1+3220*k
Cela ressemble à une identité de Bézout, dont une des solutions se trouve grâce à l'algorithme d'Euclide
3220 = 40*79 + 60 donc 60 = 3220 - 40*79
79 = 1*60 + 19 donc 19 = 79 - 60
60 = 3*19 + 3 donc 3 = 60 - 3*19
19 = 6*3 + 1 donc 1 = 19 - 6*3
puis en remontant
1 = 19 - 6*(60-3*19) = 19*19 - 6*60
1 = 19*(79-60) - 6*60 = 19*79 - 25*60
1 = 19 * 79 - 25(3220 - 40*79)
1 = (19+25*40)*79 - 25*3200
donc d = 1019 (et accessoirement k = 25)

[invite4b26dc46]

Merci beaucoup Je suis très contente que tu m'ai aidé. J'ai très bien compris tes explications et je te remercie aussi pour les détails des calculs.
Voilà, il ne me reste plus maintenant que de développer mon code (en C et C++) et de m'occuper de la partie réseau et mon chat est fini. A bientôt j'espère. Adina.

[prgasp77]

c'est marrant, je viens juste de le terminer (y'a 5minutes) en php.
Un conseil : cripte tes donnees avant de les cripter en RSA.

[A voir en vidéo sur Futura]