Shor-Algorithmus
Was ist Shor-Algorithmus?
Shor-AlgorithmusEin Quantenalgorithmus, der große Ganzzahlen in Polynomialzeit faktorisiert und diskrete Logarithmen berechnet und damit RSA, Diffie-Hellman und Elliptische-Kurven-Kryptografie auf einem hinreichend großen Quantenrechner bricht.
Der 1994 von Peter Shor veröffentlichte Shor-Algorithmus löst die Probleme der Ganzzahlfaktorisierung und des diskreten Logarithmus auf einem fehlertoleranten Quantenrechner in Polynomialzeit. Genau diese beiden Probleme bilden das Sicherheitsfundament fast aller heutigen Public-Key-Verfahren: RSA, Diffie-Hellman, DSA und ECDSA. Aktuelle Quantenhardware kann kryptografisch relevante Schlüssellängen noch nicht faktorisieren, doch seriöse Schätzungen gehen davon aus, dass einige tausend stabile logische Qubits ausreichen, um RSA-2048 zu brechen. Diese Aussicht ist der Hauptgrund für den NIST-PQC-Standardisierungsprozess sowie für die Sorge vor "Harvest now, decrypt later"-Angriffen.
● Beispiele
- 01
Wird als theoretische Grundlage zur Abschätzung der Quantenbedrohung für RSA-2048 und ECC P-256 verwendet.
- 02
Begründet die Migration klassischer asymmetrischer Primitive zu gitterbasierten KEMs wie CRYSTALS-Kyber.
● Häufige Fragen
Was ist Shor-Algorithmus?
Ein Quantenalgorithmus, der große Ganzzahlen in Polynomialzeit faktorisiert und diskrete Logarithmen berechnet und damit RSA, Diffie-Hellman und Elliptische-Kurven-Kryptografie auf einem hinreichend großen Quantenrechner bricht. Es gehört zur Kategorie Kryptografie der Cybersicherheit.
Was bedeutet Shor-Algorithmus?
Ein Quantenalgorithmus, der große Ganzzahlen in Polynomialzeit faktorisiert und diskrete Logarithmen berechnet und damit RSA, Diffie-Hellman und Elliptische-Kurven-Kryptografie auf einem hinreichend großen Quantenrechner bricht.
Wie schützt man sich gegen Shor-Algorithmus?
Schutzmaßnahmen gegen Shor-Algorithmus kombinieren typischerweise technische Kontrollen und operative Praktiken, wie in der Definition oben beschrieben.
Welche anderen Bezeichnungen gibt es für Shor-Algorithmus?
Übliche alternative Bezeichnungen: Shorscher Faktorisierungsalgorithmus.