In Cybersicherheitskreisen nennt man ihn den Q-Day: der Tag, an dem Quantencomputer das Internet zerstören werden. Bei fast allem, was wir online tun, agieren kryptografische Algorithmen stetig und meist unbemerkt im Hintergrund. Diese Systeme verschlüsseln Daten, um unsere Privatsphäre zu schützen, prüfen Zugangsdaten und sichern Zahlungen ab. Und sie funktionieren gut: Selbst mit den besten Supercomputern wäre es aussichtslos, die Codes zu knacken, mit denen die Onlinewelt arbeitet.

Aber Maschinen, die sich die Eigenheiten der Quantenphysik zu Nutze machen, bedrohen das gesamte System. In Zukunft könnten Quantencomputer aktuelle Verschlüsselungsalgorithmen exponentiell schneller knacken als die besten Superrechner. »Ein echter Quantencomputer wäre extrem gefährlich«, warnt Eric Rescorla, Chief Technology Officer des Firefox-Browser-Teams bei Mozilla in San Francisco.

Das Ganze gleicht einer typischen Zeitreise-Geschichte: Die Maschinen, die es noch nicht gibt, gefährden nicht nur unsere zukünftigen Daten, sondern auch die aktuellen und vergangenen. Manche Fachleute befürchten, dass Hacker schon jetzt den Datenverkehr abfangen und verschlüsselte Informationen sammeln, um sie in einigen Jahren – sobald Quantencomputer verfügbar sind – zu entschlüsseln. Dann wären sie in der Lage, alles über eine Person zu erfahren, von deren Krankengeschichte bis zu alten Bankunterlagen. »Angenommen, 2024 wird ein Quantencomputer entwickelt«, erklärt Rescorla. »Dann ist alles, was Sie vor 2024 im Internet gemacht haben, gefährdet.«

Aber selbst die optimistischsten Befürworter von Quantencomputern betonen, dass wir noch eine Weile warten müssen, bis die Maschinen leistungsfähig genug sind, um aktuelle Verschlüsselungstechniken zu knacken. Viele bezweifeln, dass das in diesem Jahrzehnt geschehen wird – wenn überhaupt.

Dennoch besteht das Risiko. Daher ist es nur sinnvoll, sich auf eine Umgestaltung vorzubereiten, um mögliche Schäden bei einem Q-Day zu begrenzen. Das heißt, man muss zu stärkeren kryptografischen Methoden übergehen. Glücklicherweise hat jahrzehntelange Forschung in der theoretischen Informatik eine ganze Reihe von Kandidaten hervorgebracht. Diese Post-Quanten-Verschlüsselungen scheinen unangreifbar: Selbst mit quantenalgorithmischen Ansätzen haben Expertinnen und Experten keinen Weg gefunden, sie in einer angemessenen Zeit zu überwinden.

Welcher dieser Algorithmen das Rennen gewinnt, könnte zu einem großen Teil von einer Entscheidung abhängen, die das US National Institute of Standards and Technology (NIST) in Gaithersburg, Maryland, demnächst bekannt geben wird. Es hatte 2016 Computerwissenschaftler weltweit dazu aufgerufen, Post-Quanten-Codes einzureichen, um deren Qualität mit Hilfe der gesamten Krypto-Community zu prüfen. Anlass für den Wettbewerb gab eine ungewöhnliche Äußerung der National Security Agency (NSA) im Jahr 2015, die vor anfälligen Verschlüsselungssystemen warnte und US-Unternehmen und der Regierung riet, diese zu ersetzen. Von 65 eingereichten Programmen sind nun noch 15 übrig. In den nächsten Monaten wird das NIST die Gewinner auswählen und offizielle Versionen der Algorithmen veröffentlichen. Mit ihren Bemühungen stehen die USA jedoch nicht allein da; ähnliche Organisationen in anderen Ländern werden bald ihre eigenen Empfehlungen äußern.

Das ist jedoch nur der Anfang eines langen Prozesses, um die Verschlüsselungen auf der ganzen Welt zu aktualisieren. Die Veränderung wird sich zwar auf jeden Aspekt unseres digitalen Lebens auswirken, aber hoffentlich für Normalnutzer unmerklich vollzogen. Erste Tests von Unternehmen wie Google sind jedoch nicht immer reibungslos verlaufen. »Wir wissen, wie es geht; es ist nur nicht klar, ob wir es rechtzeitig schaffen werden«, sagte der Mathematiker Peter Shor vom Massachusetts Institute of Technology in Cambridge 2020 gegenüber »Nature«.

Selbst wenn der Q-Day nie eintritt, hat allein die theoretische Möglichkeit, dass Quantencomputer unsere Codes knacken könnten, bereits die Informatik geprägt – insbesondere den Bereich der Kryptografie. »Die meisten Leute, die ich kenne, denken über quantenresistente Programme nach«, so Shafi Goldwasser, Direktor des Simons Institute for the Theory of Computing an der University of California, Berkeley.

Die Geburtsstunde der modernen Kryptografie

Das digitale Zeitalter ist zwar noch recht jung, doch die Geschichte der Kryptografie reicht weit zurück: Das Militär und Spione waren schon immer daran interessiert, Nachrichten sicher zu übermitteln, auch wenn ein Kanal (ob Brieftaube oder Funkverbindung) abgehört wird. Möglich ist das durch Verschlüsselungen. Bis in die 1970er Jahre hinein mussten sich die Gesprächspartner dafür im Voraus auf eine gemeinsame geheime Chiffre einigen.

Doch 1976 entwickelten die drei US-Informatiker Whitfield Diffie, Martin Hellman und Ralph Merkle das revolutionäre Konzept der Public-Key-Kryptografie, wodurch man Informationen sicher austauschen kann, ohne sich vorher abzusprechen. Die Idee beruht auf einem mathematischen Trick mit zwei Zahlen: Eine entspricht dem öffentlichen Schlüssel und wird zur Codierung eines Textes verwendet, die andere ist der private Schlüssel, den man zur Dechiffrierung braucht. Um vertrauliche Nachrichten zu erhalten, kann man seinen öffentlichen Schlüssel preisgeben, etwa indem man ihn in einer Zeitung druckt. Jeder kann diesen Code verwenden, um etwas zu verschlüsseln und dann zu veröffentlichen, doch nur der Empfänger besitzt den privaten Schlüssel, mit dem er die Informationen lesen kann.

In der Praxis nutzt man das Public-Key-Verfahren jedoch nicht, um direkt die Daten zu codieren, sondern um einen konventionellen symmetrischen Schlüssel sicher auszutauschen. Diesen können dann beide Parteien verwenden, um vertrauliche Inhalte hin- und herzusenden. Ab Mitte der 1990er Jahre war der am häufigsten verwendete Algorithmus zum Austausch öffentlicher Schlüssel das RSA-Verfahren, benannt nach seinen Erfindern Ron Rivest, Adi Shamir und Leonard Adleman.

Die Methode basiert auf Primzahlen, die nur durch eins und sich selbst teilbar sind. Der öffentliche Schlüssel ist das Produkt aus mindestens zwei Primzahlen (etwa 221 = 13 · 17), wobei nur eine Partei die Faktoren (13 und 17) kennt, aus denen der private Schlüssel besteht. Der Schutz wird dadurch gewährleistet, dass die Multiplikation zweier großer Zahlen zwar einfach ist, es hingegen extrem schwierig ist, ein vorhandenes Ergebnis in seine Primfaktoren zu zerlegen.

»Ein echter Quantencomputer wäre extrem gefährlich«Eric Rescorla, Chief Technology Officer des Firefox-Browser-Teams

In jüngster Zeit ist man vom RSA-Verfahren abgerückt, das inzwischen selbst für klassische Angriffe (also ohne Quantencomputer) anfällig ist. 2018 hat die auf Konsens basierende virtuelle Organisation »Internet Engineering Task Force« (IETF), welche die Annahme von Sicherheitsstandards auf globaler Ebene steuert, ein anderes Public-Key-System als Ersatz vorgeschlagen: die elliptische Kurven-Kryptografie. Sie basiert auf einem Zweig der Geometrie des 19. Jahrhunderts, der sich mit elliptischen Kurven beschäftigt.

Bei dieser Verschlüsselungstechnik muss man die n-te Potenz einer ganzen Zahl berechnen, die mit einem Punkt auf einer elliptischen Kurve verbunden ist. Dabei kennt nur eine Partei den Wert von n, welcher der private Schlüssel ist. Eine Zahl zu potenzieren, ist einfach, aber es ist extrem schwierig, bei einem gegebenen Ergebnis herauszufinden, was n war. Wie sich herausstellte, ist diese Methode schneller und sicherer als RSA.

Alle möglichen digitalen Geräte, von Mobiltelefonen bis hin zu Autos, verwenden Public-Key-Verschlüsselungen, um sich zu vernetzen. Die Technologie hat sich sogar über das Internet hinaus verbreitet: So verwendet man elliptische Kurvenalgorithmen in den Chips von Kreditkarten sowie in Sicherheitsausweisen.

Angriff der Quantencomputer

Damit schien die Onlinewelt abgesichert. Doch gerade, als die Zahl der weltweiten Internetnutzer – und somit die Verwendung von Public-Key-Verfahren – exponentiell zu wachsen begann, legte Shor, damals bei den AT&TnBell Laboratories in Murray Hill, den Grundstein für den Untergang dieser Algorithmen. 1994 bewies er, dass künftige Quantencomputer große Zahlen deutlich schneller in ihre Primfaktoren zerlegen können als herkömmliche Rechner – und ein Teil von Shors Algorithmus kann einen Schlüssel mit elliptischen Kurven effizient knacken.

Damit hatte Shor gezeigt, dass Quantencomputer auch praktische Probleme bewältigen können. Damals handelte es sich weitgehend um ein rein theoretisches Ergebnis, da die Geräte in weiter Ferne lagen. Doch noch im selben Jahrzehnt setzten Forscherinnen und Forscher von IBM erstmals Quantenberechnungen um, indem sie Moleküle in starken Magnetfeldern manipulierten. 2001 zeigten sie sogar, dass das System den Shor-Algorithmus ausführen kann – allerdings nur für kleine Zahlen. Sie berechneten die Primfaktoren von 15, also 3 und 5. Seither gab es zwar enorme Fortschritte in dem Bereich, aber man ist noch immer weit davon entfernt, Shors Algorithmus für große Zahlen auszuführen.

Dennoch befasste sich die Forschungswelt der Kryptografie nach Shors Durchbruch vermehrt mit der Möglichkeit eines Q-Day. Fachleute hatten sich bereits mit alternativen Public-Key-Verfahren beschäftigt, und die Nachricht lockte viele Talente zu dem Gebiet, sagt Goldwasser.

Gittersysteme als Schutz

Die meisten Algorithmen, die es in die finale Liste des NIST geschafft haben, stützen sich direkt oder indirekt auf einen Zweig der Kryptografie, der in den 1990er Jahren mit Hilfe mathematischer Gitter entwickelt wurde. Dabei handelt es sich um Mengen von Punkten, die sich an den Kreuzungen aus Geraden befinden. Wie in der Schule kann man die Punkte durch Vektoren miteinander addieren; einige lassen sich auch in Summen kleinerer Vektoren zerlegen. Das klingt zunächst einfach, doch wenn das Gitter viele Dimensionen hat, etwa 500, ist es sehr zeitaufwändig, solche Berechnungen durchzuführen. Das ist wie mit Primzahlen: Kennt man die kürzesten Vektoren, die das Gitter aufspannen, kann man sie als privaten Schlüssel verwenden. Für Außenstehende ist es hingegen sehr schwierig, sie zu bestimmen.

Seit den 1990er Jahren haben Forscher zahlreiche Public-Key-Verfahren entworfen, die entweder direkt mit Gittern arbeiten oder in irgendeiner Weise mit ihnen verwandt sind. Üblicherweise zeigt man, dass eine kryptografische Methode vertrauenswürdig ist, indem man beweist, dass sie mindestens so schwer zu knacken ist wie ein bekanntes Problem – in diesem Fall das Gitterproblem. Das 1996 entwickelte NTRU-Programm ist einer der frühesten solchen Algorithmen. Die Schlüssel bestehen zwar aus Polynomen mit ganzzahligen Koeffizienten, lassen sich aber auf das Gitterproblem reduzieren.

»Wir wissen, wie es geht; es ist nur nicht klar, ob wir es rechtzeitig schaffen werden«Peter Shor

Ein weiterer beliebter Ansatz für gitterbasierte Kryptografie ist »Learning with Errors«, kurz LWE, das die Grundlage mehrerer NIST-Finalisten bildet. In seiner einfachsten Form beruht das 2005 vom Informatiker Oded Regev von der New York University eingeführte Problem bloß auf simpler Arithmetik. Zunächst wählt der Empfänger eine große, geheime Zahl – den privaten Schlüssel. Dann bildet man immer wieder Vielfache dieser Zahl und addiert jedes Mal zufällige kleine Zahlenwerte, die »Fehler«, hinzu. Die so entstandene Liste ist der öffentliche Schlüssel. Um eine Nachricht (eine Zahl) zu versenden, summiert man sie zu einer gewissen Auswahl der Liste und übermittelt das Ergebnis. Um das Ergebnis zu decodieren, muss der Empfänger sie durch den geheimen Schlüssel teilen.

Vier Jahre nach seiner Veröffentlichung konnte Regev etwas Erstaunliches beweisen: Wenn es gelingt, das LWE-Verfahren zu knacken, dann lässt sich auch das wesentlich komplizierter wirkende Gitterproblem lösen. Das heißt, LWE ist genauso sicher wie Gittermodelle – aber es kommt ohne mehrdimensionale Vektoren aus, die durchaus Schwierigkeiten bereiten können, sagt Goldwasser. »Das ist großartig und erleichtert die Arbeit ungemein.« Ironischerweise bekam Regev die Idee für das LWE-Verfahren, als er erfolglos versuchte, einen Quantenalgorithmus zu finden, der das Gitterproblem effizient löst. »Manchmal ist Scheitern ein Erfolg«, sagt er.

Seither haben Forscherinnen und Forscher daran gearbeitet, eine Schwäche von gitterbasierten Systemen zu beheben. »Die öffentlichen Schlüssel sind schlichtweg riesig«, erklärt der Informatiker Yu Yu von der Shanghai Jiao Tong University in China. Während sie bei aktuell genutzten Verfahren die Länge eines Tweets haben, sind gitterbasierte Schlüssel teilweise mehr als ein Megabyte groß. Mit Hilfe strukturierter Gitter kann man die öffentlichen Schlüssels verkleinern, das macht die Systeme jedoch anfälliger. Die besten Algorithmen müssen ein ausgewogenes Verhältnis zwischen Sicherheit und Effizienz finden.

Zeitgleich zum Wettbewerb für Post-Quanten-Algorithmen rief das NIST 2016 auch dazu auf, Kandidaten für digitale Signaturen einzureichen. Mit diesen Systemen überprüfen Webserver die Identität eines Nutzers, um etwa Betrüger daran zu hindern, Passwörter zu stehlen. Die gleichen mathematischen Methoden, die den Austausch öffentlicher Schlüssel ermöglichen, eignen sich in der Regel auch für diese Aufgabe. Deshalb sind die derzeitig genutzten Signaturen ebenfalls anfällig für Quantenangriffe.

»Star Trek« und »Herr der Ringe« als Inspiration

Teams von Universitäten und Unternehmen aus vier Dutzend Ländern auf sechs Kontinenten haben daraufhin insgesamt 82 Algorithmen (sowohl zur Verschlüsselung als auch für digitale Signaturen) eingereicht, von denen das NIST 65 akzeptiert hat. Wie es sich für Nerds gehört, trugen viele der Programme Namen aus »Star Wars«, »Star Trek« oder »Herr der Ringe«, etwa: FrodoKEM, CRYSTALS-DILITHIUM oder New Hope. Die Kandidaten werden sowohl nach ihrer Sicherheit als auch nach ihrer Effizienz beurteilt, das heißt, die Ausführungsgeschwindigkeit und die Länge der öffentlichen Schlüssel spielen ebenfalls eine Rolle. Zudem müssen alle Algorithmen, die das NIST standardisiert, lizenzfrei sein.

Und schon war die Jagd eröffnet: Kryptografen versuchten, die Codes anderer zu hacken. Bereits kurz nach der Veröffentlichung wurden mehrere Systeme geknackt. »Ich glaube, die Leute hatten eine Menge Spaß dabei, sich diese Algorithmen vorzuknöpfen«, sagt Moody.

»Manchmal ist Scheitern ein Erfolg«Oded Regev

Obwohl das NIST eine US-amerikanische Regierungsbehörde ist, hat sich auch die breitere Kryptografie-Community an der Arbeit beteiligt. »Es ist eine weltweite Herausforderung«, sagt der Mathematiker Philip Lafrance von der Computersicherheitsfirma ISARA Corporation in Waterloo, Kanada. »Die Welt wird die NIST-Standards grundsätzlich befürworten.« Er gehört einer Arbeitsgruppe an, welche die Auswahl im Auftrag des Europäischen Instituts für Telekommunikationsnormen (ETSI) überwacht. »Wir gehen davon aus, dass der von uns geschaffene Standard international weit verbreitet sein wird«, so Moody.

Da die Kryptografie jedoch sensible nationale Interessen berührt, beobachten andere Länder die Entwicklung sehr genau – und einige sind vorsichtig. »Die Post-Quanten-Algorithmen sind noch nicht vollständig ausgereift, viele Aspekte befinden sich noch im Forschungsstadium«, mahnt die Verschlüsselungsexpertin Mélissa Rossi von der Nationalen Cybersicherheitsbehörde in Frankreich. Dennoch, so fügt sie hinzu, sollte man Post-Quanten-Systeme zur Unterstützung aktueller Verfahren weiter vorantreiben.

Die Organisation Chinese Association for Cryptologic Research hat bereits einen Wettbewerb für Post-Quanten-Algorithmen durchgeführt und die Ergebnisse 2020 bekannt gegeben. Das veranlasste einige Fachleute in anderen Ländern zu der irrigen Annahme, die chinesische Regierung habe schon eine offizielle Entscheidung für künftige Verschlüsselungen getroffen.

Hartnäckiges System-Update

Von den 15 übrigen NIST-Kandidaten sind 9 Verschlüsselungsalgorithmen und 6 digitale Signaturen. Zu den Finalisten gehören Implementierungen von NTRU und LWE sowie ein weiteres bewährtes System, das auf Techniken zur Fehlerkorrektur basiert. Diese »codebasierten« Algorithmen speichern Daten mit einer Redundanz, die es ermöglicht, eine Originaldatei zu rekonstruieren, selbst wenn sie leicht beschädigt wurde. In der kryptografischen Anwendung entspricht der Algorithmus, der Inhalte sichert, dem öffentlichen Schlüssel. Der geheime ist dann erforderlich, um eine ursprüngliche Nachricht wiederherzustellen.

In den nächsten Monaten wird das Institut je zwei Algorithmen für Public-Key-Verfahren und digitale Signaturen auswählen. Dann arbeiten die Fachleute von NIST Normen für einen der beiden Kandidaten aus und behalten den anderen als Reserve, falls der erste durch einen unerwarteten Angriff unbrauchbar wird.

Mit der Auswahl und Standardisierung ist es aber noch nicht getan. »Es ist sicherlich wichtig, einen Kandidaten abzusegnen, doch anschließend muss man sehen, wie sich ein Algorithmus in bestehende Protokolle integrieren lässt«, sagt der Kryptograf Nick Sullivan vom Internetdienstleister Cloudflare in New York City.

Sowohl Cloudflare als auch Google testen bereits – oft in Zusammenarbeit – Post-Quanten-Algorithmen, indem sie diese in mache Betaversionen des Chrome-Browsers und in Serversoftware integrieren. Solche Tests sind von entscheidender Bedeutung, es reicht nämlich nicht aus, dass Server und Browser perfekt kompatibel sind, damit die Kommunikation im Internet reibungslos funktioniert. Denn die Daten durchlaufen auch Netzwerkgeräte, die den Datenverkehr blockieren könnten, wenn sie unbekannte Verschlüsselungsprotokolle als ungewöhnlich einstufen. Antivirus-Software kann ähnliche Probleme verursachen. Die Schwierigkeiten bestehen »auf einer breiteren, internetweiten Ebene. Etwa in einigen Ländern, die nachverfolgen, was Benutzer tun«, so Sullivan. Derartige Hindernisse haben bereits den Übergang von RSA zu elliptischen Kurven erschwert und könnten ebenso die Einführung von Post-Quanten-Algorithmen stören.

2016 hat Google New Hope, eine strukturierte Version von LWE benannt nach dem »Star Wars«-Film, in eine Betaversion des Chrome-Browsers implementiert, die problemlos lief. Ein größeres Experiment, das Google 2021 mit einem anderen Algorithmus durchführte, verlief jedoch nicht so glatt. Einige Geräte blockierten die Verbindung, weil das genutzte Protokoll ungewöhnlich wirkte. Das Problem könnte darin bestehen, dass der öffentliche Schlüssel größer war als erwartet. Algorithmen, die das Internet auf diese Weise blockieren, muss man auf Eis legen, bis die Probleme gelöst sind. »Manchmal verhält sich ein einziges Netzelement falsch, wenn man etwas Neues hinzufügt«, so Rescorla. Um die Anbieter dazu zu bringen, ihre Produkte anzupassen – was oft durch ein einfaches Software-Update möglich ist –, bedarf es einiger Anstrengungen, sagt er. »Das könnte also eine Weile dauern.«

Dennoch ist Rescorla optimistisch, zumindest was Browser betrifft. Da nur wenige Unternehmen die verbreitetsten Browser und Server kontrollieren, müssen nur sie ihre Verschlüsselungssysteme ändern. »Alle sind ziemlich zuversichtlich, dass wir, sobald das NIST und die IETF neue Standards festlegen, in der Lage sein werden, diese recht schnell einzuführen«, so Rescorla.

Schwieriger könnte die Umstellung bei den zahllosen vernetzten Objekten wie Autos, Sicherheitskameras und allen Arten von Smart-Home-Geräten werden, bei denen viele Protokolle ineinandergreifen – vor allem bei jenen, die Sicherheitsfunktionen fest in ihre Chips eingebaut haben. »Es dauert fünf bis sieben Jahre, ein Fahrzeug zu entwickeln, und es wird ein Jahrzehnt lang auf den Straßen unterwegs sein«, sagt Lafrance. »Wird es auch in zehn Jahren noch sicher sein?«

Eines ist jedenfalls klar: Erste Umsetzungen von Post-Quanten-Verschlüsselungen werden hybride Systeme sein, die zusätzliche zu den bestehenden Codes eingesetzt werden. Der Informatiker Vadim Lyubashevsky bei IBM in Zürich, dessen Team zwei gitterbasierte Algorithmen unter den NIST-Finalisten zählt, meint, man solle die Post-Quanten-Kryptografie etwa ein Jahrzehnt lang mit aktuellen Methoden einsetzen, bevor man die neuen Verschlüsselungen allein verwendet.

Falls alles nach Plan läuft, wird das Internet schon längst in der Post-Quanten-Ära sein, wenn Q-Day eintritt. Diesem Post-Quanten-Internet könnte eines Tages ein Quanten-Internet folgen, ein Netz, das Informationen mit Hilfe quantenmechanischer Prinzipien austauscht. Der Vorteil davon wäre, dass solche Systeme nicht hackbar sind.

Der Traum vom Quanten-Internet

Aber zurück zu unserem gegenwärtigen Internet: Um aktuelle Verschlüsselungssysteme zu knacken, müssten Quantencomputer nach Schätzungen von Experten etwa 1000-mal mehr Rechenkomponenten (Qubits) haben als heute. »Es besteht eine sehr gute Chance dafür, dass Quantencomputer zunächst all die positiven Dinge tun können, lange bevor sie in der Lage sind, unsere kryptografischen Verfahren zu brechen«, sagt Lyubashevsky.

Das ist jedoch kein Grund, sich entspannt zurückzulehnen. Die vollständige Umstellung auf Post-Quanten-Systeme wird mindestens fünf Jahre dauern, schätzt Rescorla. Wenn der Q-Day kommt, existieren höchstwahrscheinlich irgendwo versteckte Geräte, die immer noch anfällig sind, sagt er. »Selbst wenn wir unser Bestes geben, wird ein echter Quantencomputer einen unfassbaren Umbruch mit sich bringen – und zwar nicht nur in positiver Hinsicht.«