Échange de clés Diffie-Hellman

Un article de Wikipédia, l'encyclopédie libre.

En cryptographie, l'échange de clés Diffie-Hellman, du nom de ses auteurs Whitfield Diffie et Martin Hellman, est une méthode[1], publiée en 1976, par laquelle deux agents, nommés par convention Alice et Bob, peuvent se mettre d'accord sur un nombre (qu'ils peuvent utiliser comme clé pour chiffrer la conversation suivante) sans qu'un troisième agent appelé Ève puisse découvrir le nombre, même en ayant écouté tous leurs échanges. Cette idée valut en 2015 aux deux auteurs le prix Turing.

Principe[modifier | modifier le code]

Illustration conceptuelle d'un échange de clés Diffie-Hellman

Principe expliqué avec des couleurs[modifier | modifier le code]

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.

A 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 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 original[modifier | modifier le code]

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 p et un nombre g strictement plus petit que 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 au hasard a, élève g à la puissance a, et dit à Bob ga modulo p, nombre que l'on note A. Elle envoie A à Bob ;
  3. De même, Bob choisit un nombre au hasard b, et fait de même ; il transmet le nombre B = gb modulo p
  4. Alice, en élevant le nombre B reçu de Bob à la puissance a, obtient gba modulo p.
  5. Bob fait le calcul analogue avec le nombre A reçu d'Alice et obtient gab modulo p, qui est le même résultat.

A la fin du protocole, Alice et Bob connaissent tous les deux le nombre gab [mod 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, donc ne peut pas calculer gab [mod p].

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.

Exemple[modifier | modifier le code]

  1. Alice et Bob ont choisi un nombre premier p et une base g. Dans notre exemple, p=23 et g=5
  2. Alice choisit un nombre secret a=6
  3. Elle envoie à Bob la valeur A = ga [mod p] = 56 [23] = 8
  4. Bob choisit à son tour un nombre secret b=15
  5. Bob envoie à Alice la valeur B = gb [mod p] = 515 [23] = 19
  6. Alice peut maintenant calculer la clé secrète : Ba [mod p] = 196 [23] = 2
  7. Bob fait de même et obtient la même clé qu'Alice : Ab [mod p] = 815 [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).

Fondement mathématique[modifier | modifier le code]

La méthode utilise la notion de groupe (multiplicatif), par exemple celui des entiers modulo p, où p est un nombre premier : dans ce cas, les opérations mathématiques (multiplication, puissance, division) sont utilisées telles quelles, mais le résultat doit être divisé par p pour ne garder que le reste, appelé modulo. Les groupes ayant la propriété de l'associativité, l'égalite (gb)a = (ga)b est valide et les deux parties obtiennent bel et bien la même clé secrète.

La sécurité de ce protocole réside dans la difficulté du problème du logarithme discret : pour que Ève retrouve gab à partir de ga et gb, elle doit élever l'un ou l'autre à la puissance b ou à la puissance a respectivement. Mais déduire a (resp. b) de ga (resp. gb) est un problème que l'on ne sait pas résoudre efficacement. Ève est donc dans l'impossibilité (calculatoire) de déduire des seules informations ga, gb, g et p, la valeur de gab .

Il faut toutefois que le groupe de départ soit bien choisi et que les nombres utilisés soient suffisamment grands pour éviter une attaque par recherche exhaustive. À l'heure actuelle, un nombre premier p de l'ordre de 300 chiffres ainsi que a et b de l'ordre de 100 chiffres sont tout simplement impossibles à casser même avec les meilleurs algorithmes de résolution du logarithme discret[réf. nécessaire]. Si une solution pratique pour résoudre un logarithme discret venait à apparaître, d'autres systèmes cryptographiques pourraient tomber, notamment le système de ElGamal, qui repose sur le même principe.

L'attaque de l'homme du milieu[modifier | modifier le code]

Ce protocole est vulnérable à « l'attaque de l'homme du milieu », qui implique un attaquant capable de lire et de modifier tous les messages échangés entre Alice et Bob.

Cette attaque repose sur l'interception de ga et gb, ce qui est facile puisqu'ils sont échangés en clair ; l'élément g étant supposé connu par tous les attaquants. Pour retrouver les nombres a et b et ainsi casser complètement l'échange, il faudrait calculer le logarithme discret de ga et gb, ce qui est impossible en pratique.

Mais un attaquant peut se placer entre Alice et Bob, intercepter la clé ga envoyée par Alice et envoyer à Bob une autre clé ga', se faisant passer pour Alice. De même, il peut remplacer la clé gb envoyée par Bob à Alice par une clé gb', se faisant passer pour Bob. L'attaquant communique ainsi avec Alice en utilisant la clé partagée gab' et communique avec Bob en utilisant la clé partagée ga'b, Alice et Bob croient communiquer directement. C'est ce que l'on appelle « attaque de l'homme du milieu ».

Alice et Bob croient ainsi avoir échangé une clé secrète alors qu'en réalité ils ont chacun échangé une clé secrète avec l'attaquant, l'homme du milieu.

Solution[modifier | modifier le code]

La parade classique à cette attaque consiste à 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.

Références[modifier | modifier le code]

  1. a et b W. Diffie et M. Hellman, « New directions in cryptography », IEEE Transactions on Information Theory, vol. 22, no 6,‎ , p. 644–654 (DOI 10.1109/TIT.1976.1055638, lire en ligne)
  2. Johannes A. Buchmann, Introduction to Cryptography, Springer Science+Business Media, , Second éd., 190–191 p. (ISBN 978-1-4419-9003-7, lire en ligne)

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (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, , 13 p. (ISBN 978-1-4503-3832-5, ISSN 1543-7221, OCLC 5979157254, DOI 10.1145/2810103.2813707, lire en ligne [PDF])

Articles connexes[modifier | modifier le code]