Diffie-Hellman avec des nombres

L'opération qui joue le rôle du mélange s'appelle l'exponentiation modulaire : élever un nombre à une puissance, modulo un grand nombre premier.

Le protocole

Alice et Bob conviennent publiquement de deux nombres : un grand nombre premier p et une base g.

              (public : p, g)
Alice                                   Bob
  a (secret)                              b (secret)
  A = g^a mod p
       ------------- A ------------->
       <------------ B --------------     B = g^b mod p
  s = B^a mod p                           s = A^b mod p

Les deux calculs aboutissent au même nombre :

B^a = (g^b)^a = g^(ab) mod p
A^b = (g^a)^b = g^(ab) mod p

L'ordre des exposants ne change rien — exactement comme l'ordre des peintures.

Un exemple minuscule

Prenons p = 23 et g = 5. Alice choisit a = 6, Bob choisit b = 15.

A = 5^6  mod 23 = 15625 mod 23 = 8
B = 5^15 mod 23 = 19
s = 19^6 mod 23 = 2          (cote Alice)
s = 8^15 mod 23 = 2          (cote Bob)

Les deux trouvent 2. Eve, elle, a vu passer 23, 5, 8 et 19.

Pourquoi Eve est bloquée

Pour retrouver a, Eve doit résoudre 5^a mod 23 = 8. Avec des nombres aussi petits, elle essaie toutes les valeurs et gagne en quelques instants.

Mais en pratique p fait 2048 bits ou plus, soit plus de 600 chiffres décimaux. Le nombre de valeurs à tester dépasse alors de très loin ce que toute machine pourra jamais parcourir.

Note bien l'asymétrie : Alice calcule g^a mod p instantanément par exponentiation rapide, alors que remonter de A vers a reste hors de portée. Facile dans un sens, infaisable dans l'autre — le mélange de peintures, en arithmétique.