Problème de Diffie-Hellman
Le problème de Diffie-Hellman (abrégé DHP de l'anglais Diffie-Hellman problem) est un problème mathématique évoqué en premier par Whitfield Diffie et Martin Hellman en cryptologie. Le leitmotiv de ce problème est le fait que beaucoup de systèmes de sécurité utilisent des opérations mathématiques rapides à calculer, mais très difficiles, voire impossibles à l'échelle humaine, à inverser. Par exemple il est facile de calculer le hash d'un message avec les fonctions mathématiques de hachage, mais très difficile de revenir au message originel. Si la résolution du problème de Diffie-Hellman était facile, ces systèmes seraient faciles à corrompre.
Description du problème
Le problème de Diffie-Hellman est énoncé informellement comme tel :
- Soit un élément g et les valeurs gx et gy, quelle est la valeur de gxy?
Formellement, g est un générateur d'un groupe et x et y sont des nombres entiers choisis aléatoirement.
Par exemple, dans l'échange de clés Diffie-Hellman, un observateur indiscret observe gx et gy échangés, appartenant au protocole, et les deux tiers calculent la clé partagée gxy. Une méthode rapide pour résoudre le problème de Diffie-Hellman serait un moyen pour l'observateur indiscret de violer le secret de l'échange de la clé de Diffie-Hellman ainsi que ses variantes, incluant le Cryptosystème de ElGamal.
Complexité de calcul
En cryptologie, pour certains groupes, il est supposé que la résolution du problème de Diffie-Hellman est difficile. Ce problème a été étudié minutieusement pendant des dizaines d'années, sans pour autant qu'aucune solution "facile" n'ait été proposée.
En 2006, le moyen le plus efficace connu pour résoudre ce problème est de résoudre le problème du logarithme discret, qui consiste à trouver x connaissant g et gx. En réalité, des progrès significatifs ont été réalisés par den Boer, Maurer, Wolf, Boneh et Lipton avançant que la résolution du problème de Diffie-Hellman est presque aussi complexe que celle du logarithme discret.