Échange de clés Diffie-Hellman

Donnons d'abord une explication intuitive en faisant une analogie avec des couleurs. L'objectif est qu'Alice et Bob se mettent d'accord sur une couleur secrète, sans qu'Ève ne puisse la connaître. Cette explication est imagée et n'a pas de sens pratique, mais permet de comprendre l'essence de l'échange de clés Diffie-Hellman. On suppose que les agents peuvent mélanger des couleurs, mais qu'il est difficile (notamment pour Ève !) d'extraire les couleurs utilisées pour réaliser un mélange. Le principe est le suivant.

1. Alice et Bob choisissent au préalable une peinture commune, ici le jaune. Cette couleur est connue de tous, y compris de l'intrus Ève.
2. Alice choisit une autre couleur secrète (ici du rouge). Elle mélange la peinture commune et sa couleur secrète et obtient de l'orange. Alice envoie la couleur orange à Bob. La couleur orange est connue d'Ève.
3. Bob fait de même : il choisit une couleur secrète (ici du cyan) qu'il mélange à la peinture commune et il obtient du bleu. Bob envoie sa couleur bleu à Alice. La couleur bleue est connue d'Ève.
4. Alice prend la couleur reçue (le bleu) qu'elle mélange avec sa couleur secrète rouge. Elle obtient une couleur brune.
5. Bob prend la couleur reçue (le orange) qu'il mélange avec sa couleur secrète cyan. Il obtient la même couleur brune.

À la fin du protocole, Alice et Bob possèdent la même couleur brune, qui représente la couleur secrète partagée. En supposant qu'il est difficile pour Ève d'extraire les couleurs utilisées pour obtenir les couleurs publiques orange et bleue, Ève ne connaît pas la couleur brune finale.

Dans le principe original décrit plus bas, un nombre premier p est choisi. Les « couleurs » sont des nombres modulo p. Le mélange de deux couleurs consiste à élever un nombre à une certaine puissance modulo p. Retrouver les couleurs utilisées dans un mélange correspond à inverser l'exponentiation, qui est un problème algorithmique difficile.

Principe d'un échange de clés Diffie-Hellman (le groupe choisi est ici Z/pZ)

Nous décrivons le principe original[1].

1. Alice et Bob ont choisi un nombre premier ${\displaystyle p}$ et un générateur ${\displaystyle g}$ du groupe Z/pZ strictement plus petit que ${\displaystyle p}$ (ils peuvent aussi, comme montré sur la figure, ne décider de ce choix qu'au moment de l'échange et se le communiquer en clair, ce qui n'améliore pas les chances d'Ève) ;
2. Alice choisit un nombre ${\displaystyle a}$ au hasard, et envoie à Bob le nombre ${\displaystyle A=g^{a}[p]}$ (« g puissance a modulo p ») ;
3. De même, Bob choisit un nombre ${\displaystyle b}$ au hasard, et transmet le nombre ${\displaystyle B=g^{b}[p]}$, ;
4. Alice, avec le nombre ${\displaystyle B}$ reçu de Bob, calcule ${\displaystyle B^{a}[p]}$. Elle obtient donc le nombre ${\displaystyle g^{ba}[p]}$ ;
5. Bob fait le calcul analogue avec le nombre ${\displaystyle A}$ reçu d'Alice : ${\displaystyle A^{b}[p]}$. Il obtient ${\displaystyle g^{ab}[p]}$, ce qui est le même nombre que celui obtenu par Alice.

À la fin du protocole, Alice et Bob obtiennent tous les deux le nombre ${\displaystyle g^{ab}[p]}$ mais pas Ève. Puisqu'il est difficile d'inverser l'exponentiation dans un corps fini (ou sur une courbe elliptique), c’est-à-dire de calculer le logarithme discret, Ève ne peut pas découvrir ni calculer ${\displaystyle g^{ab}[p]}$. Alice et Bob ont donc trouvé une clé secrète commune sans jamais se l'échanger et sans que personne puisse la calculer.

Dans la description ci-dessus, Alice et Bob travaillent dans le corps fini Z/pZ, ils échangeront les nombres modulo p. De manière générale, l'échange de clés Diffie-Hellman se généralise à un groupe fini cyclique quelconque[2] (au lieu de se mettre d'accord sur un nombre premier p, ils se mettent d'accord sur un groupe fini). Ce groupe fini peut être un corps fini, dont ils n'utilisent que la multiplication, ou une courbe elliptique.

Alice Secret Calcul Public p, g a ${\displaystyle A=g^{a}[p]}$ A (reçoit) ${\displaystyle B^{a}[p]=(g^{b}[p])^{a}[p]=g^{ab}[p]}$

Bob Public Calcul Secret p, g b (reçoit) B ${\displaystyle B=g^{b}[p]}$ ${\displaystyle A^{b}[p]=(g^{a}[p])^{b}[p]=g^{ab}[p]}$

1. Alice et Bob ont choisi un nombre premier p et une base g. Dans notre exemple, ${\displaystyle p=23}$ et ${\displaystyle g=5}$.
2. Alice choisit un nombre secret ${\displaystyle a=6}$, Bob choisit aussi un nombre secret ${\displaystyle b=15}$
3. Alice envoie à Bob la valeur ${\displaystyle A=g^{a}[p]=5^{6}[23]=8}$
4. Bob envoie à Alice la valeur ${\displaystyle B=g^{b}[p]=5^{15}[23]=19}$
5. Alice peut maintenant calculer la clé secrète : ${\displaystyle B^{a}[p]=19^{6}[23]=2}$
6. Bob fait de même et obtient la même clé qu'Alice : ${\displaystyle A^{b}[p]=8^{15}[23]=2}$

Dans la pratique, on pourra prendre un premier p de Sophie Germain (tel que q = 2p + 1 premier lui aussi) de grande taille et un générateur g dans Z/pZ (g est donc premier avec p-1).

La parade classique à cette attaque intègre dans chaque message une authentification, qui peut, par exemple consister à signer les échanges de valeurs à l'aide d'une paire de clés asymétriques certifiées par une tierce partie fiable, ou dont les moitiés publiques ont été échangées auparavant par les deux participants. Alice peut ainsi être assurée que la clé qu'elle reçoit provient effectivement de Bob, et réciproquement pour Bob.

• (en) David Adrian, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green, J. Alex Halderman, Nadia Heninger, Drew Springall, Emmanuel Thomé, Luke Valenta, Benjamin VanderSloot, Eric Wustrow, Santiago Zanella-Béguelin et Paul Zimmermann, Imperfect Forward Secrecy : How Diffie-Hellman Fails in Practice, Denver, 22nd ACM Conference on Computer and Communications Security, octobre 2015, 13 p. (ISBN 978-1-4503-3832-5, ISSN 1543-7221, OCLC 5979157254, DOI 10.1145/2810103.2813707, lire en ligne [PDF])

• Complexité algorithmique
• Cryptographie asymétrique
• Ralph Merkle
• Chiffrement RSA
• Chiffrement El Gamal
• Keyed-Hash Message Authentication Code (HMAC)