26/12/2023 - Modifié le 03/03/2024

L'échange de clés Diffie-Hellman

Présentation du protocole

L'échange de clés Diffie-Hellman est un protocole qui permet à deux entités de convenir d'une clé de chiffrement sur Internet sans qu'une troisième entité puisse la connaître, même en ayant écouté les échanges.

Le protocole Diffie-Hellman se base pour cela sur l'hypothèse calculatoire de Diffie-Hellman (CDH) qui stipule qu'en connaissant g, g^a et g^b, il ne serait calculatoirement pas possible de calculer g^ab[1]. Elle se base pour cela sur l'hypothèse du logarithme discret selon laquelle il serait calculatoirement impossible de calculer a à partir de g et g^a grâce au logarithme, pour des valeurs de g^a suffisamment élevées^[2].

Détail de l'échange de clés

Nommons par convention Alice et Bob deux agents qui souhaitent communiquer via Internet. Pour se communiquer une clé de chiffrement avec la méthode Diffie-Hellman, l'échange se passera ainsi^[3] :

• Alice et Bob se partagent p un nombre premier, et g avec g < p.
• Alice choisit un nombre a < p au hasard et Bob un nombre b < p. Ceux-ci ne seront jamais partagés.
• Alice envoie A = g^a [p] à Bob.
• Bob envoie B = g^b [p] à Alice.
• Alice calcule B^a [p] = (g^b [p])^a [p] = g^b.a [p]
• Bob calcule A^b [p] = (g^a [p])^b [p] = g^b.a [p]

Ainsi, Alice et Bob obtiennent une même clé g^b.a [p].

Imaginons maintenant qu'un troisième agent Ève intercepte les échanges, il disposera de g, p, A et B, mais ne pourra pas calculer g^b.a [p]. En effet, il faudrait pour cela calculer a (ou b) puis calculer B^a [p] (ou A^b [p]). Cependant, pour calculer a, il faudrait calculer le logarithme discret de A, mais A étant une très grande valeur^[4] (2048 bits, soit plus de 10⁶⁰⁰ en décimal) et le logarithme ne pouvant être calculé efficacement^[2], le calcul de a est considéré comme impossible.

Exemple d'échange de clé

On présente ici un échange de clé en utilisant des petits nombres :

• Alice et Bob conviennent de p = 17 et g = 3
• Alice choisit a = 7 et Bob choisit b = 10
• Alice calcule A = g^a [p] = 3⁷ [17] = 2187 [17] = 11 et l'envoie à Bob.
• Bob calcule B = g^b [p] = 3¹⁰ [17] = 59 049 [17] = 8 et l'envoie à Alice.
• Alice calcule B^a [p] = 8⁷ [17] = 2 097 152 [17] = 15
• Bob calcule A^b [p] = 11¹⁰ [17] = 25 937 424 601 [17] = 15

Alice et Bob obtiennent bien la même clé 3^10x7 [17] = 15

Pourquoi utiliser le modulo ?

Réaliser toutes les opérations de l'échange de clé en modulo p permet :

• de choisir g, a, et b des nombres aléatoires inférieurs à p. En effet, il est impossible de choisir un nombre aléatoire si aucune borne supérieure n'est définie car les possibilités sont infinies.
• de manipuler les nombres mis en jeu. En effet, ceux-ci peuvent aller jusqu'à 2²⁰⁴⁸ (2048 bits), or il est actuellement impossible de stocker, transmettre ou même simplement calculer des nombres si élevés. Utiliser le modulo p permet de limiter leur valeur à celle de p.

Asymétrique ou symétrique ?

La méthode Diffie-Hellman permet de convenir d'une même clé pour le chiffrement et déchiffrement, il s'agit donc d'une clé symétrique. Pourtant, la méthode Diffie-Hellman est considérée comme un algorithme asymétrique car elle permet de produire la clé symétrique à partir de données publiques g, p, A et B et de données privées a et b.

L'utilisation de l'échange de clés Diffie-Hellman aujourd'hui

Aujourd'hui, certains protocoles cryptographiques comme le cryptosystème de ElGamal^[5] (utilisé par GPG^[6]) et le cryptosystème de Cramer-Shoup^[7] reposent sur l'hypothèse décisionnelle Diffie-Hellman (DDH, variante de la CDH) basée sur la difficulté calculatoire du logarithme discret.

Le protocole TLS, utilisé aujourd'hui principalement pour sécuriser les connexions HTTPS^[8][9] supporte également l'échange de clés Diffie-Hellman^[10].