Dans la Grande Vadrouille, Stanislas et Augustin se rencontrent par cette étrange échange dans le grand hammam de la Mosquée de Paris : « 🎶 Tea for two and two for tea 🎶 ». Cette phrase est un code pour que chacun s'assure que l'autre est celui qu'il croit. Mais comment Stanislas et Augustin peuvent être sûr que quelqu'un n'a pas – par malveillance – intercepté le code puis usurpé l'identité d'un des deux en annonçant lui aussi ce code ?
Cette petite scène de film nous permet d'illustrer un problème classique de la cryptographie que nous allons découvrir ici. Étant donné deux personnes qui souhaitent communiquer entre elles, comment peuvent-elles s'accorder ensemble sur un code commun sans prendre le risque que ce code tombe entre de mauvaises mains lors son échange ? Le risque est grand ! Si le code s'échange oralement, un passant peu entendre la conversation. S'il s'échange par courrier, un facteur malveillant peut ouvrir l'enveloppe.
En informatique, on s'est posé la même question. Quand on discute sur internet ou sur son téléphone avec quelqu'un, nos messages traversent beaucoup – mais vraiment beaucoup – de machines différentes (serveurs, antennes, relais, routeurs etc.). En l'absence de chiffrement, si une machine est infectée, les communications sont compromises. Les cryptologues se sont donc creusé les méninges et ont abouti à d'incroyables protocoles pour trouver une solution au problème posée plus haut.
D'un point de vue théorique, les cryptologues sont d'accord sur un point fondamental : si l'on veut discuter en toute confidentialité, l'échange doit pouvoir faire l'objet d'un interception. En d'autres termes, si intercepter toute ou partie des données d'un échange rend vulnérable la confidentialité des informations échangées, alors le protocole n'est pas sûr. Ce principe se comprend facilement pour échanger des informations chiffrées et il se résout avec l'usage d'un clé : l'utilisation d'une clé à l'envoi puis à la réception d'un message garantie qu'en cas d'interception, personne ne puisse déchiffrer le message sans la clé.
D'accord, mais comment s'accorder à distance sur la clé ? Si la clé est la seule protection contre l'interception, alors elle ne pourrait être envoyée telle quelle au risque d'être interceptée. C'est le serpent qui se mort la queue ! La clé doit donc être le fruit d'un échange particulier qui ne fonctionne pas comme un échange classique chiffrée à l'aide d'une clé commune. Le clé doit être obtenue de manière plus maline, plus complexe. Là intervient le sujet de ce billet : la méthode d'échange de clés Diffie-Hellman.
En 1976, Whitfield Diffie et Martin Hellman développent une méthode brillante pour régler ce problème. Cette méthode d'échange de clés permet non pas qu'une partie choisisse unilatéralement une clé pour l'autre, mais que les parties construisent ensemble une clé à la suite de deux échanges dont l'interception de toute ou partie des données rend impossible de trouver la clé finale. Nous allons voir comment.
Alice et Bob souhaitent s'accorder sur une clé. Pour cela, il vont chacun choisir un nombre secret : a pour Alice, b pour Bob. La méthode consiste à passer dans une fonction magique mathématique chacun de ces nombres : les résultats A et B respectifs sont envoyés à l'interlocuteur : Bob reçoit A et Alice reçoit B. Cette fonction mathématique est telle qu'il est impossible pour un assaillant de retrouver a à partir de A et b à partir de B.
En revanche, la magie de cette fonction se révèle dans l'étape suivante. En possession de A et B, Alice et Bob vont chacun associer – à l'aide d'une nouvelle fonction – ces nombres publics avec leur nombre secret respectif : Alice va associer a et B, Bob va associer b et A. À noter que cette fonction, comme la précédente, rend impossible de retrouver a et B ou b et A à partir du résultat. Et là, comme par magie, les deux vont aboutir au même résultat ! La clé commune est née :)
Les deux fonctions utilisées présentent l'avantage de rendre mathématiquement impossible le fait de retrouver les éléments d'une opération à partir de son résultat. De plus, à aucun moment les nombres secrets choisis ou obtenus dans le processus ne font l'objet d'un échange : a et b ne sont jamais échangés, la clé commune non plus car elle est générée par Alice et Bob eux-mêmes. Notre problème de départ est résolu : nous avons trouvé un moyen de s'accorder sur une clé commune avec la garantie que tout interception des échanges ne permettent pas de (re)trouver cette clé !
La question est maintenant de savoir à quoi ressemble ces fonctions magiques. Il y en existe plusieurs différentes, nous allons voir le cas d'école classique qui est en réalité une seule fonction. Il s'agit de \(f(n, e, p) = n^e \mod p\). Ce que fait cette fonction est assez simple : elle prend un nombre \(n\), le met à la puissance \(e\) puis garde le reste de la division euclidienne (= modulo) de \(n^e\) par \(p\). Reprenons ensemble la méthode expliquée plus haut avec notre nouvelle fonction.
Au préalable, Alice et Bob s'accordent sur un nombre g premier, ainsi que p, une de ses « racines primitives modulo g » (appelé nombre générateur). Sans chercher à comprendre ce que cela veut dire, il faut comprendre qu'un nombre premier g et son générateur p associé doivent être choisis au préalable. Comme ces nombre peuvent être publics et réutilisés, on peut toujours utiliser les mêmes. Ici, nous choisirons \(g = 23\) et \(p = 5\) trouvés sur cette page wikipedia. Si l'assaillant intercepte ces nombres, il n'y aucun problème de sécurité !
Ensuite, nous choisissons les nombres secret a et b. On peut se faire plaisir et prendre ceux que l'on veut. Au pif, autant prendre \(a = 1871\) et \(b = 1916\). Comme expliqué plus haut, on génère nos nombres publics A et B. Pour cela, on calcule \(A = g^a\mod p\) et \(B = g^b\mod p\). On obtient \(A = 2\) et \(B = 1\). Nos nombres sont petits car ils sont tous modulo de p, or p vaut 5 donc nous obtiendront toujours un A et un B inférieurs à 5.
Alice et Bob s'échangent A et B. À la réception, une nouvelle opération intervient. Alice va calculer \(K_a = B^a\mod p\) et Bob va calculer \(K_b = A^b\mod p\). Ça y est, Alice et Bob se sont accordés sur leur clé commune : \(K_a\) est égal à \(K_b\). Vous pouvez calculer tout ça chez vous avec Python à l'aide de la fonction pow(a, b, c) permettant de calculer \(a^b\mod c\).
>>> g = 23
>>> p = 5
>>> a = 1871
>>> b = 1916
>>> A = pow(g, a, p)
>>> B = pow(g, b, p)
>>> Ka = pow(B, a, p)
>>> Kb = pow(A, b, p)
>>> Ka == Kb
True
La méthode d'échange de clés Diffie-Hellman s'utilise en pratique avec un système de chiffrement symétrique. Cela veut dire que la clé commune trouvée est utilisée pour chiffrer et déchiffrer des messages. Par exemple, une messagerie chiffrée de bout en bout (comme Signal ou What's App) utilise un échange de clé Diffie-Hellman pour que deux téléphones s'accordent sur une clé qui leur permettra de chiffrer et déchiffrer leurs messages.
Imaginons qu'Alice et Bob utilisent une telle messagerie et que Alice envoie le premier message. Elle va récupérer sur le profil public de Bob son nombre public B (il est public et attaché à son profil) puis va calculer son propre nombre public A à l'aide d'un nombre secret a qu'elle va générer pour l'occasion. Elle en profite pour calculer la clé commune K à l'aide de B et de a. Son premier message chiffrée grâce à la clé K s'accompagne d'un message transparent communiquant le nombre public A.
Bob va ainsi recevoir deux messages. Un premier message transparent communiquant A. Bob va l'utiliser pour générer la clé commune K à l'aide de A et son nombre secret b (qu'il avait généré à la création de son profil et à l'inscription du nombre public B dans son profil public). À l'aide de K, il va pouvoir déchiffrer le second message qui est – en réalité – le premier vrai message d'Alice. Ils peuvent maintenant continuer à s'envoyer des messages chiffrés à l'aide de la clé commune K.
Voilà, vous savez maintenant comment tirer avantage des mathématiques pour créer un code secret commun. Imaginez la scène de la Grande Vadrouille si Stanislas et Augustin avaient utilisé la méthode d'échange de clés Diffie-Hellman plutôt que Tea for two and two for tea. « 2, 23 et 5 ? 1 ? 1. Pareil. » ça n'aurait pas été drôle, je suis d'accord.
L'échange de clés Diffie-Hellman est une méthode largement utilisée en cryptographie et dans le chiffrement des communications numériques. Il permet de facilement créer la clé d'un chiffrement symétrique en toute sécurité. Pour autant, il existe d'autres manières d'initier un échange de données chiffrées sans passer par une clé commune. Nous verrons tout ça dans un prochain billet de blog consacré au chiffrement asymétrique !