Pour le RSA, comment dois-je calculer l'exposant secret?
-
13-09-2020 - |
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
La solution
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 (une)d = unde mod m
.Mais
depuis de = 1 mod phi(m)
, Euler indicateur théorème nous dit qu'unde est congruent
pour un1 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é.