Algorithmenwettbewerb zur Post-Quanten-Kryptografie

Gegen die Apokalypse

Claus Diem, Klaus Schmeh

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?“).

Wann können Quantencomputer RSA knacken?

Quantencomputer-Experte Prof. Frank Wilhelm-Mauch von der Universität des Saarlandes (Abb. 2) Quelle: Ehrlich / Universität des Sauerlandes

In einem Interview befragte iX den Experten für Quantencomputer Frank Wilhelm-Mauch zum Thema Leistungsfähigkeit der Systeme. Er ist Professor für Quanten- und Festkörperphysik an der Universität des Saarlandes.

iX: Quantencomputer sind momentan in aller Munde, zu Recht?

Wilhelm-Mauch: Ja, es passiert momentan einiges in diesem Bereich. Quantencomputer waren lange ein Thema für die Grundlagenforschung – tatsächliche Maschinen schienen dagegen selbst 2015 noch Jahrzehnte weg zu sein. Nur in den USA wurde echte Quantenrechner-Entwicklung schon länger gefördert. Der Fortschritt war immerhin so vielversprechend, dass jetzt erste große Firmen wie Google, IBM und Microsoft eingestiegen sind. Außerdem sind Start-ups wie Rigetti aktiv. Einfaches, aber nicht banales Quantencomputing gibt es in der Cloud bereits, und immer mehr Firmen, Organisationen und sogar Privatnutzer probieren aus, was sie mit Quantencomputern erreichen können.

Die EU legt gerade ein Flaggschiffprogramm auf – das größte Forschungsförderungsformat, das sie hat. Damit will man Quantentechnologien zur Anwendungsreife verhelfen.

Die bisher existierenden Quantencomputer (jedenfalls diejenigen, die für die asymmetrische Kryptografie von Bedeutung sind) schaffen es gerade einmal, die Zahl 21 in ih re Faktoren 3 und 7 zu zerlegen. Das klingt nicht besonders beeindruckend.

Faktorisieren ist ein sehr ambitioniertes Langzeitziel, da es unter anderem aktive Fehlerkorrektur erfordert. Naheliegendere Anwendungen gibt es im Moment in der Chemie.

Wann werden Quantencomputer RSA und andere Verfahren knacken können?

Quantencomputer sind immer noch ein junges Forschungsgebiet, das sich jedoch gerade sehr steil entwickelt. Das Faktorisieren ist ein Langzeitziel, das sich im Augenblick schwer abschätzen lässt. Mindestens so wichtig wie die Zahl der Qubits ist deren Zuverlässigkeit, und da kann man durch den Einstieg von Industrielabors einiges erwarten.

Quelle: Ehrlich / Universität des Sauerlandes

Post-Quanten-Verfahren

Gitterverfahren: In einem Gitter in einem vieldimensionalen Raum ist es einfach, einen Punkt in kurzem Abstand zu einem Gitterpunkt zu platzieren. Der umgekehrte Vorgang, das Finden des nächstgelegenen Gitterpunkts, ist dagegen schwierig. NTRU, das wohl bekannteste Post-Quanten-Verfahren, beruht auf dieser Tatsache.

Multivariate Verfahren: Es ist einfach, eine Anzahl von Polynomgleichungen mit mehreren Variablen zu erstellen, für die man die Lösung kennt. Es ist jedoch schwierig, die Lösung eines solchen multivariaten Gleichungssystems zu bestimmen. Dies lässt sich für Signatur- (beispielsweise SFLASH) und Schlüsselaustauschverfahren nutzen.

Korrekturcodeverfahren: Mit geeigneten Methoden (wie Prüfsummen) kann man beliebige Daten so codieren, dass ein Fehler (etwa ein umgekipptes Bit) auffällt. Es ist zwar einfach, einen solchen Fehler absichtlich herbeizuführen. Das Finden eines Fehlers durch eine Analyse der Codierung kann aber bei größeren Datenblöcken schnell sehr aufwendig werden. Dies lässt sich für asymmetrische Kryptoverfahren (zum Beispiel McEliece) ausnutzen.

Nichtkommutative-Gruppen-Verfahren: In bestimmten mathematischen Strukturen (nichtkommutativen Gruppen) ist für die Elemente x und a das Berechnen von x·a·x^-1 = b recht einfach, bei bekanntem a und b ist es jedoch schwierig, ein passendes x zu bestimmen. Auf dieser Basis kann man einen Schlüsselaustausch definieren, der dem von Diffie-Hellman ähnelt. Auch asymmetrische Verschlüsselungsmethoden lassen sich auf diese Art realisieren. Ein bekanntes Beispiel sind Zopfgruppenverfahren, deren mathematische Struktur dem Flechten von Zöpfen nachempfunden ist.

Hash-basierte Verfahren: Mit kryptografischen (also kollisionsfreien) Hashfunktionen lassen sich bestimmte Signaturverfahren definieren. Merkle-Hellman-Signaturen sind die bekanntesten Vertreter.

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“.