Der Shor-Algorithmus ist ein Quantenalgorithmus, der große Zahlen in polynomieller Zeit faktorisieren kann – eine Aufgabe, für die klassische Computer nur exponentielle Zeit benötigen. Er wurde 1994 von Peter Shor veröffentlicht und ist der Hauptgrund für die Migration zur Post-Quanten-Kryptographie.
Warum er RSA bedroht
Die Sicherheit von RSA beruht darauf, dass das Faktorisieren großer Zahlen (Produkte zweier Primzahlen) praktisch unmöglich ist. Ein klassischer Angriff benötigt für 2048-Bit-Schlüssel astronomische Rechenzeiten. Der Shor-Algorithmus zerlegt eine Zahl n in nur etwa O((log n)³) Quantengatter-Operationen – polynomiell, also für Quantencomputer mit genügend Qubits machbar.
Das Verfahren kombiniert zwei Ideen: eine Reduktion der Faktorisierung auf das Finden der Ordnung einer Zahl (über die Periodizität der Modulo-Exponentiation) und die Quanten-Fouriertransformation, die diese Periode in einem einzigen Schritt auslesen kann. Dasselbe Prinzip bricht auch den diskreten Logarithmus und damit digitale Signaturen auf Basis elliptischer Kurven.
Stand der Praxis
2001 faktorisierten IBM-Forscher mit 7 Qubits die Zahl 15 in 3 und 5 – ein prinzipieller Nachweis. Für reale RSA-Schlüssel wären mehrere tausend fehlertolerante logische Qubits nötig, die heutige Quantencomputer noch nicht erreichen. Der Shor-Algorithmus ist ein Monte-Carlo-Algorithmus: In seltenen Fällen liefert er kein Ergebnis und muss wiederholt werden. Er gehört zur Klasse BQP (bounded-error quantum polynomial time).
Der Quantencomputer mit Shor-Algorithmus ist die zentrale Bedrohung hinter Harvest-Now-Decrypt-Later: Daten, die heute abgefangen werden, könnten später entschlüsselt werden. Gegenmittel sind ML-KEM, ML-DSA und andere gitterbasierte Verfahren.
Verwandte Grundlagen: Kryptographie, Schlüsselaustausch, Quantenkryptographie.