Wie berechne ich für RSA den geheimen Exponenten?

Question

Wie berechne ich für RSA den geheimen Exponenten?

Gegeben p und q die zwei Primzahlen und phi = (p-1) (q-1), und der öffentliche Exponent (0x10001), wie bekomme ich den geheimen Exponenten 'd'?

Ich habe gelesen, dass ich zu tun habe: d = e ^-1 mod phi mit modular inversion und die euclidean equation aber ich kann nicht verstehen, wie die obige Formel Karten entweder auf die ein ^-1 ≡ x mod m Formel auf der modularen Inversion Wiki-Seite, oder wie es auf die euklidische GCD-Gleichung abbildet.

Kann jemand bitte helfen, prost

Answer 1

Sie die extended Euclidean algorithm für d in der Kongruenz lösen können

de = 1 mod phi(m) 

Für die RSA-Verschlüsselung, e ist der Verschlüsselungsschlüssel, d ist der Entschlüsselungsschlüssel und Verschlüsselung und Entschlüsselung werden beide durch Potenzierung Mod m durchgeführt. Wenn Sie eine Nachricht a mit Schlüssel e verschlüsseln und dann entschlüsseln es mit der Taste d, Sie berechnen (a ^e) ^d = a ^de mod m. Aber seit de = 1 mod phi(m), Euler's totient theorem sagt uns, dass ein ^de kongruent ist zu einem mod m - mit anderen Worten, erhalten Sie das Original a zurück.

Es gibt keine bekannten effiziente Wege, um die Entschlüsselungsschlüssel d wissen nur die Verschlüsselungsschlüssel e und den Modul m, ohne zu wissen, die Faktorisierung m = pq, so RSA-Verschlüsselung sicher zu sein ist zu erhalten glaubte.