Problème de Diffie-Hellman

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 rapide à calculer, mais très difficile, voire impossible à 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[modifier | modifier le code]

Le problème de Diffie-Hellman est énoncé informellement comme tel:

Soit un élément g et les valeurs gx et gy, quel 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. Un 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[modifier | modifier le code]

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.