Juliane Krämer sieht eine Bedrohung auf die Welt zukommen: den Quantencomputer. In einem Jahrzehnt könnten Rechner auf Basis der Quantenphysik leistungsstark genug sein, um die im Internet gängigen Verschlüsselungen zu knacken, befürchtet die Kryptografin von der Technischen Universität Darmstadt. »Wir müssen uns schon heute dagegen wappnen.«

Ob es wirklich so kommt? Noch gibt es viele technische Hürden. Doch für Forscher wie Krämer ist das Risiko einfach zu groß: Sie entwickeln bereits jetzt kryptografische Methoden, die den futuristischen Wunderrechnern trotzen sollen.

Meist sind sich Internetnutzer der Sicherheitsverfahren gar nicht bewusst, die sie beim Surfen im Internet schützen, denn sie laufen unbemerkt und automatisch ab. Mit Hilfe einer digitalen »Signatur« verhindern die Verfahren, dass ausgetauschte Daten bei Dritten landen, etwa während des Onlinebankings oder beim Aufspielen von Softwareupdates.

Ein digitaler Reißwolf

Neben dem Urhebernachweis dienen die Sicherheitsverfahren dem Verschlüsseln von Daten. Dazu verwandelt der Sender sie in einen Zeichensalat, den nur der Empfänger wieder entwirren kann. Damit die beiden keinen geheimen Schlüssel tauschen müssen, verwendet man so genannte asymmetrische Kryptoverfahren.

Diese kann man sich wie einen besonderen Reißwolf vorstellen, der Papier nicht etwa in immer gleich geformte Streifen zerschneidet, sondern sie in charakteristisches Muster aus winzigen Dreiecken, Vierecken und Streifen zerstückelt und anschließend wild durchmischt. Eine Botschaft wird dadurch unleserlich gemacht, Experten sprechen von einem »öffentlichen Schlüssel«.

Allein der Empfänger besitzt einen dazu passenden »privaten Schlüssel«. Aus ihm geht hervor, nach welchem Schema der Reißwolf das Dokument zerschnitten hat – und wie man die Dreiecke, Vierecke und Streifen schnell wieder zusammenfügen kann.

»Welche Alternativen sich in der Praxis durchsetzen werden, muss sich erst noch zeigen«Juliane Krämer, TU Darmstadt

Bei der digitalen Signatur ist der Weg umgekehrt: Der Sender verschlüsselt eine Nachricht mit seinem privaten Schlüssel. Jeder Empfänger kann dann mit dem öffentlichen Schlüssel prüfen, ob die Botschaft echt ist. In unserer Metapher könnte er also anhand der Form der Schnipsel sagen, ob diese wirklich von einem bestimmten Reißwolf zerkleinert wurden.

Realisiert werden asymmetrische Kryptoverfahren durch mathematische Funktionen. Das sind Rechenvorschriften, die eine Zahl in eine andere umwandeln. In einer Richtung sind die für Verschlüsselungen relevanten Transformationen leicht auszuführen. Rückwärts aber sind sie derart schwer, dass selbst Superrechner dafür Jahrzehnte bräuchten.

Mit dem privaten Schlüssel lässt sich hingegen eine Hintertür öffnen, die Rückwärtsrechnung also deutlich schneller ausführen. Ein populäres Beispiel ist die Multiplikation zweier Primzahlen. Sie ist eine leichte Rechenoperation, die jeder Taschenrechner hinbekommt. Der umgekehrte Weg, eine vorgegebene Zahl in ihre Primfaktoren zu zerlegen, ist indessen äußerst schwer, zumindest für sehr große Zahlen. Ein Computer muss hierfür unzählige Möglichkeiten durchtesten.

Das Ende der RSA-Verschlüsselung

Für die Verschlüsselung von Botschaften lässt sich die Primfaktorzerlegung wie folgt nutzen: Das Produkt der Primzahlen kann jeder Nutzer als öffentlichen Schlüssel zum Verschlüsseln verwenden. Nur der Empfänger kennt die Primfaktoren, die er als privaten Schlüssel verwendet. Das Prinzip stammt aus den 1970er Jahren und ist seitdem Basis des so genannten RSA-Kryptosystems, benannt nach den US-Informatikern Ron Rivest, Adi Shamir und Leonard Adleman. Varianten davon sichern bis heute die Kommunikation im Netz.

Doch damit könnte es auf einen Schlag vorbei sein, sobald ein leistungsstarker Quantencomputer bereitstünde. Denn ausgerechnet die derzeit genutzten digitalen Reißwölfe sind für ihn keine. Ein Quantenrechner führt die Rückwärtsrechnung in Windeseile durch – mit einem speziellen Algorithmus, den der Informatiker Peter Shor 1994 entwickelt hat.

Allerdings werden derartige Maschinen keine Allrounder sein. Es sind erst wenige Probleme bekannt, deren Lösung sie radikal beschleunigen können. Die Primfaktorzerlegung ist das prominenteste. Viele Aufgaben, so die Meinung unter Forschern, werden die Maschinen hingegen kaum oder gar nicht schneller lösen als ein normaler Computer.

Juliane Krämer und ihre Kollegen glauben deshalb, dass mit dem Quantencomputer nicht automatisch die Ära der Privatsphäre enden muss. Sie setzen ihre Hoffnung auf mathematische Funktionen, bei deren Umkehrung sich auch Quantenrechner schwertun würden und die das RSA-Verfahren eines Tages ablösen könnten.

Hoffen auf die gitterbasierte Kryptografie

Eine dieser Methoden, die »gitterbasierte Kryptografie«, erforscht Krämer. Unter Gitter verstehen Mathematiker einen Raum, gefüllt mit regelmäßig angeordneten Punkten. Ein Bauzaun ähnelt einem Gitter mit zwei Dimensionen. Kryptografen interessieren sich für deutlich komplexere Varianten, die hunderte Dimensionen aufspannen, freilich nur als virtuelles Gebilde.

Wenn man einen Punkt irgendwo zwischen die einzelnen Gitterpunkte setzt, kann es wegen der vielen Dimensionen äußerst schwierig sein, den nächsten Gitterpunkt zu finden. Es kann aber auch leicht sein. Das hängt davon ab, wie das Gitter mathematisch beschrieben wird. Experten sprechen von einer »schlechten« oder einer »guten« Basis. Verwendet man eine »schlechte Basis« als öffentlichen Schlüssel und eine »gute« als privaten, hat man einen mathematischen Reißwolf gestaltet.

Bekannt sind dieses und ähnliche Verfahren schon lange. »Doch welche davon sich in der Praxis durchsetzen werden und welche nicht, muss sich erst noch zeigen«, sagt Krämer. Derzeit seien Entwickler auf der Suche nach einer geeigneten Balance zwischen Sicherheit und Effizienz.

Die Effizienz ist ein wichtiges Thema unter Kryptografen. »Niemand will beim Onlineshopping sekundenlang auf die Verschlüsselung oder die Prüfung der Authentizität warten«, sagt Ruben Niederhagen vom Fraunhofer-Institut für Sichere Informationstechnologie in Darmstadt. Doch genau das könnte mit den neuen Verfahren passieren.

Außerdem erfordern die Methoden der Post-Quanten-Kryptografie bislang deutlich mehr Ressourcen als die gängigen Verfahren. Das Rechnen mit Gittern, wie es beim Ver- oder Entschlüsseln nötig ist, braucht viel Rechenpower. Die Schlüssel sind auch um ein Vielfaches länger als bei RSA und Co, benötigen also mehr Speicherplatz.

Das erscheint in Zeiten von Terabyte-Festplatten und Gigahertz-Prozessoren nicht als Problem. »Doch die Speicher eingebetteter Systeme, wie etwa im Airbag oder in Zukunft in der Ampel, die mit Autos kommuniziert, haben nur wenige Kilobyte Speicher und wenig Rechenkapazität«, sagt Fraunhofer-Forscher Niederhagen. Er ist an einem neuen Projekt des Bundesforschungsministeriums (BMBF) beteiligt, das Post-Quanten-Kryptografie für den Automobilbereich fit machen soll. »Bei der Bordelektronik zählt jeder Cent, weshalb man nicht erwarten darf, dass die Ressourcen für alternative Kryptoverfahren erweitert werden.«

Die neuen Verfahren sind ineffizient

Also gilt es, die Effizienz zu erhöhen. Dafür ist Kreativität gefragt. Die Forscher spielen etwa mit unterschiedlichen mathematischen Darstellungen von Gittern. Mit einer davon, in Form von »Polynomen«, laufen die Rechenoperationen schneller. Doch die Schlüssellängen bleiben, je nach Methode, fünf- bis hundertmal so groß wie bei gängigen Verfahren. »Es gibt kein Patentrezept für die Steigerung der Effizienz«, sagt Krämer.

Mittlerweile diskutieren Experten über viele verschiedene Methoden mit unterschiedlichen Vorzügen und Nachteilen in puncto Sicherheit und Effizienz. Die US-amerikanische Standardisierungsbehörde NIST versucht seit 2017, die Spreu vom Weizen zu trennen – und so vielleicht einen Algorithmus zu finden, der RSA als Internetstandard ablösen kann. In einem Wettbewerb hat das NIST rund 80 Vorschläge für quantencomputerresistente Kryptografieansätze gegeneinander antreten lassen. Nach einer ersten Evaluierung Anfang 2019 blieben 29 Methoden übrig. Die meisten davon sind gitterbasiert.

Die NIST hat seitdem Schwächen der einzelnen Verfahren benannt und fordert Nachbesserungen von den Autoren. Da die Methoden öffentlich sind, können andere Wissenschaftler nach Sicherheitslücken suchen, welche die Urheber dann stopfen müssen. Mitte 2020 wollte das NIST das Bewerberfeld auf dieser Basis weiter einschränken.

Unterdessen setzt die Münchner Firma genua ein mit der TU Darmstadt entwickeltes Verfahren namens XMSS für digitale Signaturen testweise schon ein. Es gilt seit 2018 offiziell als zulässiger Internetstandard und kann frei verwendet werden. Genua hat besonders sicherheitsbewusste Firmen und Behörden als Kunden, die abhörsicher kommunizieren wollen.

Ein Problem, viele Lösungen

Dazu nutzt ihr Verfahren »Hashfunktionen«. Diese erstellen aus der zu versendenden Datei eine Art digitalen Fingerabdruck, der als Schlüssel dient. Die Methode gilt als resistent gegen Quantenalgorithmen, eignet sich aber nur für digitale Signaturen. Zudem benötige der Anwender eigens eine Maschine, um die Schlüssel in einem gesicherten Netz zu erzeugen und zu managen, sagt genua-Wissenschaftler Stefan-Lukas Gazdag.

Der Fall XMSS zeigt, dass es die eine Lösung für alle Kryptografiesorgen wohl nicht geben wird. Das verdeutlichen auch die Teilnehmer im NIST-Wettbewerb: Manche der Verfahren eignen sich eher für digitale Signaturen, andere zur Verschlüsselung. Die einen sind schnell berechenbar, haben aber lange Schlüssel oder umgekehrt. »Am Ende wird die NIST mehrere Verfahren standardisieren«, prognostiziert Krämer.

Eine Umsetzung plant die US-Behörde jedoch erst zwischen 2022 und 2024. Bis dahin klafft eine Art Verschlüsselungslücke. Auch das BMBF hat das Dilemma erkannt. Es fördert Projekte der Post-Quanten-Kryptografie für unterschiedliche Bereiche, »QuantumRISC« für die Autobranche etwa oder »PQC4Med« für den Schutz medizinischer Geräte.

Lassen sich heutige Daten in Zukunft entschlüsseln?

Sorgen bereitet den Experten derweil ein prinzipielles Problem: Während digitale Signaturen nur für den Moment sicher sein müssen, sollten es verschlüsselte Daten idealerweise dauerhaft bleiben. Heute chiffrierte Daten könnten, sofern sie auf einer Festplatte gespeichert sind, auch in Jahrzehnten noch von einem Quantenrechner entschlüsselt werden. Ob das ein Problem ist, hängt wohl von der Art der Daten sowie ihrem Alter ab. »Stellen Sie sich eine zukünftige Website vor, auf der jeder Ihre Whatsapp-Kommunikation von heute sehen könnte«, sagt Krämer. »Ab wann würde Sie das nicht mehr stören? In einem Jahr? In zehn Jahren?«

Wer längerfristig auf der sicheren Seite sein will, sollte RSA und Co daher bereits heute nicht mehr nutzen, fordert die Mathematikerin. Obwohl die Standardisierung durch die NIST noch ausstehe, gebe es schon jetzt einsatzfähige Post-Quanten-Verfahren. Allerdings könnten diese noch unbekannte Schwachstellen haben.

Überhaupt ist es nur eine Annahme, dass die Post-Quanten-Kryptografie auch wirklich dauerhaft dem Quantencomputer oder den Gehirnen genialer Mathematiker trotzen kann. Zwar präsentieren die Entwickler gerne mathematische Beweise für die Zuverlässigkeit der Methoden. Diese besagen aber letztlich nur, dass die Verfahren zu einer Klasse besonders schwerer Probleme gehören. »Eine Garantie, dass nicht doch irgendwann ein mathematisches Rezept gegen die neuen Verfahren auftaucht, gibt es nicht«, räumt Krämer ein.

Experten plädieren daher für eine gewisse Flexibilität in Sachen Verschlüsselung, auch »Krypto-Agilität« genannt. Konkret schwebt Forschern eine Infrastruktur vor, die den schnellen Austausch des Verfahrens erlaubt, sobald es geknackt wurde. »Diese Flexibilität ist mindestens genauso wichtig wie die neuen Verfahren an sich«, sagt Niederhagen. Daher berücksichtigen die Darmstädter Forscher sie in ihren aktuellen Projekten. Software könne beispielsweise so entworfen werden, dass es ihr egal ist, welche Art von digitaler Signatur sie empfängt. So sei es möglich, Verfahren rasch auszutauschen.

Ob all das wirklich notwendig ist, werden die nächsten Jahre und Jahrzehnte zeigen. Zwar arbeiten sowohl staatlich als auch privat geförderte Wissenschaftler mit Hochdruck an der Weiterentwicklung von Quantencomputern. Bisher machen die Rechenmaschinen aber noch viel zu viele Fehler. Ebenso müsste man statt derzeit rund 50 Qubits zehntausende der Recheneinheiten vernetzen, um dem RSA-Verfahren wirklich gefährlich zu werden. Ob das technisch gelingen wird, ist nach wie vor offen.