rotiert

Editorial: Kann der "Quantencomputer" wirklich alles knacken?

Die Wunderwaffe, an der die NSA derzeit forscht, rechnet prinzipiell anders als ein herkömmlicher PC. Sie hat einige spezifische Stärken und Schwächen. Zumindest ein Kryptoverfahren ist aber vor ihr nicht sicher.

Bei genauerer Betrachtung ist eines der jüngst veröffentlichten Snowden-Dokumente eher ein Grund zur Entwarnung: Die NSA forscht an einem Quantencomputer. Mit anderen Worten: Sie hat ihn anscheinend noch nicht. Und das ist auch gut so. Denn eine der wichtigsten Verschlüsselungsmethoden im Internet, RSA, fällt unter dem Angriff eines Quantencomputers in sich zusammen wie ein Kartenhaus. Mit normalen Computern gilt RSA bei ausreichender Schlüssellänge (1024 Bit, besser mehr) zwar noch als sicher.

Das Besondere an Quantencomputern ist, dass sie mit allen denkbaren Eingabewerten gleichzeitig rechnen können. Das macht sie zum perfekten Werkzeug für Codeknacker. Denn ein klassischer Computer muss, um einen Code zu knacken, alle Schlüssel durchprobieren: Bei einer vierstelligen PIN zum Beispiel 0000, 0001, 0002, 0003 usw. usf. bis 9999. Enigma K Verschlüsselungsmaschine, die um 1938 im Einsatz war. Enigma K Verschlüsselungsmaschine, die um 1938 im Einsatz war.
Bild: dpa
Ist der Schlüssel nur lang genug (bei AES mindestens 128 Bit; bei RSA mindestens 2048 Bit) dauert das Durchprobieren beim gegenwärtigen Stand der Technik so lange, dass mit heutigen Computern in "vernünftiger" Zeit (also z.B. der Lebenszeit eines Menschen) kein Treffer zu erwarten ist. Der Quantencomputer kann hingegen alle Codes gleichzeitig untersuchen!

Diese Fähigkeit zum parallelen Rechnen auf allen denkbaren Eingabewerten gleichzeitig ist aber weniger wert, als man im ersten Moment denken würde. Denn das Ergebnis einer Berechnung auf einem Quantencomputer ist quasi eine "Kakophonie" aller Ergebnisse aller Berechnungen mit allen Eingabewerten gleichzeitig. In dieser ist das eine gesuchte Ergebnis (der richtige Code) von Myriaden an falschen Ergebnissen (den falschen Codes) überlagert. Liest man dieses Ergebnis aus und überträgt es auf einen klassischen Computer (oder bringt es auf einem Display zum Ablesen durch einen Bediener zur Anzeige), dann wird aufgrund der besonderen Eigenschaften der Quantenmechanik ein zufälliger Wert herausgegriffen, der einer der Eingaben entspricht. Das ist aber nicht besser als beim klassischen PC, denn auch dort ist es kein Problem, einen einzelnen Code zufällig auszuprobieren. Doch findet man so nie und nimmer die gesuchte Nadel im Code-Heuhaufen.

Ergebnis erst verdichten, dann auslesen

Doch es ist nicht alles verloren. Ein 1996 von Lov Grover entdeckter Quantenalgorithmus ermöglicht es, die gesuchte Stecknadel im Heuhaufen der unerwünschten Ergebnisse quasi zu vervielfältigen, bevor man das Ergebnis ausliest und auf einen klassischen Computer überträgt. Mit jeder Schleife des Grover-Algorithmus steigt die Chance, die Stecknadel zu finden! Hat man genügend der Grover-Schleifen gedreht, dann wird man beim Auslesen des Quanten-Registers mit hoher Wahrscheinlichkeit das richtige Ergebnis vorfinden. Doch ist die Zahl der Schleifen immens: Um einen Schlüssel mit einer bestimmten Zahl an Bits zu knacken, muss man mit dem Quantencomputer so viele Schleifen drehen, wie beim Knacken eines halb so langen Schlüssels auf einem klassischen Computer.

Praktisch bedeutet das: Gelingt es der NSA, einen zuverlässigen und auch noch schnellen Quantencomputer zu bauen, dann ist AES mit 128-Bit-Schlüssel nicht mehr sicher. AES mit 256-Bit-Schlüssel ist hingegen weiterhin sicher. Und es gibt noch eine gute Nachricht: Zwischenzeitlich wurde mathematisch bewiesen, dass auch kein anderes Programm auf einem Quantencomputer den Grover-Algorithmus schlagen kann. Besser geht nicht, es sei denn, man nutzt zusätzlich auch noch Schwächen im angegriffenen Krypto-Verfahren selber aus. Wenn der Algorithmus solche Schwächen hat, ist er aber meist bereits mit klassischen PCs angreifbar. Beispiel: Die Sprachverschlüsselung normaler GSM-Handys wurde schon vor Jahren geknackt. So konnte die NSA das Parteihandy der Kanzlerin abhören. Auch ohne Quantencomputer.

Lesen Sie auf Seite 2, welche Besonderheit den für online-Banking, Software-Verteilung und viele weitere Zwecke eingesetzten RSA-Standard so anfällig für den Quantencomputer macht, warum der Bau von Quantencomputerm zum Glück so schwer ist, und welche Alternativen es gibt, sollte er dennoch gelingen.

1 2

Weitere Editorials