Seite 1 von 1

RSA: n faktorisieren bei bekanntem d

Verfasst: 17.05.2016 18:28
von KryptoFreund
Hallo zusammen,

leider habe ich mit Google keine konkreten Ansätze gefunden, sondern nur, dass es generell möglich ist.
Angenommen, ich als Angreifer kenne den geheimen Exponenten d (z.B. duch einen Meet-in-the-Middle Angriff). Dadurch kenne ich also N, e, d. Wie ist es mir mit diesem Wissen möglich, effizient p und q zu berechnen?

Viele Grüße

ein Kryptofreund

Re: RSA: n faktorisieren bei bekanntem d

Verfasst: 17.05.2016 19:27
von ChristianB
Ich musste erstmal mein RSA Wissen in der wikipedia kurz auffrischen (https://de.wikipedia.org/wiki/RSA-Krypt ... lerzeugung). Warum willst du p und q berechnen wenn du den geheimen Schlüssel (mit N und d) schon hast? Das Grundproblem ist ja meist das man d nicht kennt und deshalb versucht N zu faktorisieren. Wenn du den geheimen Teil kennst dann kannst du ja versuchen mittels phi(N)=(p-1)*(q-1) die beiden Faktoren zu bestimmen dabei musst du aber selbst phi(N) ausrechnen (https://de.wikipedia.org/wiki/Eulersche ... Berechnung).

Re: RSA: n faktorisieren bei bekanntem d

Verfasst: 17.05.2016 23:35
von KryptoFreund
Hallo ChristianB,

danke für deine schnelle Antwort!
Natürlich hast du Recht. Mit der Kenntnis des geheimen Exponenten d kann ein Angreifer alle Nachrichten entschlüsseln und ist dadurch vollkommen glücklich.
Trotzdem würde ich den Zusammenhang zwischen der Kenntnis von d und dem Faktorisieren von N gerne kennen. Dein Ansatz sollte dabei funktionieren. Aber wie kann ich Phi(N) ohne p und q berechnen?

Re: RSA: n faktorisieren bei bekanntem d

Verfasst: 18.05.2016 13:31
von ChristianB
Tja da musst du mal den Wikipediaautor fragen der den Satz "Die Zahlen p, q und \varphi(N) werden nicht mehr benötigt und können nach der Schlüsselerstellung gelöscht werden. Es ist jedoch relativ einfach, diese Werte aus e, d und N zu rekonstruieren." geschrieben hat. Mir fällt auf anhieb auch nichts ein was nicht die komplette Faktorisierung von N einschliesst.

Re: RSA: n faktorisieren bei bekanntem d

Verfasst: 18.05.2016 19:13
von KryptoFreund
Dann werde ich mal weiter suchen.
Auf jeden Fall vielen Dank! :)