Grover-Algorithmus
Was ist Grover-Algorithmus?
Grover-AlgorithmusEin 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.
Der 1996 von Lov Grover vorgestellte Grover-Algorithmus findet eine markierte Eingabe einer Black-Box-Funktion in O(sqrt(N)) Anfragen statt klassisch O(N). Auf die Kryptografie übertragen halbiert er das effektive Sicherheitsniveau symmetrischer Primitive und Hashfunktionen: AES-128 sinkt auf rund 64 Bit Sicherheit, die Preimage-Resistenz von SHA-256 auf etwa 128 Bit. Die übliche Gegenmaßnahme besteht darin, Schlüssel- und Digestlängen zu verdoppeln, etwa AES-256 und SHA-384 bzw. SHA-512, was auch unter Grover-artigen Angriffen einen komfortablen Sicherheitspuffer bewahrt. Im Gegensatz zu Shor bricht Grover die Public-Key-Kryptografie nicht direkt.
● Beispiele
- 01
Wird in NIST-Leitlinien zur Einschätzung der Post-Quantum-Sicherheit von AES-128 gegenüber AES-256 herangezogen.
- 02
Begründet die Umstellung von HMAC- und KDF-Ausgaben auf mindestens 256 Bit.
● Häufige Fragen
Was ist 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. Es gehört zur Kategorie Kryptografie der Cybersicherheit.
Was bedeutet 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.
Wie funktioniert Grover-Algorithmus?
Der 1996 von Lov Grover vorgestellte Grover-Algorithmus findet eine markierte Eingabe einer Black-Box-Funktion in O(sqrt(N)) Anfragen statt klassisch O(N). Auf die Kryptografie übertragen halbiert er das effektive Sicherheitsniveau symmetrischer Primitive und Hashfunktionen: AES-128 sinkt auf rund 64 Bit Sicherheit, die Preimage-Resistenz von SHA-256 auf etwa 128 Bit. Die übliche Gegenmaßnahme besteht darin, Schlüssel- und Digestlängen zu verdoppeln, etwa AES-256 und SHA-384 bzw. SHA-512, was auch unter Grover-artigen Angriffen einen komfortablen Sicherheitspuffer bewahrt. Im Gegensatz zu Shor bricht Grover die Public-Key-Kryptografie nicht direkt.
Wie schützt man sich gegen Grover-Algorithmus?
Schutzmaßnahmen gegen Grover-Algorithmus kombinieren typischerweise technische Kontrollen und operative Praktiken, wie in der Definition oben beschrieben.
Welche anderen Bezeichnungen gibt es für Grover-Algorithmus?
Übliche alternative Bezeichnungen: Grover-Suche.
● Verwandte Begriffe
- cryptography№ 846
Post-Quanten-Kryptografie
Klassische kryptografische Algorithmen, die sowohl gegen klassische als auch gegen großskalige Quantencomputerangriffe sicher bleiben sollen.
- cryptography№ 020
AES (Advanced Encryption Standard)
NIST-standardisierte 128-Bit-Blockchiffre mit Schlüssellängen von 128, 192 oder 256 Bit, entworfen von Daemen und Rijmen und weltweit die dominierende symmetrische Chiffre.
- cryptography№ 247
Kryptographische Hashfunktion
Deterministische Einwegfunktion, die Eingaben beliebiger Länge auf einen festen Digest abbildet und gegen Urbilder, zweite Urbilder und Kollisionen resistent ist.
- cryptography№ 1036
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.
- cryptography№ 1121
Symmetrische Verschlüsselung
Verschlüsselungsverfahren, bei dem derselbe geheime Schlüssel zum Ver- und Entschlüsseln dient – schnell und stark, sofern der Schlüssel sicher geteilt wird.
- cryptography№ 890
Quantenkryptografie
Kryptografie, die quantenmechanische Eigenschaften — meist von Photonen — nutzt, um Sicherheitsgarantien zu erzielen, die mit klassischer Kommunikation allein unmöglich sind.