L'algorithme de Grover contre votre mot de passe : ce que disent vraiment les maths
L’algorithme de Grover est l’attaque quantique à laquelle les gens pensent réellement lorsqu’ils s’inquiètent des mots de passe « à l’épreuve du quantique ». Il ne casse rien instantanément. Il offre une accélération quadratique pour la recherche non structurée : un travail de force brute qui prend classiquement N essais nécessite environ √N itérations quantiques, ce qui divise par deux la robustesse en bits d’un mot de passe plutôt que de l’effondrer.
L’accélération quadratique, en une ligne
Si l’espace de clés de votre mot de passe compte 2^n possibilités, un attaquant classique s’attend à parcourir de l’ordre de 2^n tentatives. Grover réduit cela à environ 2^(n/2) itérations. Ainsi une recherche de 128 bits devient une recherche de 64 bits — spectaculaire en théorie, mais c’est une racine carrée, pas l’effondrement exponentiel que l’algorithme de Shor inflige aux clés RSA et à courbe elliptique. Grover ne factorise pas ; il recherche.
| Entropie effective | Travail classique (~2^n) | Travail Grover (~2^(n/2)) | Verdict pratique |
|---|---|---|---|
| 40 bits | ~1,1 × 10^12 | ~1,0 × 10^6 | Faible même aujourd’hui |
| 64 bits | ~1,8 × 10^19 | ~4,3 × 10^9 | Vulnérable au quantique à long terme |
| 80 bits | ~1,2 × 10^24 | ~1,1 × 10^12 | Limite ; ajoutez de la longueur |
| 128 bits | ~3,4 × 10^38 | ~1,8 × 10^19 | Sûr ; la √ laisse encore 64 bits |
Pourquoi Grover est bien moins effrayant en pratique que sur le papier
Trois choses émoussent gravement Grover pour le craquage de mots de passe :
- Il est intrinsèquement séquentiel. Les itérations de Grover ne peuvent pas être parallélisées comme les grappes de GPU classiques répartissent une liste de mots ; faire tourner M machines ne donne qu’une accélération de √M, on ne peut donc pas simplement lui jeter du matériel.
- La vitesse par opération est glaciale. Le matériel quantique actuel exécute les portes à des débits de plusieurs ordres de grandeur plus lents qu’un GPU ne calcule des empreintes, et chaque itération de Grover nécessite l’exécution cohérente de l’intégralité du circuit de hachage.
- La correction d’erreurs est énorme. Une exécution de Grover cryptographiquement utile nécessite des millions de qubits logiques stables maintenus sur un nombre astronomique d’itérations — bien au-delà des machines actuelles.
Ce que cela signifie pour le choix d’un mot de passe
La défense est ennuyeuse et efficace : ajoutez de la longueur. Chaque caractère aléatoire supplémentaire restaure à peu près les bits que Grover a retirés. Un mot de passe véritablement aléatoire de 16 caractères issu d’un jeu de clés complet se situe bien au-dessus de la barre des 128 bits après la pénalité en racine carrée. C’est exactement pour cela que notre vérificateur de mots de passe modélise Grover comme √(devinettes) plutôt que de prétendre que les ordinateurs quantiques sont magiques.
Pour l’autre moitié de l’histoire quantique — la rupture à clé publique qui, elle, est exponentielle — lisez La cryptographie post-quantique expliquée. Et pour voir la longueur à l’œuvre, voyez Combien de temps faut-il pour craquer un mot de passe de 16 caractères ?.