Motivation

Dieser Beitrag stellt dar, welche Auswirkungen Quantencomputer auf kryptographische Verfahren haben könnten. Dazu werden die Grundlagen und der aktuelle Stand symmetrischer und asymmetrischer Verschlüsselungsmethoden grundlegend erläutert. Ziel ist es, wichtige Begriffe möglichst verständlich zu erläutern und die unterschiedlichen kryptographischen Verfahren in ihrem Zweck einzuordnen. Abschließend werden die besonderen Herausforderungen durch Quantencomputer aufgezeigt sowie Lösungsansätze durch Post-Quanten-Kryptographie vorgestellt.

Der Text soll, der Hoffnung des Autors nach, auch ohne umfassende Vorkenntnisse gut verständlich sein. Der Autor empfiehlt ferner, sich den Text möglichst entspannt an einem sonnigen Sonntagnachmittag auf Terrasse, Balkon oder im Lieblingssessel mit einem Glas Tee durchzulesen.

Einleitung

Allzu oft werden Artikel zu den Auswirkungen von Quantencomputern auf die Informationssicherheit übertrieben apokalyptisch dargestellt. Beispiele hierfür sind ein Beitrag auf Telepolis mit der Äußerung „Dazu wird wohl auch die Fähigkeit zählen, die aktuell verwendete Kryptografie und Verschlüsselung schneller zu knacken, als man sich das derzeit vorstellen kann“ oder der ZDNET-Beitrag, der mit Sätzen wie „Damit wäre alles von Staatsgeheimnissen bis hin zu Bankkontodaten in Gefahr“ ein vergleichbar dystopisches Zukunftsbild zeichnet.

Es ist Zeit, der Sache mal auf den Grund zu gehen – auf Basis der aktuellen Erkenntnisse. Natürlich kann niemand sagen, welche Entdeckungen morgen oder übermorgen noch das Licht der Welt erblicken. Einige Aussagen sind deshalb noch unter Vorbehalt, andere können heute schon sehr verlässlich getroffen werden. Los geht's.

Die Grundwerte der Informationssicherheit sind Vertraulichkeit, Integrität und Verfügbarkeit, die häufig durch weitere Anforderungen wie Authentizität und Verbindlichkeit ergänzt werden. Auf technischer Ebene werden diese Forderungen in weiten Teilen durch kryptografische Primitive erfüllt. Insbesondere die Vertraulichkeit kann über sogenannte symmetrische Chiffren erreicht werden. Das sind Verfahren, bei denen der selbe Schlüssel zur Ver- und Entschlüsselung verwendet wird.

Symmetrische Chiffren

Nahezu jeder kennt dabei klassische Chiffren wie die Cäsar-Chiffre oder Vigenère-Chiffre. Aber natürlich ist auch die Enigma-Verschlüsselung eine symmetrische Chiffre, so wie der Data Encryption Standard (DES) und der heutige Platzhirsch: der Advanced Encryption Standard (AES).

Wer sich das aktuelle TLS 1.3 genauer anschaut, wird herausfinden, dass ausschließlich AES und ChaCha20 als symmetrische Chiffren zur Auswahl stehen. Tools wie VeraCrypt bieten neben AES hingegen noch vier weitere Verfahren an, die voraussichtlich aber nur Lesern mit Vorwissen bekannt sein dürften: Twofish, Serpent, Kuznyechik und Camellia.

Wenn wir die fünf zuletzt genannten betrachten, haben diese alle gemeinsam, dass sie eine (maximale) Schlüssellänge von 256 Bit aufweisen. Wenn wir also etwas verschlüsseln wollen, brauchen wir als Schlüssel eine Folge von 256 Einsen und Nullen, welche das Schlüsselmaterial bildet. Zur Entschlüsselung müssen diese 256 Bits exakt identisch zum Verschlüsselungsvorgang sein. Ist nur ein Bit verkehrt, wird der ursprüngliche Klartext nicht wiedererkennbar sein. Nur mit der richtigen Kombination bekommen wir den ursprünglichen Inhalt wieder entschlüsselt. Es ist nun einmal wie ein Schlüssel: Ein bisschen richtig genügt eben nicht.

Die letzten 50 Jahre Informatikgeschichte lassen stets den Eindruck entstehen, dass alle Probleme einfach nur eine Frage der Zeit sind. Ein bisschen auf die nächste Prozessorgeneration warten, hier noch schauen, was Nvidia auf den Markt bringt. Früher oder später haben wir doch sicher genug Leistung, um alle 256 Bit, also 32 Bytes, durchzuprobieren.

Wer jedoch denkt, dass das vollständige Durchrechnen eines Verfahrens mit 256-Bit-Schlüssellänge in naher Zukunft Realität sein wird, unterschätzt dieses Problem gewaltig. Der Mensch ist sehr schlecht darin, exponentielles Wachstum zu verstehen. Zwar haben die drei Pandemiejahre dabei geholfen, den Begriff bekannter zu machen, dennoch unterschätzen bisweilen auch viele Informatiker weiterhin die Bedeutung.

Angenommen, uns würde das Kunststück gelingen, ein Entschlüsselungsergebnis auf nur einem einzelnen Atom zu speichern. Dann wäre es so, dass auf unserer Erde nicht genug Atome zur Verfügung stehen, um das Ergebnis jedes möglichen AES-Schlüssels zu speichern. Auch nicht in unserem Sonnensystem. Nicht einmal die ca. 200–400 Mrd. Sterne unserer Milchstraße stellen genug Atome zur Verfügung.

Dazu kommt, dass 256 Bit einfach eine willkürliche Grenze darstellen. Den Aufwand, eine gute Verschlüsselung zu konstruieren, sollte man nicht unterschätzen. Aber es hält uns wirklich nichts davon ab, eine 512-Bit-Verschlüsselung zu konstruieren. Hier könnte nun der Einwand sein, dass sich das Verfahren dadurch verlangsamen würde. Dies ist aber deutlich weniger merklich, als man meinen könnte.

Zur Frage, wie leicht sich die symmetrischen Verfahren skalieren lassen, ein kurzer Exkurs: Der AES ist in Runden aufgebaut und unterstützt 128 Bit, 192 Bit und 256 Bit Schlüssellängen. Die kleinste Variante mit 128 Bit wird in 10 Runden durchgeführt, die 192 Bit in 12 Runden und 256 Bit in 14 Runden. Damit ist die 256-Bit-Variante nur ca. 30–40 % langsamer als die 128-Bit-Variante. Ein normaler Rechner schafft recht problemlos 8–10 Gigabyte pro Sekunde AES-Verschlüsselung (256 Bit). Selbst wenn der Rechner in einer theoretischen 512-Bit-Variante nur 4–5 Gigabyte pro Sekunde verschlüsseln könnte, wäre dies verkraftbar.

Ganz ohne Neuentwicklung könnten wir auch die Schlüssellänge des AES durch Mehrfachanwendung steigern. Ein gutes Beispiel hierfür hat es in der Geschichte der Kryptologie schon gegeben: der 3-DES. Aufgrund der Tatsache, dass der Data Encryption Standard nur 56 Bit (effektive) Schlüssellänge hatte, wurde dieser durch eine dreifache Anwendung zum 3-DES weiterentwickelt. Durch die dreifache Anwendung verdoppelte sich die Schlüssellänge auf ca. 112 Bit. Auch wenn der 3-DES heute nicht mehr empfohlen wird, könnte eine solche Vorgehensweise dennoch als Vorbild dienen, sofern keine generellen Schwachstellen im AES bekannt werden.

Es ist also leicht einzusehen, dass uns eine Skalierung hier keine Probleme bereitet. Dennoch wird davon ausgegangen, dass 256 Bit auch in der Welt der Quantencomputer noch ausreichend sicher sind. Das liegt auch in der groben Schätzung begründet, dass die Anzahl der 256-Bit-AES-Schlüssel die Anzahl der Photonen in der Milchstraße übersteigt. Auf die Gefahr durch Quantencomputer möchte ich jedoch erst am Ende näher eingehen, vorweg kann allerdings bereits festgehalten werden, dass moderne symmetrische Chiffren als nicht gefährdet gelten.

Nach diesem Ausritt in die symmetrischen Chiffren können wir uns erst mal ein zweites Glas Tee gönnen und im Anschluss die Welt der asymmetrischen Kryptologie betreten. Fertig? Dann geht es jetzt weiter.

Asymmetrische Verfahren

Ein wesentliches Merkmal asymmetrischer Verfahren ist, dass zwei Schlüssel existieren: ein öffentlicher und ein privater. Der öffentliche darf, dem Namen nach, jedem bekannt sein. Der private Schlüssel muss geheim bleiben. Wer die Welt der asymmetrischen Verfahren betritt, kann diese grob in drei Bereiche unterteilen: Ver- und Entschlüsselung, Signaturerstellung und Schlüsselaustausch. Wir schauen uns zunächst mal den Bereich Ver- und Entschlüsselung an.

Wer in der Schule, Berufsschule oder im Studium asymmetrische Chiffren kennenlernt, wird häufig zunächst mit dem RSA-Algorithmus konfrontiert. Das RSA-Verfahren besteht zunächst aus der Idee, sich zwei Primzahlen auszudenken, die, miteinander multipliziert, nur noch mit hohem Aufwand getrennt, also faktorisiert werden können. Mit einer Zahl aus zwei großen Primfaktoren lässt sich aber noch nichts verschlüsseln. Wir brauchen ein Zahlenpaar, welches in einem speziellen Verhältnis zueinandersteht. Das ist ganz vereinfacht so ähnlich wie mit der 5 und der 0,2. Wenn ich eine Zahl mit 5 multipliziere, z. B. die 3, erhalte ich die 15: Wir haben damit den Klartext 3 erfolgreich verschlüsselt und die 15 als Chiffretext erhalten. Wenn ich anschließend die 15 mit 0,2 multipliziere, erhalte ich die Klartextnachricht 3 zurück. Wenn wir nun die 5 als öffentlichen Schlüssel und die 0,2 als privaten Schlüssel betrachten, haben wir eine vereinfachte Vorstellung davon, wie zwei verschiedene Zahlen für den Ver- und Entschlüsselungsvorgang genutzt werden können. Das ist bei RSA ähnlich, nur dass nicht multipliziert, sondern exponenziert wird. Also wird zur Verschlüsselung eine Zahl mit dem öffentlichen Schlüsselexponenten exponenziert und mit dem privaten Schlüsselexponenten für die Entschlüsselung exponenziert. So existiert ein öffentlicher Exponent zur Verschlüsselung und ein privater Exponent zur Entschlüsselung.

Wenn die zwei Primfaktoren bekannt sind, können wir ein solches Zahlenpaar bestimmen, welches in Bezug auf das oben erwähnte Primzahlprodukt in diesem inversen Verhältnis zueinandersteht. Kann ein böser Mensch die Faktorisierung mit geringem Aufwand durchführen, ist dieser natürlich ebenfalls in der Lage, zum öffentlichen Schlüssel den zugehörigen privaten Schlüssel zu ermitteln. Aus diesem Grund spricht man häufig davon, dass RSA auf dem Faktorisierungsproblem beruht. Das ist akademisch betrachtet jedoch nur halb korrekt. Die Ermittlung des privaten Schlüssels in Unkenntnis der Primfaktoren beruht auf dem Problem der Faktorisierung, soweit richtig. Allerdings ist die Verschlüsselung eine (modulare) Exponentiation, weshalb die Entschlüsselung auch auf dem Problem der sogenannten diskreten Wurzel beruht. Wird für eines dieser Probleme eine einfache Lösung gefunden, ist das Verfahren gebrochen.

Diese Idee entstand Ende der 70er-Jahre, und seitdem hat sich natürlich viel verändert, weshalb die Ver- und Entschlüsselung mit RSA heute nur noch geringe Relevanz besitzt. In TLS 1.3 wird RSA zur Datenverschlüsselung gar nicht mehr unterstützt und war bereits in TLS 1.2 seit langem nicht mehr empfohlen. Dies hängt mit der sogenannten vorwärtsgerichteten Sicherheit (Forward Secrecy) zusammen: Wird nämlich der private Schlüssel zu einem späteren Zeitpunkt bekannt, könnten auch ältere verschlüsselte Daten entschlüsselt werden. Spätestens seit den Snowden-Enthüllungen 2013 versucht man genau dies möglichst zu verhindern.

Es gibt andere Verfahren zur asymmetrischen Ver- und Entschlüsselung wie ElGamal und Rabin. Diese sind jedoch ähnlich alt und haben praktisch noch weniger Relevanz als RSA. Der Grund dafür ist, dass wir das nicht wirklich brauchen. Denn egal, welches asymmetrische Verfahren wir wählen: Es wird entsetzlich viel langsamer sein als eine symmetrische Chiffre. Daher ist vielen bereits bekannt, dass die Absicherung der Kommunikation häufig hybrid funktioniert. Das bedeutet, dass wir ein asymmetrisches Verfahren nehmen, um die 128–256 Bit auszutauschen, die wir im Anschluss als AES-Schlüssel verwenden können. Wir wollen, dass auf den zwei Seiten der Kommunikation der gleiche Schlüssel vorliegt. Was wir also eigentlich brauchen, ist ein Schlüsselaustausch.

Schlüsselaustausch

Wer bereits Vorkenntnisse hat, wird bei Schlüsselaustausch unmittelbar an Diffie-Hellman denken. Allerdings ist vielen nicht bekannt, dass das klassische Diffie-Hellman-Verfahren noch (etwas) älter als RSA ist. Auch hier können wir leicht wieder eine Vereinfachung vornehmen. Angenommen, wir haben zwei Kommunikationsparteien A und B, und jede denkt sich eine Zahl aus. Sagen wir, A denkt sich die 5 aus und B die 7. Dann brauchen wir noch eine gemeinsame öffentliche Zahl, die nicht geheim ist, nehmen wir die 3. Wenn A nun 5*3 und B 7*3 rechnet, kommen hier jeweils die 15 und die 21 heraus. Nun werden die Ergebnisse ausgetauscht: A übermittelt die 15 an B und B die 21 an A. Jede Seite multipliziert nun das übermittelte Ergebnis mit ihrer eigenen geheimen Zahl. So nimmt A die 21 von B und multipliziert sie mit 5: 5*21=105. B multipliziert die 15 von A mit 7: 15*7=105. Auf beiden Seiten liegt nun die 105 vor. Ausgetauscht wurde die Zahl 3 und die Ergebnisse 15 und 21. Die 105 selbst wurde nicht übertragen, liegt aber nun auf beiden Seiten vor.

Ein Schlüsselaustauschverfahren ermöglicht, dass auf nahezu magische Weise bei den Kommunikationspartnern ein Schlüssel entsteht, ohne dass dieser explizit übermittelt wird. Wir können nun die Zahl 105 als AES-Schlüssel verwenden, um die auszutauschenden Inhalte symmetrisch zu verschlüsseln.

Grundsätzlich funktioniert Diffie-Hellman ähnlich. Aber während in diesem einfachen Beispiel multipliziert wurde, wird im klassischen Diffie-Hellman exponenziert. Ein Angreifer könnte mit einer Division das Verfahren brechen: dies gelingt es bei Diffie-Hellman nur mit dem sogenannten diskreten Logarithmus. Lässt sich der diskrete Logarithmus effizient berechnen, kann der geheime Exponent aus den übermittelten Nachrichten bestimmt werden.

Heute wird Diffie-Hellman regelmäßig kaum noch mit Primzahlen durchgeführt. Das liegt daran, dass die Zahlen, um die Sicherheit zu gewährleisten, immer größer gewählt werden müssen. Heute würde ein solches privates Geheimnis wie die 5 und die 7 im Bereich einer 4000-Bit-Zahl liegen. Das ist zwar für den Rechner noch zu bewältigen, benötigt jedoch insbesondere auf mobilen Geräten viel Zeit.

Elliptische-Kurven-Kryptographie

Die oben genannten Verfahren kommen mit den uns bekannten Operationen aus der Schule wie Addition, Multiplikation und Exponentiation aus. Es hat sich jedoch gezeigt, dass sich mit diesen Operationen die asymmetrischen Verfahren nur noch schwer „steigern“ lassen. „Steigern“ bedeutet in diesem Kontext, den Abstand zwischen dem Aufwand zur (legitimen) Berechnung und dem Aufwand für einen erfolgreichen Angriff zu vergrößern. In der Vergangenheit mussten wir die Größe der Zahlen stark steigern, damit der praktische Angriff weiterhin ausgeschlossen bleibt.

Um dieses Problem zu adressieren, hat man sich überlegt, wie man ggf. neue Operationen entwickeln lassen könnte, die diesen Abstand vergrößern. Den Abstand, dass die legitime Berechnung leicht ist, die erforderlichen Aufwände für einen erfolgreichen Angriff jedoch weiterhin groß bleiben. Die Antwort darauf sind elliptische Kurven. Eine elliptische Kurve ähnelt den Polynomen aus dem Mathematikunterricht, erfüllt jedoch zusätzliche Bedingungen, die ihr besondere Eigenschaften verleihen. Es ist möglich, Operationen auf Punkte der Kurve durchzuführen, welche als Ergebnis wiederum ebenfalls auf der Kurve liegen.

Wenn wir uns noch mal das Diffie-Hellman-Beispiel anschauen, dann hatten wir eine öffentliche Zahl 3 sowie die geheimen Zahlen 5 und 7. Bei Diffie-Hellman auf elliptischen Kurven ersetzen wir die 3 durch einen Punkt in einem Koordinatensystem. Statt der öffentlichen 3 haben wir zum Beispiel den Punkt (3 | 2), wobei 3 die X- und 2 die Y-Komponente darstellt. Beide Seiten multiplizieren jetzt diesen öffentlichen Punkt mit ihrer geheimen Zahl. Bei der Addition von Punkten, die wir aus dem Matheunterricht kennen, würden wir nun die 3 und die 2 jeweils mit 5 und mit 7 multiplizieren und die 5*(3 | 2) = (15 | 10) und 7*(3 | 2) = (21 | 14) erhalten. Wenn nun jede Seite der anderen Seite dieses Ergebnis übermittelt, also A erhält (21 | 14) und B erhält (15 | 10), muss jeder seinen privaten Schlüssel anwenden, um die Ergebnisse 5*(21 | 14) = (105 | 70) und 7*(15 | 10) = (105 | 70) zu erhalten. Auf beiden Seiten wurde der gleiche Punkt bestimmt.

Diffie-Hellman auf elliptischen Kurven funktioniert exakt auf die gleiche Weise, nur dass die Multiplikation einer Zahl mit einem Punkt anders definiert ist. Wird ein entsprechend ausgewählter Punkt auf einer elliptischen Kurve mit einer Zahl multipliziert, erhalten wir einen anderen Punkt, der ebenfalls auf der Kurve liegt. Übermittelt nun jede Seite dieses Ergebnis der Gegenseite, entsteht nach erneuter Anwendung des privaten Schlüssels auf beiden Kommunikationsseiten der gleiche Punkt. Wir nehmen anschließend wahlweise die X- oder Y-Komponente als gemeinsames Geheimnis.

Findige Leser werden einwenden, dass es mit der bekannten (3 | 2) und dem Ergebnis (15 | 10) nicht sonderlich schwierig ist, die 5 als Geheimnis zu ermitteln. Über eine Division der Komponenten der Punkte lässt sich das private Geheimnis ermitteln. Bei elliptischen Kurven ist die Operation so definiert, dass diese Rückrechnung durch den diskreten Logarithmus möglich wäre. Ist dieses Problem mit geringem Aufwand lösbar, ist das Verfahren nachhaltig gebrochen. Hier unterscheiden sich die zwei Diffie-Hellman-Varianten nicht: in beiden Fällen basiert die Sicherheit auf der Schwierigkeit des diskreten Logarithmus. Allerdings kann bei elliptischen Kurven eine äquivalente Sicherheit durch deutlich kleinere private Geheimnisse realisiert werden (ca. 256 Bit anstelle 4096 Bit).

Nahezu bei jeder TLS-Verbindung im Netz wird ein solcher Schlüsselaustausch über elliptische Kurven durchgeführt. Jedoch, egal welche Schlüsselaustauschvariante wir wählen, bleibt dennoch das Problem, dass wir uns nicht sicher sein können, ob wir uns mit dem „richtigen“ Kommunikationspartner austauschen. Nur weil wir Zahlen hin und her schicken, können wir uns nicht sicher sein, ob diese Zahlen auch von der Person kommen, die wir annehmen. Wir lösen mit einem Schlüsselaustausch das Vertraulichkeitsproblem, lassen hierbei jedoch die Authentizität auf der Strecke. Daher kommen wir nun zum dritten und letzten großen Feld: die Signaturen.

Digitale Signaturen

Zur Erstellung von Signaturen findet RSA, so wie oben erläutert, weiterhin breite Anwendung. Dies hat sich auch mit TLS 1.3 nicht geändert. Neben der Signaturerstellung mit RSA kommt auch der sogenannte Digital Signature Algorithm (DSA) zum Einsatz. Dieser kann ebenfalls auf elliptischen Kurven basieren. Ein prominentes Beispiel für den Einsatz von DSA auf elliptischen Kurven sind die Signaturen auf der Bitcoin-Blockchain.

Ziel einer digitalen Signatur ist es, Integrität und Authentizität zu sichern. Integrität bedeutet, dass der Inhalt unverändert ist bzw. unrechtmäßige Änderungen entdeckt werden können. Authentizität ist die Sicherstellung und Überprüfung der Identität. Also, dass der Kommunikationspartner tatsächlich die Person ist, für die er oder sie sich ausgibt.

So wie zur Ver- und Entschlüsselung mit RSA ist es auch bei Signaturverfahren so, dass ein öffentlicher und ein privater Schlüssel existiert. Mit dem privaten Schlüssel können Unterschriften erzeugt werden, die mittels öffentlichem Schlüssel verifiziert werden können. Wenn wir jedoch über den gleichen unsicheren Kanal den öffentlichen Schlüssel übermitteln, könnte man sich nicht sicher sein, ob dieser nicht von einem Angreifer ausgetauscht wurde.

Diese Vertrauenslücke wird durch ein Zertifikat überbrückt. Ein Zertifikat ist eine Zuordnung einer Identität, z. B. durch einen Namen, mit einem öffentlichen Schlüssel und wird von einer vertrauenswürdigen Instanz bescheinigt. Zu den im Zertifikat beurkundeten öffentlichen Schlüsseln gehört somit der private Schlüssel. Beweist jemand, dass er oder sie über den privaten Schlüssel verfügt, indem beispielsweise eine Signatur erzeugt wird, beweist diese Person, über den zum öffentlichen Schlüssel im Zertifikat zugehörigen geheimen Schlüssel zu verfügen. Auf diese Weise wird die Identität nachgewiesen, die im Zertifikat bescheinigt wurde.

Und nun mal alles zusammen. Bauen wir im Browser eine TLS-Verbindung auf, wird uns ein Zertifikat übermittelt, welches wir anhand bereits bekannter Zertifikate überprüfen können. Ferner beweist die Gegenseite durch eine Signatur, in Kenntnis des privaten Schlüssels zu sein. Auf diese Weise können wir überprüfen, auch nur mit der Gegenseite zu sprechen, die im Zertifikat genannt ist. Außerdem wird mittels Diffie-Hellman ein Schlüsselaustausch durchgeführt, um auf beiden Seiten einen symmetrischen Schlüssel zu erzeugen. Anschließend kann dieser Schlüssel zur Verschlüsselung der Inhalte verwendet werden. Somit haben wir Vertraulichkeit, Integrität und Authentizität auf Basis einer TLS-Verbindung sichergestellt.

Gefahr durch Quantencomputer

Quantencomputer nutzen die Prinzipien der Superposition und Verschränkung, um innerhalb eines einzigen Rechenablaufs eine extrem große Anzahl möglicher Zustände zu erzeugen. Vielen Informatikern kommt hierbei möglicherweise eine nichtdeterministische Turingmaschine in den Kopf. Diese Vorstellung entspricht jedoch nicht ganz der Realität. Anders als bei klassischer Parallelverarbeitung ist es nicht einfach ein gleichzeitiges Ausführen aller Rechenwege. Vielmehr ermöglicht die Quantenmechanik, dass durch gezielte Quantengatter bestimmte Resultate verstärkt und andere ausgelöscht werden.

Vielleicht hilft an dieser Stelle ein Gedankenbild, um die Besonderheit der Arbeit mit Quantencomputern zu verdeutlichen: Wenn man einen Stein in einen stillen See wirft, entsteht eine einzelne Welle, die sich gleichmäßig ausbreitet. An einem beliebigen Punkt im Wasser kann man das Auf und Ab dieser Welle gut vorhersagen – es verhält sich, wie man es erwarten würde. Mit Quantencomputern zu arbeiten ist hingegen, als würde man viele Steine gleichzeitig an verschiedenen Stellen ins Wasser werfen. Die Wellen überlagern sich, verstärken oder löschen sich gegenseitig aus. Beobachtet man nun einen zufälligen Punkt auf dem See, erscheint das Verhalten chaotisch und kaum vorhersehbar. Doch wenn man das Muster der Störungen versteht und die Steine gezielt wirft – also das Problem clever formuliert – kann man sich diese Überlagerung zunutze machen. Gerade in dieser Gleichzeitigkeit liegt das große Potenzial von Quantencomputern.

Das bedeutet, dass nicht für jedes Problem ein effizienter Quantenalgorithmus existiert. Es gibt Probleme, bei denen Quantencomputer keinen oder nur einen geringen Mehrwert liefern. Bei anderen Problemen ist die Überlegenheit hingegen bereits nachgewiesen.

Gegenwärtig sind Quantenprozessoren noch sehr fehleranfällig, weshalb sich ein Großteil der Forschung auf verbesserte Hardwaresysteme und ausgefeilte Fehlerkorrekturverfahren konzentriert. Aber ungeachtet dessen entwickelt man bereits heute Algorithmen und Gatterdesigns, um gewappnet zu sein, sobald ausgereiftere Quantenchips zur Verfügung stehen.

In Bezug auf die Kryptologie sind hier zwei solcher Verfahren bekannt: der Grover- und der Shor-Algorithmus. Der Grover-Algorithmus dient der Suche in einer unsortierten Datenbank. Abstrakt betrachtet ist es der Algorithmus, der zur Berechnung symmetrischer Verfahren verwendet werden könnte. Die schlechte Nachricht dabei ist, dass der Grover-Algorithmus den Aufwand einer vollständigen Schlüsselsuche, also das Durchprobieren aller möglichen 256-Bit-AES-Schlüssel, auf die Wurzel dieses Schlüsselraums reduziert. Das bedeutet, dass wir mit einem 256-Bit-AES nur noch den Aufwand einer 128-Bit-Verschlüsselung hätten – dies aber unter der Berücksichtigung, dass wir einen funktionierenden, fehlerfreien Quantencomputer mit mehreren tausend Qubits hätten. Vereinfacht halbiert sich der Aufwand um die Hälfte der Bitlänge.

Die gute Nachricht ist: 128 Bit ist immer noch eine unglaublich große Anzahl an Schlüsseln. Auch mit diesem Werkzeug wären wir weit davon entfernt, vom Quantencomputer bedroht zu sein. Ebenfalls eine gute Nachricht: Die Wurzel stellt eine asymptotisch untere Schranke dar. Das bedeutet, dass der Grover-Algorithmus auch physikalisch nicht besser sein kann.

Das bedeutet nicht, dass ein Quantencomputer nicht für ein spezielles symmetrisches Verfahren gefährlich werden könnte, weil ein besserer Quantenalgorithmus entdeckt wird. Es bedeutet nur, dass nicht generell jedes symmetrische Verfahren in der Gefahr steht, gebrochen zu werden. Insbesondere aufgrund der Tatsache, dass die Stärke der Verschlüsselung leicht hochskaliert werden kann.

Zusammengefasst sind unsere Passworttresore und unsere Festplattenverschlüsselung nicht in unmittelbarer Gefahr. Sicherlich ist es sinnvoll, hier wachsam zu bleiben, allerdings können wir erstmal entspannt bleiben.

Etwas weniger entspannt sieht es bei den asymmetrischen Verfahren aus. Wer den Text genau gelesen hat, konnte zwei Probleme identifizieren, auf denen die asymmetrischen Verfahren beruhen: die Faktorisierung bei RSA und das Problem des diskreten Logarithmus bei Diffie-Hellman und bei den Verfahren auf Basis elliptischer Kurven. Der Quantencomputer ist aufgrund des Shor-Algorithmus eine Gefahr für die Sicherheit dieser Verfahren. Dieser macht sich einen mathematischen Trick zunutze. Wenn man eine beliebige Zahl nimmt und nacheinander mit den Zahlen 1, 2, 3 etc. exponenziert und modulo dem Primfaktorprodukt in RSA rechnet, wiederholt sich diese Sequenz nach einer gewissen (vorher unbekannten) Anzahl. Diese Wiederholung ist ein Muster, welches durch eine sogenannte Quanten-Fouriertransformation erkannt werden kann. Aus dieser Wiederholungsfrequenz lässt sich im Anschluss mindestens einer der Primfaktoren ermitteln.

Auf unseren normalen Rechnern wäre diese Suche ein Algorithmus mit exponentieller Laufzeit und deshalb praktisch nicht durchführbar. Auf einem Quantencomputer wird aus dem Problem ein polynomialzeitiger Algorithmus und wäre somit nicht länger sicher. Auch für das Problem des diskreten Logarithmus bietet der Shor-Algorithmus eine zu effiziente Lösung, sodass Verschlüsselungsverfahren nicht länger auf diesem Problem basieren dürften.

Damit haben die Berichte in gewisser Weise einen validen Punkt, dass wir ohne asymmetrische Verfahren keinen sicheren Schlüsselaustausch mehr hätten und auch die Korrektheit einer digitalen Signatur in Frage gestellt werden müsste. Aber es gibt Hoffnung.

Post-Quanten-Kryptographie

Schon 1978 wurde das McEliece-Kryptosystem veröffentlicht, von dem auch heute noch ausgegangen wird, dass es Sicherheit gegenüber Quantencomputern bietet. Allerdings werden hier Schlüsselgrößen im höheren Kilobyte- bis sogar Megabyte-Bereich erzeugt. Insbesondere in den 70er-, 80er- und 90er-Jahren wäre dies nicht realistisch gewesen. Seit Ende der 90er ist auch mit NTRU ein asymmetrisches Verfahren bekannt, bei dem von einer Resistenz gegenüber Quantencomputern ausgegangen wird.

Im Jahr 2017 startete das NIST eine offizielle Suche nach einem neuen QC-resistenten asymmetrischen Verfahren und, wie wir heute wissen, sollte es 7 Jahre dauern, bis diese Suche abgeschlossen ist.

Die Suche endete im August 2024 mit einem Verfahren für einen Schlüsselaustausch und drei Verfahren zur Erzeugung digitaler Signaturen. So wurde u. a. ML-KEM (vormals Kyber genannt) für den Schlüsselaustausch und ML-DSA (vormals Dilithium genannt) zur Erstellung von Signaturen standardisiert. Beide Verfahren basieren auf dem sogenannten Modul-Learning-with-Errors-Problem, daher stammt auch das ML im Namen. [Kleiner Funfact: Kyber sind die Kristalle in den Lichtschwertern der Jedi und aus Dilithium-Kristallen erhalten Raumschiffe wie die Enterprise ihre Energie.]

Bei ML-KEM steht das KEM für Key-Encapsulation Mechanism, was bedeutet, dass auf Basis des öffentlichen Schlüssels ein Geheimnis „verpackt“ wird, das auf der Empfängerseite mit Kenntnis des privaten Schlüssels entpackt werden kann. Bei ML-KEM kann lediglich eine 256-Bit große Nachricht chiffriert werden. Eben genau so viel, dass es für einen AES-Schlüssel genügt. Findige Leser werden einwenden, dass dies eigentlich dem Forward Secrecy Gedanken widerspricht. Aber die Parameter können für jeden Verbindungsvorgang neu gewählt/gewürfelt werden, weshalb sich die Sache hier anders verhält, als ein Schlüsselaustausch mit RSA.

Das Problem, auf dem das ML-KEM Verfahren basiert, ist eines aus der linearen Algebra und chiffriert eine Nachricht auf Basis von Matrizenmultiplikation, bei der ein zusätzlicher Fehlervektor integriert wird – was man als „Rauschen“ bezeichnen könnte. Es verrauscht die Nachricht in dem Umfang, dass es ein großes Hindernis für den Angreifer darstellt. Das Rauschen lässt sich auch mit Kenntnis des privaten Schlüssels nicht vollständig entfernen, allerdings ist die Auswirkung des Rauschens für den Entschlüsselungsvorgang so gering, dass es die Dechiffrierung und Wiederherstellung der Nachricht nicht verhindert.

ML-KEM steht in drei Varianten zur Verfügung: ML-KEM-512, ML-KEM-768 und ML-KEM-1024. Im Wesentlichen ändert sich lediglich die Größe der Matrizen und Vektoren. Die 1024-Variante wird auch als „paranoid“ bezeichnet, und so dachten sich die Entwickler des Signal-Messengers (vermutlich): Das ist der Weg. Daher ist hier bereits ML-KEM-1024 integriert. Dieser wird mit einem „klassischen“ Schlüsselaustausch auf elliptischen Kurven kombiniert, sodass beide Verfahren gebrochen werden müssten, um an den gemeinsamen Schlüssel zu gelangen.

Zurück zum Thema. Es gibt berechtigte Zweifel bezüglich der PQ-Verfahren. Das liegt daran, dass viele Kandidaten, die vormals von Experten als sicher eingestuft wurden, von anderen Experten regelrecht zerstört wurden. Daher gibt es eine gewisse Unruhe darüber, ob diese selektierten Verfahren nicht ebenfalls Schwächen enthalten, die einfach nur noch unentdeckt sind. Möglich ist das natürlich. Daher ist es immer gut, ein Verfahren in Reserve zu haben. Im März 2025 erweiterte das NIST die vier Verfahren um ein weiteres mit dem Namen HQC, welches als Backup für das Schlüsselaustauschproblem dienen soll. Strukturell ist HQC näher an McEliece als an Kyber, beruht somit auf einer anderen Klasse von Problemen weshalb davon ausgegangen wird, dass nicht zeitgleich beide Verfahren gefährdet sind.

Fazit

Quantencomputer könnten sich tatsächlich als großer Wurf auf der einen Seite und realistisches Problem für die derzeitigen klassischen asymmetrischen Verfahren auf der anderen Seite erweisen. Wie in den referenzierten Artikeln in der Einleitung basieren Einschätzungen zur „Kryptoapokalypse“ durch Quantencomputer häufig noch auf dem Wissen von vor 10 Jahren. Heute stehen wir dieser Zukunft nicht mehr ganz ungerüstet gegenüber.

Achso: Falls jemand die kryptografisch sicheren Hashverfahren vermisst haben sollte, dem sei gesagt, dass ich diese nicht vergessen habe. Auch für Hashfunktionen gelten ähnliche Bedingungen und Herausforderungen wie für symmetrischen Verschlüsselungsverfahren. Hier ist jedoch zu berücksichtigen, dass im SHA-2 und SHA-3 bereits jeweils eine 512-Bit-Variante existiert. Hier haben wir also keine Probleme. Aus diesem Grund können Quantencomputer in Bezug auf Hashfunktionen weitgehend ignoriert werden.

Ich bedanke mich bei allen Lesern, die es bis hierher durchgehalten haben, und verabschiede mich mit einem hierzu passenden Zitat von Goethe: „Durch Stolpern kommt man bisweilen weiter, man muss nur nicht fallen und liegen bleiben.“

Hinweis: Artikelbild ML generiert, der Text aber nicht