Diffie–Hellman : un secret convenu en public

Alice transmet gᵃ mod p, Bob envoie gᵇ mod p, et tous deux aboutissent à gᵃᵇ mod p sans qu’aucun d’eux ne l’ait divulgué. Eve voit défiler chaque nombre sur la ligne. Suivez l’échange puis l’attaque menée contre lui, et modifiez p ainsi que g pour observer ce qui écourte ses calculs.

Exemple résolu — Diffie–Hellman : un secret convenu en public

Valeur publique d’Alice	8
Valeur publique de Bob	19
Secret partagé	2
Valeurs possibles du secret partagé	22 sur 22
Essais par force brute pour ce A	7 (au pire 22)
Essais par Pohlig–Hellman pour ce A	8 (au pire 13)
Secret d’Eve déduit de x	2

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Diffie–Hellman : un secret convenu en public

Lors d’un échange de clés Diffie–Hellman, deux correspondants s’accordent sur un nombre secret à travers un canal ouvert à tous les regards. Ils choisissent publiquement un nombre premier p ainsi qu’une base g. Chacun tire un exposant privé, diffuse la puissance correspondante de g mod p, puis élève le nombre reçu à son propre exposant secret : (gᵇ)ᵃ = (gᵃ)ᵇ = gᵃᵇ mod p. Casser ce protocole revient à résoudre un logarithme discret : connaissant A = gᵃ mod p, trouver un entier x vérifiant gˣ ≡ A (mod p). Diffie et Hellman indiquaient dès 1976 qu’ils ne concevaient aucun moyen d’extraire le secret partagé des valeurs publiques sans résoudre ce problème, tout en admettant n’avoir aucune preuve de cette impossibilité. L’ordre de g est le plus petit entier n ≥ 1 tel que gⁿ ≡ 1 (mod p) ; g est dit générateur lorsque son ordre atteint p − 1.

Ce que signifie chaque symbole

p: le module premier, public
g: la base, publique
a, b: les exposants secrets d’Alice et de Bob
A, B: leurs valeurs publiques, gᵃ mod p et gᵇ mod p
x: l’exposant déterminé par Eve ; tout x vérifiant gˣ ≡ A convient, si bien qu’elle obtient a modulo l’ordre de g
ord(g): l’ordre de g : le nombre de valeurs distinctes que peut prendre le secret partagé

Suppose: p est un nombre premier compris entre 5 et 1 999, g une base quelconque entre 2 et p − 2, tandis que a et b parcourent l’intervalle de 1 à p − 2. Chaque essai correspond à la comparaison d’une puissance calculée avec la cible visée, et les deux totaux comptabilisent l’essai fructueux. Chaque chiffre de Pohlig–Hellman s’obtient en testant successivement les candidats dans l’ordre, selon la méthode décrite par Pohlig et Hellman pour les petits facteurs ; pour un grand facteur, ils proposent également une recherche combinant mémoire et rapidité, que cette page n’exécute pas. L’exemple original de Diffie et Hellman reposait sur un premier d’environ 200 bits, pour lequel ils estimaient le calcul d’un logarithme à quelque 2¹⁰⁰ opérations.

Pour 257, la base 2 ne laisse que seize secrets possibles 🖖

Cliquez sur Une boucle de 16. Comme 257 est premier, A et B semblent a priori pouvoir prendre 256 valeurs distinctes. Or 2⁸ = 256, ce qui donne −1 mod 257 : ainsi, 2¹⁶ = 1, et les puissances de 2 tournent en une boucle de 16 valeurs : 1, 2, 4, 8, 16, 32, 64, 128, 256, 255, 253, 249, 241, 225, 193, 129. Ce sont précisément les cases grisées. Quels que soient a et b, gᵃᵇ figure parmi elles ; ici, il vaut 129. La force brute menée par Eve s’arrête après 14 essais et ne saurait en exiger plus de 16. La valeur x = 13 qu’elle dégage n’est pas le 77 d’Alice, mais elle produit le même effet : toutes deux coïncident modulo 16, ce qui représente toute l’information portée par l’exposant. Choisir un module premier ne vous met donc pas à l’abri. Parmi les 254 bases comprises entre 2 et 255, 126 ne sont pas génératrices ; deux d’entre elles, 16 et 241, ne laissent même que quatre secrets possibles. Pour 263, en revanche, où p − 1 = 2 × 131, l’ordre de chaque base entre 2 et 261 vaut 131 ou 262.

Deux premiers jumeaux : 811 essais contre 21 🖖

Cliquez sur p − 1 en petits facteurs. 1621 est premier et 1620 = 2² · 3⁴ · 5 : l’algorithme de Pohlig–Hellman n’a donc jamais à explorer les 1 620 puissances de g. Il détermine a mod 4 deux candidats à la fois, a mod 81 par groupes de trois et a mod 5 parmi cinq, puis assemble ces fragments grâce au théorème des restes chinois : au pire 2·2 + 4·3 + 5 = 21 essais, et seulement 15 ici, contre 1 235 pour la force brute. Choisissez à présent 1619 dans la table des premiers voisins. Il lui est inférieur de deux unités seulement, et pourtant 1618 = 2 × 809 : une seule composante de 809 candidats, au pire 811 essais, et 427 pour ce même a. L’effort imposé à Eve dépend du plus grand facteur premier de p − 1, non de la taille de p. Sur les 301 nombres premiers acceptés par cette page, le pire des cas de Pohlig–Hellman ne dépasse jamais ce facteur de plus de 25 essais ; il reste inférieur au dixième de celui de la force brute pour 172 d’entre eux, et diminue même lors de 146 des 300 transitions d’un premier au suivant. Pohlig et Hellman l’ont formulé sans détour dès 1978 : lorsque p − 1 ne possède que de petits facteurs premiers, l’exponentiation mod p « n’est pas une bonne fonction à sens unique ».

La base la plus sûre n’est pas un générateur 🖖

Cliquez sur Base d’ordre premier. Pour 263, la base 2 n’est pas un générateur : ses puissances bouclent au bout de 131 termes, si bien que 131 secrets seulement sont envisageables. Saisissez g = 5, qui est générateur : l’éventail double aussitôt. Observez le pire des cas de Pohlig–Hellman : 133 essais, dont 2 consacrés au dernier bit de a, car A¹³¹ vaut 1 lorsque a est pair, et 262 (soit −1) lorsque a est impair. Un générateur trahit ce bit pour tout nombre premier impair, puisque p − 1 est pair. Revenez à g = 2. Son ordre, 131, étant premier, Pohlig–Hellman n’a rien à scinder : son coût maximal est de 131 essais, exactement comme la force brute. Le générateur doublait l’espace des secrets mais offrait gracieusement un bit à Eve, capable de déduire des seuls A et B si le secret est un carré mod 263. Avec g = 2, chaque puissance étant un carré, il n’y a plus rien à intercepter.

Problème entièrement résolu

Retrouver le secret d’Alice pour p = 101 5 étapes
Alice et Bob choisissent p = 101 et g = 2. Eve intercepte A = 12 et B = 53. Déterminez par l’algorithme de Pohlig–Hellman un entier x tel que 2ˣ ≡ 12 (mod 101), dénombrez les essais, puis déduisez-en le secret partagé. Indiquez ensuite ce que coûterait la même attaque pour p = 65 537.

Ouvrez ce problème dans l'outil
1. 100 = 2² · 5², de sorte que x est entièrement déterminé par x mod 4 et x mod 25. L’ordre de 2 divise 100 ; or 2⁵⁰ = 100 et 2²⁰ = 95 sont tous deux distincts de 1, ce qui impose un ordre de 100 : 2 est donc générateur.
  
  $100 = 2^{2} \cdot 5^{2}, 2^{50} \equiv 100, 2^{20} \equiv 95 (both \neq = 1) \Rightarrow ord (2) = 100$
2. Modulo 4, γ = 2⁵⁰ = 100, soit −1. Pour le premier chiffre binaire : 12⁵⁰ = 100, d’où d = 1 dès le second essai. On élimine ce terme : 12 · 2⁻¹ = 12 · 51 = 612 ≡ 6, puis 6²⁵ = 100, ce qui donne à nouveau 1 pour chiffre suivant, là encore au second essai. Ainsi, x ≡ 1 + 1 · 2 = 3 (mod 4).
  
  $1 2^{50} \equiv 100 \Rightarrow d_{0} = 1; 12 \cdot 2^{- 1} = 12 \cdot 51 \equiv 6, 6^{25} \equiv 100 \Rightarrow d_{1} = 1; x \equiv 3 (mod 4)$
3. Modulo 25, γ = 2²⁰ = 95, dont les puissances successives valent 1, 95, 36, 87, 84. Premier chiffre en base 5 : 12²⁰ = 95, d’où d = 1 au second essai. On élimine ce terme : 6⁴ = 1 296 ≡ 84, ce qui livre 4 pour chiffre suivant, au cinquième essai. D’où x ≡ 1 + 4 · 5 = 21 (mod 25).
  
  $9 5^{0..4} = 1, 95, 36, 87, 84; 1 2^{20} \equiv 95 \Rightarrow d_{0} = 1; 6^{4} = 1296 \equiv 84 \Rightarrow d_{1} = 4; x \equiv 21 (mod 25)$
4. Les entiers inférieurs à 100 congrus à 21 mod 25 sont 21, 46, 71 et 96 ; seul 71 est congru à 3 mod 4. On trouve donc x = 71 en 2 + 2 + 2 + 5 = 11 essais, alors que le pire des cas en prévoit 2·2 + 2·5 = 14. La force brute aurait testé de 0 à 71, soit 72 essais. Le secret partagé vaut 53⁷¹ mod 101 = 35.
  
  $x \in {21, 46, 71, 96}, x \equiv 3 (mod 4) \Rightarrow x = 71; 2 + 2 + 2 + 5 = 11 tries, at worst 2 \cdot 2 + 2 \cdot 5 = 14$
5. 65 537 = 2¹⁶ + 1 est premier, et p − 1 = 2¹⁶. Pohlig–Hellman résout ses seize chiffres binaires un à un, à raison de deux candidats chacun : au pire 32 essais, là où la force brute pourrait en nécessiter 65 536. Pohlig et Hellman ont résolu ce cas précis, p = 2ⁿ + 1, avant d’aborder le cadre général.
  
  $s = B^{x} = 5 3^{71} mod 101 = 35; 65537 = 2^{16} + 1 : at worst 16 \cdot 2 = 32 tries$
Réponse

x = 71, au terme de 11 essais (au pire 14), et le secret partagé est 35. Pour p = 65 537, l’attaque requiert au plus 32 essais. La page s’arrêtant à 1 999, cette dernière valeur relève du calcul théorique et non d’une simulation.

$x = 71, 11 tries, s = 35$

Parcours

Comment casser les chiffres

Références (2)

The exchange itself, the definition's sentence that its authors could see no way round a logarithm and had no proof, and the 200-bit example in `assumes`: Whitfield Diffie and Martin E. Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory 22(6), 644–654, November 1976. §III, p. 649.
The second insight's quotation, the digit-by-digit search the page runs, and the worked problem's p = 2ⁿ + 1: Stephen C. Pohlig and Martin E. Hellman, "An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance," IEEE Transactions on Information Theory 24(1), 106–110, January 1978. §III–IV, pp. 107–110.

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.