Verschlüsselung: RSA zerstört? Experten zweifeln

Eine Gruppe chinesischer Wissenschaftler hat zum Jahreswechsel einen neuen Faktorisierungsalgorithmus vorgestellt, der viel schneller als bisher angenommen das Ende der Verschlüsselung RSA einläuten könnte. In ihrem Paper "Factoring integers with sublinear resources on a superconducting quantum processor" behaupten die Autoren, dass mit ihrem Algorithmus nur 372 Qubits notwendig sind, um die 2048-Bit-Variante von RSA zu knacken.

Der Algorithmus sei sehr viel schneller als der von Shor 1994 entwickelte. Auf den ersten Blick sieht das Paper bedrohlich aus, die Mathematik anspruchsvoll und überzeugend. Experten glauben dem Paper aber nicht und das hat mehrere Gründe.

Große Töne

Der neue Algorithmus fußt auf zwei Studien des renommierten deutschen Kryptologen Claus Peter Schnorr. Eines davon ist das 2021 erschienene Paper, in dem er behauptet RSA gebrochen zu haben ("This destroyes the RSA cryptosystem"). Der von ihm vorgestellte Algorithmus funktioniert zwar bei kleinen RSA-Modulen, aber bei größeren war er langsamer als herkömmliche Verfahren. Die Kinderkrankheit haben nun die chinesischen Wissenschaftler angeblich ausgemerzt, indem sie Verbesserungen vornahmen und auf einen Quantencomputer zurückgriffen.

In ihren Versuchen verwendeten sie drei, fünf und zehn supraleitende Qubits, um die Zahlen 1961, 48567227 und 261980999226229 in ihre Primfaktoren aufzulösen. Laut dem Paper sei die 48 Bit große Zahl damit die größte, die jemals von einem Quantencomputer zerlegt wurde. Die Autoren stellen zudem eine steile These auf: Der neue Algorithmus könne mit nur 372 Qubits RSA-Module der Größe 2048 Bit knacken. Das wäre der heute verwendete Standard und Quantencomputer dieser Größe gibt es schon, zum Beispiel bei IBM.

Laute Zweifel

Der Sicherheitsexperte Bruce Schneier zweifelt daran, ob das neue Verfahren tatsächlich RSA bezwingen kann. Viel strenger ins Gericht geht Scott Aaronson, Experte in Sachen Quantencomputer: Das Paper sei eins der irreführendsten, die er je gesehen hat und würde Behauptungen aufstellen, die es keineswegs beweisen kann. Auch der berühmte Kryptograf Peter Shor meldete sich und verwies in einem Tweet auf eine Erklärung des Wissenschaftlers Craig Gidney:

Am einfachsten wäre es wohl, wenn die Leute von IBM den Algorithmus auf ihrem Quantencomputer ausprobieren und versuchen, die Primfaktoren für das 2048-Bit-Modul aus der RSA Factoring Challenge zu berechnen. Da das wahrscheinlich nicht passieren wird, kann man RSA wohl vorerst weiter nutzen – zumindest bis es leistungsstarke Quantencomputer gibt, die den Shor-Algorithmus handhaben können.

(wid)