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 g^x et g^y, quelle est la valeur de g^xy?

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 g^x et g^y échangés, appartenant au protocole, et les deux tiers calculent la clé partagée g^xy. 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 g^x. 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.

Portail de la cryptologie
Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.