La cryptographie asymétrique avec la méthode de Diffie-Hellman est l’une des plus connues pour échanger un secret entre deux correspondants. En cas d’interception d’un message chiffré entre deux correspondants, celui-ci sera illisible pour l’attaquant. On l’oppose généralement à la cryptographie symétrique. En effet, la cryptographie asymétrique ne nécessite pas que les deux interlocuteurs échangent une clé commune par un canal sécurisé. Voyons comment tout cela fonctionne.
L’histoire de la cryptographie asymétrique
Elle est somme toute assez récente. Il faut attendre 1974 pour que Ralph Merkel (les fans des blockchains reconnaîtront l’inventeur des « arbres de Merkel ») conçoive son protocole appelé « Puzzles de Merkel ». Il s’agit du premier cryptosystème à clé publique jamais inventé.
Le concept des Puzzles de Merkel
Alice et Bob, nos deux compères inséparables et accros à la cryptographie, veulent communiquer à distance pour s’échanger leurs petits secrets. Alice va commencer par créer beaucoup de puzzles dont la complexité de résolution est modérée. Elle aura pris soin d’identifier chaque puzzle de manière unique (un numéro assez long plus une clé de session) avant de désassembler les pièces. Comme elle connaît Bob, elle sait qu’il sera capable de reconstituer toutes les pièces (par brute force) en un temps raisonnable.
Alice envoie les pièces des puzzles à Bob. Elles sont mélangées mais toujours liées à leur puzzle respectif. Bob choisit un lot aléatoirement et décide de le résoudre. Une fois la reconstitution terminée, il peut logiquement lire le numéro du puzzle ainsi que la clé de session. A cet instant précis, Alice et Bob ont en commun la même clé de session sans qu’Eve, la méchante de l’histoire, ne sache laquelle.
En effet, elle a vu passer tous les lots de pièces des puzzles mais ceci ne lui donne aucun indice sur le contenu du puzzle terminé ni sur la clé de session. Néanmoins, elle les a tout de même potentiellement interceptés. Charge à elle de ré-assembler tous les puzzles. Elle y arrivera mais en un temps beaucoup plus importante que Bob avant de tomber sur la clé de session effectivement utilisée.
Pour répondre à Alice, Bob chiffre son message clair avec la clé de session qu’il vient de trouver puis associe son message chiffré avec le numéro unique du puzzle précédemment ré-assemblé. Il transmet le tout à Alice qui récupère le numéro unique puis l’associe à la clé de session correspondante. Elle est désormais capable de déchiffrer le message de Bob. Le tour est joué !
Whitfield Diffie et Martin Hellman
Ces deux cryptologues ont transformé le concept des « Puzzles de Merkel » en méthode mathématique. Ils ont d’ailleurs collaboré avec Ralph Merkel pour arriver à construire ce qu’on appelle « l’échange de clés Diffie-Hellman ». Ci-dessous une citation d’Hellman provenant de sa publication An Overview Of Public Key Cryptography publiée en novembre 1978 dans le IEEE Communications Magazine.
Bien que ce système ait été décrit pour la première fois dans un document de Diffie et moi, il s’agit d’un système de distribution à clé publique, un concept développé par Merkle, et devrait donc s’appeler « échange de clé Diffie-Hellman-Merkel » si des noms doivent y être associés. J’espère que cette petite chaire pourrait aider à reconnaître la contribution égale de Merkle à l’invention de la cryptographie à clé publique.
Les travaux de Diffie et Hellman sur la cryptographie asymétrique leur ont valu l’obtention du Prix Turing de l’Association for Computing Machinery en 2015.
James Ellis et le GCHQ
James Ellis était un mathématicien du Government Communications Headquarters (GCHQ), l’équivalent anglais de la NSA américaine. Grâce à la déclassification de documents datant des années 70, on sait qu’Ellis avait pensé au « chiffrement non secret » autrement dit au chiffrement asymétrique avant les travaux de Diffie, Hellman et Merkle. Il se serait inspiré d’une publication écrite lors de la Seconde Guerre Mondiale par les Laboratoires Bell, décrivant comment protéger une communication voix en ajoutant ou en ôtant du bruit. Seulement, il n’a pas été capable d’implémenter cette idée mathématiquement.
L’échange de clés Diffie-Hellman
Contrairement à ce l’on pourrait penser, dans la méthode d’échange de clés Diffie-Hellman (souvent réduit sous la forme DH), il n’y a pas à proprement parlé de communication directe de clés. On a pu le voir avec le concept des « Puzzles de Merkel ». On échange seulement des paramètres publics qui seront utilisés pour créer parallèlement chez les deux interlocuteurs une même clé secrète.
L’algorithme mathématique
Passons aux choses sérieuses. Que se passe-t-il sous le capot de cet algorithme ? À titre d’information, il existe différentes variantes de DH. Je n’aborderai ici que l’originale de 1976.
Alice et Bob sont de retour ! Ils choisissent ensemble un nombre premier vraiment grand noté p puis un nombre g appelé le générateur de telle sorte que \(\small 1 < g < p\). Notez qu’ici g est une racine primitive modulo p.
Alice choisit secrètement un entier n. Bob fait de même avec un entier m. Alice envoie à Bob le résultat du calcul \(\small g^n\bmod p\) puis Bob transmet à Alice la solution \(\small g^m\bmod p\). Grâce à son secret n, Alice calcule \(s\equiv(g^m)^n\bmod p\). Bob résout à son tour \(\small s\equiv(g^n)^m\bmod p\). Ils ont désormais une clé s identique !
Exemple chiffré
Pour cet exemple, je vais utiliser des nombres volontairement intelligibles. Cependant, il faut savoir qu’actuellement l’état de l’art recommande une taille pour p codé sur 2048 bits. C’est ici qu’on voit l’intérêt des ordinateurs pour effectuer de tels calculs !
- Alice et Bob communiquent par canal non chiffré dans le but de choisir p et g. Ils s’accordent sur les valeurs \(\small p = 281\) et \(\small g = 2\).
- Alice choisit son entier \(\small n = 50\). Bob fait de même avec \(\small m = 33\). Ces entiers ne sont pas partagés.
- Alice calcule \(\small 2^\left(50\right)\equiv109\bmod281\) de son côté. Bob quant à lui résout \(\small 2^\left(33\right)\equiv70\bmod281\).
- Ils échangent ces deux solutions toujours par canal public.
- Alice calcule désormais \(\small 70^\left(50\right)\equiv249\bmod281\) et Bob \(\small 109^\left(33\right)\equiv249\bmod281\).
Alice et Bob obtiennent le même résultat soit 249 sans jamais avoir échangé ce nombre par canal public ! Ils peuvent désormais utiliser cette clé avec le cryptosystème symétrique de leur choix.
Dans un prochain article, nous aborderons la notion de groupe multiplicatif qui est au coeur du fonctionnement mathématique du système d’échange de clés Diffie-Hellman. Puis de façon logique, nous parlerons des attaques possibles sur celui-ci.
