Stürzen Quantencomputer die RSA-Verschlüsselung im Jahr 2023?

In den letzten Tagen des Jahres 2022 wurde die IT-Community durch eine Studie einer Gruppe chinesischer Wissenschaftler in Aufregung versetzt. Darin wird behauptet, dass es in naher Zukunft möglich sein wird, den RSA-Krypto-Algorithmus mit einer Schlüssellänge von 2048 Bit – der für das Funktionieren von Internetprotokollen von grundlegender Bedeutung ist – durch eine geschickte Kombination von klassischem und Quanten-Computing zu knacken. Doch wie real ist diese Bedrohung? Wir finden es heraus.

Quanten-Grundlagen

Die theoretische Fähigkeit eines Quantencomputers, eine ultraschnelle Faktorisierung riesiger ganzer Zahlen durchzuführen und damit Schlüssel für eine Reihe asymmetrischer Kryptoalgorithmen – einschließlich der RSA-Verschlüsselung – zu finden, ist schon lange bekannt. In unserem Blogartikel erklären wir ausführlich, was ein Quantencomputer ist, wie er funktioniert und warum seine Entwicklung und Umsetzung so schwierig ist. Bislang sind sich alle Experten einig, dass ein Quantencomputer, der groß genug ist, um RSA zu knacken, vermutlich erst in einigen Jahrzehnten gebaut werden kann. Um eine ganze 2048-Bit-Zahl zu faktorisieren, die normalerweise als RSA-Schlüssel verwendet wird, muss der Shor-Algorithmus mit Millionen von Qubits (Quantenbits) auf einem Quantencomputer ausgeführt werden. Wir sprechen hier keineswegs von einem kurzfristig möglichen Szenario, denn die besten Quantencomputer arbeiten heute mit 300-400 Qubits – und das nach jahrzehntelanger Forschung.

Dennoch wurde über dieses Zukunftsproblem bereits aktiv nachgedacht, und Sicherheitsexperten fordern schon jetzt die Einführung von Post-Quantum-Kryptografie, d. h. von Algorithmen, die gegen das Hacking via Quantencomputer immun sind. Man ging ursprünglich von einem Jahrzehnt oder mehr für einen reibungslosen Übergang aus, daher kam die Nachricht, dass RSA-2048 bereits im Jahr 2023 fällig sein könnte, sehr überraschend.

Nachrichten aus China

Chinesische Forscher konnten einen 48-Bit-Schlüssel auf einem 10-Qubit-Quantencomputer faktorisieren und berechneten dann, dass es möglich ist, den Algorithmus für die Verwendung mit 2048-Bit-Schlüsseln mit einem Quantencomputer mit nur 372 Qubits zu skalieren. Solche Computer gibt es bereits heute, z. B. bei IBM, wodurch die Notwendigkeit, Kryptosysteme eines Tages im gesamten Internet zu ersetzen, plötzlich nicht mehr so weit in der Zukunft liegt. Ein Durchbruch wurde durch die Kombination des Schnorr-Algorithmus (nicht zu verwechseln mit dem oben erwähnten Shor-Algorithmus) mit einem zusätzlichen Schritt des Quantenapproximierungsalgorithmus (QAOA) versprochen.

Das vorgeschlagene Schema des hybriden Faktorisierungsalgorithmus

Schnorrs Algorithmus wird für die angeblich effizientere Faktorisierung ganzer Zahlen unter Einsatz der klassischen Berechnung verwendet. Die chinesische Gruppe schlägt vor, die Quantenoptimierung in der rechenintensivsten Phase ihrer Arbeit anzuwenden.

Offene Fragen

Schnorrs Algorithmus stieß in der Mathematik-Community auf Skepsis. Die Aussage des Autors in der Beschreibung der Studie, dass „dies das RSA-Kryptosystem brechen würde“, wurde hinterfragt und als nicht realisierbar eingestuft. Der berühmte Kryptograf Bruce Schneier sagte zum Beispiel: „Das funktioniert gut für kleine Module, etwa so groß wie die von der chinesischen Gruppe getesteten, aber nicht für große.“ Und niemand hat bewiesen, dass dieser Algorithmus wirklich skalierbar ist.

Die Anwendung der Quantenoptimierung auf den „schwierigsten“ Teil des Algorithmus klingt nach einer guten Idee, aber Quanten-Computing-Experten haben Zweifel daran, dass die QAOA-Optimierung bei der Lösung dieses Rechenproblems effektiv sein kann. Der Einsatz eines Quantencomputers ist zwar möglich, wird aber wahrscheinlich nicht zu einer Zeitersparnis führen. Die Autoren erwähnen dies selbst in der Schlussfolgerung ihrer Studie:

Es sollte darauf hingewiesen werden, dass die Quantenbeschleunigung des Algorithmus aufgrund der unklaren Konvergenz von QAOA nicht klar ist.

…

Außerdem ist die Quantenbeschleunigung unbekannt, und der Weg zum quantenmäßigen RSA-Bruch lang.

Selbst wenn man diesen hybriden Algorithmus auf einem klassischen Quantensystem implementiert, dauert das Erraten von RSA-Schlüsseln genauso lange wie mit einem normalen Computer.

Neben der Anzahl der Qubits gibt es weitere wichtige Parameter von Quantencomputern, wie Rausch- und Fehlerpegel sowie die Anzahl der Gatter. Gemessen an der Gesamtheit der erforderlichen Parameter ist es unwahrscheinlich, dass selbst die vielversprechendsten Computer von 2023-2024 chinesische Algorithmen im erforderlichen Umfang ausführen können.

Praktische Erkenntnisse

Während sich die Krypto-Revolution wieder einmal verzögert, weist der Hype um diese Studie auf zwei Sicherheitsbedenken hin. Erstens sollten neue algebraische Ansätze (wie der oben erwähnte Schnorr-Algorithmus) bei der Auswahl eines quantensicheren Algorithmus unter den vielen Vorschlägen für einen „Post-Quanten-Standard“ sorgfältig geprüft werden. Zweitens müssen wir dem Übergangsprojekt zur Post-Quanten-Kryptographie unbedingt Priorität einräumen. Es scheint immer nur ein nicht dringendes Problem zu sein, bis es zu spät ist …