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
RSA: n faktorisieren bei bekanntem d
-
- Idle-Sammler
- Beiträge: 4
- Registriert: 01.03.2016 12:29
-
- Admin
- Beiträge: 1920
- Registriert: 23.02.2010 22:12
Re: RSA: n faktorisieren bei bekanntem d
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).
-
- Idle-Sammler
- Beiträge: 4
- Registriert: 01.03.2016 12:29
Re: RSA: n faktorisieren bei bekanntem d
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?
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?
-
- Admin
- Beiträge: 1920
- Registriert: 23.02.2010 22:12
Re: RSA: n faktorisieren bei bekanntem d
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.
-
- Idle-Sammler
- Beiträge: 4
- Registriert: 01.03.2016 12:29
Re: RSA: n faktorisieren bei bekanntem d
Dann werde ich mal weiter suchen.
Auf jeden Fall vielen Dank!
Auf jeden Fall vielen Dank!