Chiffren-Design - Kryptografie - page 112

7.3.3 Kryptoanalyse mit Quantencomputern

Wer sich schon einmal mit moderner Physik (insbesondere der Quantenmecha-
nik) beschäftigt hat, weiß, dass Atome und Elementarteilchen teilweise seltsame
Eigenschaften haben. So können bestimmte Teilchen mehrere gegensätzliche
Zustände gleichzeitig einnehmen, und manche Zustände sind erst in dem
Moment festgelegt, in dem man sie misst. Es gibt zwei für die Kryptografie inter-
essante Entwicklungen, welche die Quantenmechanik nutzen. Die eine ist die
Quantenkryptografie, um die es an dieser Stelle nicht gehen soll. Die zweite Ent-
wicklung sind die sogenannten Quantencomputer . Die Architektur eines Quan-
tencomputers nutzt quantenmechanische Gesetze, durch die Algorithmen mög-
lich sind, die auf einem herkömmlichen Computer nicht funktionieren. Bisher
gibt es zwar noch keine praxistauglichen Quantencomputer, doch theoretische
Überlegungen dazu wurden schon viele angestellt.
Zu den Algorithmen, die ein Quantencomputer ausführen kann, sind für uns
vor allem zwei von Bedeutung, da diese dem Knacken von Verschlüsselungen die-
nen. Der wirksamere der beiden ist der Shor-Algorithmus, um den es in Abschnitt
11.3.3 geht (für symmetrische Verschlüsselungsverfahren spielt dieser keine
Rolle). Der zweite ist der Grover-Algorithmus [Grover]. Diesen kann Mallory für
die vollständige Schlüsselsuche bei symmetrischen Verschlüsselungsverfahren
nutzen. Mit dem Grover-Algorithmus muss Mallory nur 2 n/2 Schritte durchfüh-
ren, um 2 n Schlüssel zu prüfen - eine Ersparnis, die nur durch die Nutzung der
Quantenmechanik möglich ist. Mit anderen Worten heißt dies: Wenn sich Alice
und Bob gegen eine vollständige Schlüsselsuche mit dem Quantencomputer
schützen wollen, dann müssen sie die Schlüssellänge doppelt so lang wählen, wie
sie es ohne Quantencomputer tun würden.
Organisationen, die beim Verschlüsseln eine hohe und langfristige Sicherheit
benötigen, verwenden oft besonders lange Schlüssel, weil sie die Möglichkeiten
von Quantencomputern einkalkulieren. Dabei ist jedoch völlig offen, ob es
jemals brauchbare Quantencomputer geben wird. Die bisher realisierten Exemp-
lare können nur mit einzelnen Bits umgehen und sind noch weit davon entfernt,
für nützliche Berechnungen geeignet zu sein. Alice und Bob müssen sich also vor-
erst keine Sorgen machen.

7.3.4 Weitere Kryptoanalyse-Methoden

1994 zeigten die Kryptologen Langford und Hellman, dass man die differenzielle
und die lineare Kryptoanalyse miteinander verbinden kann - die differenzielle-
lineare Kryptoanalyse war geboren [LanHel]. Daneben gibt es auch die Möglich-
keit, statt häufiger Differenzen nichtvorkommende Differenzen zu Hilfe zu neh-
men. Diese Methode heißt auf Englisch »impossible differential cryptanalysis«
[BiBiSh], auf Deutsch kann man sie als Kryptoanalyse mit unmöglichen Differen-