Pour le RSA, comment dois-je calculer l'exposant secret?

Question

Pour le RSA, comment dois-je calculer l'exposant secret?

Compte tenu de p et q deux nombres premiers, et phi=(p-1)(q-1), et le public exposant (0x10001), comment puis-je obtenir le secret de l'exposant "d"?

J'ai lu que j'ai à faire: d = e^-1 mod phi à l'aide de l'inversion modulaire et la euclidienne équation mais je ne comprends pas comment la formule ci-dessus des cartes, soit à l' un^-1 ≡ x mod m formule sur la modularité de l'inversion de la page wiki, ou comment il est associé à la euclidienne, PGCD équation.

Quelqu'un peut-il aider s'il vous plaît, merci

Answer 1

Vous pouvez utiliser l' algorithme d'Euclide étendu pour résoudre d dans la congruence

de = 1 mod phi(m)

Pour le chiffrement RSA, e est la clé de cryptage, d est la clé de déchiffrement, et le chiffrement et le déchiffrement sont effectuées par exponentiation mod m.Si vous chiffrer un message a avec clé e, et puis le décrypter à l'aide de la clé d, vous calculer (un^e)^d = un^de mod m.Mais depuis de = 1 mod phi(m), Euler indicateur théorème nous dit qu'un^de est congruent pour un¹ mod m -- en d'autres termes, vous obtenez de retour à l'original a.

Il n'existe pas de moyens efficaces pour obtenir la clé de déchiffrement d ne connaissant que l' la clé de chiffrement e et le module m, sans connaître la factorisation m = pq, de sorte Le chiffrement RSA est censé être sécurisé.