L'algorithme de Grover est un algorithme quantique de recherche dans un espace non structuré. Là où une recherche exhaustive classique demande de l'ordre de N essais, Grover en demande de l'ordre de la racine carrée de N. Appliqué à la cryptographie, il divise par deux la sécurité effective des primitives symétriques et des fonctions de hachage.
Ce que cela change en pratique
Une clé AES-128 offre 128 bits de sécurité face à un attaquant classique, et de l'ordre de 64 bits face à un attaquant disposant d'un calculateur quantique adapté — une marge jugée insuffisante. D'où la recommandation courante de passer à AES-256, qui conserve environ 128 bits de sécurité effective. Le même raisonnement s'applique aux fonctions de hachage : on privilégie des empreintes plus longues (SHA-384, SHA-512) là où la résistance doit tenir sur la durée.
Le gain de Grover est quadratique, donc absorbable en allongeant les clés. C'est une différence majeure avec l'algorithme de Shor, dont le gain exponentiel rend RSA, Diffie-Hellman et ECC irrécupérables quelle que soit la taille de clé.
À ne pas confondre avec Shor
| Grover | Shor | |
|---|---|---|
| Cible | Symétrique, hachage | RSA, DH, ECC |
| Gain | Quadratique | Exponentiel |
| Parade | Doubler la taille de clé | Changer d'algorithme (PQC) |
Autrement dit : Grover impose un redimensionnement, Shor impose une migration.
Aller plus loin : cryptographie post-quantique, ce qui casse et quand · définition de l'algorithme de Shor · l'authentification cognitive face à la menace quantique