Se mettre d'accord sur un secret en public

Deux cruches versent chacune un ruban de couleur — vert profond à gauche, bleu à droite — qui se croisent au milieu et aboutissent dans deux bols exactement de la même couleur ocre.

Le chapitre précédent s'est terminé sur un mur. Toi et ton ami avez besoin de la même clé, mais tu ne peux pas la lui envoyer — sinon l'espion la lit au passage. Et l'envoyer chiffrée ne marche pas non plus, puisqu'il te faudrait à nouveau une clé pour ça. En 1976, deux mathématiciens ont montré que ce mur n'existe pas. Tu peux convenir d'un secret pendant que tout le monde écoute. Ce chapitre ne parle que de ça, et à la fin tu l'auras fait toi-même.

Les mots dont tu as besoin

Échange de clés: Arriver à deux au même nombre secret, sans que ce nombre ne passe jamais sur la ligne. Pas : s'envoyer une clé. Mais : en calculer chacun une de son côté, qui se trouve être la même.
Secret partagé: Le nombre auquel vous arrivez tous les deux. Tu en fais ensuite une clé AES, et te revoilà au chapitre précédent.
Diffie–Hellman: Le nom de cette astuce, d'après Whitfield Diffie et Martin Hellman, qui l'ont publiée en 1976. Souvent abrégé en DH.
Calcul sur une horloge (modulo): Un calcul où tu repars de 0 une fois passée une limite, comme une horloge qui recommence à 1 après 12 heures. 17 mod 12 = 5. Ça sonne comme un truc pour enfants ; c'est le moteur de toute cette astuce, et tu vas voir pourquoi.

Le tour de magie avec de la peinture

Voici l'image avec laquelle les inventeurs l'ont eux-mêmes expliqué :

Toi et ton amie choisissez ensemble, à voix haute, une couleur : jaune. Tout le monde l'entend.
Chacun de vous choisit en secret sa propre couleur. Toi, rouge ; elle, bleu. Vous ne le dites à personne.
Chacun mélange sa couleur secrète avec le jaune, et envoie le mélange à l'autre. Tout le monde voit passer de l'orange et du vert.
Toi, tu mélanges le vert que tu as reçu avec ton rouge. Elle mélange ton orange avec son bleu. Vous arrivez tous les deux à exactement la même couleur brune.

L'espion a vu du jaune, de l'orange et du vert. Mais démélanger de la peinture, c'est impossible — il n'en extrait pas votre rouge et votre bleu secrets. Vous avez un secret partagé, et personne d'autre ne l'a.

De la peinture aux nombres

Mélanger de la peinture est facile, démélanger impossible. Il existe un calcul qui a exactement cette propriété : élever à une puissance sur une horloge. Remplace les couleurs par des nombres et tu obtiens ceci, avec une horloge de 23 :

Peinture	Nombre	Qui le sait ?
jaune (convenu)	g = 5 et p = 23	tout le monde
ton rouge	a	toi seul
son bleu	b	elle seule
ton orange	A = 5^a mod 23	tout le monde, ça passe sur la ligne
son vert	B = 5^b mod 23	tout le monde, ça passe sur la ligne
le brun	B^a mod 23 = A^b mod 23	vous deux seulement

Cette dernière ligne est toute l'astuce, et elle tient pour une raison que tu connais déjà du cours de maths : (5^b)^a et (5^a)^b valent tous les deux 5^a·b. Elle et toi faites la même multiplication dans un ordre différent, donc vous arrivez au même résultat.

Essaie toi-même

Tout se passe dans ton navigateur. Rien n'est envoyé au serveur.

Clique sur Convenez d'un secret. La démo joue toi et Noor en même temps : chacun un nombre secret, chacun un calcul.
Regarde les deux dernières lignes. Des calculs différents, le même résultat.
Clique encore quelques fois. D'autres nombres secrets, un autre résultat, et pourtant toujours la même chose à gauche et à droite.
Clique sur Maintenant avec de vraies clés. La même astuce, mais sur la courbe du chapitre suivant et avec un secret de 256 bits.

Pourquoi l'espion se bloque

Il a tout vu sauf a et b. Il sait que A = 5^a mod 23, et il veut a. Sur une horloge de 23, c'est vite fait : il essaie 5¹, 5², 5³… jusqu'à ce que ça colle. 21 tentatives au plus.

Mais sans horloge, ça aurait été vite fait aussi — élever à une puissance monte alors bien gentiment, et il peut simplement deviner l'ordre de grandeur de a. C'est le calcul sur l'horloge qui casse ça : à cause de ce modulo, les résultats sautent dans tous les sens et la taille de A ne dit plus rien sur a. Mets p à un nombre de 600 chiffres et il n'y a pas d'autre chemin que de tout essayer. C'est le mur sur lequel il bute.

Ce que ça résout et ce que ça ne résout pas

Oui	Non
Deux personnes qui ne se sont jamais vues arrivent à la même clé sous les yeux de tout le monde.	Avec qui tu as convenu cette clé. Il n'y avait pas de nom à côté de ce nombre. Pour ça, il te faut chapitre 7.1.
La clé ne passe jamais sur la ligne, donc elle ne peut pas être interceptée.	Envoyer quelque chose à quelqu'un qui n'est pas en ligne. Ceci demande deux parties qui participent en même temps.

Ce premier trou n'est pas un détail. Si quelqu'un se niche au milieu et convient séparément d'un secret avec chacun de vous, vous croyez vous parler l'un à l'autre pendant qu'il lit tout. Il s'appelle un man-in-the-middle, et le tenir dehors est un problème à part entière — chapitre 7.1.

Ceci n'est pas du chiffrement. Rien n'a été chiffré ici et rien n'a été déchiffré. Tu as seulement convenu d'une clé. Ce que tu fais ensuite avec cette clé, c'est simplement l'AES de chapitre 4. Ne confonds donc pas ça avec le chapitre suivant, où l'on chiffre bel et bien directement avec une clé que tout le monde peut avoir. Deux idées différentes, toutes deux nées dans les mêmes années, et on les mélange sans arrêt.

Voici les maths : le logarithme discret

Le logarithme ordinaire est le chemin de retour de la puissance : de 5^x = 125 tu tires x = 3, et ta calculatrice le fait en un clin d'œil. Mets une horloge autour et ce chemin de retour disparaît. De 5^x mod 23 = 8 découle x = 6, mais aucune formule ne te le donne — tu ne peux qu'essayer. Ça s'appelle le problème du logarithme discret.

Le plus étrange, c'est que personne n'a prouvé que c'est difficile. On n'a simplement pas trouvé de méthode rapide en cinquante ans. Toute la sécurité d'internet repose sur une supposition — et sur le fait que beaucoup de gens intelligents ont essayé. Ça, c'est la théorie des nombres, et c'est une des rares matières où « personne ne le sait » est une réponse utilisable.