Time-Memory-Tradeoff

Zur Lösung vom Problemen, bei denen Hin- und Rückrechnung unterschiedlich lange dauern, kann man die durchschnittliche Laufzeit verringern, indem man Werte vorberechnet und in einer Datenstruktur hält. Das reduziert die Zeit, erhöht aber den Speicherverbrauch. Hier muss man abwägen. Ein größerer Speicher kann mehr Zwischenschritte speichern und i.A. die Laufzeit verkürzen. Im folgenden dazu Beispiele.

Passwort-Erraten ([Eri04], Kap. 4.6)

Bei 95 verfügbaren Eingabezeichen und 8 Zeichen für ein Passwort gibt es 95^8 ~ 6,6 e15 verschiedene Eingaben, welche auch noch mit einer Verschlüsselungsfunktion wie z.B. crypt (DES) verschlüsselt werden. Damit ist ein Brute-Force-Angriff nicht praktikabel. Ein Einstieg wird sein, eine Anzahl Möglichkeiten mit einem Wörterbuchangriff abzutesten, also die Laufzeit zu verringern mit einem zusätzlichen Speicher. Alle Ergebnisse der Passwörter kann man nicht speichern, hier schlägt Erickson (siehe Literatur) eine Lösung vor, bei der eine verkleinerte Datenstruktur aufgebaut und einmalig berechnet wird. Durch verlustreiche Komprimierung des Suchraumes ergibt sich etwa 80% Speicherplatzersparnis im Vergleich zu einer vollständigen Suchtabelle. Pro Suchwert wird eine Anzahl Anzahl möglicher Passwörter ermittelt, welche dann relativ schnell überprüft werden können, ob sie wirklich den Wert ergeben.
Generierung Struktur für alle 4 Zeichen-Passwörter
Reduziertes Suchen nach Passwort

Faktorisieren

Beim quadratischen - oder allgemeinen Zahlkörpersieb hat man hier einen Kompromiss zwischen Primfaktorbasis und Laufzeit zu machen:
Wählt man die Primbasis zu klein, werden zu wenig Relationen aufgelöst.
Wählt man die Primbasis zu groß, werden unnötigerweise große Primfaktoren (sehr oft mit Rest, also nicht verwendbar) geteilt.
Die Primbasis ist hierbei der Schlüssel, um eine Zahl x und y der Form x² == y² mod n zu finden, was eine Faktorisierung erlaubt.

Diskreter Logarithmus

b^x = y mod p
Es liegt (speziell) eine Primzahl p und q vor, wobei q | (p - 1). Die Basis kann eine große Ordnung haben, z.B. ord(b) = q = (p-1)/2.
Dies ist schwer zu lösen. Eine einfache Möglichkeit besteht darin, für alle i von 0 bis q-1 bⁱ zu berechnen und mit y zu vergleichen, dies ist normalerweise nicht praktikabel. Beim "Giant-Step, Baby-Step"- Algorithmus speichert man eine Anzahl Werte zwischen, um sie dann vergleichen zu können. Man macht z.B. die Annahme
b^{k * q + l} = y mod p, k=0..q-1, l=0..q-1
wobei q ~ sqrt(p) ist.
Einzelschritt:
Berechne y * b^{-l * n}, n=0..q-1 und speichere diese zwischen.
Riesenschritt:
Berechne (b^q)ⁿ, n=0..q-1 und vergleiche diese mit den Ergebnissen des Einzelschrittes.
--> man kann auch weniger Werte im Einzelschritt zwischenspeichern, dann aber sind mehr Berechnungen im Riesenschritt machen (hier ist Kompromiss nötig).

Literatur: [Eri04], Jon Erickson, "Forbidden Code", Mitp-Verlag, 2004