Post-Quanten-Portfolio
Der lange Weg zu Quantencomputer-resistenten Kryptosystemen
Leistungsstarke Quantencomputer könnten gängige Verschlüsselungsalgorithmen knacken. Noch gibt es wohl keine solchen Rechner, aber „post quantum“-Kryptosysteme müssen her, bevor es so weit ist. Kandidaten gibt es reichlich, aber viele sind nicht so sicher, wie sie scheinen.
Computer können Daten so verschlüsseln und signieren, dass andere Computer die Verschlüsselung nicht knacken und die Signatur nicht fälschen können. Auf diesem Grundsatz basiert die Sicherheit fast aller moderner IT-Systeme. Auch ein Handy kann seine Kommunikation leicht so schützen, dass selbst Supercomputer utopisch lange bräuchten, um die Verschlüsselung zu brechen.
Doch mit dem Quantencomputer betritt ein neuer, wesentlich stärkerer Gegner den Ring. Können herkömmliche Computer ihre Kommunikation so schützen, dass auch ein Quantencomputer sich daran die Zähne ausbeißt? Gebräuchliche Verfahren reichen dafür jedenfalls nicht aus: Schon 1994 – bevor es erste Quantencomputer tatsächlich gab – entwickelte der Mathematiker Peter W. Shor einen Algorithmus, mit dem Quantencomputer große Zahlen faktorisieren und diskrete Logarithmen berechnen können – und zwar viel schneller als klassische Rechner.
Was nach einer Hilfe für Nischenprobleme klingt, ist in Wahrheit ein fundamentaler Angriff auf aktuelle asymmetrische Kryptosysteme: Der Schutz von weit verbreiteten Verfahren wie RSA, ECDSA oder Diffie-Hellman beruht genau auf diesen Berechnungen. Sie sind in die eine Richtung leicht zu bewältigen (Multiplikation oder Potenzierung) und in der anderen Richtung sehr schwierig (Faktorisierung oder diskreter Logarithmus). Asymmetrische Kryptografie ist auf solche „Einwegfunktionen“ angewiesen [1]. Shors Algorithmus erleichtert den Rückweg und bricht damit verbreitete Verfahren irreparabel.
Suche
Es müssen also Alternativen entwickelt werden, die auch gegen Angriffe mit Quantencomputern bestehen. Das ist nicht aussichtslos: Quantencomputer sind keine Allzwecklösung, die einfach alles besser und schneller berechnet. Shors Algorithmus arbeitet mit speziellen Eigenschaften von Faktorisierung und diskretem Logarithmus, die Quantencomputer ausnutzen können. Bei vielen anderen mathematischen Problemen bieten sie aber keine Vorteile gegenüber klassischen Rechnern.
Quantencomputer-sichere asymmetrische Verschlüsselung muss also einerseits auch auf klassischen Rechnern leicht zu berechnen sein. Andererseits muss das zugrundeliegende mathematische Problem aber schwer genug sein, sodass sowohl Quantencomputer als auch klassische Computer keine Chance haben.