Shors Algorithmus: Ressourcenbedarf für RSA-2048-Faktorisierung sank in unter einem Jahr um eine Größenordnung

Die Verschlüsselung, die die moderne digitale Infrastruktur schützt, bricht nicht in dem Moment zusammen, in dem ein Quantencomputer gebaut wird. Sie bricht in dem Moment zusammen, in dem Angreifer ausreichend Quantenrechenkapazität erlangen, um bereits gesammelten verschlüsselten Daten zu entschlüsseln. Diese zeitliche Umkehrung — die Bedrohung kommt vor der Maschine — definiert die eigentliche Struktur des Q-Day-Problems und erklärt, warum die heute gemessene Vorbereitungslücke direkt in einen in einigen Jahren messbaren Sicherheitsbruch mündet.

Der gefährdete Mechanismus ist nicht obskur. RSA-Verschlüsselung, der dominante Standard für Public-Key-Kryptographie, basiert auf einer einzigen mathematischen Asymmetrie: Zwei große Primzahlen zu multiplizieren ist rechentechnisch trivial, aber die Primfaktoren aus ihrem Produkt zurückzugewinnen skaliert in der Schwierigkeit so steil, dass kein klassischer Computer die Operation für Schlüsselgrößen von 2048 Bit oder mehr innerhalb eines praktischen Zeitrahmens umkehren kann. Der TLS-Handshake, der den Webverkehr sichert, die Zertifizierungsstellen, die Identitäten authentifizieren, die digitalen Signaturen, die Finanztransaktionen validieren: Die gesamte Architektur vertrauenswürdiger digitaler Kommunikation ruht auf dieser Asymmetrie.

Shors Algorithmus, 1994 formalisiert, bewies, dass Quantenrechnen diese Asymmetrie vollständig auflöst. Durch Ausnutzung von Quantensuperposition und Quanten-Fourier-Transformationen, um die Periode einer modularen arithmetischen Funktion zu finden, die das Faktorisierungsproblem kodiert, könnte ein hinreichend großer Quantencomputer private RSA-Schlüssel in Stunden statt in den Milliarden von Jahren zurückgewinnen, die eine klassische Maschine benötigen würde. Der Algorithmus ist seit drei Jahrzehnten bekannt. Was sich im vergangenen Jahr verändert hat, ist die Schätzung der für seine Ausführung benötigten Ressourcen.

Die Hardwareanforderungen für einen kryptographisch relevanten Quantencomputer waren bis vor Kurzem so enorm, dass sie als praktische Barriere fungierten. Frühe Schätzungen gaben den benötigten Qubit-Zähler für die Faktorisierung von RSA-2048 mit etwa einer Milliarde an. Bis 2021 hatten Gidney und Ekerå diese Schätzung auf etwa zwanzig Millionen Qubits, die acht Stunden betrieben werden, reduziert. Dann, in weniger als zwölf Monaten zwischen 2024 und 2025, ließen drei algorithmische Entwicklungen die Schätzung um eine weitere Größenordnung einbrechen.

Die erste war eine Umstrukturierung der Art, wie modulare Exponentiation — die zentrale Rechenoperation in Shors Algorithmus — ausgeführt wird. Der klassische Ansatz erforderte Quantenregister, die groß genug waren, um 2048-Bit-Ganzzahlen gleichzeitig zu halten. Die von Chevignard, Fouque und Schrottenloher entwickelte approximative modulare Arithmetik ersetzte dies durch einen segmentierten Ansatz, der die Exponentiation in Stücken mit viel kleineren Registern berechnet und kontrollierte Fehler toleriert, die später korrigiert werden können. Der Quantencomputer muss das gesamte Problem nicht mehr gleichzeitig im Speicher halten. Der zweite Fortschritt adressierte den dominanten Kostenengpass im fehlertoleranten Quantenrechnen: die Erzeugung der speziellen Quantenressourcenzustände, die für nicht-fehlerkorrigierbare Gatteroperationen benötigt werden. Magic State Cultivation, bei Google Quantum AI entwickelt, lässt hochgetreue Zustände aus qualitativ minderwertigeren mit drastisch reduziertem Overhead wachsen. Der dritte Fortschritt, in einem Artikel von Craig Gidney im Jahr 2025 synthetisiert, kombinierte beide Techniken und reduzierte die Gesamtzahl der erforderlichen Toffoli-Gatteroperationen von etwa zwei Billionen auf etwa 6,5 Milliarden — eine mehr als hundertfache Verbesserung der Recheneffizienz.

Das kombinierte Ergebnis: Die Faktorisierung von RSA-2048 erscheint nun mit etwa einer Million physischer Qubits, die etwa eine Woche betrieben werden, technisch machbar. Die Hardwarelücke zwischen diesem Bedarf und bestehenden Systemen bleibt real, aber die Kompressionstrajektorie hat sich qualitativ verändert. Die Reduktion von einer Milliarde auf zwanzig Millionen Qubits dauerte zwölf Jahre; die Reduktion von zwanzig Millionen auf unter eine Million dauerte weniger als ein Jahr. Diese Beschleunigung ist das analytisch bedeutsame Signal.

Parallele Hardwareentwicklungen bestärken diese Trajektorie. Googles Willow-Chip, Ende 2024 demonstriert, lieferte die erste experimentelle Bestätigung, dass Quantenfehlerkorrektur Rauschen unter den Schwellenwert des Oberflächencodes unterdrücken kann — den physischen Beweis, dass die Rauschvoraussetzungen, die allen Ressourcenschätzungen zugrunde liegen, physisch erreichbar sind. IBMs veröffentlichte Roadmap projiziert den ersten großmaßstäblichen fehlertoleranten Quantencomputer mit etwa 200 logischen Qubits für 2029. Mehrere unabhängige Plattformen haben Zwei-Qubit-Gatertreue von 99,9% oder darüber demonstriert. Die Lücke zwischen theoretischem Ressourcenbedarf und demonstrierter Hardwarekapazität hat sich von mehreren Größenordnungen auf etwas nahe einer einzigen komprimiert.

Diese Kompression verleiht einer Bedrohung, die bisher als bequem fern behandelt wurde, materielle Dringlichkeit: jetzt sammeln, später entschlüsseln. Nationalstaatliche und hochentwickelte nichtstaatliche Akteure, die seit Jahren verschlüsselten Netzwerkverkehr sammeln, besitzen Chiffriertext, der lesbar wird, sobald ein kryptographisch relevanter Quantencomputer existiert. Der angemessene Zeitrahmen zur Bewertung des Q-Day-Risikos ist nicht, wann Quantencomputer gebaut werden, sondern wie lange die heute verschlüsselten Daten vertraulich bleiben müssen.

Die kryptographische Antwort auf diese Bedrohung hat einen Namen, einen Standardsatz und einen Compliance-Zeitplan. Post-Quanten-Kryptographie ersetzt die dem RSA und der Elliptic-Curve-Kryptographie zugrunde liegenden Integer-Faktorisierungs- und diskreten Logarithmusprobleme durch mathematische Strukturen, die als resistent gegen klassische und quantische Angriffe gleichermaßen gelten. Die von globalen Normungsgremien übernommene Hauptfamilie ist die gitterbasierte Kryptographie, die ihre Sicherheit auf der Schwierigkeit des Kürzesten-Vektor-Problems und verwandter geometrischer Herausforderungen in hochdimensionalen Räumen begründet. Im August 2024 finalisierte NIST drei Post-Quanten-Kryptographiestandards. Im März 2025 wurde ein fünfter Algorithmus, HQC, als codebasierte Alternative zu ML-KEM ausgewählt.

Die Existenz von Standards löst das Migrationsproblem nicht. Sie beginnt es. Kryptographische Übergänge dieser Größenordnung haben historisch fünfzehn bis zwanzig Jahre für eine vollständige Infrastrukturdurchdringung benötigt — und diese Migration ist strukturell komplexer als jeder Vorläufer. Die Public-Key-Infrastruktur muss auf jeder Schicht neu konzipiert werden. Hardware-Sicherheitsmodule, die Schlüssel speichern und verwalten, müssen ersetzt oder aufgerüstet werden; Zertifizierungsstellen müssen neue Credential-Hierarchien ausstellen; TLS-Implementierungen auf Milliarden von Endpunkten müssen aktualisiert werden; Protokolle, die in eingebetteten Systemen, industrieller Steuerungsinfrastruktur und langlebigen Finanzsystemen eingebettet sind, müssen auditiert und ersetzt werden. Vielen dieser Systeme fehlt die kryptographische Agilität, die eine direkte Migration möglich machen würde.

Für den deutschen Industriestandort, dessen Stärke in Präzisionsengineering, eingebetteten Systemen und langlebiger Fertigungsinfrastruktur liegt, hat diese Migration eine besondere Dimension. Industriesteuerungssysteme und Maschinenparks mit Lebenszyklen von zwanzig und mehr Jahren tragen Verschlüsselung, die weder für Agilität noch für nachträgliche Aktualisierung ausgelegt wurde. Der regulatorische Rahmen hat mit einem verdichteten Zeitplan reagiert, der die Dringlichkeit der Hardwaretrajektorie widerspiegelt. Die CNSA 2.0 der NSA schreibt vor, dass alle neuen nationalen Sicherheitssysteme bis Januar 2027 quantensicher sein müssen. NISTs Abschaffungsplan sieht vor, quantenanfällige Algorithmen nach 2035 aus genehmigten Standards zu entfernen. Die NIS-Kooperationsgruppe der Europäischen Union veröffentlichte 2025 eine koordinierte Implementierungsroadmap. Das Quantensicherheits-Bereitschafts-Assessment des IBM Institute for Business Value 2025 stellte einen globalen Durchschnittswert von nur 25 von 100 Punkten fest.

Der praktische Rat, der aus dieser technischen Lage erwächst, ist nicht Panik, sondern phasenweise, priorisierte Handlung. Kryptographisches Inventar ist die Voraussetzung: Organisationen können nicht migrieren, was sie nicht lokalisieren können. Systeme, die Daten mit langen Vertraulichkeitshorizonten verwalten, müssen auch vor dem regulatorischen Stichtag für eine frühe Migration priorisiert werden. Hybride kryptographische Deployments, die ML-KEM parallel mit klassischen Schlüsselaustausch-Algorithmen kombinieren, bieten eine praktische Brücke: Daten, die durch ein hybrides Schema geschützt sind, erfordern, dass ein Angreifer gleichzeitig die klassischen und die post-quanten Komponenten bricht, was die Kosten jedes Angriffs der Art „jetzt sammeln, später entschlüsseln“ substanziell erhöht.

Was die algorithmischen Entwicklungen von 2024 und 2025 grundlegend verändert haben, ist die Unsicherheitsverteilung rund um den Q-Day. Der vorherige Konsens platzierte kryptographisch relevantes Quantenrechnen bequem in den 2030ern, mit erheblichen Fehlerbalken, die sich bis in die 2040er erstreckten. Die Kompression der Ressourcenschätzungen auf unter eine Million Qubits, kombiniert mit IBMs Roadmap für 2029 und Googles experimenteller Bestätigung der Fehlerkorrektur unter dem Schwellenwert, hat glaubwürdige Schätzungen bedeutsam vorgezogen und den Unsicherheitsbereich verengt.

Der Übergang zur Post-Quanten-Kryptographie endet nicht mit dem Deployment gitterbasierter Algorithmen. Er schafft eine neue kryptographische Oberfläche, deren langfristige Sicherheit von Annahmen über die Schwierigkeit geometrischer Probleme in hochdimensionalen Räumen abhängt — Annahmen, die Jahrzehnten klassischer Kryptoanalyse standgehalten haben, aber noch nicht der Prüfung durch Quantencomputer ausgesetzt wurden, die letztlich in großem Maßstab existieren werden. Was der gegenwärtige Moment erfordert, ist keine Gewissheit darüber, wann das Quantenrechnen reifen wird, sondern eine nüchterne Einschätzung dessen, was es bedeutet, eine Institution zu bauen, deren Sicherheitslage noch immer auf der Annahme gründet, dass die Faktorisierung großer Primzahlen schwierig ist. Diese Annahme hat ein Ablaufdatum.

Shors Algorithmus: Ressourcenbedarf für RSA-2048-Faktorisierung sank in unter einem Jahr um eine Größenordnung

Mehr davon

StoneHold als Hybrid aus Action-MOBA und Sammelkartenspiel vorgestellt

ROBOBEAT: Das rhythmische Roguelite-FPS startet auf Steam und im Epic Games Store

Das Suncatcher-Gambit: Googles Plan zur Eroberung der KI-Zukunft

Samsung erweitert KI-Laptop-Portfolio mit Galaxy Book5 Pro und Galaxy Book5 360

Roboter von Dreame Technology stehen auf der World Robot Conference 2023 im Rampenlicht

„Reverse: 1999“ startet zweite Phase des australischen Events „Revival! The Uluru Games“ mit neuem 6-Sterne-Charakter Ezra

Diskussion