Accueilretour

Systèmes modernes à clé publique

2. Le protocole Diffie-Hellman

Généralités

Stéganographie

Cryptanalyse

Littérature

Transpositions

Subs. monoα

Subs. polyα 1 - 2

One-time pad

DES 1 - 2

Clef publique

Knapsack

Diffie-Hellman

protocole d'échange

application

exemple

sécurité

algo. Shanks

RSA 1 - 2

Grands noms

Références



 Dans les années 70, Whitfield Diffie et Martin Hellman ont eu, indépendamment, l'idée du cryptage asymétrique, avant d'unir leurs efforts de recherche au sein de l'Université de Stanford.

Travaillant en commun, ils ont créé différents systèmes à clef publique qui n'ont pas connu le succès pour des raisons évoquées plus loin.

Leurs travaux ont finalement débouché sur la mise au point d'un protocole d'échange de clefs. Il revient à M. Hellman d'avoir effectué le percée décisive [1]. Il a cependant tenu à associer son collègue W. Diffie à la découverte, indiquant qu'elle n'aurait pas été possible sans leurs échanges.

Le protocole Diffie-Hellman est une méthode d'échange de clef secrète via un canal non sûr. Cette clef secrète peut à son tour être utilisée dans un procédé de chiffrage, même symétrique.

Le système Diffie-Hellman permet lui-même le cryptage à clef publique ; voyons comment.

retour

Protocole d'échange de clefs

Retrouvons nos héros favoris Alice et Bob.

1. Ils s'accordent sur le choix d'un entier premier p∈ℙ et d'un autre entier g>1 (qui servira de base d'exponentiation). Cette étape n'est pas secrète.

2. En secret,
  • Alice choisit un entier a<p et détermine

    A = ga mod. p

    qu'elle communique à Bob.

  • Bob choisit de même un entier b<p puis calcule

    B = gb mod. p

    qu'il fait parvenir à Alice.
Ces deux étapes peuvent être effectuées dans n'importe quel ordre, voire simultanément. Alice et Bob n'ont pas besoin de recourir à un canal sécurisé pour s'échanger les paramètres A et B.

3. Alice calcule

s = Ba mod. p

cependant que Bob détermine de son côté

s' = Ab mod. p

mais alors, Alice et Bob disposent d'une clef secrète commune, puisque :

s = s'

En effet :

s = Ba mod. p = (gb)a mod. p = gba mod p ;
s' = Ab mod. p = (ga)b mod. p = gab mod. p :


Il s'agit donc bien de la même valeur. L'échange de clef a été réalisé.

Notons que le transfert de clefs peut être étendu à plus de deux membres, sur la base de relations telles que :

(gab)c = (gba)c  = (gac)b = gabc mod. p

La généralisation est transparente ; nous ne la détaillons pas.

retour

application au chiffrement

Le système Diffie-Hellman peut être appliqué au chiffrage à clef publique. Reprenons les mêmes notations (et les mêmes personnages).

La clef publique de Bob est (g, p, B). Il partage avec Alice la clef secrète s.

Alice souhaite lui envoyer un message M -- typiquement, M représente un unique caractère noté binairement comme dans le cas du knapsack. Alice calcule puis envoie à Bob :

C = M × s mod. p

Pour déchiffrer le message codé S, il suffirait à Bob de calculer :

M = C × s−1 mod. p

pour peu qu'il connaisse l'inverse modulaire de s = gab (mod. p).

... Il peut le faire ! En effet, dans le groupe multiplicatif 𝔽p*, qui est  de cardinal n = p−1,  l'ordre de tout élément x est un diviseur de n. On a donc xn = 1 [2].

Par conséquent, Bob peut calculer

    t = An−b = (ga)n−b
      = (ga)n(gab)−1 = s−1 [p]

(rappelons que Bob dispose de "A"), et ainsi reconstituer M. De même, Alice pourrait calculer en sens inverse

    t' = Bn−a = (gb)n−a
       = (gb)n(gba)−1 = s−1 [p]
      (= t)

et ainsi déchiffrer les messages envoyés par Bob.

Ainsi, le système Diffie-Hellman est aussi une méthode de chiffrage à clef publique. Il n'a pas connu le succès, pour des raisons tant commerciales qu'historiques. Un concurrent sérieux est arrivé avec l'invention du système RSA. Ce dernier avait un atout décisif : il permet l'authentification des messages. Ce que Diffie-Hellman ne sait pas faire [3].

retour

Exemple

Inutile de préciser que les valeurs en jeu dans cet exemple sont bien trop faibles pour une utilisation réelle.

Alice et Bob choisissent en commun p = 53 et g = 9.

1. Alice choisit a = 8. Pour calculer ga elle utilise l'exponentiation rapide (8 = 23) modulaire (càd, dans ℤ/pℤ) :
  • g2 = 81 ≡ 28 mod. p ;
  • g4 = 282 = 784 ≡ 42 mod. p ;
  • A = ga = g8 = 422 = 1764 ≡ 15 mod. p.
2. Bob choisit quant à lui b = 12. Il effectue les mêmes calculs et les complète par l'étape suivante (12 = 8 + 4 = 23 +22) :
  • B = gb = g12 = g8g4 ≡ 42×15 mod. p = 630 ≡ 47 mod. p.
3. Alice reçoit cette dernière valeur de la part de Bob et calcule
  • B2 = 472 = 2209 ≡ 36 mod. p ;
  • B4 = 362 = 1296 ≡ 24 mod. p ;
  • s = Ba = B8 ≡ 242 mod. p = 576 ≡ 46 mod. p.
4. Bob entre-temps a reçu la valeur A = 15 d'Alice et peut former, toujours selon le même algorithme :
  • A2 = 152 = 225 ≡ 13 mod. p ;
  • A4 = 132 = 169 ≡ 10 mod. p ;
  • A8 = 102 = 100 ≡ 47 mod. p ;
  • s' = Ab = A12 = A8A4 ≡ 10×47 = 470 ≡ 46 mod. p.
Ainsi Alice et Bob ons partagé la clef secrète s (= 46) sans compromettre la sécurité de leurs communications ultérieures.

retour

Sécurité du protocole

Supposons que p, a et b soient "grands". Actuellement, cela veut dire : de l'ordre de 300 chiffres pour p, 100 pour a et b. Alors, connaissant p, g, gb mod. p et ga mod. p, il est "impossible" de retrouver a et b. Cette impossibilité n'est pas théorique, mais algorithmique : ce n'est pas faisable en un temps réaliste, puisque aucun algorithme polynomial n'est connu. C'est le problème du logarithme discret que nous avons déjà évoqué.

Plus précisément : si le problème du logarithme discret était "résolu" (càd si un algorithme polynomial était découvert), le protocole Diffie-Hellman serait "cassé". Inversement, il n'est pas sûr que la cryptanalyse de Diffie-Hellman conduise à la résolution du problème du logarithme discret. Mais on admet généralement que les deux problèmes sont équivalents. En pratique, on estime donc que le système Diffie-Hellman est aussi sûr que le logarithme discret.

retour

L'algorithme de Shanks

Expliquons pourquoi le problème du logarithme discret est "difficile". On se donne A, g, p et on cherche à résoudre

A = gx (mod. p).   (1)

La recherche naïve exige p essais pour x. Elle est donc clairement exponentielle (p = exp(ln(p))).

Selon Shanks, effectuons la division euclidienne de x par u (à préciser ultérieurement) :

x = u × q + r (0 ≤ r < u)

On réécrit ensuite (1) sous la forme

A(g−u)q = gr

et on calcule (en mettant en mémoire)
  • les gr pour 0 ≤ r < u ;
  • les (g−u)q pour 0 ≤ q < u/p (de proche en proche à partir de q = 1).
Si l'on obtient une coïncidence entre deux valeurs de chaque famille, on a terminé. Le coût est minimal pour u = √p̅, ce qui conduit à O(√p̅) = O(exp(d/2)) (où d = ln(p)), améliorant ainsi la méthode naïve, mais encore bien loin d'une efficacité polynomiale.

retour

Notes

[1]  Comme le dit joliment M. Hellman, "C'est à moi que la muse a parlé".

[2]  On a ainsi redémontré au passage le petit théorème de Fermat.

[3]  en tout cas, pas simplement