Wenn wir unsere E-Mails abrufen, uns bei unseren Bankkonten anmelden oder Nachrichten auf Signal austauschen, werden unsere Log-in-Daten durch Verschlüsselung geschützt. Sie funktioniert wie eine Art Cyber-Vorhängeschloss: Mit dem richtigen Schlüssel kann jemand die Daten auslesen. Ohne diesen Schlüssel muss er auf rohe Gewalt zurückgreifen – das digitale Äquivalent zu Bohrern und Schneidbrennern.

Unser Vertrauen in die Online-Sicherheit gründet fest in der Mathematik. Verschlüsselungssysteme basieren auf Familien von mathematischen Problemen, die als Einwegfunktionen bezeichnet werden – Berechnungen, die in einer Richtung einfach auszuführen, in der anderen aber kaum effizient zu lösen sind, selbst mit einem leistungsstarken Computer. Sie sind so etwas wie das rechnerische Äquivalent zu den einseitig überfahrbaren Nagelsperren an den Ausgängen von Autovermietungen an Flughäfen. Fährt man in eine Richtung, merkt man es kaum. Legt man den Rückwärtsgang ein, braucht man neue Reifen.

Es gibt jedoch ein Problem. Bisher verwenden Mathematiker zwar Funktionen, von denen sie glauben, dass sie Einwegfunktionen sind, aber dass es diese wirklich gibt, müssen sie erst noch beweisen. Denn es könnte durchaus sein, dass wir einfach noch nicht die geeigneten mathematischen Methoden gefunden haben, um sie auch in der anderen Richtung effizient zu berechnen. Dieses Problem stellt sich bei jeder Verschlüsselung. Unsere Daten sind dadurch gesichert, dass niemand weiß, wie man die Verfahren, die sie schützen, knacken kann – zumindest noch nicht.

Aber es sind nicht nur Cyberkriminelle von heute, über die wir uns Sorgen machen müssen. Sicherheitsexperten warnen seit Langem vor einer Bedrohung, die noch in der Zukunft liegt: Quantencomputer könnten künftig die mathematischen Probleme hinter heutigen hochmodernen Verschlüsselungen vergleichsweise schnell lösen. Also könnten private und staatliche Datendiebe – in Erwartung dieser neuen Technologie – heute schon verschlüsselte Daten stehlen und speichern. Informatiker, Mathematiker und Kryptografen sind daher auf der Suche nach neuen Verschlüsselungsalgorithmen, die nicht nur den Angriffen heutiger Computer, sondern auch denen der Quantencomputer von morgen standhalten können: Post-Quantum-Kryptografie.

Dieser Text ist zuerst in der Ausgabe 2/2024 von MIT Technology Review erschienen. Hier könnt ihr das Heft als pdf- oder Print-Ausgabe bestellen.

Leider hat noch niemand auch nur ein einziges Problem gefunden, das sowohl für klassische als auch Quantencomputer nachweislich schwer zu lösen ist. (In der Welt der Kryptografie bezeichnet „schwer“ ein Problem, dessen Lösung eine unangemessene Anzahl von Rechenschritten oder Menge an Rechenleistung erfordert.) Existieren Einwegfunktionen nicht, werden Kryptografen in einem ewigen Wettlauf um Schwachstellen und gestopfte Sicherheitslöcher mit Hackern gefangen sein.

„Die Frage, ob es Einwegfunktionen gibt, ist wirklich das wichtigste Problem“, sagt Rafael Pass, theoretischer Informatiker an der Universität Tel Aviv in Israel. Dieses Rätsel geht auf die 1970er-Jahre und die Anfänge eines Forschungsgebiets zurück, das heute als Komplexitätstheorie der Datenverarbeitung bekannt ist. Fünf Jahrzehnte lang haben Theoretiker und Kryptografen nach Wegen gesucht, um überhaupt herauszubekommen, ob solche Funktionen tatsächlich existieren.

Pass erforscht, wie Einwegfunktionen mit einer Reihe anderer offener Probleme zusammenhängen. Die vielversprechende Forschungsrichtung hat auch andere Theoretiker auf den Plan gerufen. Gleichzeitig arbeiten Menschen, die sich auf die praktische Seite der Kryptografie konzentrieren, an neuen Verfahren, die – wenn bisher auch nicht nachweislich – stark genug sind, um Quantencomputern standzuhalten.

In den letzten acht Jahren wurde die Suche nach den besten Kandidaten vom National Institute of Standards and Technology (NIST) angeführt, der US-Regierungsbehörde, die mit der Sammlung, Prüfung und Standardisierung kryptografischer Algorithmen für den öffentlichen Gebrauch beauftragt ist. Das NIST hat Dutzende von potenziellen Post-Quantum-Algorithmen selbst einer Reihe von Tests unterzogen und für externe Tests zur Verfügung gestellt. Im August 2023 gab das NIST den ersten Algorithmus bekannt, den es bis 2024 offiziell für den öffentlichen Gebrauch empfiehlt: CRYSTALS-Kyber. Er soll robust genug sein, um Quantenangriffe abzuwehren. Danach werden Unternehmen und Regierungen den Algorithmus für die Verschlüsselung von Daten übernehmen.

Allerdings zeigt uns die Geschichte, dass unser Glaube an unknackbare Verschlüsselungen oft unangebracht war. Im Laufe der Jahre sind scheinbar unangreifbare Verschlüsselungskandidaten immer wieder überraschend einfachen Angriffen zum Opfer gefallen. Sind Post-Quantum-Algorithmen wirklich unangreifbar – oder glauben wir das nur?

Die Sicherung geheimer Nachrichten war nicht immer mit schwierigen mathematischen Problemen verbunden; bis vor Kurzem war die Kryptografie kaum mathematisch. Im antiken Griechenland verschlüsselten militärische Anführer Nachrichten mit einer Skytale – griechisch für Stab oder Stock. Der Sender wickelte einen Streifen Pergament oder Leder um den Stab und schrieb dann seine Botschaft längs des Stabes auf das Band. Die Botschaft wurde dann ohne Stab verschickt. Um sie zu lesen, brauchte der Empfänger einen Stab mit dem gleichen Durchmesser. Jahrhunderte später beschrieben römische Historiker einen Julius Cäsar zugeschriebenen Code. Dafür wurde jeder Buchstabe einer Nachricht um eine bestimmte Zahl von Stellen – bei Julius Cäsar waren es drei – im Alphabet nach rechts verschoben; so wurde beispielsweise ein A als D geschrieben.

Im 16. Jahrhundert verwendete Maria Stuart, als sie 18 Jahre von ihrer Cousine Königin Elisabeth I. gefangen gehalten wurde, ausgeklügelte, auf Symbolen basierende Chiffren. Sie verschlüsselte damit Hunderte von Briefen, die ihr zu Freiheit und Thron verhelfen sollten. Doch ein Team von Spionen und Codebrechern von Elisabeth I. fing die Briefe ab, entschlüsselte und kopierte sie. In dem Brief, der ihr Schicksal besiegelte, billigte Maria einen Plan zur Ermordung von Elisabeth mit sechs Worten: „Schickt die sechs Herren zur Arbeit.“ Daraufhin ließ Elisabeth ihre Cousine 1587 enthaupten.

1932 knackten polnische Codebrecher den Code der frühen deutschen Enigma-Maschine, die am Ende des Ersten Weltkriegs erfunden wurde. Später gaben sie ihre Informationen an britische Codebrecher weiter, die während des Zweiten Weltkriegs eine weiterentwickelte Version der Enigma entschlüsselten.

Die Zeit vor den 1970er-Jahren bezeichnet Pass jedoch halb im Scherz als das „dunkle Zeitalter der Kryptografie“. „Kryptografie war nicht wirklich wissenschaftlich“, sagt er. „Es war eher eine Kunst. Man musste [künstlerische] Fähigkeiten haben, um ein Verschlüsselungsverfahren zu erfinden. Und dann wurde es so lange eingesetzt, bis ein cleverer Mensch herausfand, wie man es knacken konnte. Und so ging es immer weiter.“

Das änderte sich, so Pass, im November 1976, als die Kryptografen Whitfield Diffie und Martin Hellman in Stanford eine neuartige Methode beschrieben, mit der zwei Personen einen Schlüssel entwickeln konnten, den sie beide kennen und mit dem sie geheime Nachrichten übermitteln können. Entscheidend ist, dass sie sich dazu nicht treffen müssen und auch keinen abgesicherten Kanal brauchen, um den geheimen Schlüssel auszutauschen. Dies war ein bahnbrechender Gedanke. Bisher mussten sowohl der Sender als auch der Empfänger den Schlüssel zum Ver- und Entschlüsseln besitzen. Um beispielsweise eine mit der Enigma-Maschine verschlüsselte Nachricht zu entschlüsseln, benötigte der Empfänger ein Schlüsselblatt, das die ursprünglichen Verschlüsselungseinstellungen enthielt.

Das Geheimnis der Diffie-Hellman-Strategie bestand darin, dass zwei Personen den Schlüssel anhand eines einfachen mathematischen Problems erstellten, das in der einen Richtung leicht zu berechnen und in der anderen mühsam ist: Die beiden Personen, die heimlich miteinander kommunizieren wollen, von Kryptografen Alice und Bob genannt, wählen jeweils eine geheime Zahl aus. Dann einigen sie sich gemeinsam auf ein Zahlenpaar, das sie öffentlich teilen (eine ist eine große Primzahl, die andere wird als Basis bezeichnet). Als Nächstes führt jeder von ihnen eine Reihe von mathematischen Operationen durch, um ihre jeweiligen privaten Zahlen mit der Primzahl und der Basis zu kombinieren.

Dann tauschen sie die Ergebnisse aus, und jeder führt eine weitere Reihe von mathematischen Operationen mit den neuen Zahlen durch. Am Ende haben Alice und Bob die gleichen Operationen mit den gleichen Zahlen durchgeführt – nur in unterschiedlicher Reihenfolge – und sind zu der gleichen Antwort gekommen. Die Ziffern dieser Antwort bilden den gemeinsamen, von Alice und Bob miteinander geteilten, geheimen Schlüssel. Ein Lauscher, der die Übertragung abfängt – mit dem Spitznamen Eve –, wird nicht in der Lage sein, das mathematische Durcheinander zu entschlüsseln, ohne mindestens eine der privaten Zahlen zu kennen.

Das komplizierte Problem, das Eve lösen müsste, heißt „diskreter Logarithmus“. Der Diffie-Hellman-Ansatz wird auch heute noch verwendet, um beispielsweise VPNs zu sichern, und ist ein wesentlicher Bestandteil einiger Post-Quantum-Verfahren.

In ihrer Arbeit stellten Diffie und Hellman fest, dass es keinen Algorithmus gibt, der das diskrete Logarithmusproblem in einer angemessenen Zeit lösen kann. Das ist auch heute noch nicht der Fall. Daraufhin führten sie zum ersten Mal den Begriff der Einwegfunktionen als Grundlage für die sichere Kryptografie ein. Heute basieren sichere Online-Interaktionen, die zum Beispiel Authentifizierung oder digitale Signaturen beinhalten, auf dieser allgemeinen Idee. Ohne den mathematischen Beweis, dass es sich tatsächlich um Einwegfunktionen handelt, besteht jedoch die Möglichkeit, dass jemand ein effizientes Verfahren zum Knacken dieser Funktionen entdeckt.

Heutzutage beginnen Online-Transaktionen mit einer Art digitalem Handschlag, und die Sicherheit dieses Handschlags wird oft durch ein anderes mathematisches Problem garantiert, das als schwierig gilt. Das derzeit verbreitetste Verschlüsselungsverfahren hat 1977 ein Trio junger Informatiker eingeführt, angeregt durch die Veröffentlichung von Diffie und Hellman. Sie nannten ihren Ansatz RSA, nach den Nachnamen der Wissenschaftler Ron Rivest, Adi Shamir und Leonard Adleman. RSA beruht auf der Schwierigkeit, Zahlen in ihre Primfaktoren zu zerlegen: Es ist zwar einfach, Primzahlen miteinander zu multiplizieren, aber schwierig, herauszufinden, welche miteinander multipliziert wurden, um ein bestimmtes Ergebnis zu erhalten.

Das Verfahren unterscheidet sich ein wenig vom Diffie-Hellman-Ansatz: Bei Diffie-Hellman können zwei Teilnehmer über einen unsicheren Kanal (z. B. das Internet) einen Schlüssel ausarbeiten, der zur Verschleierung von Nachrichten verwendet wird. Bei RSA verwendet Alice den öffentlichen, bekannten Schlüssel von Bob, der auf großen Primzahlen basiert, um eine Nachricht an Bob zu verschlüsseln. Nur Bob kann mit einem geheimen Schlüssel, der zu seinem öffentlichen Schlüssel passt, diese Nachricht entschlüsseln.

RSA wurde schnell zu einer der beliebtesten Verschlüsselungsmethoden mit öffentlichen Schlüsseln. Es ist einfach zu verwenden und anzupassen. Da im Laufe der Zeit neue Algorithmen aufgetaucht sind, die schneller faktorisieren können, und Computer immer leistungsfähiger geworden sind, hat das NIST jedoch empfohlen, immer größere Zahlen für die Sicherheit zu verwenden. Zurzeit sollte ein Schlüssel aus mindestens 2048 Bits besteht, was einer Zahl mit über 600 Ziffern entspricht. (Die größte Zahl, die bisher in zwei Primzahlen zerlegt wurde, bestand aus 250 Ziffern. Sie zu faktorisieren, erforderte fast 3000 Stunden Rechenzeit).

 

Das ist eine Stärke von RSA – selbst wenn es nicht unknackbar ist, ist es einfach, den Rechenaufwand für das Knacken des Schlüssels immer weiter zu erhöhen. Im Jahr 1994 entwickelte der amerikanische Mathematiker Peter Shor, der damals an den Bell Labs arbeitete, allerdings einen Algorithmus für Quantencomputer, der das Faktorisierungsproblem – zumindest theoretisch – sehr viel schneller lösen könnte. Das war eine doppelte Bedrohung: Sein Ansatz konnte auch das diskrete Log-Problem des Diffie-Hellman-Ansatzes überwinden. Shors Arbeit löste sowohl bei denjenigen, die Quantencomputer bauen wollten, als auch bei denjenigen, die die damit verbundene Bedrohung für die Cybersicherheit erkannten, Begeisterung und Besorgnis aus. Zum Glück für Kryptografen bräuchte man einen Quantencomputer, der mit sehr, sehr vielen Quantenbits (Qubits) rechnet, um real existierende RSA-Schlüssel zu knacken.

Vor einigen Jahren schätzten Forscher von Google und der Königlichen Technischen Hochschule KTH in Schweden, dass ein Quantencomputer, der mit 20 Millionen Qubits rechnet, etwa acht Stunden brauchen würde, um heutige 2048-Bit-RSA-Schlüssel zu knacken. Der derzeitige Stand der Technik reicht bei Weitem nicht an diese Größe heran: Der bisher größte Quantenchip, der von IBM im Dezember 2023 vorgestellt wurde, rechnet mit gerade einmal 1121 supraleitenden Qubits, die obendrein noch viel zu fehlerbehaftet sind, um Codes zu knacken.

Doch der technische Fortschritt ist rasant. Ob RSA als unmittelbar von einem Quantenangriff bedroht angesehen werden kann, hängt weitgehend davon ab, wen man fragt, sagt der Informatiker Ted Shorter, der das Cybersicherheitsunternehmen Keyfactor mitbegründet hat. Für einige scheint das Ende nah, sagt er. „Wenn man mit theoretischen Informatikern spricht, sagen sie: Ja, RSA ist erledigt, allein weil sie es sich vorstellen können“, so Shorter. Für sie, fügt er hinzu, bedeute die Existenz von Shors Algorithmus das Ende der Verschlüsselung, wie wir sie kennen.

Viele Kryptografen, die reale Sicherheitssysteme implementieren, machen sich weniger Sorgen über die Quantenzukunft als über die cleversten Cyberkriminellen von heute. Thomas Decru, Kryptograf an der KU Leuven in Belgien, sagt, dass die Quantenbedrohung ernst genommen werden müsse, aber es sei schwer zu sagen, ob RSA in fünf Jahren oder später – oder nie – an Quantencomputer fallen wird. „Solange es keine Quantencomputer gibt, ist alles, was man über sie sagt, in gewisser Weise spekulativ“, sagt er. Pass ist sich hinsichtlich der Bedrohung sicherer: „Man kann mit Sicherheit sagen, dass die Existenz dieses Quantenalgorithmus bedeutet, dass es Risse in dem Problem gibt, oder?“

Wir müssten auf alles gefasst sein, sagt Lily Chen, eine Mathematikerin, die die Cryptographic Technology Group des NIST leitet und an den laufenden Bemühungen um Post-Quantum-Verschlüsselungsstandards mitarbeitet. Unabhängig davon, ob sie in drei oder 30 Jahren laufen werden, stehen Quantencomputer vor der Tür, und RSA, Diffie-Hellman und andere Verschlüsselungssysteme könnten angreifbar werden.

Es wird nicht einfach, ein quantenresistentes kryptografisches Verfahren zu finden. Zwar entwickeln Forscher ständig neue Verfahren, die dafür infrage kommen könnten. Es werden aber auch immer wieder vielversprechende Kandidaten geknackt. Im Februar 2022 beispielsweise entdeckten Kryptografen eine fatale Schwachstelle in Rainbow, einem Algorithmus, der drei Analyserunden des NIST überstanden hatte. Ein paar Monate später, nachdem die NIST-Liste erneut gesäubert worden war, gaben Decru und sein Kollege Wouter Castryck von der KU Leuven bekannt, dass sie einen weiteren Finalisten, einen Algorithmus namens SIKE, geknackt hatten.

SIKE wurde vor einigen Jahren in Zusammenarbeit mit Forschern und Ingenieuren von Amazon, Microsoft, der Universität von Versailles und anderen Unternehmen entwickelt. Es basiert auf einer speziellen mathematischen Abbildung, einer sogenannten Isogenie, die aus Verbindungen zwischen elliptischen Kurven besteht. In Leuven haben Decru und Castryck jedoch Wege gefunden, die schwierigste Version von SIKE in nur wenigen Stunden Rechenzeit auf einem normalen Desktop-Computer zu knacken. Andere Gruppen haben seitdem Wege gezeigt, mit denen es noch schneller geht. Das gelang Decru und Castryck fast zufällig und nur wenige Wochen, nachdem SIKE zum alternativen NIST-Finalisten erklärt worden war. „Wir haben überhaupt nicht versucht, es zu knacken“, betont Decru. „Wir haben nur versucht, es zu verallgemeinern.“

Chen sagt, dass der Fall von SIKE – und Rainbow davor – veranschaulicht, was die Bemühungen um quantensichere Algorithmen vorantreibt. Einerseits, sagt sie, „muss man ein Problem finden, das sowohl für Quantencomputer als auch für klassische Computer schwierig ist.“ Auf der anderen Seite geht es um die Umsetzung dieses schwierigen Problems in ein kryptografisches System, das in der Praxis verwendet werden kann. Selbst bei den heute klar definierten Problemen, so Shorter, sei es sehr schwierig, jede Lücke in jedem Betriebssystem und jedem Gerät auf dem Markt vorherzusehen und zu verhindern. „Und dann gibt es noch Interoperabilitätstests, Zertifizierungen und andere Tests“, sagt er, „um sicherzustellen, dass sie nicht nur korrekt, sondern auch sicher implementiert sind.“ Das mathematische Problem, auf dem SIKE basiert, scheint rechnerisch wahrlich schwierig zu sein. Es könnte sogar tatsächlich quantensicher sein. Der Fehler lag in dem Verfahren selbst, das zu viel von der übertragenen Information preisgab.

Andere Verfahren haben sich besser bewährt. Der erste von der NIST standardisierte Post-Quantum-Verschlüsselungsalgorithmus, CRYSTALS-Kyber, bietet Sicherheit durch die Verwendung von mathematischen Gittern, Objekten, die als Punktfelder modelliert werden können. CRYSTALS-Kyber ist ein allgemeines Verschlüsselungsverfahren wie RSA, das für Aufgaben wie die Sicherung der Online-Kommunikation verwendet werden kann. Drei weitere zugelassene Algorithmen dienen der Authentifizierung digitaler Signaturen. Sie sollen sicherstellen, dass digitale Dokumente nicht in betrügerischer Absicht von Kriminellen unterzeichnet wurden. Das NIST plante, diese Verfahren bis zum Frühjahr 2024 zu standardisieren. Drei weitere Algorithmen könnten in den nächsten Jahren ebenfalls standardisiert werden, sofern sie weitere Prüfungsrunden überstehen.

„Wir sind wieder bei diesem Katz-und-Maus-Spiel angelangt, bei dem die Entwickler von Algorithmen neue Konstruktionskandidaten vorschlagen und andere Entwickler versuchen, sie zu brechen“, sagt Shorter. Das perfekte mathematische Verfahren könnte uns aus diesem Schwebezustand herausführen, aber es darf kein klebriges Durcheinander sein, das sich ein reiner Theoretiker an einem langen Wochenende ausgedacht hat. Es muss ein Gleichgewicht zwischen Mathematik und Kryptografie herstellen, mit rechnerischer Schwierigkeit auf der einen und einfacher Implementierung auf der anderen Seite. Entfernt man sich zu weit von einer dieser Eigenschaften, wird es angreifbar – wenn nicht jetzt, dann in Zukunft.

Bis dahin werden die Kryptografen in einem chaotischen Schwebezustand verharren, in dem überzeugend robuste Verschlüsselungssysteme vertrauenswürdig sind – aber nur so lange, bis sie es erwiesenermaßen nicht mehr sind. Aber hey, es geht ja nur um die vergangene, gegenwärtige und zukünftige Sicherheit der Daten von jedermann und überall. Kein Druck.