RSA: n faktorisieren bei bekanntem d

Knacken von Verschlüsselungen bei den Projekten RC5-72, Enigma@Home und anderen
Nachricht
Autor
KryptoFreund
Idle-Sammler
Idle-Sammler
Beiträge: 4
Registriert: 01.03.2016 12:29

RSA: n faktorisieren bei bekanntem d

#1 Ungelesener Beitrag von KryptoFreund » 17.05.2016 18:28

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

ChristianB
Admin
Admin
Beiträge: 1920
Registriert: 23.02.2010 22:12

Re: RSA: n faktorisieren bei bekanntem d

#2 Ungelesener Beitrag von ChristianB » 17.05.2016 19:27

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).

KryptoFreund
Idle-Sammler
Idle-Sammler
Beiträge: 4
Registriert: 01.03.2016 12:29

Re: RSA: n faktorisieren bei bekanntem d

#3 Ungelesener Beitrag von KryptoFreund » 17.05.2016 23:35

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?

ChristianB
Admin
Admin
Beiträge: 1920
Registriert: 23.02.2010 22:12

Re: RSA: n faktorisieren bei bekanntem d

#4 Ungelesener Beitrag von ChristianB » 18.05.2016 13:31

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.

KryptoFreund
Idle-Sammler
Idle-Sammler
Beiträge: 4
Registriert: 01.03.2016 12:29

Re: RSA: n faktorisieren bei bekanntem d

#5 Ungelesener Beitrag von KryptoFreund » 18.05.2016 19:13

Dann werde ich mal weiter suchen.
Auf jeden Fall vielen Dank! :)

Antworten

Zurück zu „Kryptographie“