L'Algorithme qui Sécurise Internet (entre autres...)

0:00 Bonjour à tous, aujourd'hui on va parler d'une technique de cryptographie incroyable

0:05 qui permet à deux personnes de s'échanger des secrets

0:08 même quand elles sont en permanence écoutées par un espion.

0:12 Cette méthode qu'on appelle l'algorithme de Diffie-Hellman

0:16 paraît assez invraisemblable

0:18 et les premières fois que j'en ai entendu parler

0:20 je me suis dit que ça n'était pas possible qu'une telle technique puisse exister.

0:24 Et pourtant, on va voir que ça marche vraiment.

0:31 Si deux personnes souhaitent s'échanger un message dans le plus grand secret

0:36 vous allez me dire que c'est facile, il suffit de coder le message.

0:39 Techniquement on appelle ça une opération de chiffrement.

0:42 On part d'un message en clair, par exemple rendez-vous ce soir au parc

0:47 et on va essayer de le transformer en un charabia incompréhensible

0:51 mais qui pourra être déchiffré par notre interlocuteur.

0:55 Une des plus vieilles techniques, c'est ce qu'on appelle le décalage de César

0:59 puisqu'il aurait été popularisé par le célèbre général romain.

1:03 L'idée est de simplement décaler toutes les lettres de l'alphabet d'une certaine quantité.

1:08 Par exemple, si on décale de 3, on remplace le A par le D

1:12 le B par le E, le C par le F, etc.

1:15 jusqu'au W qui devient Z et XYZ qui deviennent A, B et C.

1:20 Avec ça, le message semble complètement brouillé

1:23 mais notre interlocuteur pourra sans problème le reconstituer

1:27 en appliquant le décalage inverse.

1:30 Cette technique est toutefois assez superficielle.

1:32 Si un espion devine que le message a été chiffré de cette façon

1:36 il n'a que 26 possibilités de décalage à essayer, et même seulement 25 en fait.

1:41 Et donc il aura assez vite fait de tout tester jusqu'à découvrir le message secret.

1:46 Pour faire plus robuste que la méthode de César

1:49 on peut utiliser ce qu'on appelle le chiffrement par substitution.

1:53 Ça consiste à remplacer chaque lettre de l'alphabet

1:56 par une autre lettre mais sans logique particulière.

1:59 Pour chiffrer et déchiffrer le message, il faut donc connaître l'ensemble de la table de conversion.

2:05 Et c'est très efficace, car cette fois il y a factoriel 26 possibilités

2:10 soit de l'ordre d'un milliard de milliards de milliards.

2:13 Mais malgré ça, on sait aussi très bien casser ces chiffrements par substitution

2:18 en faisant des statistiques sur les fréquences des lettres et de leurs enchaînements.

2:22 Par exemple, comme c'est toujours la même lettre qui représente le E

2:25 sur un message en français suffisamment long, on arrive facilement à l'identifier.

2:30 Et idem pour des lettres fréquentes comme le A ou le S, et ainsi de suite.

2:34 J'avais d'ailleurs fait une vidéo sur comment casser ce type de chiffrement

2:38 très rapidement de façon automatisée

2:40 en utilisant ce qu'on appelle des méthodes de Monte Carlo par chaîne de Markov.

2:45 Pour se prémunir de ces attaques, il faut essayer un autre type de chiffrement.

2:50 Une option, c'est par exemple d'utiliser un mot-clé qui va dicter les décalages de lettres.

2:56 Prenons le mot jardin, et écrivons-le en dessous de notre message.

3:00 Chacune des lettres du mot va représenter un décalage en fonction de sa position dans l'alphabet.

3:06 Le J c'est 9, le A c'est 0, le R c'est 17, etc.

3:10 Et on applique ensuite chaque décalage aux lettres de notre message.

3:15 Le R on décale de 9, ça fait un A, le E on décale de 0, ça fait un E,

3:19 le N on décale de 17, ça devient aussi un E, etc.

3:23 Et on répète le mot-clé autant de fois que nécessaire, jusqu'à avoir tout fait.

3:29 Si la personne qui reçoit le message possède la clé, ça ne pose pas de problème pour elle,

3:33 il suffit de soustraire les décalages.

3:36 L'intérêt de cette méthode, vous le voyez, c'est que les deux E du message d'origine

3:40 seront représentées par des lettres différentes dans le message chiffré.

3:44 Et inversement, la même lettre dans le message chiffré

3:47 peut représenter deux lettres différentes dans le message d'origine.

3:51 Et cela va donc considérablement gêner les attaques utilisant des approches statistiques.

3:56 Pour que la méthode soit assez robuste, il faut bien sûr utiliser un mot-clé suffisamment long.

4:01 Mais ça n'a même pas besoin d'être un vrai mot, en fait.

4:04 Ça peut être simplement une longue suite de lettres prises au hasard,

4:08 qu'on appellera alors la clé de chiffrement.

4:11 Elle permettra à la fois à l'envoyeur de chiffrer son message et au destinataire de le déchiffrer.

4:17 Le gros problème de cette technique, c'est que si deux personnes souhaitent communiquer ainsi,

4:22 elles doivent, à un moment donné, se mettre d'accord sur la clé à utiliser.

4:27 Alors si c'est la CIA qui envoie un agent sur le terrain, il n'y a pas de problème,

4:31 ils peuvent convenir d'une clé à l'avance, avant le départ.

4:39 Mais si on a deux personnes à distance qui n'ont pas la possibilité de se voir physiquement,

4:45 si on ne fait que se téléphoner ou s'envoyer des messages par internet,

4:49 comment se fixer une clé de chiffrement qui soit secrète ?

4:54 On ne peut pas avoir juste un des deux qui décide d'une clé et qui écrive à l'autre

4:59 « on n'a qu'à utiliser la clé bateau ».

5:01 Parce que si ce message-là est intercepté, l'espion connaîtra la clé, évidemment.

5:06 Il faut donc trouver un moyen de se mettre d'accord sur une clé,

5:10 mais sans jamais vraiment l'écrire explicitement.

5:13 C'est ce qu'on appelle le problème de l'échange de clés, ou de l'établissement de clés.

5:18 Comment se mettre d'accord à distance sur une clé de chiffrement commune,

5:23 sachant qu'on est potentiellement écouté en permanence ?

5:27 À première vue, ça paraît quasi impossible à résoudre.

5:30 Si on n'a aucun moyen d'échanger des infos secrètement,

5:34 comment est-ce qu'on pourrait se mettre d'accord à distance sur une même clé

5:37 sans qu'un curieux ne puisse la connaître aussi ?

5:40 C'est ce problème qu'ont résolu les mathématiciens Diffie et Hellman en 1976.

5:47 Classiquement, en cryptographie, on décrit les choses de la façon suivante.

5:52 Imaginons deux personnes, traditionnellement nommées Alice et Bob,

5:56 qui ne se sont jamais vues ou parlées auparavant,

5:59 mais qui peuvent communiquer à distance sur une ligne qui n'est pas sécurisée.

6:03 D'ailleurs, on a une personne, usuellement nommée Eve,

6:06 qui s'est justement branchée sur cette ligne

6:09 et qui peut capter absolument tout ce qui va s'y raconter.

6:13 Comment Alice et Bob peuvent se mettre d'accord sur une clé commune

6:17 sans qu'Eve ne puisse connaître cette clé ?

6:20 Ça paraît impossible !

6:23 Petite précision avant de commencer.

6:25 Dans la méthode de Diffie-Hellman, la clé ne sera pas un mot ou une suite de lettres,

6:29 mais un nombre.

6:31 Au fond, ça ne change pas grand-chose.

6:33 C'est très facile de fabriquer l'un à partir de l'autre.

6:36 Pour vous montrer comment Alice et Bob peuvent procéder pour décider d'une clé numérique,

6:41 je vais commencer doucement par une méthode qui ne marche pas,

6:45 mais qui va nous mettre sur la voie.

6:47 Imaginons qu'Alice et Bob s'appellent et décident ensemble d'un nombre de bases

6:52 qu'on va appeler G.

6:54 Mettons qu'ils choisissent G égale 17.

6:56 Et évidemment, la ligne n'est pas sécurisée,

6:58 donc Eve entend tout et enregistre cette valeur de G.

7:02 Ensuite, Alice et Bob choisissent chacun de leur côté un nombre secret,

7:07 qu'on note A pour Alice et B pour Bob.

7:10 Ils vont ensuite chacun multiplier leur nombre secret par le nombre commun G.

7:15 Alice fabriquera donc le nombre G fois A et Bob G fois B.

7:19 Si Alice choisit 4 et Bob 6, ça fera 68 et 102.

7:24 Puis, ils communiquent à l'autre le résultat de cette multiplication.

7:28 Alice envoie G fois A à Bob, qui lui envoie G fois B.

7:33 Et cela se fait sans sécurisation.

7:35 Donc là, à nouveau, Eve est au courant de ses valeurs.

7:38 Et enfin, dernière étape, chacun multiplie ce nombre qu'il vient de recevoir

7:42 par son propre nombre secret.

7:44 Alice fabrique donc le nombre G fois B fois A, ça fera 408,

7:49 et Bob G fois A fois B, ça fera 408 aussi, évidemment.

7:53 Et voilà, ils peuvent maintenant décider d'utiliser ce résultat commun

7:57 comme clé de chiffrement.

7:59 Vous voyez qu'avec ce protocole, ils auront bien à la fin chacun le même nombre,

8:03 G fois A fois B.

8:05 Ils se sont donc bien mis d'accord sur une clé commune,

8:08 mais sans qu'à aucun moment cette clé n'ait explicitement transité

8:13 sur la ligne non sécurisée.

8:15 À aucun moment, ils n'ont communiqué l'un à l'autre le nombre 408.

8:20 Le souci, vous le voyez, c'est qu'Eve connaît G, c'est 17,

8:24 mais connaît également G fois A, 68, et G fois B, 102.

8:28 À partir de là, c'est très facile pour elle de retrouver

8:31 les nombres secrets d'Alice et Bob.

8:33 Par exemple, A s'obtient en divisant G A par G,

8:37 ici 68 par 17, on retrouve 4.

8:39 Et donc Eve pourra sans problème reconstituer elle-même la clé complète.

8:44 Donc la méthode que je viens de proposer n'est pas terrible,

8:47 car même si la clé ne transite pas explicitement,

8:50 Eve a suffisamment d'informations pour la refabriquer facilement.

8:54 Pour essayer de contourner ce problème, essayons une variante plus compliquée.

8:58 On garde le nombre commun G et les nombres secrets A et B,

9:02 mais cette fois on va prendre la puissance au lieu de faire la multiplication.

9:06 Ça veut dire qu'Alice fabrique le nombre G puissance A,

9:10 qu'elle envoie à Bob, et Bob fabrique G puissance B,

9:13 qu'il lui envoie en retour.

9:16 Et ensuite, chacun prend la puissance avec son propre nombre secret.

9:20 Donc Alice fait G puissance B puissance A,

9:23 tant qu'il que Bob fait G puissance A puissance B.

9:26 Et à nouveau, avec ce protocole, ils auront à la fin le même résultat,

9:30 G puissance A fois B,

9:32 donc une clé commune sans l'avoir jamais explicitement communiquée sur la ligne.

9:36 Eve, de son côté, connaît seulement ce qu'elle a intercepté,

9:40 à savoir G, G puissance A et G puissance B.

9:43 Sauf qu'à nouveau, elle peut s'en sortir rien qu'avec ces infos.

9:47 Si Eve connaît le nombre G puissance A,

9:50 elle peut prendre son logarithme,

9:52 qui vaut A fois logarithme de G.

9:55 Et ensuite, en divisant par le logarithme de G,

9:58 elle peut isoler A.

9:59 Donc à nouveau, elle peut reconstituer facilement les nombres secrets,

10:03 et donc la clé commune.

10:04 Ça ne va toujours pas.

10:06 L'origine fondamentale du problème, c'est qu'Alice et Bob

10:09 essayent à chaque fois de maquiller leur nombre secret

10:12 en le mélangeant en quelque sorte avec G.

10:15 Mais à chaque fois, Eve peut défaire ce mélange

10:18 et retrouver les nombres secrets.

10:20 Si on utilise la multiplication, Eve peut utiliser la division.

10:23 Si on utilise la puissance, Eve utilise le logarithme.

10:27 Pour que l'idée fonctionne, il faudrait une opération de mélange

10:30 qui soit facile à faire pour Alice et Bob,

10:32 mais quasi impossible à inverser pour Eve.

10:35 C'est ce qu'on appelle en cryptographie une fonction à sens unique.

10:39 Eh bien, on peut justement en créer une à partir de notre tentative précédente

10:44 en ajoutant juste un ingrédient, le modulo.

10:53 Le modulo, c'est une opération qui calcule

10:55 le reste de la division entière par un nombre.

10:58 Par exemple, 17 modulo 3, ça fait 2.

11:01 Parce que si vous faites la division entière de 17 par 3,

11:04 vous trouvez 5 et vous reste 2 à la fin.

11:06 De même, 14 modulo 5, ça fait 4.

11:09 Ou encore 42 modulo 6, ça fait 0, etc.

11:12 L'idée de la méthode de Diffie-Hellman,

11:14 c'est de choisir un nombre P

11:16 qu'Alice et Bob se communiquent publiquement, comme G,

11:19 et ensuite de faire exactement comme dans mon exemple,

11:22 avec les puissances, mais cette fois,

11:24 après chaque opération, on va appliquer modulo P.

11:28 C'est-à-dire qu'avec son nombre secret A,

11:30 Alice calcule G puissance A modulo P et l'envoie à Bob.

11:35 Bob, de son côté, calcule G puissance B modulo P et l'envoie à Alice.

11:40 Et ensuite, chacun applique la puissance de son nombre secret

11:44 et prend à nouveau modulo P.

11:46 Et là, ça ne se voit pas forcément,

11:48 mais en faisant ça, ils auront exactement le même nombre à la fin,

11:53 qui est en fait G puissance A fois B modulo P.

11:57 D'ailleurs, ceux qui font MathExpert en terminale

11:59 peuvent essayer de démontrer ça avec les congruences.

12:02 Grâce à cette technique, qui est presque la même que la précédente,

12:06 mais en appliquant le modulo P après chaque opération,

12:09 Alice et Bob auront à nouveau réussi à se mettre d'accord sur une clé commune,

12:13 sans jamais la faire circuler explicitement.

12:16 Sauf que pour Eve, qu'est-ce que ça change ?

12:19 Est-ce qu'elle ne peut pas à nouveau extraire A ou B des infos dont elle dispose

12:23 et reconstituer la clé comme avant ?

12:26 Eh bien non, car pour quelqu'un qui intercepterait même toutes les conversations,

12:31 ça devient très très compliqué à démêler,

12:34 à cause du modulo qui en quelque sorte mélange tout.

12:38 Mathématiquement, même en connaissant G, P et G puissance A modulo P,

12:44 il est très difficile de retrouver A.

12:47 L'opération de puissance avec modulo est très difficile à inverser.

12:51 C'est une opération à sens unique, comme on le souhaitait.

12:54 On peut le voir sur un exemple si vous voulez.

12:56 Prenons P égale 17 et G égale 5,

12:59 sur lesquels Alice et Bob se mettent d'accord publiquement.

13:02 Donc Eve est parfaitement au courant de ces deux valeurs.

13:05 Alice choisit son nombre secret, disons 4,

13:09 et Bob choisit 6.

13:11 Alice met 5 à la puissance 4, ça fait 625,

13:14 et prend modulo 17, il reste 13.

13:17 Pareil pour Bob, il calcule 5 puissance 6,

13:20 prend modulo 17, ça fait 2.

13:22 Et chacun envoie le résultat à l'autre, qui applique sa propre puissance.

13:26 Alice prend 2 puissance 4 modulo 17, ça fait 16.

13:30 Bob fait 13 puissance 6 modulo 17, ça fait 16 aussi.

13:34 On a donc bien une clé commune pour les deux interlocuteurs.

13:38 De son côté, Eve connaît P égale 17 et G égale 5, bien sûr,

13:43 mais ne dispose que de 13 et 2 comme intermédiaire.

13:47 Pour retrouver par exemple A, le nombre secret d'Alice,

13:50 elle doit trouver un nombre qui, quand on l'applique en puissance à 5,

13:54 redonne 13 modulo 17.

13:57 Et ça n'a pas l'air comme ça, mais c'est très difficile comme équation.

14:01 L'opération qu'on doit résoudre pour trouver la solution,

14:04 c'est ce qu'on appelle le problème du logarithme discret.

14:07 Dans ma méthode précédente avec juste les puissances,

14:10 Eve s'en sortait en appliquant un simple logarithme.

14:13 Maintenant, à cause du modulo, il faut résoudre le logarithme discret,

14:17 ce qui est possible en théorie, mais très fastidieux en pratique.

14:21 Il faut quasiment essayer toutes les possibilités.

14:24 Alors je dis que c'est très compliqué, il faut quand même faire un peu attention.

14:28 Quand on prend un nombre modulo P, le résultat est forcément entre 0 et P-1.

14:34 C'est le reste d'une division entière.

14:37 Donc si on veut qu'il y ait un maximum de possibilités différentes à tester pour Eve,

14:42 il faut déjà prendre un P le plus grand possible.

14:45 Mais ce n'est pas tout, il faut aussi bien le choisir,

14:48 et surtout bien choisir le G qui va avec.

14:51 Je vous illustre ça avec un exemple.

14:53 Si je prends P égale 15 et G égale 4,

14:57 on sait que la clé sera à la fin G puissance AB modulo P,

15:01 donc G puissance quelque chose modulo P.

15:04 Et on peut regarder ce que valent les différentes puissances de G modulo P.

15:09 Avec mon choix de valeur, G puissance 1 modulo P c'est 4,

15:12 G puissance 2 modulo P c'est 1,

15:14 G puissance 3 modulo P c'est 4,

15:16 G puissance 4 modulo P c'est 1, etc.

15:20 On se rend compte que bien qu'on ait choisi P égale 15,

15:23 les puissances de G tombent toujours sur 1 ou 4.

15:27 Donc on croyait avoir 15 clés possibles que Eve devait essayer,

15:31 mais on en a seulement 2.

15:33 Il faut absolument éviter ce genre de situation,

15:36 car en réduisant ainsi l'espace des possibilités,

15:39 on facilite considérablement la tâche d'Eve qui cherche à percer notre clé.

15:44 Heureusement, il existe une solution.

15:46 L'idéal, c'est de prendre un nombre P qui soit premier,

15:50 et un nombre G qui soit ce qu'on appelle une racine primitive modulo P.

15:55 Une racine primitive, ça veut dire que si vous élevez G

15:58 à toutes les puissances entre 1 et P-1,

16:01 vous allez trouver tous les nombres possibles entre 1 et P-1.

16:05 Donc on sera dans un cas où il y aura un maximum de possibilités.

16:09 On peut le voir sur un exemple.

16:11 Avec P égale 13, par exemple, je ne vous le démontre pas,

16:14 mais les racines primitives sont uniquement 2, 6, 7 et 11.

16:18 Donc si on prend G égale 6,

16:20 les puissances de 6 modulo 13 s'étalent bien entre 1 et 12, c'est parfait.

16:25 Mais avec G égale 5, ça ne marche pas bien,

16:27 car les puissances ne bouclent que sur 5, 12, 8 et 1.

16:31 Donc il y a seulement 4 possibilités au lieu de 12.

16:35 D'où l'intérêt qu'il y a à bien choisir pour G

16:38 une racine primitive du nombre P qu'on a sélectionné.

16:42 Avec ces petites précautions,

16:44 on a ainsi l'essence de l'algorithme de Diffie-Hellman,

16:47 qui résout donc le problème de la détermination d'une clé de chiffrement commune

16:52 quand on est sur un canal public.

16:54 Cet algorithme a été d'abord publié en 1976

16:57 et breveté aux États-Unis l'année suivante.

16:59 Mais heureusement, il est maintenant dans le domaine public

17:02 et il est très largement utilisé pour sécuriser

17:05 une grande partie des communications sur Internet.

17:08 Ainsi, quand deux ordinateurs ont besoin de mettre en place

17:11 un canal de communication chiffré,

17:13 pour ne pas que vos données soient diffusées en clair sur le réseau,

17:16 ils utilisent souvent une variante de l'algorithme de Diffie-Hellman.

17:20 Et c'est d'ailleurs ce principe qui sécurise notamment le protocole TLS,

17:24 qui se trouve derrière la plupart des visites que vous pouvez faire sur des sites web.

17:28 Donc merci Diffie-Hellman.

17:31 Malgré tout, comme toujours, la méthode n'est pas non plus totalement inviolable.

17:35 Par exemple, il faut faire attention à ce qu'Ève n'arrive pas

17:38 à usurper les identités d'Alice et Bob.

17:41 Ça lui permettrait de se mettre entre les deux

17:44 en se faisant passer pour Bob aux yeux d'Alice et inversement.

17:47 Et là, c'est open bar pour Ève.

17:50 En dehors de ce risque, il faut aussi s'assurer

17:52 que quand Alice et Bob choisissent chacun leur nombre secret de leur côté,

17:56 Ève ne puisse pas le deviner facilement.

17:59 Et donc, idéalement, il faut qu'ils fassent leur choix

18:02 en utilisant un bon générateur de nombres aléatoires.

18:06 Et d'ailleurs, cette question de comment faire un générateur aléatoire,

18:10 je me dis que ça ferait un très bon sujet pour un prochain épisode.

18:13 Merci d'avoir suivi la vidéo.

18:15 Abonnez-vous pour ne rien rater des futures publications.

18:17 Rejoignez-moi sur le Discord de Science Étonnante,

18:20 je vous mets le lien en description.

18:22 Et puis je vous dis à très vite pour une nouvelle vidéo.

18:24 A bientôt !

L'Algorithme qui Sécurise Internet (entre autres...)

0 commentaire

Synchronisation des sous-titres

Signaler une erreur

L'Algorithme qui Sécurise Internet (entre autres...)

0 commentaire

⏱ Synchronisation des sous-titres

🚩 Signaler une erreur

Synchronisation des sous-titres

Signaler une erreur