L'échange de clés Diffie-Hellman expliqué

Pendant des milliers d'années, envoyer un message secret supposait d'abord de partager une clé secrète en personne ou par messager. En 1976, deux chercheurs de Stanford ont montré que deux parties pouvaient créer une clé commune à partir de rien, en échangeant des messages au vu de tous. Cette idée a ouvert l'ère de la cryptographie à clé publique et elle est toujours à l'œuvre chaque fois qu'un navigateur affiche un cadenas.

Alice et Bob de part et d'autre d'un canal public, chacun mélangeant une peinture jaune commune avec une couleur secrète, et tous deux obtenant le même mélange sous le regard d'Eve
Alice et Bob de part et d'autre d'un canal public, chacun mélangeant une peinture jaune commune avec une couleur secrète, et tous deux obtenant le même mélange sous le regard d'Eve

Le problème de la distribution des clés

Un chiffrement comme AES n'est sûr que dans la mesure où sa clé l'est, et les deux parties ont besoin de la même clé. Avant 1976, la clé devait être remise en secret : par valise diplomatique, par messager de confiance ou au moyen de carnets de codes imprimés à l'avance. Pour deux inconnus qui veulent communiquer en sécurité tout de suite, par exemple une boutique et un client sur Internet, c'est impossible. L'article de Whitfield Diffie et Martin Hellman, « New Directions in Cryptography », a résolu le problème avec une méthode qui ne nécessite aucun secret préalable.

De l'arithmétique sur une horloge

L'échange utilise l'arithmétique modulaire : des calculs sur une horloge à p heures, où p est un grand nombre premier. Sur cette horloge, les puissances se comportent de façon remarquable. Si g est une racine primitive, les nombres g, g², g³, … mod p sautent d'un endroit à l'autre et passent par chaque heure de 1 à p − 1 avant de se répéter, dans un ordre qui semble aléatoire. Calculer gᵃ mod p est rapide, avec à peu près autant de multiplications que a a de chiffres binaires. L'opération inverse ne l'est pas.

L'échange étape par étape

Alice et Bob conviennent ouvertement de p et g. Alice choisit un secret a et envoie A = gᵃ mod p ; Bob choisit un secret b et envoie B = gᵇ mod p. Alice calcule Bᵃ = (gᵇ)ᵃ et Bob calcule Aᵇ = (gᵃ)ᵇ, tous deux mod p. Comme l'ordre des exposants n'a pas d'importance, tous deux obtiennent g^(ab) mod p. Avec le petit exemple classique p = 23, g = 5, a = 6 et b = 15, Alice envoie 8, Bob envoie 19, et tous deux arrivent au secret partagé 2.

Le problème du logarithme discret

Eve voit p, g, A et B. Si elle pouvait retrouver a à partir de A = gᵃ mod p, elle pourrait calculer le secret exactement comme Alice. C'est le problème du logarithme discret. Les meilleurs algorithmes classiques connus, comme le crible algébrique, sont bien plus rapides que l'essai de chaque exposant, mais demandent encore un temps qui croît plus vite que n'importe quelle puissance du nombre de chiffres. Avec des nombres premiers de 2048 bits, le problème est hors de portée de tout ordinateur existant. On ignore si quelque chose de plus rapide est possible, et la sécurité de l'échange repose sur cette conviction.

L'homme du milieu

Diffie-Hellman protège contre une personne qui écoute, mais pas contre un imposteur. Mallory, placé entre Alice et Bob, peut mener un échange avec chacun d'eux et transmettre les messages en lisant tout. La parade est l'authentification : en HTTPS, le serveur signe sa partie de l'échange avec une clé certifiée par une autorité de confiance, si bien que le navigateur sait qu'il communique vraiment avec le bon site. Échange de clés et signatures vont toujours de pair.

Qui l'a inventé ?

Diffie et Hellman ont publié en 1976, en s'appuyant sur des idées de Ralph Merkle, dont Hellman a ensuite demandé qu'il soit lui aussi reconnu. En 1997, l'agence de renseignement britannique GCHQ a révélé que ses mathématiciens y étaient parvenus les premiers : James Ellis avait eu l'idée de la cryptographie à clé publique en 1970, Clifford Cocks avait trouvé un système proche de RSA en 1973, et Malcolm Williamson avait découvert le même échange de clés en 1974, le tout gardé secret pendant plus de vingt ans.

Martin Hellman (à gauche) et Whitfield Diffie (à droite), 1977
Martin Hellman (à gauche) et Whitfield Diffie (à droite), 1977
Ralph Merkle au Singularity Summit de 2007.
Ralph Merkle au Singularity Summit de 2007.

Diffie-Hellman aujourd'hui

Les connexions modernes utilisent surtout Diffie-Hellman sur courbes elliptiques, qui offre la même sécurité avec des nombres beaucoup plus courts, par exemple la courbe X25519 dans TLS 1.3, Signal et WhatsApp. Utiliser une nouvelle paire de secrets pour chaque connexion assure la confidentialité persistante : même si la clé à long terme d'un serveur est volée plus tard, les conversations passées restent protégées. Les paramètres faibles restent un danger, comme l'a montré en 2015 l'attaque Logjam pour d'anciens nombres premiers de 512 bits, et un grand ordinateur quantique exécutant l'algorithme de Shor casserait aussi bien Diffie-Hellman classique que sur courbes elliptiques ; c'est pourquoi des échanges de clés post-quantiques sont désormais déployés à leurs côtés.

À vous d'explorer

Ouvrez le visualiseur Diffie-Hellman pour suivre les cinq étapes sur un tableau de ce que savent Alice, le canal public et Bob, en peinture et en nombres. Choisissez des nombres premiers de 23 jusqu'à 2 147 483 647, fixez vous-même les secrets et laissez Eve attaquer en essayant chaque exposant : regardez-la réussir instantanément sur les petits nombres premiers et voyez comment le temps de recherche estimé augmente à mesure que le nombre premier s'allonge.

Questions fréquemment posées

Diffie-Hellman est-il la même chose que RSA ?

Non, même si ce sont deux méthodes à clé publique des années 1970. RSA, publié en 1977, peut chiffrer et signer avec une clé publique et une clé privée, et repose sur la difficulté de factoriser de grands nombres. Diffie-Hellman permet seulement de convenir d'un secret partagé et repose sur le problème du logarithme discret.

Quelle est la taille des nombres en pratique ?

Diffie-Hellman classique utilise des nombres premiers d'au moins 2048 bits, soit environ 617 chiffres décimaux, et souvent 3072 ou 4096 bits. Les versions sur courbes elliptiques utilisent des clés d'environ 256 bits pour une sécurité comparable.

Pourquoi chaque bit supplémentaire double-t-il le travail d'Eve ?

Un nombre premier avec un bit de plus est environ deux fois plus grand, il y a donc environ deux fois plus d'exposants à essayer. Les vraies attaques sont plus astucieuses que l'essai de chaque exposant, mais leur coût croît tout de même très vite avec la taille du nombre premier.

Pourquoi Alice et Bob ont-ils besoin d'un nombre premier ?

Avec un module premier, chaque nombre de 1 à p − 1 a un inverse et il existe des racines primitives, de sorte que les puissances de g couvrent toutes les possibilités. On choisit souvent des nombres premiers sûrs, pour lesquels (p − 1)/2 est aussi premier, afin d'exclure les raccourcis qui exploitent de petits facteurs de p − 1.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Ouvrir le visualiseur Diffie-Hellman