iX 6/2018
S. 116
Wissen
Kryptografie
Aufmacherbild

Algorithmenwettbewerb zur Post-Quanten-Kryptografie

Gegen die Apokalypse

Derzeit sucht die US-Standardisierungsbehörde NIST in einem Wettbewerb die besten quantencomputersicheren Kryptoverfahren. Diese sollen RSA, Diffie-Hellman und Co. irgendwann ablösen, falls Quantenrechner Realität werden. Die Konkurrenz ist hart – nicht weniger als 69 Verfahren sind am Start.

Es klingt ein bisschen nach Science-Fiction. Quantencomputer sind Rechner, die nach den Prinzipien der Quantenphysik arbeiten – mit Speicherbausteinen, die mehrere Zustände gleichzeitig einnehmen können. Mit speziellen Algorithmen, die nur auf Quantencomputern ausführbar sind, könnte ein solches Gerät im Handumdrehen bestimmte Aufgaben lösen, für die herkömmliche Rechner astronomische Zeiträume benötigen. Vor allem für das Knacken einiger asymmetrischer Kryptoverfahren wären Quantencomputer wie geschaffen.

Praktisch alle in der Praxis eingesetzten Algorithmen dieser Art – insbesondere RSA, Diffie-Hellman, DSA und Verfahren auf Basis elliptischer Kurven – sind betroffen. Sollte es eines Tages leistungsfähige Quantencomputer geben, wären diese Methoden allesamt so gut wie nutzlos. Die Folgen wären katastrophal. Schließlich kommen die genannten Verfahren in Webbrowsern, Betriebssystemen, E-Mail-Verschlüsselungsprogrammen und Geldautomaten zum Einsatz – um nur einige Beispiele zu nennen.

So sieht ein Quantencomputer aus: Im unteren, auf 10 Millikelvin gekühlten Teil befinden sich die Quantenprozessoren in Chiphaltern; darüber, in einem weniger kalten Bereich, die Mikrowellenperipherie und verschiedene Leitungen (Abb. 1). Quelle: E. Leonard Jr., University of Wisconsin – Madison

Jedoch sind die derzeitigen, experimentellen Quantencomputer längst noch nicht stark genug, um RSA und Co. gefährlich zu werden; Abbildung 1 zeigt exemplarisch einen Aufbau. Aber die Entwicklung macht Fortschritte, wie das Interview mit dem Quantencomputer-Experten Prof. Frank Wilhelm-Mauch verdeutlicht (siehe Kasten „Wann können Quantencomputer RSA knacken?“).

Daher gibt es seit einigen Jahren ein großes Interesse an asymmetrischen Kryptoverfahren, die – nach dem momentanen Stand der Forschung – gegen Quantencomputerangriffe resistent sind. Man fasst diese unter dem Begriff Post-Quanten-Kryptografie zusammen. Dazu gehören fast ausschließlich Methoden, die bisher in der Praxis keine Rolle spielen. Je nach Konstruktionsprinzip und naheliegenden Fragestellungen für Angriffe spricht man von Gitter-, multivarianten, Korrekturcode-, Nichtkommutative-Gruppen- und Hash-basierten Verfahren (siehe Kasten „Post-Quanten-Verfahren“). Zu deren Beurteilung sollte man sich zunächst mit der Frage vertraut machen, wann ein Kryptosystem als sicher gelten kann.

Was heißt hier „sicher“?

Eine Antwort auf diese Frage kann man sich zunächst einfach machen. Die RSA-Methoden für Verschlüsselung und Signatur beispielsweise nutzen bekanntlich die Tatsache, dass das Zerlegen (Faktorisieren) eines Primzahlproduktes schwierig ist. Der Diffie-Hellman-Schlüsselaustausch setzt voraus, dass für das Berechnen des diskreten Logarithmus das Gleiche gilt. Man könnte also sagen: Die Sicherheit von RSA basiert auf der Schwierigkeit des Faktorisierens und die Sicherheit von Diffie-Hellman auf der Schwierigkeit, diskrete Logarithmen zu berechnen.

Diese einfachen Aussagen haben jedoch ihre Tücken. So lässt sich beispielsweise das Diffie-Hellman-Verfahren leicht durch einen Man-in-the-Middle-Angriff knacken – ohne dass der Angreifer einen diskreten Logarithmus berechnen muss. Die Kryptologen Shafi Goldwasser und Silvio Micali haben daher nach einer aussagekräftigeren Definition für die Sicherheit von Kryptoverfahren gesucht – und eine solche gefunden. Für ihre Entdeckung erhielten sie im Jahr 2012 mit dem Turing Award den „Nobelpreis der Informatik“.

Kommentieren