Knacken Qubits die RSA-Verschlüsselung?

Ende der Kryptografie in Sicht? Bisher hält die Datenverschlüsselung der Rechenpower von Quantencomputern stand – doch das könnte sich bald ändern. US-Forscher haben jetzt eine Methode entwickelt, die das quantengestützte Knacken der gängigen RSA-Verschlüsselung schneller und effizienter macht. Statt Millionen von Qubits und fehlerfreien Quantenoperationen wie vom Shor-Algorithmus gefordert, reichen deutlich kleinere, weniger perfekte Quantencomputer. Droht das baldige Ende der RSA-Verschlüsselung?

Ob E-Mails, Online-Shopping oder andere digitale Kommunikation: Die meisten Daten werden heute verschlüsselt übermittelt. Gängiges Verfahren ist dabei die RSA-Kryptografie, bei der große, durch die Multiplikation von Primzahlen erzeugte Zahlen als Schlüssel dienen. Denn durch welche Faktoren diese Zahl erzeugt wurde, lässt sich wegen der großen Auswahl an Möglichkeiten nur mit enormem Rechenaufwand ermitteln – für klassische Computer ist dies nahezu unmöglich.

Der Shor-Algorithmus und seine Schwächen

Aber nicht für Quantencomputer: Weil deren Qubits durch die quantenphysikalische Überlagerung unzählige potenzielle Lösungen gleichzeitig prüfen können, ist der RSA-Verschlüsselung für sie nicht mehr unknackbar – zumindest in der Theorie. Einen Algorithmus, mit dem dies gelingen könnte, hat der US-Mathematiker Peter Shor bereits 1994 veröffentlicht. „Das war ein Wendepunkt. Aber 1994 wusste noch niemand, wie man einen Quantencomputer der nötigen Größe baut“, erklärt Vinod Vaikuntanathan vom Massachusetts Institute of Technology (MIT).

Das Problem: Der Shor-Algorithmus ist ineffizient. Um die zurzeit gängige 2048-Bit-RSA-Verschlüsselung mit ihm zu knacken, bräuchte man rund 20 Millionen fehlerfrei arbeitende Qubits – was wegen der Störanfälligkeit der Qubits kaum machbar ist. „Einige Leute denke sogar, dass es nie möglich sein wird, einen ausreichend großen Quantencomputer zu entwickeln“, sagt Vaikuntanathan. Tatsächlich umfassen die meisten aktuellen Quantencomputer nur wenige Dutzend Qubits, der bisher größte Quantenrechner hat gut 1.100 Qubits.

Neue Methode ist schneller und sparsamer

Doch es gibt noch eine weitere Möglichkeit – und die haben nun Vaikuntanathan und sein Kollege Seyoon Ragavan genutzt: Sie haben eine Verbesserung des Shor-Algorithmus entwickelt, die diesen weit schneller und sparsamer macht. Ausgangspunkt dafür ist ein Algorithmus, den Oded Regev von der New York University vor knapp einem Jahr entwickelt hat. Dieser kann das Krypto-Codeknacken gegenüber Shors Algorithmus zwar beschleunigen, benötigt aber noch mehr Quantenbits als Speicher.

An diesem Punkt setzen nun die beiden MIT-Forscher an: Sie haben nun eine Lösung entwickelt, die so schnell ist wie Regevs Ansatz, aber weniger Qubits benötigt. Ihr Quanten-Algorithmus beinhaltet zudem eine Methode, die die Fehlerquote verringert und die Quantenberechnungen so robuster gegenüber Störeinflüssen macht. „Unsere Arbeit könnte uns damit einen Schritt näher an eine praktische Umsetzung bringen“, sagt Vaikuntanathan.

Pingpong im Speicherregister

Konkret umfasst die neue Methode zwei Ansätze. Zum einen umgehen die beiden MIT-Forscher die Notwendigkeit, mit Quadrierungen arbeiten zu müssen. Denn Rechnungen mit der Potenz von zwei sind nicht direkt reversibel und daher aufwendig und speicherintensiv. „Wir vermeiden dies durch die Fibonacci-Potenzierung. Diese Methode kommt ohne modulares Quadrieren aus und nutzt stattdessen nur die modulare Multiplikation“, erklären Vaikuntanathan und Ragavan. Durch diese Spielart der mathematischen Matrixpotenzierung lassen sich Potenzrechnungen schneller und effizienter abwickeln.

Im Fall des Codeknackens per Quantencomputer bedeutet dies: Für jeden Exponenten, der beim Faktorisieren des kryptografischen Codes berechnet werden muss, benötigt der neue Algorithmus nur zwei Quanten-Speichereinheiten. „Das ist wie bei einer Art Pingpong-Spiel: Wir beginnen mit einer Zahl und springen dann beim Multiplizieren zwischen den beiden Quantenspeicherregistern hin und her“, erklärt Vaikuntanathan. „Dadurch nutzt unser Algorithmus bei 2048 Bit mindestens 13-mal weniger Qubits als der von Regev.“

Fehler werden ausgesiebt

Die zweite Verbesserung betrifft die Fehlerkorrektur: Für die Quantenalgorithmen von Shor und Regev muss jede Quantenoperation quasi fehlerfrei ablaufen – eine praktisch in absehbarer Zukunft nicht umsetzbare Forderung. Zwar haben Physiker bereits einige Methoden entwickelt, um die Fehlerquote von Quantenrechnern zu senken. Selbst bei Rekordmodellen liegt die Zuverlässigkeit aber bisher nur bei rund 35 Prozent.

Die beiden MIT-Forscher umgehen dies, indem sie potenziell defekte Ausgaben der Qubit-Schaltkreise anhand bestimmter Merkmale identifizieren. „Darauf aufbauend entwickeln wir eine Filter-Prozedur, durch die wir diese korrumpierten Einheiten detektieren und herausfiltern“, erklären Vaikuntanathan und Ragavan. „Dadurch erhalten wir eine Sammlung intakter Einheiten, die dann in die klassische Nachbearbeitung nach Regevs Algorithmus eingespeist werden kann.“

Zwei Hürden der Quantenfaktorisierung überwunden

Zusammen ist es dem Team damit gelungen, zwei große Hürden des Kryptografie-Brechens mittels Quantencomputer zu knacken. „Die große Frage ist allerdings, ob uns dies näher an das Knacken der RSA-Verschlüsselung bringt“, sagt Ragavan. „Bisher ist das noch nicht ganz klar, denn unsere Verbesserungen greifen erst bei größeren Zahlen als 2048 Bit.“ Ob der Algorithmus sich noch weiter optimieren lässt, um auch die gängigen 2048-Bit-Zahlenschlüssel zu knacken, muss sich daher erst noch zeigen.

Dennoch rückt damit das Ende der RSA-Verschlüsselung ein kleines Stück näher, meinst auch Regev: „Die beiden Forscher überwinden die beiden wichtigsten Flaschenhälse der früheren Algorithmen für die Quantenfaktorisierung“, kommentiert er. „Auch wenn ihre Arbeit noch nicht unmittelbar praktisch umsetzbar ist, bringt sie die Quantenfaktorisierung der Realität näher.“ (2024 International Cryptology Conference; Preprint, doi: 10.48550/arXiv.2310.00899)

Quelle: Massachusetts Institute of Technology (MIT)