RSA-Algorithmus - Private Key < Algorithmen < Schule < Informatik < Vorhilfe
|
Hallo,
ich schreibe derzeit an einem Programm, welches den RSA Algorithmus umsetzt.
Ich habe soweit auch alles berechnet, aber der Private Schlüssel d macht mir Probleme. Ich weiß, dass
e * d mod phi(n) = 1
ist. Nur wie berechne ich d? Es kann ja auch nicht sein, dass ich ohne weiteres aus e und n d berechnen kann, da der Private Key dann aus dem Public Key errechenbar wäre. (Die zu Grunde liegenden Primzahlen p und q kenne ich auch!)
Jemmand eine Idee, wie ich an d komme?
|
|
| |
|
Hallo,
> Es kann ja auch nicht sein, dass ich ohne weiteres aus e und n d berechnen kann, da der Private Key dann aus dem Public Key errechenbar wäre.
Das ist ja das ganze Geheimnis! Es geht nicht ohne Weiteres, weil du nur n, nicht aber [mm] $\Phi(n)$ [/mm] kennst. Und man kann auch nicht ohne riesigen Rechenaufwand von n darauf schließen.
> (Die zu Grunde liegenden Primzahlen p und q kenne ich auch!)
Genau! Und das sollte auch tunlichst so bleiben. Nur du als Schlüsselerzeuger darfst über dieses Wissen verfügen. Da du p und q kennst, kennst du auch [mm] $\Phi(n)=(p-1)(q-1)$. [/mm] Damit kannst du aber auch das modulare Inverse zu e mod [mm] $\Phi(n)$ [/mm] berechnen (Stichwort: erweiterter euklidischer Algorithmus).
Gruß
Martin
|
|
|
| |
|
Hallo,
danke für die Antwort.
> Damit kannst du aber auch das modulare Inverse zu e mod
> [mm]\Phi(n)[/mm] berechnen (Stichwort: erweiterter euklidischer
> Algorithmus).
Genau war mein Problem, da ich nicht wusste wie. Bin aber doch noch auf eine Erklärung gestoßen:
http://www.matheprisma.uni-wuppertal.de/Module/RSA/index.htm
|
|
|
|
