Dialog Angriff auf kleine geheime Exponenten

Sie erreichen diesen Dialog über den Menüeintrag Einzelverfahren \ RSA-Kryptosysteme \ Gitterbasierte Angriffe auf RSA \ Angriff auf kleine geheime Schlüssel.

Der Benutzer hat im oberen Teil des Dialoges zum Angriff auf kleine geheime Schlüssel die Wahl zwischen zwei Betriebsmodi:
1. Alle Eingabedaten selbst eingeben, dann Angriff durchführen
Er gibt selbst e und N ein und schätzt die Größe von d mittels delta ab.
2. Beispieldaten erzeugen lassen, dann Angriff durchführen
Er lässt sich ein Beispiel erzeugen, indem er die Bitlänge von N und das gewünschte delta wählt.

1. Alle Eingabedaten selbst eingeben, dann Angriff durchführen

  1. Zunächst müssen N und e eingegeben werden.
  2. Danach muss man noch eine Schätzung für delta abgeben. Man kann d auch direkt eingeben und delta wird berechnet. Das ist für den Angriff allerdings nicht erforderlich, bietet aber die Möglichkeit zu prüfen, ob der verwendete Schlüssel anfällig für den Angriff ist.
  3. Nun kann der Angriff mit einem Klick auf "Starten" durchgeführt werden.

In der Gruppierung "Angriff" werden Informationen zum laufenden Angriff angezeigt und bei Erfolg werden die Faktoren p und q ausgegeben.

Beispiel

Der Angreifer gibt e=741077250369232479059668207375016571081542804590833038433249892326787378484956638636330841 und N=1259723741173449567548189641230786965150346729930314335887552587458506570619692703188420329 ein und schätzt die Größe von d mittels delta=0,260 ab.

2. Beispieldaten erzeugen lassen, dann Angriff durchführen

Um ein eigenes Beipiel zu erzeugen, wählt man die Bitlänge von N (z.B. 300) und ein delta (z.B. 0,260). Danach klickt man "Beispielschlüssel erzeugen" und startet den Angriff.

Bemerkungen

In beiden Fällen kann noch der Parameter m geändert werden. m beeinflusst die Gitterdimension und sollte nicht zu groß gewählt werden, da dies die Laufzeit stark negativ beeinflusst. Von m hängt auch ab, wie groß delta maximal gewählt werden kann, damit der Angriff funktioniert. Dabei gilt jedoch zu beachten, dass für kleine N (N <1000 Bit) die Berechnung des maximalen delta nicht exakt ist und das gewählte delta ca. 0,05 unter dem maximalen Wert für delta liegen sollte. Die verwendete Formel für delta lautet:

Hier wird die Nullstelle einer Gleichung in zwei Unbekannten gesucht. Um die gesuchte Lösung zu finden werden daher zwei kurze Vektoren benötigt, aus denen dann zwei Polynome aufgestellt werden. Es ist allerdings nicht bewiesen, dass diese Polynome ausreichen, um die Nullstelle eindeutig zu bestimmen. Daher ist der Angriff auch als Heuristik zu verstehen. Aus den gefundenen Polynomen werden Resultanten gebildet. Dabei wird aus zwei Polynomen in zwei Unbekannten ein weiteres Polynom in einer Unbekannten erzeugt.