Dialog Faktorisieren mit teilweise bekanntem p

Sie erreichen diesen Dialog über den Menüeintrag Einzelverfahren \ RSA-Kryptosystem \ Gitterbasierte Angriffe auf RSA \ Faktorisieren mit teilweise bekanntem p.

Der Dialog zur Faktorisierung bei teilweise bekanntem p bietet zwei verschiedene Herangehensweisen, die im oberen Fensterteil ausgewählt werden können:
1. Man gibt selbst den RSA-Modulus N , die Bitlänge von p und den bekannten Teil P von p ein.
2. Man wählt die Bitlänge von N und die Bitlänge von p und lässt sich ein Beispiel erzeugen.

Durchzuführende Schritte:

  1. Abhängig von der oben genannten Aus wahl muss nun entweder N selbst oder die Bitlänge von N angegeben werden.
    Die Auswahl "Zahlenbasis" ermöglicht es, die Zahlendarstellung von N, p und P zu ändern.
  2. In beiden Fällen muss die Bitlänge von p eingegeben werden (für dieses Verfahren muss man die Bitlänge von p exakt kennen!).
  3. Anschließend wählt man aus, ob die höherwertigen oder die niederwertigen Bits von p bekannt sein sollen.
  4. Abhängig vom gewählten Modus gibt man nun entweder den bekannten Teil von p selbst ein, oder man gibt die Anzahl der übereinstimmenden Bits ein und klickt auf "Beispiel erzeugen".
    Beachte:
    Wenn man P selbst eingibt, muss dies bei z.B. 40 mit p übereinstimmenden Bits in der Binärschreibweise identisch sein. Deshalb sollten Sie, wenn Sie Option 1 wählen und alles selbst eingeben, zwischendurch auf die Binär- oder Hexadezimal-Anzeige umschalten, um zu kontrollieren, dass die Bits auch identisch sind!
  5. Nun kann mit dem Button "Starten" der Angriff gestartet werden.

Die Gruppierung "Angriff" informiert darüber, wie viel Zeit im laufenden Angriff verstrichen ist und wie viele Gitterreduktionen durchgeführt wurden. Nach Beendigung des Angriffs werden die gefundenen Faktoren p und q ausgegeben. Darüber hinaus wird hier auch die Anzahl der benötigten Bits (n / 4+1) angegeben, die in Abhängigkeit von N berechnet wird. Daraus ergibt sich auch die Dimension des zu reduzierenden Gitters: Je mehr Bits eines der Faktoren bekannt sind, desto kleiner kann das Gitter sein.

Beispiel:

Angriff auf einen RSA-Modulus N mit der Bitlänge 200:

Vorgehen nach Option 1:

  1. Der Angreifer gibt den ihm bekannten Wert
    N = 1100928820568180272388944445745883306779673638843521865435523 ein.
  2. In den meisten Fällen haben die beiden Faktoren genau halb soviele Bits wie N . So auch hier:
    Bitlänge von p : 100
  3. Der Angreifer wählt, dass er die höchstwertigen Bits (also die linken) von p kennt.
  4. Er gibt P = 831311796601422049670156 ein.
  5. Mit einem Klick auf "Start" beginnt der Angriff.

Dialog zum Beispiel:

Bemerkungen:

  1. Wieviel des Faktors p von N bekannt sein muss, hängt nicht von der Größe von p sondern nur von der Größe von N ab. Es müssen bei einem N mit n Bit Länge mindestens (n/4)+1 Bit von p bekannt sein. Dabei ergibt soch ein Gitter der Gitterdimension n, was ab einer größe von n = 128 schwer lösbar ist.
  2. Wenn sich P und p in der Dezimaldarstellung oder der Hexadezimaldarstellung teilweise entsprechen, bedeutet das nicht, dass sie sich auch in der Binärdarstellung exakt entsprechen. Dies ist jedoch die Grundvoraussetzung für den Angriff.