Hallo allerseits,
ich stelle mir gerade die Frage, wie man aus dem Bekanntwerden eines privaten Schlüssels alle anderen Parameter berechnen kann.
Angenommen der Public Key ist:
( e, n= pq) und die privaten (so gesehen..) ( d, phi, p, q)
Nun lassen sich vier (bzw. drei mit einem analogen Fall) betrachten: (gibt es hier auch eine Latex-Umgebung?)
Es ist einer der Fälle 1-3 bekannt:
Zu 3.) Es ist p (oder q) bekannt.
Wegen n = pq ist q = n/p. Damit ergibt sich phi=(p-1)(q-1) und damit lässt sich d über den erweiterten euklidischen Algorithmus ggT(e, phi ) oder der Kongruenz ed = 1 mod phi berechnen.
zu 2.) Es ist phi bekannt.
Analog zu 1) lässt sich d berechnen. Fehlt noch p, womit sich dann auch q ergibt.
Die weitere Berechnung ist ohne LaTeX sehr unschön, aber hier mal in Kurzform:
n - phi - 1 = phi(p) + phi(q)
und
phi(p) - phi(q) = sqrt ( (n-phi-1)^2 - 4phi )
Addition beider Zeilen liefert dann
2 phi(p) = n - phi - 1 + sqrt ( (n-phi-1)^2 - 4phi ).
Da phi(p) = p-1 lässt sich dann p und somit auch q berechnen.
zu 1.) Es ist d bekannt.
Es gilt zunächst ed = 1 mod phi also ed - 1 = k*phi. Damit lässt sich also ein ganzzahliges (positives) Vielfaches von phi berechnen.
Wie kann ich hier nun weiter vorgehen? Hat jemand einen Tipp?
Viele Grüße
ich stelle mir gerade die Frage, wie man aus dem Bekanntwerden eines privaten Schlüssels alle anderen Parameter berechnen kann.
Angenommen der Public Key ist:
( e, n= pq) und die privaten (so gesehen..) ( d, phi, p, q)
Nun lassen sich vier (bzw. drei mit einem analogen Fall) betrachten: (gibt es hier auch eine Latex-Umgebung?)
Es ist einer der Fälle 1-3 bekannt:
- d
- phi
- p (analog q)
Zu 3.) Es ist p (oder q) bekannt.
Wegen n = pq ist q = n/p. Damit ergibt sich phi=(p-1)(q-1) und damit lässt sich d über den erweiterten euklidischen Algorithmus ggT(e, phi ) oder der Kongruenz ed = 1 mod phi berechnen.
zu 2.) Es ist phi bekannt.
Analog zu 1) lässt sich d berechnen. Fehlt noch p, womit sich dann auch q ergibt.
Die weitere Berechnung ist ohne LaTeX sehr unschön, aber hier mal in Kurzform:
n - phi - 1 = phi(p) + phi(q)
und
phi(p) - phi(q) = sqrt ( (n-phi-1)^2 - 4phi )
Addition beider Zeilen liefert dann
2 phi(p) = n - phi - 1 + sqrt ( (n-phi-1)^2 - 4phi ).
Da phi(p) = p-1 lässt sich dann p und somit auch q berechnen.
zu 1.) Es ist d bekannt.
Es gilt zunächst ed = 1 mod phi also ed - 1 = k*phi. Damit lässt sich also ein ganzzahliges (positives) Vielfaches von phi berechnen.
Wie kann ich hier nun weiter vorgehen? Hat jemand einen Tipp?
Viele Grüße
Zuletzt bearbeitet: