Algorithme Diffie-Hellman

Diffie-Hellman est un algorithme d'échange de clefs: il permet à deux personnes de mettre en place un système par lequel elles pourront échanger de façon secrète. C'est le premier algorithme créé dans ce but, en 1976, par Whitfield Diffie et Martin E. Hellman dans leur article New Directions in Cryptography.

Utilité

Imaginons que deux personnes, Alfred et George, veuillent s'envoyer des messages secrets.
Pour cela, ils peuvent utiliser un algorithme de chiffrement, qui brouillera leurs messages pour tout le monde, sauf eux deux. Un tel algorithme transforme les messages grâce à une clef, qui est en fait un nombre ou une suite de lettres. Pour chiffrer (rendre illisible) et déchiffrer (rendre à nouveau compréhensible) le message, il faut forcément avoir la clef. Avec une telle clef, Alfred et George peuvent s'envoyer tous les messages qu'ils voudront, sans que personne d'autre puisse les lire !

Seulement, voilà: si Alfred choisit comme clef le mot clefsecrète, comment la faire parvenir à George ? Si Alfred la lui envoie « normalement », des gens pourront la voir, et donc lire les futurs messages chiffrés, car il suffit pour cela de connaître la clef. Même en utilisant les moyens les plus sûrs, comme une valise diplomatique, Alfred et George ne seront jamais certains que personne ne connaît leur clef secrète.

C'est là que sert un algorithme d'échange de clefs comme Diffie-Hellman, qui permet de choisir une clef secrète de façon complètement publique !

Principe

Pour cela, on utilise une particularité des mathématiques: le « problème du calcul du logarithme discret ». Ce nom compliqué cache quelque chose de plutôt simple: s'il est facile d'élever un nombre à une puissance, comme $3^{5}=3\times 3\times 3\times 3\times 3=243$ (ce que fait n'importe quelle calculatrice, et même un humain), il est beaucoup plus difficile de faire l'opération inverse (retrouver $3^{5}$ à partir de 243), surtout lorsque les nombres utilisés sont très grands.

Par exemple, un logiciel spécialisé calcule très rapidement le résultat de $25488756^{1521}$ (un nombre énorme, à 193 chiffres) ; par contre, il lui est impossible de retrouver $25488756^{1521}$ à partir de ce nombre dans une durée raisonnable. C'est le problème du calcul du logarithme discret. Aujourd'hui, on recommande d'utiliser des nombres de 300 chiffres, élevés à des puissances de 100 chiffres, ce qui est bien plus solide.

Voyons maintenant comment Alfred et George vont appliquer l'algorithme de Diffie-Hellman.

Protocole

1. Alfred et George choisissent, publiquement (par téléphone, courrier ou courriel, par exemple), un même nombre entier que nous notons B, ainsi qu'un autre entier n. B et n doivent être premiers entre eux ;
2. Ensuite, Alfred choisit, de son côté et secrètement, un nombre entier aléatoire qu'on appelle a. Il calcule ensuite le nombre $A=B^{a}\mod n$ (mod étant le symbole du modulo) et envoie A à George, toujours par voie publique ;
3. George fait la même chose: il se trouve un nombre entier aléatoire g qu'il garde secret, et calcule $G=B^{g}\mod n$, qu'il envoie à Alfred ;
4. À présent, chacun dispose du résultat du calcul de l'autre. Alfred n'a plus qu'à calculer $G^{a}\mod n$, et George $A^{g}\mod n$. Et c'est fini !

Explication

En effet, si l'on regarde bien:

• $G=B^{g}\mod n$ donc $G^{a}\mod n=\left(B^{g}\right)^{a}\mod n=B^{ag}\mod n$ ;
• de l'autre côté, $A=B^{a}\mod n$ donc $A^{g}\mod n=\left(B^{a}\right)^{g}\mod n=B^{ag}\mod n$.

Finalement, les deux nombres sont identiques !

Alfred et George disposent enfin d'un nombre, B^ag mod n, qu'ils sont les seuls à connaître et qui, donc, peut leur servir de clef ; et pourtant, leurs échanges se sont faits devant tout le monde. Comment est-ce possible ?

Les éventuels espions de cet échange de clef n'ont jamais connu ni le nombre a, ni le nombre g (qui sont indispensables pour trouver B^ag mod n), car aucun d'entre eux n'est jamais échangé. Les seules informations dont ces espions disposent sont les nombres n, B, A et G ; mais pour retrouver a à partir de A, par exemple, il faut affronter ce fameux problème du logarithme discret, dont nous avons vu qu'il est pratiquement impossible à résoudre pour de grands nombres.

Applications

Tout le monde peut utiliser l'algorithme Diffie-Hellman, car ses brevets (logiciels, valables uniquement aux États-Unis) ont expiré.

De manière générale, un tel protocole résout les situations d'échange d'informations privée sur un réseau totalement public.

Par exemple, sur Vikidia: toutes les pages sont accessibles à tous et il n'existe aucun moyen entre deux contributeurs d'avoir une discussion privée sur le site. Avec Diffie-Hellman, c'est possible ; il suffit d'appliquer le protocole précédent. Cela vaut sans doute pour n'importe quelle autre situation.

Pour approfondir – sources

• Cryptographie appliquée, 2^e édition, de Bruce Schneier ;
• Échange de clés Diffie-Hellman sur Wikipédia

Portail des mathématiques —  Les nombres, la géométrie, les grands mathématiciens...