Pourquoi une fonction de hachage ne peut-elle jamais être bidirectionnelle ?
L'une des questions fondamentales en informatique et en cryptographie est : pourquoi une fonction de hachage utilisée pour sécuriser des mots de passe est-elle irréversible ?
La réponse se trouve dans la conception même de ces fonctions. Une fonction de hachage, comme celles utilisées dans des bibliothèques populaires telles que bcrypt, transforme un mot de passe en une chaîne unique, appelée "hash". Cependant, il est pratiquement impossible de revenir au mot de passe initial à partir du hash. Explorons les raisons derrière cette caractéristique essentielle.
Les bases : qu'est-ce qu'une fonction de hachage ?
Une fonction de hachage est une transformation mathématique qui prend une entrée (comme un mot de passe) et produit une sortie fixe, souvent sous la forme d'une chaîne alphanumérique. Ces fonctions possèdent trois propriétés majeures :
- Déterminisme : la même entrée produit toujours la même sortie.
- Efficacité : le calcul du hash est rapide.
- Irréversibilité : il est infeasible de déduire l'entrée initiale à partir du hash.
Les fonctions de hachage modernes, comme celles utilisées dans la cryptographie, sont également conçues pour résister à des attaques, grâce à des caractéristiques comme la résistance aux collisions (deux entrées différentes ne doivent pas produire le même hash) et la robustesse face aux attaques de type brute force.
Pourquoi sont-elles unidirectionnelles ?
L'irréversibilité des fonctions de hachage repose sur des principes mathématiques fondamentaux, liés à la théorie de la complexité algorithmique. Le fait de retrouver un mot de passe à partir d’un hash est un problème extrêmement complexe, car il faudrait essayer toutes les combinaisons possibles (par exemple, toutes les chaînes de caractères jusqu'à une certaine longueur).
En cryptographie, ce caractère irréversible repose souvent sur des conjectures mathématiques non résolues, notamment la fameuse conjecture P ≟ NP.
Le lien avec le problème P ≟ NP
Le problème P vs NP est l’une des grandes énigmes des mathématiques et de l’informatique théorique. Il cherche à répondre à une question fondamentale : si une solution peut être vérifiée rapidement, peut-elle également être trouvée rapidement ?
En quoi cela concerne les fonctions de hachage ?
- Vérification rapide : Lorsque vous entrez un mot de passe, le système le hache et compare le résultat avec le hash stocké. Cette vérification est rapide et efficace.
- Calcul inverse difficile : Revenir en arrière, c'est-à-dire trouver l'entrée à partir du hash, correspond à résoudre un problème NP-complet. Cela signifie que nous ne connaissons aucun algorithme capable de le faire rapidement (et on doute qu'il en existe).
Si un jour P = NP était prouvé, alors tout problème difficile à résoudre deviendrait aussi facile à résoudre qu’à vérifier. Cela aurait des implications majeures :
- Les systèmes cryptographiques actuels, basés sur l’intractabilité des fonctions de hachage ou des problèmes mathématiques comme la factorisation de grands nombres (RSA), deviendraient vulnérables.
- La cryptographie asymétrique, les signatures numériques et même les blockchains pourraient être compromis.
Pourquoi cette conjecture est si importante ?
Le problème P ≟ NP est considéré comme l’un des plus grands mystères des mathématiques modernes. S’il était prouvé que P = NP, cela bouleverserait :
- La cryptographie : Les mots de passe, les transactions en ligne et les communications sécurisées deviendraient vulnérables.
- Les mathématiques : De nombreux problèmes non résolus deviendraient soudainement accessibles.
- L'ingénierie et la médecine : La résolution d'énigmes complexes, comme le repliement des protéines, pourrait être révolutionnée.
Cependant, la communauté scientifique est largement convaincue que P ≠ NP, ce qui garantit la sécurité des fonctions de hachage telles que bcrypt.
Par Aghilas AZZOUG
sources: https://fr.wikipedia.org/wiki/Probl%C3%A8me_P_%E2%89%9F_NP