Cryptography Reference
In-Depth Information
4.6
Wiederholung Algorithmen
Ab dem nächsten Abschnitt werden Algorithmen ein wichtiger Gegenstand unserer Un-
tersuchungen werden, denn - wie in der Einführung des Kapitels angedeutet - werden
wir uns Angreifer zukünftig als Algorithmen vorstellen. Daher müssen wir Schreibweisen
und andere Festlegungen im Zusammenhang mit Algorithmen ansprechen.
Unter einem Algorithmus wollen wir uns formal eine Turing-Maschine vorstellen, auch
wenn wir Algorithmen weiterhin in Pseudocode schreiben werden. Für unsere weiteren
Studien werden allerdings Aspekte wichtig sein, die bisher nicht aufgetreten sind. Zum
einen werden wir nun zufallsgesteuerte Algorithmen betrachten, statt, wie bisher, nur
deterministische Algorithmen. Zum anderen werden unsere Algorithmen nun Prozedu-
ren/Orakel als Eingaben übergeben bekommen, statt nur gewöhnliche Daten wie Bitvek-
toren oder Zahlen. Auf beide Aspekte gehen wir deshalb im Folgenden näher ein. Zunächst
besprechen wir allerdings den Ressourcenverbrauch eines Algorithmus. Dieser Aspekt ist
wichtig, da, wie angedeutet, im Rest des Buches Angreifer ressourcenbeschränkt sein
werden.
4.6.1
Ressourcenverbrauch
Die Laufzeit eines Algorithmus wird wie für Turing-Maschinen üblich gemessen, d. h., sie
ergibt sich aus der Anzahl ausgeführter Programmschritte bzw. Transitionen. Allerdings
treffen wir folgende, etwas ungewöhnliche, in der Kryptographie aber übliche Festlegung:
Die Laufzeit eines Algorithmus ergibt sich als die Summe aus der eigentlichen Laufzeit
des Algorithmus (Anzahl ausgeführter Programmschritte) plus der Länge des Programm-
codes des Algorithmus (formal: Größe der Transitionstabelle der Turing-Maschine). Diese
Festlegung ist wichtig für die Ressourcenbeschränkung von Angreifern. Ohne diese Festle-
gung könnte ein Angreifer/Algorithmus mit realistischer Laufzeitbeschränkung durch ein
unrealistisch großes Programm beschrieben sein, welches es ihm erlauben würde, kom-
plexe Berechnungen in unrealistisch kurzer Zeit auszuführen, wie im Folgenden näher
erläutert wird.
Betrachten wir zum Beispiel einen Angreifer auf ein l -Block-Kryptosystem. Dieser
könnte für jede Menge T von, sagen wir, fünf Klartext-Chiffretext-Paaren speichern, wel-
che Schlüsselkandidaten für T in Frage kommen, d. h., welche Schlüssel die Klartexte
in T zu den in T angegebenen zugehörigen Chiffretexten verschlüsseln würden. (Für
die meisten in der Praxis eingesetzen Block-Kryptosysteme wird jeweils höchstens ein
Schlüsselkandidat in Frage kommen; siehe auch Aufgabe 4.9.23.) Sind dem Angreifer nun
fünf Klartext-Chiffretext-Paare gegeben, so kann er einfach in seiner Tabelle die zuge-
hörigen Schlüsselkandidaten nachschlagen. Dieses Nachschlagen benötigt nur sehr wenig
Laufzeit, auch wenn die Tabelle selbst und damit der Programmcode des Angreifers, gi-
gantischgroßsind(
2 l ). Genau genommen hängt die benötigte Zeit zum Nachschlagen
vom Maschinenmodell ab. Im Fall einer Turing-Maschine könnte die Tabelle in Form der
Transitionstabelle der Turing-Maschine, die dem Programmcode einer Turing-Maschine
entspricht, vorliegen. Eine solche Maschine müsste lediglich die fünf Klartext-Chiffretext-
Paare einlesen und könnte dann direkt von ihrem internen Zustand die in Frage kom-
menden Schlüssel ablesen. In der Terminologie von Abschnitt 2.4 wären damit Angriffe
Search WWH ::




Custom Search