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 funktioniert Shor-Algorithmus?
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.
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.
● Verwandte Begriffe
- cryptography№ 846
Post-Quanten-Kryptografie
Klassische kryptografische Algorithmen, die sowohl gegen klassische als auch gegen großskalige Quantencomputerangriffe sicher bleiben sollen.
- cryptography№ 890
Quantenkryptografie
Kryptografie, die quantenmechanische Eigenschaften — meist von Photonen — nutzt, um Sicherheitsgarantien zu erzielen, die mit klassischer Kommunikation allein unmöglich sind.
- cryptography№ 951
RSA-Algorithmus
Public-Key-Algorithmus von Rivest, Shamir und Adleman (1977), dessen Sicherheit auf der Schwierigkeit beruht, das Produkt zweier großer Primzahlen zu faktorisieren.
- cryptography№ 454
Grover-Algorithmus
Ein Quantensuchalgorithmus, der ein markiertes Element in einer unstrukturierten Datenbank mit N Einträgen in etwa sqrt(N) Schritten findet und so eine quadratische Beschleunigung gegen symmetrische Chiffren und Hashfunktionen liefert.
- cryptography№ 732
NIST-PQC-Standardisierung
Mehrjähriger NIST-Prozess zur Auswahl und Standardisierung post-quantensicherer Kryptoalgorithmen; die ersten drei Standards FIPS 203, 204 und 205 wurden im August 2024 veröffentlicht.
- cryptography№ 253
CRYSTALS-Kyber
Ein gitterbasiertes Schlüsselkapselungsverfahren, das das NIST im August 2024 als FIPS 203 (ML-KEM) standardisiert hat und das RSA- und Diffie-Hellman-Schlüsselaustausch in einer post-quantenfähigen Welt ablösen soll.