RSA private Schlüssel aus bekannten Key berechnen

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(n), 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:
  1. d
  2. phi(n)
  3. p (analog q)

Zu 3.) Es ist p (oder q) bekannt.
Wegen n = pq ist q = n/p. Damit ergibt sich phi(n)=(p-1)(q-1) und damit lässt sich d über den erweiterten euklidischen Algorithmus ggT(e, phi(n) ) oder der Kongruenz ed = 1 mod phi(n) berechnen.

zu 2.) Es ist phi(n) 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(n) - 1 = phi(p) + phi(q)
und
phi(p) - phi(q) = sqrt ( (n-phi(n)-1)^2 - 4phi(n) )

Addition beider Zeilen liefert dann
2 phi(p) = n - phi(n) - 1 + sqrt ( (n-phi(n)-1)^2 - 4phi(n) ).

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(n) also ed - 1 = k*phi(n). Damit lässt sich also ein ganzzahliges (positives) Vielfaches von phi(n) berechnen.
Wie kann ich hier nun weiter vorgehen? Hat jemand einen Tipp?

Viele Grüße
 
Zuletzt bearbeitet:
Hallo allerseits,
ich stelle mir gerade die Frage, wie man aus dem Bekanntwerden eines privaten Schlüssels alle anderen Parameter berechnen kann.
Wenn alles bekannt ist, warum sollte man es dann erneut berechnen? Ich verstehe ehrlich gesagt den Sinn der Frage nicht...

Wie kann ich hier nun weiter vorgehen? Hat jemand einen Tipp?
Wenn phi(n) bekannt ist, dann berechnest du einfach das multiplikative Inverse von e mit Hilfe des Erweiterten Euklidschen Algorithmus. Eben so, wie es der Besitzer des private Schlüssels auch gemacht hat...
 
Wenn alles bekannt ist, warum sollte man es dann erneut berechnen? Ich verstehe ehrlich gesagt den Sinn der Frage nicht...
Sagen wir, es sind nur Teile des privaten Schlüssel bekannt geworden. Oder ein Angreifer hat einen Algorithmus, der effizient einen der Fälle von 1 - 3 berechnen kann.

Wenn phi(n) bekannt ist, dann berechnest du einfach das multiplikative Inverse von e mit Hilfe des Erweiterten Euklidschen Algorithmus. Eben so, wie es der Besitzer des private Schlüssels auch gemacht hat...

Beim übrig gebliebenen Fall konnte nur das "d" effizient berechnet werden. Aus den Parametern e,n und d müssen nun p,q und phi(n) hergeleitet werden.
 
wofür willst du noch irgendwas herleiten wenn e,d und n bekannt sind?

x^(e*d) mod n = x ... ende im gelände
 
wofür willst du noch irgendwas herleiten wenn e,d und n bekannt sind?

x^(e*d) mod n = x ... ende im gelände

Einfach nur aus Interesse :D

Es gibt aber auch andere nützliche Einsatzgebiete. Der Diffie Hellman Schlüsselaustausch oder RSA-DSA wären Ansätze. Angenommen ich kann eine Kommunikation abfangen und eben aus den öffentlichen Schlüsseln (e,n) auch d (mit den zusätzlichen Informationen aus der Kommunikation) effizient berechnen. Dann kann ich dieses d aber nur für die Kommunikation mit einem Partner nutzen. Kann ich nun aber aus den Parametern (e,d,n) auch phi(n) oder einen Primteiler p herleiten, könnte ich das gesamte System zum öffentlichen Schlüssel brechen und allen Kommunkationspartnern Fälschungen zukommen lassen.


Ich habe nun auch mal in ein paar Büchern gestöbert. In dem Buch "Kryptographie in Theorie und Praxis" von Beutelspacher, 2. Auflage (2010). Steht auf S. 126 im Satz 10.4 die Aufgabe, dass es äquivalent ist die beiden Primteiler von n zu berechnen oder aus n und e mit ggT(e, phi(n) )=1 das d zu berechnen. Der Beweis dort wirkt aber ein wenig konstruiert auf mich.
Es gibt doch da sicherlich noch einen anderen Weg. :)
 
du wirfst hier ein paar mehr dinge in einen topf als hinein gehören... aber bleiben wir zunächst bei RSA

das problem mit RSA ist, dass die komplexität des problems nicht bewiesen ist sondern nur angenommen wird... (auf grund der tatsache dass an der nuss seit jahren geknackt wird, aber noch keiner nen wirklich großen treffer gelandet hat)

bislang ist kein anderer weg bekannt phi(n) zu berechnen, also die anzahl der invertierbaren elemente mod n, als nach euler, was im rsa fall eben (p-1)*(q-1) ist. findest du einen anderen weg diese zahl zu ermitteln, der signifikant einfacher in der berechnung ist, als die primfaktorzerlegung von n, zerbröselt RSA auf eben diese komplexität... hast du phi, auf welchem weg auch immer, ist der ganze rest von RSA nicht weiter der rede wert.

analog trifft das natürlich auf RSA signaturen zu, da das zugrundeliegende problem bei dieser signaturart natürlich definitionsbedingt das RSA problem umfasst: brichst du effektiv RSA, brichst du logischerweise auch die signaturvariante

nun aber zu dem wo du vermutlich dinge vermischt:

DSA ... DHKE ... die grundlage hier ist ein gänzlich anderes problem als bei RSA: der diskrete logarithmus... ein kleiner mathe exkurs:

2^4 = 16 ...

log2(16) = 4 ...

log2(2^4) = 4 ...

die umkehrung der exponentiation ist der logarithmus ... soweit so schulbuch

wie sieht das aber aus wenn wir nicht auf den reellen Zahlen rechnen wollen, sondern in einer endlichen zyklischen gruppe? (in der kryptografischen praxis, oft eine multiplikative prime restklassengruppe wie bei DSA,DHKE,elGamal...)

exponentiation geht da einfach...
die umkehrung, also der diskrete logarithmus lässt sich bislang aber bei üblichen größenordnungen der Zahlen nicht effizient berechnen
 
Zurück
Oben