Wie berechne ich für RSA den geheimen Exponenten?

Question

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

Answer 1

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 (a^e)^d = ein^de modisch m.Aber da de = 1 mod phi(m), Eulers Totientensatz sagt uns, dass a^de ist kongruent zu einem¹ 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.