Sichere Kryptografie im Quantenzeitalter?

Seit Ende letzten Jahres beansprucht Google für sich, mit seinem Quantencomputer Sycamore die sogenannte Quantum Supremacy erreicht zu haben. Das will heißen, dass dieser Rechner allen konventionellen Maschinen überlegen ist. In einem Nature Paper behaupteten die Forscher, dass ihre Entwicklung ein Problem in 200 Sekunden lösen könne, für das ein herkömmlicher Supercomputer 10.000 Jahre benötigen würde. Zwar wurden diese Zahlen von anderer Seite in Zweifel gezogen, doch eines scheint sicher: Wir stehen am Anfang einer neuen Ära des Computing.

Qbits: unheimlich schnell

Ein Bit, Grundlage der heutigen Computer-Technologie, kann entweder den Zustand 1 oder 0 haben und behält diesen so lange, bis er aktiv geändert wird. Bei Quantenbits verhält sich das jedoch anders. Quantenobjekte haben die Eigenschaft, dass sie ihren Zustand erst bei Beobachtung offenbaren. Ein anschauliches Beispiel dafür ist das Gedankenexperiment, das als Schrödingers Katze bekannt wurde. In diesem Beispiel weiß der Beobachter nicht, ob das Tier noch lebt, bis er die Kiste öffnet, in der sich die Katze befindet. Erst dadurch wird ihr Zustand definiert.

Ähnlich verhält es sich auch mit Quantenbits: Sie haben keinen festgelegten Zustand, sondern nehmen ihn erst dann an, wenn er abgefragt wird. Solange können diese Bits prinzipiell 1 und 0 „gleichzeitig“ sein. Ohne eine Messung lassen sich für ihren Zustand nur Wahrscheinlichkeiten angeben.

Ein weiteres Phänomen in der Quantenwelt ist die Verschränkung von zwei Teilchen. Diese können dabei völlig unabhängig von ihrem Ort miteinander wechselwirken. Im Zuge dieser Verschränkung gibt es auch keine Zustandswahrscheinlichkeiten für die einzelnen Teilchen mehr, sondern nur noch eine komplexe Wahrscheinlichkeitsbeziehung für das Gesamtsystem. Nimmt man als Beispiel Photonen, also Lichtteilchen, könnte eine Wahrscheinlichkeitsfunktion aussagen, dass die Polarisation der beiden Teilchen senkrecht zueinander stehen muss. Ob Teilchen A vertikal polarisiert ist und Teilchen B horizontal oder ob es sich genau andersherum verhält, lässt sich erst durch eine Messung sagen. Wird nun beispielsweise A als vertikal polarisiert gemessen, so ist B dann automatisch und sofort horizontal – vollkommen unabhängig davon, wie weit die Teilchen auseinander sind. Außerdem wird bei dieser Messung die Verschränkung zerstört. Diese Eigenschaften der Quantenbits bilden die Grundlage für die enormen Geschwindigkeiten, die mit Quantencomputern (theoretisch) erreicht werden können.

Brute Force der nächsten Generation?

Die Brute-Force-Methode beruht darauf, alle möglichen Lösungen für ein Problem durchzuprobieren, bis man zur korrekten Lösung gelangt – etwa durch ein Passwort oder einen kryptografischen Schlüssel. Bei Passwörtern geht man gegen dieses „Erraten“ vor, indem die Versuche der Eingabe begrenzt werden. In der Kryptologie wird ein entsprechender Schutz dadurch erreicht, dass Schlüssel entsprechend komplex werden. Wird ein Schlüssel so gewählt, dass es selbst mit den besten Supercomputern Jahrtausende dauern würde, ihn zu knacken, kann er als sicher gelten. Quantencomputer bergen nun aber das Potenzial, diese Gewissheit auf den Kopf zu stellen.

Mit dem Grover-Algorithmus für Quantencomputer ist ein Verfahren bekannt, das Suchen quadratisch beschleunigt. Sind bei einer linearen Suche in einer Datenbank mit n Einträgen n Rechenschritte notwendig, reduziert sich diese Zahl durch den Grover-Algorithmus auf Rechenschritte. Um eine AES-128-Verschlüsselung zu knacken, wären mit linearer Suche 2.128 Rechenschritte notwendig, mit dem Grover-Algorithmus nur noch 264 Rechenschritte. Dem lässt sich relativ einfach dadurch begegnen, indem man die Länge des Schlüssels verdoppelt. Dennoch stellen Quantencomputer eine Gefahr für Verschlüsselungsmethoden, die auf komplexen mathematischen Problemen beruhen, dar. Schließlich erlauben nicht nur spezielle Algorithmen eine Reduktion der Rechenoperation, überlegene Quantenrechner können auch einfach viel mehr davon in einer gegebenen Zeit ausführen (vgl. Faktor 1.000 bei Sycamore).

Lösung: Post-Quanten-Kryptografie

Aktuell werden fünf allgemeine Arten von Post-Quanten-Kryptografie in der Fachwelt diskutiert und darauf basierende Algorithmen befinden sich auch bereits im Einsatz. Jeder dieser Ansätze basiert auf verschiedenen mathematischen Problemen, die sowohl auf herkömmlichen als auch auf Quantencomputern schwer zu lösen sind. Sie unterscheiden sich hinsichtlich der Effizienz, der benötigten Rechenleistung und ihrer Stärke. Die Effizienz der kryptografischen Verfahren ist deshalb wichtig, weil dadurch ihre Verwendbarkeit auf Geräten mit beschränkten Ressourcen (z. B. Mobiltelefone) eingeschränkt werden kann. Generell hat Quantensicherheit immer ihren Preis, denn alle Verfahren benötigen in der Regel mehr Ressourcen als klassische Kryptografie.

Dies ist ein Artikel aus unserer Print-Ausgabe 12/2020. Bestellen Sie ein kostenfreies Probe-Abo.

Einige dieser Verfahren für die Post-Quanten-Kryptografie werden bereits seit vielen Jahren diskutiert und erforscht, darunter Code- und Hash-basierte Schemata. Da diese beiden Verfahren bereits Ende der 1970er-Jahre eingeführt wurden, sind sie heute gut erforscht und gelten als sicher. Multivariate Kryptografie wurde während der 1980er entwickelt und das zugrundeliegende Problem gilt ebenfalls als hinlänglich bekannt. Ein effizientes Public-Key-System auf dieser ­Basis aufzubauen, gilt allerdings als eine große Herausforderung, da nur wenige Schemata als sicher gelten können. Ende der 1990er-Jahre wurde gitterbasierte Kryptografie eingeführt, die auf dem Problem des kürzesten Vektors in hochdimensionalen Gittern basiert. Als fünftes und jüngstes Verfahren existiert die auf Isogenie elliptischer Kurven basierende Kryptografie, die zuerst 2006 eingeführt und 2011 verfeinert wurde.

Zeit zu handeln

Wie lange es nun genau dauern wird, bis Quantencomputer flächendeckende Verbreitung finden werden, ist schwer zu sagen – doch kommen werden sie. Um auf die Zukunft vorbereitet zu sein, sollten Unternehmen sich jetzt krypto-agil aufstellen – das will heißen, dass sie ihre Systeme so vorbereiten, dass diese einen Wechsel zu quantensicheren Kryptografie unterstützen sowie auch einen hybriden Betrieb. Da die Umstellung ihre Zeit brauchen wird, ist es wichtig, dass eine Zeit lang moderne Post-Quanten-Algorithmen und konventionelle Algorithmen nebeneinander laufen können. Zudem gilt es, mitunter lange Produktlebenszyklen zu beachten: Wird heute ein vernetztes Auto konstruiert, das vielleicht erst in einigen Jahren auf den Markt kommt und dann noch eine Nutzungsdauer von über zehn Jahren hat, muss seine Elektronik schon heute quantensicher entworfen werden. Die gute Nachricht für Unternehmen ist: Es gibt jetzt schon Möglichkeiten und Werkzeuge, um die Auswirkungen von Post-Quanten-Algorithmen auf die eigene Infrastruktur zu testen und quantensichere Algorithmen im Live-Betrieb einzusetzen.

Bildquelle: Getty Images / iStock / Getty Images Plus