Als ich ein Kind war, hat mir mein Vater Rechenaufgaben gestellt, um mich zu beschäftigen. Ich sollte große Zahlen miteinander multiplizieren oder dividieren. Als ich allmählich schneller wurde, fügte er den Zahlen weitere Ziffern hinzu, damit ich in etwa gleich viel Zeit für die Lösung aufwenden musste. Hätten wir damals schon einen Computer besessen, hätte sich mein Vater etwas anderes überlegen müssen. Denn die Aufgaben, die ich mühsam von Hand bewältigte, kann ein Rechner fast augenblicklich knacken – unabhängig davon, wie groß die Zahlen sind.

Der Unterschied zwischen meinen bescheidenen Rechenfähigkeiten im Alter von fünf Jahren und einem Computer ist in etwa so groß wie jener zwischen heutigen Rechnern und zukünftigen Quantencomputern. Diese absehbare Kluft hat schwer wiegende Auswirkungen auf die moderne Kryptografie, mit der digitale Daten gesichert sind. Deshalb suchen Fachleute aus der Mathematik und Informatik fieberhaft nach etwas, worüber mein Vater glücklicherweise nicht nachdenken musste: Aufgaben, die sowohl für klassische Rechner als auch für Quantencomputer schwer zu lösen sind.

Die heutige Kryptografie fußt auf mathematischen Problemen. Da die Rechengeschwindigkeit immer weiter zunimmt, passen Fachleute die Verschlüsselungssysteme ungefähr so an, wie es mein Vater damals tat, um mich zu beschäftigen: Sie greifen zu größeren Zahlen. Bislang reichte es, kleinere Änderungen an den Kryptosystemen vorzunehmen und bestehende Ideen geschickt weiterzuentwickeln. Aber diese Art der Optimierung wird nicht mehr funktionieren, wenn Quantencomputer voll funktionsfähig sind. Wir sind auf völlig neue Verfahren angewiesen, um auch in Zukunft sensible Informationen zu schützen.

Einen solchen neuartigen Ansatz bietet die Codierungstheorie. Dieser Bereich der Mathematik beschäftigt sich eigentlich damit, wie man Nachrichten über verrauschte Kanäle übermitteln kann. Es geht also darum, Mechanismen zu finden, um Fehler zu erkennen und zu korrigieren. Das Forschungsgebiet hat sich in der Vergangenheit weitgehend unabhängig von der Kryptografie entwickelt. Doch wie sich herausstellt, könnten codebasierte Verfahren quantensichere Verschlüsselungssysteme ermöglichen.

Schöne neue Quantenwelt

Quantencomputer sind völlig anders aufgebaut als herkömmliche Rechner. Anstatt mit gewöhnlichen Informationseinheiten zu arbeiten, die entweder den Wert eins oder null haben, nutzen Quantencomputer so genannte Qubits, die einer Überlagerung von Nullen und Einsen (etwa mit 40-prozentiger Wahrscheinlichkeit eins und mit 60-prozentiger Wahrscheinlichkeit null) entsprechen können. Indem man bestimmte mathematische Aufgaben neu formuliert, lassen sich die quantenphysikalischen Eigenschaften der Geräte bei der Lösung nutzen.

Wie sich herausstellt, können Quantencomputer einige Probleme, einschließlich derer, die aktuell unsere Daten schützen, viel schneller berechnen als herkömmliche Maschinen. Die Quanteninformatik verspricht bahnbrechende technologische Fortschritte: die Simulation von Molekülen in ungeahntem Detail, die Entdeckung neuer Wirkstoffe, die Lösung komplexer Verkehrs- und Netzflussprobleme oder die Vorhersage der Entwicklung von Finanzmärkten.

Dafür sind allerdings sehr große und zuverlässige Quantencomputer nötig, die bisher noch nicht gebaut wurden. Wenn es so weit ist, steht der Welt ein Umbruch bevor, der als Post-Quanten-Ära bezeichnet wird. Neben all den positiven Perspektiven geht diese Zeit aber auch mit einer neuen Bedrohung einher: dem drohenden Ende der Cybersicherheit.

Information verstecken

Die Kryptografie ist eine uralte Praxis der Geheimhaltung. Es ist die Kunst, Informationen so zu verschleiern, dass sie für Unbeteiligte unlesbar werden. Im Alltag nutzen wir ständig unbemerkt Verschlüsselungstechniken, etwa wenn wir digitale Nachrichten versenden oder etwas mit einer Kreditkarte bezahlen. Aber solange es Geheimnisse gibt, gibt es auch Menschen, die sie lüften wollen.

Bislang konnten die Algorithmen, die unsere digitalen Informationen schützen, mit der Rechenleistung Schritt halten. Doch staatliche und private Organisationen in vielen Nationen liefern sich ein Wettrennen. Alle wollen einen Quantencomputer bauen, der diese Verschlüsselungen knacken kann. Sobald jemand die Ziellinie überquert, besitzt er die Macht, die meisten heutigen digitalen Sicherheitssysteme zu überwinden. Schon jetzt könnten verschlüsselte Daten gesammelt und gespeichert werden, um sie irgendwann in der Zukunft mit Hilfe von Quantentechnologie offenzulegen.

Die aktuelle Kryptografie fußt auf dem so genannten Public-Key-Ansatz. Jede Partei ist dabei mit zwei Schlüsseln ausgestattet, einem geheimen und einem öffentlich einsehbaren. Das kann man sich wie ein Schlüssel-Schloss-Paar vorstellen: Wenn Alice eine Nachricht an Bob schicken möchte, dann verschlüsselt sie den Text mit Bobs öffentlichem »Key«; sie verschließt sie gewissermaßen mit seinem Schloss. Um das Schloss zu öffnen – also die Chiffre zu entschlüsseln –, braucht man Bobs geheimen Schlüssel.

In der Praxis sind dafür mathematische Probleme nötig, die sich leicht ausführen, aber kaum umkehren lassen (das Schloss, mit dem man die Nachricht geheim hält) – es sei denn, man besitzt gewisse Zusatzinformationen (den geheimen Schlüssel). Zwei der am stärksten verbreiteten Umsetzungen dieser Überlegungen sind das RSA-Verfahren und die Elliptische-Kurven-Kryptografie.

Die drei Informatiker Ron Rivest, Adi Shamir und Leonard Adleman entwickelten das nach ihren Nachnamen benannte RSA-Verfahren im Jahr 1977. Die Methode beruht auf der Faktorisierung einer Zahl, die das Produkt zweier Primzahlen ist. Ein einfaches Beispiel ist 15 = 3 · 5 – die tatsächlich gewählten Zahlen haben viel mehr Ziffern. Die Idee ist, dass Computer zwei große Zahlen zwar sehr schnell miteinander multiplizieren können, aber extrem lange brauchen, um einen großen Wert in seine Primfaktoren zu zerlegen.

Auch wenn das RSA-Kryptosystem sehr gut funktioniert, erfordert es recht lange Schlüssel. Deswegen ist inzwischen eine zweite Methode weit verbreitet, die Elliptische-Kurven-Kryptografie. Sie beruht ebenfalls auf der Umkehrung eines einfachen mathematischen Problems: Computer können schnell die Potenz einer Zahl berechnen (etwa 2⁷ = 128 oder 2¹⁰ = 1024), aber deutlich langsamer den Logarithmus eines Werts bestimmen. So lässt sich nur schwer erkennen, dass 137 438 953 472 = 2³⁷ ist.

Für große Zahlenwerte können heutige Computer das RSA-Verfahren und die Elliptische-Kurven-Kryptografie kaum lösen – sie bräuchten dafür hunderttausende Jahre. In den 1990er Jahren entwickelte der Mathematiker Peter Shor jedoch einen Algorithmus, der es einem Quantencomputer ermöglicht, solche Probleme extrem schnell zu bewältigen. Mit Shors Ansatz kann man zwar nicht alle mathematischen Probleme besser lösen, aber immerhin jene Aufgaben, die hinter RSA und den elliptischen Kurven stecken. Damit sind unsere heutigen Verschlüsselungen angreifbar.

Rettung aus dem Reich der Quanten

Eine nachweislich quantensichere Verschlüsselungsmethode beruht auf der Quantenphysik selbst. Mit dem so genannten Quanten-Schlüsselaustausch erzeugen zwei Parteien über verschränkte Photonen einen gemeinsamen, geheimen Schlüssel, durch den sie ihre Nachrichten chiffrieren können. Selbst ein mit Quantencomputern ausgestatteter Angreifer kann den Schlüssel weder unbemerkt abfangen noch manipulieren. Allerdings ist diese Technik bislang sehr aufwändig und nicht für die breite Masse zugänglich.

Deshalb ist man vorerst auf die »Post-Quanten-Kryptografie« angewiesen. Für die neuen Ansätze benötigt man weder einen Quantencomputer noch andere Konzepte der Quantenphysik. Die Idee ist dieselbe wie bei herkömmlichen kryptografischen Methoden. Man sucht nach einem mathematischen Problem, das Rechner nur schwer lösen können – in diesem Fall müssen aber auch Quantencomputer ihre Schwierigkeiten damit haben.

Staatliche Behörden haben die Dringlichkeit dieser Angelegenheit ebenfalls erkannt. Angesichts der wachsenden Fortschritte im Bereich des Quantencomputings haben verschiedene Länder und Organisationen erklärt, dass es an der Zeit sei, sich von den bestehenden Kryptosystemen wie RSA und der Elliptische-Kurven-Kryptografie zu verabschieden. Doch bevor das geschehen kann, sind Alternativen nötig. Die US-amerikanische Bundesbehörde National Institute of Standards and Technology (kurz: NIST) hat daher im Jahr 2016 einen Prozess eingeleitet, um neue kryptografische Algorithmen einzuholen und dann zu standardisieren, die auch leistungsstarken Quantencomputern standhalten sollen.

Im Rahmen des Wettbewerbs wurden über mehrere Jahre insgesamt 69 Verschlüsselungssysteme auf Herz und Nieren geprüft: Halten sie den Angriffen stand? Lassen sich die Probleme effizient umsetzen? Inzwischen sind vier Kandidaten übrig, die das NIST standardisieren wird. Unter den verschiedenen kryptografischen Ansätzen findet sich ein codebasiertes System.

Aus Alt mach Neu

Im Gegensatz zu den meisten anderen Post-Quanten-Verfahren ist die codebasierte Kryptografie recht alt. Die Idee stammt aus der Informationstheorie, die der Mathematiker Claude Shannon in den 1940er Jahren begründete. Das Forschungsgebiet widmet sich der Frage, wie sich Information über verrauschte Kanäle übertragen lässt. Denn in die Kommunikation schleichen sich gelegentlich Fehler ein, die korrigiert werden müssen. Inzwischen enthält ein Großteil unserer Technologie Fehler korrigierende Codes, die diese Aufgabe für uns übernehmen.

Die Verfahren fügen den Daten Redundanzen hinzu, die mögliche Fehler ausgleichen. Die Codierungstheorie befasst sich mit der Entwicklung und Umsetzung solcher Konzepte, um eine zuverlässige Kommunikation in verrauschten Umgebungen zu gewährleisten. Fehler korrigierende Codes sind überall: von Satelliten, die Signale durch den Weltraum senden, bis hin zu QR-Codes, die auf Websites führen, auch wenn Teile ihres Musters verdeckt sind.

Die Grundidee hinter Fehler korrigierenden Codes wie dem »Reed-Solomon-Code« basiert auf einem cleveren mathematischen Ansatz. Angenommen, man hat zwei Punkte A und B auf einer Ebene, die eine Gerade definieren. Diese enthält neben A und B natürlich noch viele weitere Punkte wie C, D, E und so weiter. Jedes beliebige Punktepaar erzeugt dieselbe Gerade; alle Paare stellen redundante Information dar. Statt aus A und B kann man die Gerade auch aus A und C oder C und D bestimmen. Wenn ein Punkt F durch einen Fehler außerhalb der Geraden landet, zeigen die anderen Punkte an, dass F nicht zu ihnen passt. Das lässt sich dann einfach korrigieren.

Die gleiche Idee funktioniert mit quadratischen Gleichungen und Polynomen höheren Grades. Die quadratische Gleichung ax² + bx + c = y ist beispielsweise durch drei Punkte definiert. Aber genau wie im Fall der Geraden liegen noch unendlich viele weitere Punkte auf der zugehörigen Parabel. Ein Trio dieser Punkte wird stets dieselbe Kurve liefern. Indem man also mehr Punkte mitliefert als nötig, schafft man redundante Informationen, mit denen sich Fehler ausbessern lassen. Das ist das Konzept hinter Reed-Solomon-Codes. Falls einige Punkte nicht auf der Kurve liegen, werden sie als fehlerhaft identifiziert und auf die vorgesehenen Werte zurückgeführt.

In der Praxis sieht das so aus: Möchte man eine Nachricht versenden, codiert man sie mit Hilfe eines Polynoms. Dafür ordnet man den Zeichen einer Nachricht Zahlenwerte zu (etwa A = 1, B = 2, C = 3 und so weiter) und setzt diese als Koeffizienten des Polynoms ein. Der Text »Spektrum« wird auf diese Weise zunächst zur Zahlenfolge 19, 16, 5, 11, 20, 18, 21, 13 und somit zum Polynom 19x⁷ + 16x⁶ + 5x⁵ + 11x⁴ + 20x³ + 18x² + 21x + 13 = y. Nun kann man das Polynom an verschiedenen Stellen x auswerten, zum Beispiel: x = 1, 2, 3, …, um entsprechende Werte für y zu erhalten.

Anstatt also direkt die ursprüngliche Zahlenfolge (19, 16, 5, 11, 20, 18, 21, 13) zu versenden, verschickt man Codewörter (x, y), die auf dem Graphen des Polynoms liegen. Ein Empfänger braucht dann bloß noch die Kurve zu bestimmen, die durch die Punkte verläuft. Falls sich Fehler eingeschlichen haben, lassen sich diese in der Regel schnell erkennen und korrigieren. Daraus lässt sich das Polynom – und somit die Nachricht – ableiten.

Der Sender nutzt also Fehler korrigierende Codes, um eine Nachricht zu codieren, und der Empfänger greift ebenfalls auf einen Code zurück, um mögliche Fehler auszubessern. Die Codierungstheorie bildet die Grundlage für Technologien wie CDs, DVDs und das 5-G-Netz.

Eine Idee auf den Kopf stellen

Ein Computer braucht in der Regel lange für eine Fehlerkorrektur. Daher erkannte Elektroingenieur Robert McEliece in den 1970er Jahren, dass sich diese Verfahren für asymmetrische Verschlüsselungen eignen könnten. Wenn Alice eine Nachricht an Bob schicken möchte, codiert sie die Nachricht zunächst mit Hilfe von Bobs öffentlichem Schlüssel und fügt anschließend Fehler hinzu, die wie Rauschen aussehen. Bob besitzt durch seinen geheimen Schlüssel den passenden Code, um zuerst die Fehler aus der Nachricht zu entfernen und den Text danach zu entziffern. Ein Angreifer, der Bobs geheimen Schlüssel nicht kennt, kann mit den Daten nichts anfangen.

Der geheime Schlüssel von Bob ist so gewählt, dass er einen bestimmten Fehler korrigierenden Code enthält, den Computer schnell ausführen können. Sein dazugehöriger öffentlicher Schlüssel besteht aus diesem Code, der jedoch so stark verändert wird, dass für außen Stehende unklar ist, um welches Verfahren es sich im Speziellen handelt. Die Einzelteile werden durcheinandergewürfelt, damit ein Angreifer nicht erkennen kann, welchen Fehler korrigierenden Code Bob gewählt hat. Das hat zur Folge, dass sich eine Nachricht problemlos mit Bobs öffentlichem Schlüssel chiffrieren lässt, aber außer Bob niemand mehr den Text rekonstruieren kann, wenn diesem auch noch Fehler hinzugefügt wurden.

McEliece stellte das erste codebasierte Public-Key-Kryptosystem 1978 vor, also kurz nach der Veröffentlichung des RSA-Verfahrens. Allerdings wurde seinem Ansatz wenig Aufmerksamkeit gewidmet, da die dafür erforderlichen Schlüssel sehr groß sind und damit viel Speicherplatz und Rechenkapazität beanspruchen. Meine Kollegen und ich erforschen Methoden, um die codebasierte Kryptografie praktikabler zu gestalten. Daher versuchen wir, die Schlüsselgröße möglichst klein zu halten, ohne die Sicherheit zu beeinträchtigen.

Das ist eine Wanderung auf einem schmalen Grat. Es muss gelingen, eine codierte Nachricht – der Fehler hinzugefügt wurden – schnell zu decodieren; zugleich braucht man aber ein bestimmtes Maß an Zufälligkeit, um das System sicher zu gestalten. Dieser Balanceakt gelingt nicht so einfach, wie die lange Liste von verworfenen Codekandidaten verdeutlicht.

Die Vorgehensweise ist dabei wie in anderen Bereichen der Kryptografie. Man wandelt die mathematisch ausgearbeitete Idee zunächst in ein Protokoll um, das ein Computer ausführen kann. Um zu testen, ob diese Implementierung auch wirklich sicher ist – und keine Schlupflöcher besitzt –, testet man sie praktisch und greift das System an. Auf diese Weise lässt sich herausfinden, ob ein Verfahren als Kryptosystem geeignet ist.

Eine codebasierte Verschlüsselung

McEliece nahm sich einen bekannten Code vor, den Reed-Solomon-Code, griff aber nur auf einen Teil der möglichen Codewörter zurück. Das ist, als würde man einen Absatz aus einem Buch vorlesen, jedoch bloß dann ein Wort aussprechen, wenn es aus den Buchstaben der ersten Hälfte des Alphabets (A bis M) besteht. (Es geht hierbei nicht darum, eine Nachricht selbst auf diese Weise zu verschlüsseln, sondern darum, eine Codierung zu entwerfen, die zufällig aussieht.)

Falls einige der Codewörter zum Beispiel »abracadabra, hocus, pocus, shazam, bippity, boppity, boo, yabba, dabba, doo, bada, bing, fiddledeedee« lauten, dann kann ein Angreifer aus dieser Information schließen, welches Codierungsschema genutzt wird. Verwendet man hingegen nur Codewörter mit Buchstaben von A bis M, bleiben »dabba, bada, fiddledeedee« übrig – und die weisen kein so klares Muster mehr auf. Dieses Verfahren erschwert es Angreifern, den verwendeten Code zu ermitteln und einen maßgeschneiderten Angriff zu starten.

Indem man sich bei Reed-Solomon-Codes auf einen Teil der Codewörter beschränkt, erzeugt man eine neue Kategorie von Fehler korrigierenden Codes: so genannte Goppa-Codes, die nach dem russischen Mathematiker Valery Goppa benannt wurden. Wie sich zeigt, sind sie unter allen vorgeschlagenen Codekandidaten die einzigen, die ein funktionierendes, sicheres Kryptosystem ermöglichen.

Goppa-Codes funktionieren im Prinzip so wie Reed-Solomon-Codes. Wenn Alice eine Nachricht an Bob schicken möchte, codiert sie diese durch ein Polynom (das sich aus Bobs öffentlichem Schlüssel ergibt) und wertet dieses an bestimmten Punkten aus, um die Codewörter zu bilden. Dann fügt sie den Codewörtern Fehler hinzu und übermittelt das Ergebnis an Bob. Für einen Angreifer sieht die Chiffre wie Kauderwelsch aus – es ist keine effiziente Möglichkeit bekannt, sie ohne weitere Informationen zu entschlüsseln. Doch Bob kann mit seinem geheimen Schlüssel zunächst die Fehler korrigieren und anschließend die chiffrierte Nachricht decodieren.

Die Sicherheit des McEliece-Kryptosystems hängt mit der Schwierigkeit zusammen, einen zufälligen Code zu entziffern. Klassische Rechner haben damit bekannterweise ihre Probleme. Seit mehreren Jahren versuchen Fachleute eine clevere Methode zu finden, damit Quantencomputer die Aufgaben stemmen können – und waren bis jetzt erfolglos. Deshalb erhärtet sich der Verdacht, dass die codebasierte Kryptografie wirklich quantensicher ist. Bewiesen wurde das aber nicht – ebenso wenig wie für alle anderen Post-Quanten-Kryptosysteme.

Fehler korrigierende Codes stellen nur eine von mehreren Möglichkeiten dar, digitale Daten in einer Post-Quanten-Welt zu schützen. Weltweit werden die verschiedenen Verfahren auf Hochtouren untersucht. Die Forschenden beschäftigen sich jedoch nicht nur mit der Sicherheit der neuen Kryptosysteme. Sie suchen auch nach Wegen, sie zu beschleunigen oder zu komprimieren, ohne dabei Schwachstellen zu schaffen.

Wir müssen herausfinden, wie eine möglichst effiziente Implementierung aussieht oder für welche Anwendungen welche Methode besonders gut geeignet ist. Die Umstellung der bestehenden Systeme wird mehr Aufwand erfordern als ein bloßes Standardsicherheitsupdate – aber wir müssen schnell handeln, um für den bevorstehenden Technologiesprung gewappnet zu sein.