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 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.