Wie berechne ich für RSA den geheimen Exponenten?
-
13-09-2020 - |
Frage
Wie berechne ich für RSA den geheimen Exponenten?
Wenn p und q die beiden Primzahlen sind und phi = (p-1) (q-1) und der öffentliche Exponent (0x10001), wie erhalte ich den geheimen Exponenten 'd'?
Ich habe gelesen, dass ich tun muss: d = e-1 modphi wobei modulare Inversion und die euklidische Gleichung aber ich kann nicht verstehen, wie die obige Formel entweder der a-1 ≡ x Modell m formel auf der Wiki-Seite zur modularen Inversion oder wie sie der euklidischen GCD-Gleichung zugeordnet wird.
Kann mir bitte jemand helfen, Prost
Lösung
Sie können das verwenden erweiterter euklidischer Algorithmus lösen für d
in der Kongruenz
de = 1 mod phi(m)
Für RSA-Verschlüsselung, e
ist der Verschlüsselungsschlüssel, d
ist der Entschlüsselungsschlüssel und die Verschlüsselung
und Entschlüsselung werden beide durch Potenzierungsmod durchgeführt m
.Wenn Sie eine Nachricht verschlüsseln a
mit Schlüssel e
, und entschlüsseln Sie es dann mit dem Schlüssel d
, berechnen Sie (ae)d = einde modisch m
.Aber
da de = 1 mod phi(m)
, Eulers Totientensatz sagt uns, dass ade ist kongruent
zu einem1 mod m - mit anderen Worten, Sie erhalten das Original zurück a
.
Es sind keine effizienten Möglichkeiten bekannt, den Entschlüsselungsschlüssel zu erhalten d
zu wissen, nur die
Verschlüsselungsschlüssel e
und der Modul m
, ohne die Faktorisierung zu kennen m = pq
, so
Die RSA-Verschlüsselung gilt als sicher.