Das Zeitalter der Quantencomputer dämmert herauf und verspricht eine enorme Schubkraft für Wissenschaft und Forschung ebenso wie für innovative Geschäftsmodelle. Die Möglichkeiten, die Qbits eröffnen, bringen aber auch Gefahren mit sich. Malte Pollmann, Chief Strategy Officer von Utimaco, erklärt, wie sich die Fähigkeiten von Quantencomputern auf den Bereich Kryptografie auswirken und warum Unternehmen sich schon jetzt krypto-agil aufstellen sollten.
Glaubt man der Google-Forschungsgruppe um den US-amerikanischen Physiker John M. Martinis, so hat der Quantencomputer Sycamore des Suchmaschinenkonzerns Ende 2019 erstmals Quantenüberlegenheit („Quantum Supremacy“) erreicht und ist damit jedem konventionellen Rechner überlegen. Einem Problem, für das ein Supercomputer auf Basis herkömmlicher Bits 10.000 Jahre benötigen würde, werde Sycamore in nur 200 Sekunden Herr, so die Forscher in einem Beitrag im Wissenschaftsjournal Nature [1]. Nicht zuletzt IBM-Experten stellen diese Zahlen in Frage. Doch selbst wenn die (konventionelle) Rechenzeit für das betreffende Problem nur wenige Tage betragen würde – Sycamore bleibt um den Faktor 1.000 schneller. Das ist beachtlich, denn die Technologie steckt noch immer in der Experimentierphase. Es ist nur eine Frage der Zeit, dass marktreife Quantencomputer flächendeckend reale Probleme in Angriff nehmen. Und das betrifft in besonderem Maße auch die Kryptografie.

Was macht Quantencomputer so schnell?

Die unvorstellbaren Geschwindigkeiten, die Quantencomputer zumindest theoretisch erreichen können, sind auf Eigenschaften der Quantenbits (Qbits) zurückzuführen, die mit unserer alltäglichen Wahrnehmung kaum nachvollziehbar sind. Zum einen offenbaren Quantenobjekte ihren Zustand prinzipiell erst bei Beobachtung – im Fall der Qbits bei einer Messung. Anders als die Bits mit dem Zustand „0“ oder „1“, auf denen die bisher bekannte Computer-Technologie basiert, haben Quantenbits also per se keinen festgelegten Zustand. Das bedeutet: Qbits können gleichzeitig 1 und 0 sein – für ihren Zustand lassen sich zunächst nur Wahrscheinlichkeiten angeben. Erst im Augenblick der Messung definiert sich der Zustand eines Qbits.

Etwas greifbarer wird dies durch ein Gedankenexperiment, bekannt als „Schrödingers Katze“: Dem Beobachter ist in diesem Beispiel nicht bekannt, in welchem Zustand sich die Katze in einer Kiste befindet. Erst, wenn er die Kiste öffnet, definiert sich für ihn ihr Zustand als „tot“ oder „lebendig“.

Zum anderen kennt die Quantenwelt das Phänomen der Verschränkung von zwei Teilchen, die in Wechselwirkung miteinander stehen. Wo diese sich dabei befinden, ist egal. Zudem entfällt die Zustandswahrscheinlichkeit für die einzelnen Teilchen – die Verschränkung erlaubt nur noch eine komplexe Wahrscheinlichkeitsbeziehung des Gesamtsystems. Sobald der Zustand von einem der verschränkten Teilchen gemessen wird, zerstört dies ihre Wechselwirkung.

Kryptografische Gewissheiten auf den Kopf gestellt

Was bedeuten die enormen Geschwindigkeiten, die sich mit Quantencomputern erreichen lassen, für die Kryptografie? Kurz gesagt: Sie haben das Potenzial, bisherige Gewissheiten, was die Sicherheit von Passwörtern und kryptografischen Schlüsseln angeht, auf den Kopf zu stellen. Bislang galten in der Kryptologie Schlüssel für sicher, die so komplex waren, dass selbst leistungsstärkste Supercomputer für deren Entschlüsselung per Brute-Force-Methode Jahrtausende benötigen würden. Dabei werden alle möglichen Problemlösungen durchprobiert, bis die richtige Lösung – also das Passwort oder der Schlüssel – „erraten“ ist. Um Passwörter gegen Brute-Force-Angreifer zu schützen, begrenzt man in der Regel die Zahl der möglichen Eingaben.

Quantenrechner lassen allein durch ihre enorme Geschwindigkeit die von konventionellen Computern für solche Problemlösungen benötigten Jahrtausende rasant dahinschmelzen – man bedenke nur den Beschleunigungsfaktor 1.000 im Falle von Sycamore. Hinzukommt, dass mit dem Grover-Algorithmus für Quantencomputer bereits ein Verfahren bekannt ist, das Suchen im Quadrat beschleunigt. Würde ein herkömmlicher Rechner bei einer Suche in einer Datenbank mit n Einträgen n Rechenschritte benötigen, dann verkürzt der Grover-Algorithmus die entsprechende Suche auf einem Quantencomputer auf √n Schritte. Bei einer linearen Suche bräuchte es etwa 2¹²⁸ Rechenschritte, um eine AES-128 Verschlüsselung zu knacken – mit dem Grover-Algorithmus dagegen gerade mal 2⁶⁴. Auch wenn sich die Gefahr eines auf diese Weise geknackten Schlüssels eingrenzen lässt, indem man seine Länge schlicht und einfach verdoppelt, gibt es nur eine Sicherheit: Jede Verschlüsselungsmethode, die auf mathematischen Problemen beruht – so komplex diese auch sein mögen –, ist potenziell durch Quantencomputer gefährdet. Um auch in Zukunft Sicherheit zu gewährleisten, bedarf es also neuer kryptografischer Verfahren als Bollwerk gegen die weiter steigende Rechenleistung und Effizienz von Quantenrechnern.

Die fünf Ansätze der Post-Quanten-Kryptografie

Die Post-Quanten-Kryptografie arbeitet im Wesentlichen mit fünf Ansätzen, die zwar ebenfalls auf mathematischen Problemen basieren, deren Lösung aber nicht nur herkömmliche, sondern auch Quantenrechner vor echte Probleme stellt. Entsprechende Algorithmen sind längst im Einsatz, zumal einige der Verfahren für die Post-Quanten-Kryptografie – etwa Code- und Hash-basierte Schemata – schon seit mehr als 40 Jahren diskutiert und erforscht werden. Als entsprechend sicher gelten diese Verfahren. In den 1980er Jahren wurde dann die sogenannte multivariate Kryptografie entwickelt, bei der beispielsweise quadratische Gleichungssysteme mit mehreren Variablen zum Einsatz kommen. Allerdings sind nur wenige Schemata der multivariaten Kryptografie als sicher zu betrachten, was ein Hemmschuh für die Entwicklung eines effizienten Public-Key-Systems ist. Seit Ende der 1990er Jahre nutzt die gitterbasierte Kryptografie die Komplexität von hochdimensionalen Gittern, in denen es den kürzesten Vektor aufzuspüren gilt. Das jüngste Gebiet der Post-Quanten-Kryptografie ist die isogeniebasierte Kryptografie – eingeführt 2006 und verfeinert 2011: Zwischen elliptischen Kurven im Sinn von strukturerhaltenden Abbildungen sollen zur Entschlüsselung dabei Isogenien gefunden werden.

Erschwert wird die Entwicklung neuer kryptografischer Verfahren für den Alltagsgebrauch insbesondere dadurch, dass diese effizient sein müssen. Verglichen mit klassischer Kryptografie brauchen alle quantensicheren Verfahren mehr Rechenleistung, sollen potenziell aber auch auf schlankeren Geräten mit begrenzten Ressourcen wie Mobiltelefonen zum Einsatz kommen können, ohne diese in ihrer Anwendbarkeit zu sehr einzuschränken.

So sollten Unternehmen sich schon heute vorbereiten

Es ist eine Frage der Zeit, dass Quantencomputer auch jenseits von Forschungslaboren eingesetzt werden – und das nicht immer mit guten Absichten. Auch wenn stellenweise noch viel Forschungsbedarf besteht, sollten Unternehmen im Sinne eines angemessenen Risikomanagements schon jetzt entsprechende Vorbereitungen für die „Post-Quanten-Zeit“ treffen und ihre Systeme krypto-agil aufstellen. Denn eine vollständige Ad-hoc-Umstellung auf quantensichere Algorithmen wird in den wenigsten Fällen möglich sein. Daher empfiehlt es sich bereits heute, auf einen hybriden Betrieb zu setzen, in dem konventionelle und moderne Post-Quanten-Algorithmen nebeneinander laufen. Dieser erleichtert den späteren Umstieg auf quantensichere Kryptografie.

Gleichzeitig sollte die Elektronik von Produkten mit langen Lebenszyklen quantensicher „by design“ entworfen werden – etwa beim Bau von Maschinen für smarte Fabriken oder auch bei der Konstruktion vernetzter Autos. Eine Nutzungsdauer von zehn Jahren und länger setzt im Sinne des Anwenders Quantensicherheit voraus. Das gilt natürlich auch für Signaturzertifikate mit langer Laufzeit. Schon heute können und sollten an vielen Stellen quantensichere Algorithmen genutzt werden. Unternehmen, die herausfinden wollen, wie sich Post-Quanten-Algorithmen auf ihre bestehende Infrastruktur auswirken, können dies anhand von entsprechenden Werkzeugen testen.

Quellen und Referenzen:

[1] https://www.nature.com/articles/s41586-019-1666-5