Wie gefährlich sind Quantencomputer für unsere verschlüsselten Daten — und wo liegen ihre mathematischen Grenzen?
256 Bit — wie sicher ist das?Wenn wir eine Website besuchen, eine Nachricht verschicken oder auf unser Onlinebanking zugreifen, verlassen wir uns darauf, dass unsere Daten verschlüsselt übertragen werden.
Doch Quantencomputer sollen eines Tages in der Lage sein, Verschlüsselungen zu brechen, für die klassische Computer praktisch unbegrenzt lange benötigen würden.
Wie ernst ist diese Bedrohung?
Um das herauszufinden, betrachten wir ein konkretes Beispiel: Ein Angreifer hat den verschlüsselten Datenverkehr einer Internetverbindung aufgezeichnet. Die Daten wurden mit AES-256 verschlüsselt. Der Angreifer kennt den verwendeten Schlüssel nicht und möchte ihn mithilfe eines Quantencomputers herausfinden.
256 Bit — wie sicher ist das?
AES steht für Advanced Encryption Standard und gehört zu den weltweit am häufigsten eingesetzten Verschlüsselungsverfahren.
Bei AES-256 besteht der geheime Schlüssel aus 256 Bit. Jedes Bit kann entweder 0 oder 1 sein.
Daraus ergeben sich insgesamt:
2 ²⁵⁶ mögliche Schlüssel.
Das ist eine Zahl mit 78 Ziffern.
Wenn unser Angreifer den richtigen Schlüssel nicht kennt, bleibt ihm zunächst nur, mögliche Schlüssel auszuprobieren und zu überprüfen, ob sich damit die aufgezeichneten Daten korrekt entschlüsseln lassen.
Bei einem zufällig gewählten Schlüssel benötigt eine klassische Brute-Force-Suche durchschnittlich ungefähr die Hälfte aller möglichen Versuche.
Das wären etwa 2 ²⁵⁵ Schlüsselprüfungen.
Um die Größenordnung zu verstehen, stellen wir uns einen hypothetischen Supercomputer vor, der jede Sekunde eine Trillion Schlüssel testen kann.
Eine Trillion entspricht 10 ¹⁸, also einer Milliarde Milliarden.
Selbst bei dieser Geschwindigkeit würde eine vollständige Suche ungefähr 3,7 × 10 ⁵¹ Jahre benötigen.
Zum Vergleich: Unser Universum existiert seit ungefähr 13,8 Milliarden Jahren.
Die Suche wäre also nicht einfach sehr zeitaufwendig. Sie wäre mit klassischer Rechentechnik praktisch ausgeschlossen.
Aber unser Angreifer besitzt einen Quantencomputer!
Was ändert sich durch einen Quantencomputer?
Ein Quantencomputer verarbeitet Informationen anders als ein klassischer Computer.
Während ein klassisches Bit entweder den Wert 0 oder 1 besitzt, kann sich ein Quantenbit, kurz Qubit, in einer Überlagerung beider Zustände befinden. Diese Eigenschaft nennt man Superposition.
Mehrere Qubits können dadurch einen Quantenzustand bilden, dessen Beschreibung viele mögliche Kombinationen gleichzeitig umfasst.
Das führt häufig zu der vereinfachten Behauptung, ein Quantencomputer könne alle Schlüssel gleichzeitig ausprobieren.
Doch das ist irreführend.
Denn wenn wir einen solchen Quantenzustand messen, erhalten wir nur ein einzelnes Ergebnis.
Eine gleichmäßige Superposition über alle möglichen Schlüssel würde bei einer Messung lediglich einen zufällig ausgewählten Schlüssel liefern.
Die Wahrscheinlichkeit, auf diese Weise den richtigen AES-256-Schlüssel zu treffen, wäre genauso gering wie bei einem einzelnen zufälligen Versuch auf einem klassischen Computer.
Der entscheidende Vorteil entsteht erst durch einen geeigneten Quantenalgorithmus.
Und für unser Beispiel gibt es einen solchen Algorithmus.
Grovers Algorithmus
1996 entwickelte der Informatiker Lov Grover einen Algorithmus, mit dem ein Quantencomputer eine ungeordnete Suche erheblich beschleunigen kann.
Bei einer klassischen Suche wächst der Aufwand proportional zur Anzahl der möglichen Lösungen.
Grovers Algorithmus reduziert diesen Aufwand auf die Größenordnung der Quadratwurzel.
Wenn wir eine Million mögliche Schlüssel hätten, müsste ein klassischer Computer im ungünstigsten Fall eine Million davon überprüfen.
Ein Quantencomputer mit Grovers Algorithmus benötigt dagegen nur eine Größenordnung von tausend Suchiterationen.
Das klingt bereits beeindruckend.
Noch deutlicher wird der Unterschied bei unserem AES-256-Schlüssel.
Der klassische Suchraum enthält 2 ²⁵⁶ Möglichkeiten.
Grovers Algorithmus reduziert den theoretischen Suchaufwand auf:
√(2 ²⁵⁶) = **2 ¹²⁸**
Damit sinkt die sogenannte Sicherheitsstärke von 256 auf 128 Bit.
In der Kryptografie spricht man deshalb davon, dass Grovers Algorithmus die Sicherheitsstärke halbiert.
Aber Vorsicht: Halbiert wird nicht die Anzahl der Suchschritte. Diese sinkt auf ihre Quadratwurzel.
Und 2 ¹²⁸ ist immer noch eine gewaltige Zahl.
Wie findet Grover den richtigen Schlüssel?
Unser Angreifer muss zunächst einen Quantenalgorithmus konstruieren, der überprüfen kann, ob ein bestimmter Schlüssel zu den aufgezeichneten Daten passt.
Diese Prüfung wird als Teil einer Quantenoperation umgesetzt, die man Oracle nennt.
Das Oracle gibt den richtigen Schlüssel nicht einfach aus. Stattdessen verändert es die Phase des Quantenzustands, der die gesuchte Lösung repräsentiert.
Anschließend führt Grovers Algorithmus eine weitere Operation aus, die als Diffusion bezeichnet wird.
Sie verändert die Wahrscheinlichkeitsamplituden der verschiedenen möglichen Lösungen durch eine Spiegelung an ihrem Mittelwert.
Beide Operationen zusammen bilden eine Grover-Iteration.
Man kann sich das vereinfacht wie ein System überlagerter Wellen vorstellen.
Durch die wiederholten Operationen entsteht Interferenz: Die Amplitude der gesuchten Lösung wird verstärkt, während sich die Amplituden der übrigen Möglichkeiten insgesamt verringern.
Nach ausreichend vielen Wiederholungen ist die Wahrscheinlichkeit hoch, bei einer Messung den gesuchten Schlüssel zu erhalten.
Der Quantencomputer liest also nicht einfach alle Schlüssel gleichzeitig aus.
Er verändert den Quantenzustand schrittweise, sodass am Ende mit hoher Wahrscheinlichkeit der richtige Schlüssel gemessen wird.
Das ist der eigentliche Vorteil von Grovers Algorithmus.
Allerdings benötigt auch dieser Vorgang eine sehr große Zahl aufeinanderfolgender Iterationen.
Wie lange würde der Angriff dauern?
Für unseren AES-256-Schlüssel liegt der theoretische Suchaufwand in der Größenordnung von 2 ¹²⁸ Grover-Iterationen.
Ausgeschrieben entspricht das:
340.282.366.920.938.463.463.374.607.431.768.211.456
Eine Zahl mit 39 Ziffern.
Nehmen wir an, unser Angreifer hätte einen Quantencomputer, der jede Sekunde eine Billion vollständige Grover-Iterationen durchführen könnte.
Für 2 ¹²⁸ Iterationen würde dieser Computer rechnerisch etwa 10,8 Trillionen Jahre benötigen.
Berücksichtigt man die für Grovers Algorithmus tatsächlich erforderliche Iterationszahl von ungefähr π/4 × 2 ¹²⁸, reduziert sich die Laufzeit auf rund 8,5 Trillionen Jahre.
Zum Vergleich: Unser Universum existiert seit ungefähr 13,8 Milliarden Jahren.
Die Berechnung würde also mehr als 600 Millionen Mal so lange dauern, wie das Universum bisher existiert.
Der Vergleich bleibt trotzdem eindrucksvoll.
Und wir haben unserem Angreifer bereits einen Quantencomputer zugestanden, dessen angenommene Geschwindigkeit weit über den heute verfügbaren technischen Möglichkeiten liegt.
Warum eine Iteration keine einfache Rechenoperation ist
Die bisherige Rechnung setzt voraus, dass eine vollständige Grover-Iteration in einer Billionstel Sekunde ausgeführt werden kann.
Das ist eine rein hypothetische Annahme.
In Wirklichkeit muss unser Quantencomputer für jede Iteration eine Reihe komplexer Quantenschaltungen ausführen.
Insbesondere muss die Überprüfung des AES-Schlüssels als reversible Quantenberechnung umgesetzt werden.
Dazu sind zahlreiche Quantengatter erforderlich, die in einer bestimmten Reihenfolge ausgeführt werden müssen.
Außerdem sind Qubits empfindlich gegenüber Störungen. Ein praktisch nutzbarer Quantencomputer müsste deshalb Verfahren zur Quantenfehlerkorrektur einsetzen, um auch lange Berechnungen zuverlässig durchführen zu können.
Die dafür notwendigen zusätzlichen Qubits und Operationen erhöhen den Hardwareaufwand erheblich.
Wissenschaftliche Untersuchungen haben bereits konkrete Ressourcenabschätzungen für Grover-Angriffe auf AES erstellt.
Sie zeigen, dass zwischen der theoretischen Beschleunigung eines Algorithmus und seiner praktischen Umsetzung auf einem Quantencomputer ein erheblicher Unterschied besteht.
Unsere angenommene Billion Iterationen pro Sekunde ist deshalb keine realistische Prognose, sondern dient ausschließlich dazu, die mathematische Größenordnung verständlich zu machen.
Könnte man den Angriff parallel ausführen?
Unser Angreifer könnte versuchen, mehrere Quantencomputer einzusetzen, die gleichzeitig nach dem Schlüssel suchen.
Das ist grundsätzlich möglich.
Allerdings lässt sich Grovers Algorithmus nicht beliebig parallelisieren, ohne einen Teil seines quantenmechanischen Vorteils zu verlieren.
Die einzelnen Iterationen innerhalb einer Grover-Suche müssen aufeinander aufbauen. Sie können nicht einfach unabhängig voneinander ausgeführt werden.
Wird der Suchraum auf mehrere Quantencomputer verteilt, kann jeder einen Teilbereich untersuchen.
Bei P gleich großen Teilbereichen reduziert sich die erforderliche Iterationszahl pro Quantencomputer jedoch nur ungefähr um den Faktor √P.
Bei einer klassischen Brute-Force-Suche lässt sich die Arbeitslast dagegen näherungsweise linear auf unabhängige Rechner verteilen.
Mehr Quantencomputer können einen Angriff also beschleunigen, aber der Zusammenhang zwischen zusätzlicher Hardware und verkürzter Laufzeit ist weniger günstig, als man zunächst vermuten könnte.
Hinzu kommen die erheblichen Ressourcen, die jeder einzelne Quantencomputer benötigt.
Auch damit verschwindet die astronomische Größenordnung unseres AES-256-Beispiels nicht einfach.
Ist die Internetverschlüsselung damit sicher?
Für unser konkretes Beispiel lautet die Antwort: Ein direkter Angriff auf einen korrekt erzeugten AES-256-Schlüssel bleibt auch mit Grovers Algorithmus praktisch außer Reichweite.
Die theoretische quadratische Beschleunigung ist bemerkenswert, aber sie reicht nicht aus, um die enorme Größe des verbleibenden Suchraums zu überwinden.
Allerdings dürfen wir daraus nicht schließen, dass Quantencomputer für die Sicherheit des Internets bedeutungslos wären.
Bei einer realen Internetverbindung wird der AES-Schlüssel nicht isoliert verwendet.
Zunächst müssen die Kommunikationspartner auf sichere Weise gemeinsame Schlüssel vereinbaren und die Identität des Servers überprüfen.
Dafür kommen zusätzliche kryptografische Verfahren zum Einsatz, von denen einige durch ausreichend leistungsfähige Quantencomputer gefährdet sind.
Wenn ein Angreifer die Schlüsselaushandlung einer Internetverbindung kompromittieren kann, benötigt er unter Umständen keinen direkten Angriff auf AES mehr. Die Sicherheit einer Verbindung hängt deshalb nicht allein von der Stärke ihrer Datenverschlüsselung ab.
Unser Beispiel beantwortet also eine klar abgegrenzte Frage: Wie widerstandsfähig ist AES-256 gegen eine direkte quantengestützte Schlüsselsuche?
Es beantwortet nicht die Frage, ob sämtliche Bestandteile heutiger Internetverbindungen bereits quantensicher sind.
Genau deshalb werden gegenwärtig neue, quantenresistente Verfahren für die Schlüsselaushandlung und digitale Signaturen eingeführt.
Fazit
Quantencomputer verändern die Sicherheitsanforderungen des Internets. Sie machen aber nicht automatisch jede Verschlüsselung unsicher.
Bei AES-256 zeigt sich, dass eine mathematisch beeindruckende Beschleunigung noch lange keinen praktisch durchführbaren Angriff bedeutet.
Quellen und weiterführende Informationen
NIST — Post-Quantum Cryptography FAQ
https://csrc.nist.gov/projects/post-quantum-cryptography/faqs
Grassl et al. — Applying Grover’s Algorithm to AES: Quantum Resource Estimates (2016)
https://arxiv.org/abs/1512.04965
NIST — Post-Quantum Cryptography Standards
https://csrc.nist.gov/projects/post-quantum-cryptography
NASA — What Is the Universe?
https://science.nasa.gov/exoplanets/what-is-the-universe/
Can Quantum Computers Break 256-Bit AES? Grover’s Algorithm Explained
https://www.youtube.com/shorts/VqSMXXiZIWo
Top comments (0)