L'Algorithme qui Sécurise Internet (entre autres...)
ログインして字幕言語の切り替え、再生速度の調整、字幕のサイズと色の変更ができます。
Cette vidéo explique l'algorithme de Diffie-Hellman, une technique de cryptographie fondamentale qui permet à deux parties d'établir une clé de chiffrement secrète sur un canal de communication non sécurisé, même en présence d'un espion.
- 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 !
- 0:00 Hello everyone, today we're going to talk about an incredible cryptography technique
- 0:05 that allows two people to exchange secrets
- 0:08 even when they are constantly being listened to by a spy.
- 0:12 This method, called the Diffie-Hellman algorithm,
- 0:16 seems quite implausible,
- 0:18 and the first few times I heard about it,
- 0:20 I thought it wasn't possible for such a technique to exist.
- 0:24 And yet, we'll see that it really works.
- 0:31 If two people want to exchange a message in the utmost secrecy,
- 0:36 you might say it's easy, just encode the message.
- 0:39 Technically, this is called an encryption operation.
- 0:42 We start with a plain text message, for example, 'meet tonight at the park',
- 0:47 and we're going to try to transform it into incomprehensible gibberish
- 0:51 that can still be deciphered by our interlocutor.
- 0:55 One of the oldest techniques is what's called the Caesar cipher,
- 0:59 as it was supposedly popularized by the famous Roman general.
- 1:03 The idea is simply to shift all the letters of the alphabet by a certain amount.
- 1:08 For example, if we shift by 3, we replace A with D,
- 1:12 B with E, C with F, and so on,
- 1:15 up to W which becomes Z, and X, Y, Z which become A, B, and C.
- 1:20 With this, the message seems completely scrambled,
- 1:23 but our interlocutor can easily reconstruct it
- 1:27 by applying the inverse shift.
- 1:30 However, this technique is quite superficial.
- 1:32 If a spy guesses that the message was encrypted this way,
- 1:36 they only have 26 possible shifts to try, or even just 25, in fact.
- 1:41 So they'll quickly test everything until they discover the secret message.
- 1:46 To make it more robust than the Caesar method,
- 1:49 we can use what's called a substitution cipher.
- 1:53 This involves replacing each letter of the alphabet
- 1:56 with another letter, but without any particular logic.
- 1:59 To encrypt and decrypt the message, you therefore need to know the entire conversion table.
- 2:05 And it's very effective, because this time there are 26 factorial possibilities,
- 2:10 which is on the order of a billion billion billion.
- 2:13 But despite that, we also know very well how to break these substitution ciphers
- 2:18 by performing statistics on letter frequencies and their sequences.
- 2:22 For example, since it's always the same letter representing E,
- 2:25 in a sufficiently long French message, we can easily identify it.
- 2:30 And the same goes for frequent letters like A or S, and so on.
- 2:34 I had actually made a video on how to break this type of encryption
- 2:38 very quickly and automatically
- 2:40 using what are called Markov chain Monte Carlo methods.
- 2:45 To protect against these attacks, we need to try another type of encryption.
- 2:50 One option, for example, is to use a keyword that dictates the letter shifts.
- 2:56 Let's take the word 'jardin' (garden), and write it below our message.
- 3:00 Each letter of the word will represent a shift based on its position in the alphabet.
- 3:06 J is 9, A is 0, R is 17, etc.
- 3:10 And then we apply each shift to the letters of our message.
- 3:15 R shifted by 9 becomes A, E shifted by 0 becomes E,
- 3:19 N shifted by 17 also becomes E, and so on.
- 3:23 And we repeat the keyword as many times as necessary, until everything is done.
- 3:29 If the person receiving the message has the key, it's no problem for them,
- 3:33 they just subtract the shifts.
- 3:36 The advantage of this method, as you can see, is that the two E's in the original message
- 3:40 will be represented by different letters in the encrypted message.
- 3:44 And conversely, the same letter in the encrypted message
- 3:47 can represent two different letters in the original message.
- 3:51 And this will therefore significantly hinder attacks using statistical approaches.
- 3:56 For the method to be robust enough, you must, of course, use a sufficiently long keyword.
- 4:01 But it doesn't even need to be a real word, in fact.
- 4:04 It can simply be a long sequence of random letters,
- 4:08 which will then be called the encryption key.
- 4:11 It will allow both the sender to encrypt their message and the recipient to decrypt it.
- 4:17 The big problem with this technique is that if two people want to communicate this way,
- 4:22 they must, at some point, agree on the key to use.
- 4:27 So if it's the CIA sending an agent into the field, there's no problem,
- 4:31 they can agree on a key in advance, before departure.
- 4:39 But if you have two people at a distance who can't see each other physically,
- 4:45 if you only call each other or send messages over the internet,
- 4:49 how do you establish an encryption key that is secret?
- 4:54 You can't just have one of them decide on a key and write to the other
- 4:59 "let's just use the common key."
- 5:01 Because if that message is intercepted, the spy will know the key, obviously.
- 5:06 So, a way must be found to agree on a key,
- 5:10 but without ever explicitly writing it down.
- 5:13 This is called the key exchange problem, or key establishment.
- 5:18 How can two people remotely agree on a common encryption key,
- 5:23 knowing that they are potentially being listened to constantly?
- 5:27 At first glance, it seems almost impossible to solve.
- 5:30 If there's no way to exchange information secretly,
- 5:34 how could we remotely agree on the same key
- 5:37 without an eavesdropper also knowing it?
- 5:40 This is the problem that mathematicians Diffie and Hellman solved in 1976.
- 5:47 Classically, in cryptography, things are described as follows.
- 5:52 Imagine two people, traditionally named Alice and Bob,
- 5:56 who have never seen or spoken to each other before,
- 5:59 but who can communicate remotely over an unsecured line.
- 6:03 Moreover, there's a person, usually named Eve,
- 6:06 who has tapped into this line
- 6:09 and can intercept absolutely everything that is said on it.
- 6:13 How can Alice and Bob agree on a common key
- 6:17 without Eve being able to know this key?
- 6:20 It seems impossible!
- 6:23 A small clarification before we begin.
- 6:25 In the Diffie-Hellman method, the key will not be a word or a sequence of letters,
- 6:29 but a number.
- 6:31 Ultimately, it doesn't change much.
- 6:33 It's very easy to create one from the other.
- 6:36 To show you how Alice and Bob can proceed to decide on a numerical key,
- 6:41 I'll start gently with a method that doesn't work,
- 6:45 but which will put us on the right track.
- 6:47 Imagine Alice and Bob call each other and together decide on a base number
- 6:52 which we'll call G.
- 6:54 Let's say they choose G equals 17.
- 6:56 And obviously, the line is not secure,
- 6:58 so Eve hears everything and records this value of G.
- 7:02 Then, Alice and Bob each choose a secret number on their own,
- 7:07 which we'll denote A for Alice and B for Bob.
- 7:10 They will then each multiply their secret number by the common number G.
- 7:15 Alice will therefore create the number G times A, and Bob G times B.
- 7:19 If Alice chooses 4 and Bob 6, that will be 68 and 102.
- 7:24 Then, they communicate the result of this multiplication to each other.
- 7:28 Alice sends G times A to Bob, who sends G times B to her.
- 7:33 And this is done without security.
- 7:35 So here, again, Eve is aware of these values.
- 7:38 And finally, the last step, each multiplies the number they just received
- 7:42 by their own secret number.
- 7:44 Alice therefore creates the number G times B times A, which will be 408,
- 7:49 and Bob G times A times B, which will also be 408, obviously.
- 7:53 And there you have it, they can now decide to use this common result
- 7:57 as an encryption key.
- 7:59 You see that with this protocol, they will each end up with the same number,
- 8:03 G times A times B.
- 8:05 So they have successfully agreed on a common key,
- 8:08 but without this key ever explicitly transiting
- 8:13 over the unsecured line.
- 8:15 At no point did they communicate the number 408 to each other.
- 8:20 The problem, as you can see, is that Eve knows G, which is 17,
- 8:24 but also knows G times A, 68, and G times B, 102.
- 8:28 From there, it's very easy for her to find
- 8:31 Alice and Bob's secret numbers.
- 8:33 For example, A is obtained by dividing G A by G,
- 8:37 here 68 by 17, we get 4.
- 8:39 And so Eve can easily reconstruct the complete key herself.
- 8:44 So the method I just proposed isn't great,
- 8:47 because even if the key doesn't explicitly transit,
- 8:50 Eve has enough information to easily recreate it.
- 8:54 To try and circumvent this problem, let's try a more complicated variant.
- 8:58 We keep the common number G and the secret numbers A and B,
- 9:02 but this time we're going to use exponentiation instead of multiplication.
- 9:06 This means Alice generates the number G to the power of A,
- 9:10 which she sends to Bob, and Bob generates G to the power of B,
- 9:13 which he sends back to her.
- 9:16 And then, each one takes the power with their own secret number.
- 9:20 So Alice does G to the power of B to the power of A,
- 9:23 while Bob does G to the power of A to the power of B.
- 9:26 And again, with this protocol, they will end up with the same result,
- 9:30 G to the power of A times B,
- 9:32 thus a common key without ever explicitly communicating it over the line.
- 9:36 Eve, for her part, only knows what she has intercepted,
- 9:40 namely G, G to the power of A, and G to the power of B.
- 9:43 Except that again, she can figure it out with just this information.
- 9:47 If Eve knows the number G to the power of A,
- 9:50 she can take its logarithm,
- 9:52 which is A times the logarithm of G.
- 9:55 And then, by dividing by the logarithm of G,
- 9:58 she can isolate A.
- 9:59 So again, she can easily reconstruct the secret numbers,
- 10:03 and thus the common key.
- 10:04 That still won't work.
- 10:06 The fundamental origin of the problem is that Alice and Bob
- 10:09 each time try to disguise their secret number
- 10:12 by mixing it, in a way, with G.
- 10:15 But each time, Eve can undo this mixture
- 10:18 and find the secret numbers.
- 10:20 If we use multiplication, Eve can use division.
- 10:23 If we use exponentiation, Eve uses the logarithm.
- 10:27 For the idea to work, we would need a mixing operation
- 10:30 that is easy for Alice and Bob to perform,
- 10:32 but almost impossible for Eve to reverse.
- 10:35 This is what we call a one-way function in cryptography.
- 10:39 Well, we can actually create one from our previous attempt
- 10:44 by just adding one ingredient: the modulo.
- 10:53 The modulo is an operation that calculates
- 10:55 the remainder of integer division by a number.
- 10:58 For example, 17 modulo 3 is 2.
- 11:01 Because if you perform integer division of 17 by 3,
- 11:04 you get 5 with a remainder of 2 at the end.
- 11:06 Similarly, 14 modulo 5 is 4.
- 11:09 Or 42 modulo 6 is 0, and so on.
- 11:12 The idea behind the Diffie-Hellman method
- 11:14 is to choose a number P
- 11:16 that Alice and Bob communicate publicly, like G,
- 11:19 and then do exactly as in my example,
- 11:22 with powers, but this time,
- 11:24 after each operation, we'll apply modulo P.
- 11:28 That is, with her secret number A,
- 11:30 Alice calculates G to the power of A modulo P and sends it to Bob.
- 11:35 Bob, on his side, calculates G to the power of B modulo P and sends it to Alice.
- 11:40 And then, each applies the power of their secret number
- 11:44 and takes modulo P again.
- 11:46 And here, it's not necessarily obvious,
- 11:48 but by doing this, they will have exactly the same number at the end,
- 11:53 which is actually G to the power of A times B modulo P.
- 11:57 By the way, those taking MathExpert in their final year of high school
- 11:59 can try to demonstrate this using congruences.
- 12:02 Thanks to this technique, which is almost the same as the previous one,
- 12:06 but by applying modulo P after each operation,
- 12:09 Alice and Bob will have once again managed to agree on a common key,
- 12:13 without ever explicitly transmitting it.
- 12:16 But for Eve, what does this change?
- 12:19 Can't she again extract A or B from the information she has
- 12:23 and reconstruct the key as before?
- 12:26 Well, no, because for someone who intercepts even all conversations,
- 12:31 it becomes very, very complicated to untangle,
- 12:34 because of the modulo which, in a way, scrambles everything.
- 12:38 Mathematically, even knowing G, P, and G to the power of A modulo P,
- 12:44 it is very difficult to find A.
- 12:47 The power operation with modulo is very difficult to reverse.
- 12:51 It's a one-way operation, as we wanted.
- 12:54 We can see it with an example if you like.
- 12:56 Let's take P equals 17 and G equals 5,
- 12:59 which Alice and Bob agree upon publicly.
- 13:02 So Eve is perfectly aware of these two values.
- 13:05 Alice chooses her secret number, let's say 4,
- 13:09 and Bob chooses 6.
- 13:11 Alice raises 5 to the power of 4, which is 625,
- 13:14 and takes modulo 17, leaving 13.
- 13:17 Same for Bob, he calculates 5 to the power of 6,
- 13:20 takes modulo 17, which is 2.
- 13:22 And each sends the result to the other, who applies their own power.
- 13:26 Alice takes 2 to the power of 4 modulo 17, which is 16.
- 13:30 Bob does 13 to the power of 6 modulo 17, which is also 16.
- 13:34 So we indeed have a common key for both parties.
- 13:38 On her side, Eve knows P equals 17 and G equals 5, of course,
- 13:43 but only has 13 and 2 as intermediaries.
- 13:47 To find, for example, A, Alice's secret number,
- 13:50 she must find a number which, when applied as a power to 5,
- 13:54 gives 13 modulo 17.
- 13:57 And it doesn't seem like it, but it's a very difficult equation.
- 14:01 The operation we need to solve to find the solution
- 14:04 is what we call the discrete logarithm problem.
- 14:07 In my previous method with just powers,
- 14:10 Eve managed by applying a simple logarithm.
- 14:13 Now, because of the modulo, we have to solve the discrete logarithm,
- 14:17 which is theoretically possible, but very tedious in practice.
- 14:21 You practically have to try all possibilities.
- 14:24 So I say it's very complicated, but we still need to be a bit careful.
- 14:28 When you take a number modulo P, the result is necessarily between 0 and P-1.
- 14:34 It's the remainder of an integer division.
- 14:37 So if we want there to be a maximum number of different possibilities for Eve to test,
- 14:42 we must first choose the largest possible P.
- 14:45 But that's not all; we also need to choose it well,
- 14:48 and especially choose the G that goes with it.
- 14:51 Let me illustrate this with an example.
- 14:53 If I take P equals 15 and G equals 4,
- 14:57 we know that the key will ultimately be G to the power of AB modulo P,
- 15:01 so G to the power of something modulo P.
- 15:04 And we can look at the values of the different powers of G modulo P.
- 15:09 With my choice of values, G to the power of 1 modulo P is 4,
- 15:12 G to the power of 2 modulo P is 1,
- 15:14 G to the power of 3 modulo P is 4,
- 15:16 G to the power of 4 modulo P is 1, etc.
- 15:20 We realize that even though we chose P equals 15,
- 15:23 the powers of G always result in 1 or 4.
- 15:27 So we thought we had 15 possible keys for Eve to try,
- 15:31 but we only have 2.
- 15:33 We absolutely must avoid this kind of situation,
- 15:36 because by thus reducing the possibility space,
- 15:39 we significantly ease Eve's task of trying to crack our key.
- 15:44 Fortunately, there is a solution.
- 15:46 Ideally, we should choose a prime number P,
- 15:50 and a number G that is what we call a primitive root modulo P.
- 15:55 A primitive root means that if you raise G
- 15:58 to all powers between 1 and P-1,
- 16:01 you will find all possible numbers between 1 and P-1.
- 16:05 So we will be in a case where there will be a maximum number of possibilities.
- 16:09 We can see this with an example.
- 16:11 With P equals 13, for example, I won't demonstrate it to you,
- 16:14 but the primitive roots are only 2, 6, 7, and 11.
- 16:18 So if we take G equals 6,
- 16:20 the powers of 6 modulo 13 spread nicely between 1 and 12; it's perfect.
- 16:25 But with G equals 5, it doesn't work well,
- 16:27 because the powers only cycle through 5, 12, 8, and 1.
- 16:31 So there are only 4 possibilities instead of 12.
- 16:35 Hence the importance of choosing for G
- 16:38 a primitive root of the number P we have selected.
- 16:42 With these small precautions,
- 16:44 we thus have the essence of the Diffie-Hellman algorithm,
- 16:47 which solves the problem of determining a common encryption key
- 16:52 when on a public channel.
- 16:54 This algorithm was first published in 1976
- 16:57 and patented in the United States the following year.
- 16:59 But fortunately, it is now in the public domain
- 17:02 and is very widely used to secure
- 17:05 a large part of Internet communications.
- 17:08 Thus, when two computers need to establish
- 17:11 an encrypted communication channel,
- 17:13 to prevent your data from being transmitted in plain text over the network,
- 17:16 they often use a variant of the Diffie-Hellman algorithm.
- 17:20 And it is this principle that notably secures the TLS protocol,
- 17:24 which is behind most of the visits you make to websites.
- 17:28 So, thank you, Diffie-Hellman.
- 17:31 Nevertheless, as always, the method is not entirely foolproof either.
- 17:35 For example, we must be careful that Eve does not manage
- 17:38 to impersonate Alice and Bob.
- 17:41 That would allow her to position herself between the two
- 17:44 by pretending to be Bob to Alice and vice versa.
- 17:47 And then, it's open season for Eve.
- 17:50 Aside from this risk, we must also ensure
- 17:52 that when Alice and Bob each choose their secret number independently,
- 17:56 Eve cannot easily guess it.
- 17:59 And so, ideally, they must make their choice
- 18:02 using a good random number generator.
- 18:06 And by the way, this question of how to make a random generator,
- 18:10 I think that would make a very good topic for a future episode.
- 18:13 Thank you for watching the video.
- 18:15 Subscribe so you don't miss any future publications.
- 18:17 Join me on the Science Étonnante Discord,
- 18:20 I'll put the link in the description.
- 18:22 And I'll see you very soon for a new video.
- 18:24 See you soon!
- 0:00 皆さん、こんにちは。今日は、驚くべき暗号技術についてお話します。
- 0:05 それは、二人が秘密を交換できるというものです。
- 0:08 たとえ常にスパイに盗聴されていてもです。
- 0:12 このディフィー・ヘルマンアルゴリズムと呼ばれる方法は
- 0:16 かなり信じがたいものです。
- 0:18 初めてこの話を聞いたとき
- 0:20 こんな技術が存在するはずがないと思いました。
- 0:24 しかし、これが本当に機能することを見ていきましょう。
- 0:31 もし二人が極秘にメッセージを交換したいなら
- 0:36 あなたは「簡単だ、メッセージを暗号化すればいい」と言うでしょう。
- 0:39 技術的には、これを「暗号化操作」と呼びます。
- 0:42 例えば「今夜公園で会おう」という平文メッセージから始めます。
- 0:47 そして、それを理解不能な意味不明なものに変換しようとします。
- 0:51 しかし、それは相手によって解読できるものです。
- 0:55 最も古い技術の一つは、シーザーシフトと呼ばれるものです。
- 0:59 それは有名なローマの将軍によって広められたと言われています。
- 1:03 その考え方は、アルファベットのすべての文字を一定量ずらすだけです。
- 1:08 例えば、3つずらすと、AはDに、
- 1:12 BはEに、CはFに、といった具合です。
- 1:15 WはZになり、XYZはA、B、Cになります。
- 1:20 これによって、メッセージは完全に混乱しているように見えますが、
- 1:23 相手は問題なくそれを復元できます。
- 1:27 逆のシフトを適用することで。
- 1:30 しかし、この技術はかなり表面的です。
- 1:32 もしスパイがメッセージがこの方法で暗号化されたと推測した場合、
- 1:36 試すべきシフトの可能性は26通りしかなく、実際には25通りしかありません。
- 1:41 そのため、彼はすぐにすべてを試して秘密のメッセージを発見するでしょう。
- 1:46 シーザー法よりも堅牢にするには、
- 1:49 換字式暗号と呼ばれるものを使用できます。
- 1:53 これは、アルファベットの各文字を
- 1:56 別の文字に置き換えるものですが、特定の論理はありません。
- 1:59 メッセージを暗号化および復号化するには、変換テーブル全体を知っている必要があります。
- 2:05 そして、これは非常に効果的です。なぜなら、今回は26の階乗の可能性があるからです。
- 2:10 つまり、10億の10億の10億、という桁になります。
- 2:13 しかし、それでも、これらの換字式暗号を破る方法はよく知られています。
- 2:18 文字の頻度とその連鎖に関する統計を取ることで。
- 2:22 例えば、Eを表す文字は常に同じなので、
- 2:25 十分に長いフランス語のメッセージであれば、簡単に特定できます。
- 2:30 AやSのような頻繁に出てくる文字についても同様です。
- 2:34 ちなみに、私はこの種の暗号を破る方法についてビデオを作りました。
- 2:38 自動的に非常に迅速に
- 2:40 マルコフ連鎖モンテカルロ法と呼ばれるものを使用して。
- 2:45 これらの攻撃から身を守るには、別の種類の暗号化を試す必要があります。
- 2:50 一つの選択肢は、例えば、文字のシフトを指示するキーワードを使用することです。
- 2:56 「jardin」という単語を取り上げ、それをメッセージの下に書きましょう。
- 3:00 その単語の各文字は、アルファベット内での位置に応じてシフトを表します。
- 3:06 Jは9、Aは0、Rは17、といった具合です。
- 3:10 そして、各シフトをメッセージの文字に適用します。
- 3:15 Rを9シフトするとAになり、Eを0シフトするとEになり、
- 3:19 Nを17シフトするとこれもEになります。
- 3:23 そして、すべてが完了するまで、必要に応じてキーワードを繰り返します。
- 3:29 メッセージを受け取る人が鍵を持っていれば、彼女にとって問題はありません。
- 3:33 シフトを引くだけでいいのです。
- 3:36 この方法の利点は、ご覧の通り、元のメッセージの2つのEが
- 3:40 暗号化されたメッセージでは異なる文字で表されることです。
- 3:44 そして逆に、暗号化されたメッセージの同じ文字が
- 3:47 元のメッセージでは2つの異なる文字を表すことがあります。
- 3:51 これにより、統計的アプローチを使用する攻撃を大幅に妨げることができます。
- 3:56 この方法が十分に堅牢であるためには、もちろん十分に長いキーワードを使用する必要があります。
- 4:01 しかし、実際には本当の単語である必要さえありません。
- 4:04 それは単にランダムに選ばれた長い文字列かもしれません。
- 4:08 それは暗号化キーと呼ばれます。
- 4:11 それは送信者がメッセージを暗号化し、受信者がそれを解読することを可能にします。
- 4:17 この技術の大きな問題は、もし二人がこのように通信したい場合、
- 4:22 ある時点で、使用するキーについて合意しなければならないということです。
- 4:27 もしCIAが現場にエージェントを送る場合、問題はありません。
- 4:31 彼らは出発前に、事前にキーを取り決めることができます。
- 4:39 しかし、もし物理的に会うことができない遠隔地の二人がいて、
- 4:45 電話で話したり、インターネットでメッセージを送り合ったりするだけの場合、
- 4:49 秘密の暗号化キーをどのように設定すればよいのでしょうか?
- 4:54 どちらか一方がキーを決めて、相手に書き送るだけではいけません。
- 4:59 「このありふれたキーを使おう」と。
- 5:01 なぜなら、もしそのメッセージが傍受されれば、スパイは当然キーを知ってしまうからです。
- 5:06 したがって、キーについて合意する方法を見つける必要があります。
- 5:10 しかし、それを明示的に書き記すことなく。
- 5:13 これが「鍵交換問題」または「鍵確立問題」と呼ばれるものです。
- 5:18 遠隔地で共通の暗号化キーについて、どのように合意すればよいのでしょうか?
- 5:23 常に傍受されている可能性があることを考えると。
- 5:27 一見すると、解決はほぼ不可能に見えます。
- 5:30 もし秘密裏に情報を交換する手段が全くないとしたら、
- 5:34 遠隔地で同じキーについて、どのように合意できるでしょうか?
- 5:37 詮索好きな人物にそれを知られることなく。
- 5:40 この問題を1976年に解決したのが、数学者のディフィーとヘルマンです。
- 5:47 伝統的に、暗号学では物事を次のように説明します。
- 5:52 伝統的にアリスとボブと呼ばれる二人の人物を想像してみましょう。
- 5:56 彼らは以前に会ったことも話したこともありませんが、
- 5:59 安全ではない回線を通じて遠隔で通信できます。
- 6:03 さらに、通常イブと呼ばれる人物がいて、
- 6:06 ちょうどその回線に接続しており、
- 6:09 そこで話されることすべてを傍受できます。
- 6:13 アリスとボブはどのようにして共通のキーについて合意できるのでしょうか?
- 6:17 イブにそのキーを知られることなく。
- 6:20 不可能に思えます!
- 6:23 始める前に少し補足します。
- 6:25 ディフィー・ヘルマン法では、キーは単語や文字列ではなく、
- 6:29 数値になります。
- 6:31 結局のところ、大した違いはありません。
- 6:33 一方からもう一方を生成するのは非常に簡単です。
- 6:36 アリスとボブがどのようにして数値キーを決定するかを示すために、
- 6:41 まず、うまくいかない方法からゆっくりと説明します。
- 6:45 しかし、それがヒントになります。
- 6:47 アリスとボブが電話で話し、一緒に基本となる数値を決めることを想像してみましょう。
- 6:52 それをGと呼びます。
- 6:54 彼らがGを17に選んだとしましょう。
- 6:56 そして当然、回線は安全ではないので、
- 6:58 イブはすべてを聞き、このGの値を記録します。
- 7:02 次に、アリスとボブはそれぞれ秘密の数を選びます。
- 7:07 アリスはA、ボブはBとします。
- 7:10 彼らはそれぞれ、自分の秘密の数に共通の数Gを掛けます。
- 7:15 アリスはGかけるAという数を作り、ボブはGかけるBという数を作ります。
- 7:19 もしアリスが4、ボブが6を選んだ場合、それぞれ68と102になります。
- 7:24 そして、彼らはこの掛け算の結果を相手に伝えます。
- 7:28 アリスはGかけるAをボブに送り、ボブはGかけるBをアリスに送ります。
- 7:33 そして、これは安全ではない状態で行われます。
- 7:35 ですから、ここでもイブはこれらの値を知っています。
- 7:38 そして最後に、最終段階として、それぞれが受け取った数を
- 7:42 自分の秘密の数で掛けます。
- 7:44 アリスはGかけるBかけるAという数を作ります。これは408になります。
- 7:49 そしてボブはGかけるAかけるBという数を作ります。これも当然408になります。
- 7:53 これで、彼らはこの共通の結果を使用することを決定できます。
- 7:57 暗号鍵として。
- 7:59 このプロトコルを使えば、最終的に彼らは同じ数を持つことになります。
- 8:03 GかけるAかけるBです。
- 8:05 彼らは共通の鍵について合意したことになります。
- 8:08 しかし、この鍵が明示的に転送されることは一度もありませんでした。
- 8:13 安全でない回線上で。
- 8:15 彼らは一度も互いに408という数を伝えませんでした。
- 8:20 問題は、ご覧の通り、イブがGを知っていることです。Gは17です。
- 8:24 そして、GかけるAが68、GかけるBが102であることも知っています。
- 8:28 そこから、彼女がアリスとボブの秘密の数を見つけるのは非常に簡単です。
- 8:31 アリスとボブの秘密の数を見つけるのは非常に簡単です。
- 8:33 例えば、AはG AをGで割ることで得られます。
- 8:37 ここでは68を17で割ると4になります。
- 8:39 したがって、イブは問題なく完全な鍵を自分で再構築できます。
- 8:44 ですから、私が提案した方法はあまり良くありません。
- 8:47 なぜなら、鍵が明示的に転送されなくても、
- 8:50 イブはそれを簡単に再作成するのに十分な情報を持っているからです。
- 8:54 この問題を回避するために、より複雑なバリアントを試してみましょう。
- 8:58 共通の数Gと秘密の数AとBはそのままですが、
- 9:02 今回は掛け算の代わりに累乗を使います。
- 9:06 つまり、アリスはGのA乗という数を作り、
- 9:10 それをボブに送ります。そしてボブはGのB乗を作り、
- 9:13 それをアリスに送り返します。
- 9:16 そして、それぞれが自分の秘密の数で累乗します。
- 9:20 つまり、アリスはGのB乗のA乗を行い、
- 9:23 ボブはGのA乗のB乗を行います。
- 9:26 そして再び、このプロトコルを使えば、最終的に彼らは同じ結果を得ます。
- 9:30 GのAかけるB乗です。
- 9:32 つまり、回線上で明示的に通信することなく共通の鍵を得るのです。
- 9:36 イブは、傍受した情報、つまりG、GのA乗、GのB乗しか知りません。
- 9:40 つまりG、GのA乗、GのB乗しか知りません。
- 9:43 しかし、またしても、彼女はこれらの情報だけで解決できてしまいます。
- 9:47 もしイブがGのA乗という数を知っていれば、
- 9:50 その対数を取ることができます。
- 9:52 それはAかけるGの対数に等しいです。
- 9:55 そして、Gの対数で割ることで、
- 9:58 彼女はAを分離することができます。
- 9:59 したがって、またしても、彼女は秘密の数を簡単に再構築でき、
- 10:03 共通の鍵も再構築できます。
- 10:04 これではまだダメです。
- 10:06 問題の根本的な原因は、アリスとボブが
- 10:09 毎回、秘密の数をGと混ぜ合わせることで隠そうとしていることです。
- 10:12 毎回、秘密の数をGと混ぜ合わせることで隠そうとしていることです。
- 10:15 しかし、毎回イブはその混合を解き、
- 10:18 秘密の数を見つけることができます。
- 10:20 掛け算を使えば、イブは割り算を使えます。
- 10:23 累乗を使えば、イブは対数を使います。
- 10:27 このアイデアが機能するためには、アリスとボブにとっては簡単にできるが、
- 10:30 イブにとってはほとんど逆転不可能な混合操作が必要です。
- 10:32 イブにとってはほとんど逆転不可能な混合操作が必要です。
- 10:35 これが暗号学で言う「一方向関数」です。
- 10:39 実は、前回の試みから、ある材料を一つ加えるだけで、
- 10:44 そのような関数を作ることができます。それは「モジュロ」です。
- 10:53 モジュロとは、ある数で整数除算したときの余りを計算する演算です。
- 10:55 ある数で整数除算したときの余りを計算する演算です。
- 10:58 例えば、17モジュロ3は2になります。
- 11:01 なぜなら、17を3で整数除算すると、
- 11:04 商が5で、最後に2が残るからです。
- 11:06 同様に、14モジュロ5は4になります。
- 11:09 あるいは42モジュロ6は0になります。などです。
- 11:12 ディフィー・ヘルマン法の考え方は、
- 11:14 Pという数を選び、
- 11:16 アリスとボブがGのように公開で共有し、
- 11:19 その後、私の例と全く同じように、
- 11:22 べき乗を使って行うのですが、今回は、
- 11:24 各操作の後にPで割った余りを取ります。
- 11:28 つまり、アリスは秘密の数Aを使って、
- 11:30 GのA乗をPで割った余りを計算し、ボブに送ります。
- 11:35 ボブは、GのB乗をPで割った余りを計算し、アリスに送ります。
- 11:40 その後、それぞれが自分の秘密の数のべき乗を適用し、
- 11:44 再びPで割った余りを取ります。
- 11:46 ここでは必ずしも明らかではありませんが、
- 11:48 これを行うことで、最終的には全く同じ数、
- 11:53 つまりGのA×B乗をPで割った余りになります。
- 11:57 ちなみに、高校でMathExpertを履修している人は、
- 11:59 合同式を使ってこれを証明してみることができます。
- 12:02 この技術は、前回のものとほぼ同じですが、
- 12:06 各操作の後にPで割った余りを適用することで、
- 12:09 アリスとボブは再び共通の鍵を合意することに成功します。
- 12:13 それを明示的に流通させることなく。
- 12:16 しかし、イブにとっては何が変わるのでしょうか?
- 12:19 彼女は、持っている情報から再びAやBを抽出して、
- 12:23 以前のように鍵を再構築することはできないのでしょうか?
- 12:26 いいえ、できません。なぜなら、すべての会話を傍受したとしても、
- 12:31 それを解きほぐすのは非常に非常に困難になるからです。
- 12:34 モジュロがすべてを混ぜ合わせてしまうからです。
- 12:38 数学的には、G、P、そしてGのA乗をPで割った余りを知っていたとしても、
- 12:44 Aを見つけるのは非常に困難です。
- 12:47 モジュロを使ったべき乗の操作は、逆算するのが非常に難しいのです。
- 12:51 それは、私たちが望んでいたような一方通行の操作です。
- 12:54 よろしければ、例で見てみましょう。
- 12:56 Pを17、Gを5としましょう。
- 12:59 これらはアリスとボブが公開で合意する値です。
- 13:02 ですから、イブもこれらの2つの値を完全に知っています。
- 13:05 アリスは秘密の数として、例えば4を選び、
- 13:09 ボブは6を選びます。
- 13:11 アリスは5を4乗します。これは625になります。
- 13:14 そして17で割った余りを取ると、13が残ります。
- 13:17 ボブも同様に、5を6乗し、
- 13:20 17で割った余りを取ると、2になります。
- 13:22 そして、それぞれが結果を相手に送り、相手は自分の秘密のべき乗を適用します。
- 13:26 アリスは2を4乗し、17で割った余りを取ると16になります。
- 13:30 ボブは13を6乗し、17で割った余りを取ると、これも16になります。
- 13:34 このように、両者にとって共通の鍵ができました。
- 13:38 一方、イブはもちろんP=17とG=5を知っていますが、
- 13:43 中間値としては13と2しか持っていません。
- 13:47 例えば、アリスの秘密の数Aを見つけるには、
- 13:50 5をべき乗したときに、
- 13:54 17で割った余りが13になる数を見つけなければなりません。
- 13:57 これは見た目ほど簡単ではなく、非常に難しい方程式です。
- 14:01 解を見つけるために解決しなければならない操作は、
- 14:04 離散対数問題と呼ばれています。
- 14:07 以前の、単にべき乗を使うだけの私の方法では、
- 14:10 イブは単純な対数を適用することで解決できました。
- 14:13 しかし今、モジュロがあるため、離散対数を解く必要があります。
- 14:17 これは理論的には可能ですが、実際には非常に手間がかかります。
- 14:21 ほとんどすべての可能性を試す必要があります。
- 14:24 非常に複雑だと言いましたが、少し注意が必要です。
- 14:28 ある数をPで割った余りを取ると、結果は必ず0からP-1の間になります。
- 14:34 これは整数除算の余りです。
- 14:37 イブがテストできる異なる可能性を最大限にするには、
- 14:42 まずPを可能な限り大きくする必要があります。
- 14:45 しかし、それだけではありません。Pを適切に選択し、
- 14:48 そして何よりも、それに合うGを適切に選択する必要があります。
- 14:51 例を挙げて説明しましょう。
- 14:53 Pを15、Gを4とすると、
- 14:57 最終的な鍵はGのAB乗モジュロPになることがわかっています。
- 15:01 つまり、Gの何乗かモジュロPです。
- 15:04 そして、Gの異なるべき乗モジュロPがどのような値になるかを見てみましょう。
- 15:09 私が選んだ値では、Gの1乗モジュロPは4、
- 15:12 Gの2乗モジュロPは1、
- 15:14 Gの3乗モジュロPは4、
- 15:16 Gの4乗モジュロPは1、といった具合です。
- 15:20 Pを15と選んだにもかかわらず、
- 15:23 Gのべき乗は常に1か4にしかなりません。
- 15:27 つまり、イブが試すべき鍵は15通りあると思っていたのに、
- 15:31 実際には2通りしかないのです。
- 15:33 このような状況は絶対に避けるべきです。
- 15:36 なぜなら、このように可能性の空間を減らすことで、
- 15:39 私たちの鍵を解読しようとするイブの作業を大幅に容易にしてしまうからです。
- 15:44 幸いなことに、解決策があります。
- 15:46 理想的なのは、Pを素数にすることです。
- 15:50 そしてGを、Pを法とする原始根と呼ばれる数にすることです。
- 15:55 原始根とは、Gを
- 15:58 1からP-1までのすべてのべき乗にすると、
- 16:01 1からP-1までのすべての可能な数が見つかるということです。
- 16:05 したがって、最大限の可能性が存在する状況になります。
- 16:09 例で見てみましょう。
- 16:11 例えばPを13とすると、証明はしませんが、
- 16:14 原始根は2、6、7、11のみです。
- 16:18 したがって、Gを6とすると、
- 16:20 6の13を法とするべき乗は1から12まできちんと広がり、完璧です。
- 16:25 しかし、Gを5とすると、うまくいきません。
- 16:27 なぜなら、べき乗は5、12、8、1の間でしか循環しないからです。
- 16:31 つまり、12通りではなく、わずか4通りの可能性しかありません。
- 16:35 したがって、Gには、
- 16:38 選択したPの原始根を適切に選ぶことが重要です。
- 16:42 これらの小さな注意を払うことで、
- 16:44 ディフィー・ヘルマンアルゴリズムの本質が得られます。
- 16:47 これは、公開チャネル上で共通の暗号化キーを決定するという問題を解決します。
- 16:54 このアルゴリズムは1976年に初めて公開され、
- 16:57 翌年には米国で特許が取得されました。
- 16:59 しかし幸いなことに、現在ではパブリックドメインとなっており、
- 17:02 非常に広く使用されています。
- 17:05 インターネット上の通信の大部分を安全にするために。
- 17:08 このように、2台のコンピューターが
- 17:11 暗号化された通信チャネルを確立する必要がある場合、
- 17:13 あなたのデータがネットワーク上で平文で拡散されないように、
- 17:16 ディフィー・ヘルマンアルゴリズムの変種がよく使われます。
- 17:20 そして、この原理が特にTLSプロトコルを保護しており、
- 17:24 これは、あなたがウェブサイトを訪問する際のほとんどの背後にあります。
- 17:28 ディフィー・ヘルマンに感謝します。
- 17:31 とはいえ、いつものことですが、この方法も完全に破られないわけではありません。
- 17:35 例えば、イブが
- 17:38 アリスとボブの身元を乗っ取らないように注意する必要があります。
- 17:41 そうなると、彼女は二人の間に割り込み、
- 17:44 アリスにはボブになりすまし、その逆も行えるようになります。
- 17:47 こうなると、イブにとってはやりたい放題です。
- 17:50 このリスク以外にも、確認すべきことがあります。
- 17:52 アリスとボブがそれぞれ秘密の数字を選ぶとき、
- 17:56 イブがそれを簡単に推測できないように。
- 17:59 ですから、理想的には、彼らは選択をする必要があります
- 18:02 良い乱数ジェネレーターを使って。
- 18:06 ところで、乱数ジェネレーターの作り方というこの問題は、
- 18:10 次エピソードの非常に良いテーマになると思います。
- 18:13 ご視聴いただきありがとうございます。
- 18:15 今後の投稿を見逃さないように、チャンネル登録をお願いします。
- 18:17 サイエンス・エトナントのDiscordに参加してください、
- 18:20 リンクは概要欄に貼っておきます。
- 18:22 それでは、また新しい動画でお会いしましょう。
- 18:24 またね!
- 0:00 안녕하세요, 오늘은 놀라운 암호화 기술에 대해 이야기할 것입니다.
- 0:05 두 사람이 비밀을 주고받을 수 있게 해주는 기술이죠.
- 0:08 심지어 스파이가 항상 엿듣고 있을 때도 말입니다.
- 0:12 디피-헬만(Diffie-Hellman) 알고리즘이라고 불리는 이 방법은
- 0:16 꽤 믿기지 않을 정도입니다.
- 0:18 처음 이 이야기를 들었을 때
- 0:20 저는 이런 기술이 존재할 수 없다고 생각했습니다.
- 0:24 하지만, 이것이 실제로 작동한다는 것을 알게 될 것입니다.
- 0:31 두 사람이 극비리에 메시지를 주고받고 싶다면
- 0:36 여러분은 메시지를 암호화하기만 하면 된다고 말할 것입니다.
- 0:39 기술적으로 이것을 암호화(chiffrement) 작업이라고 부릅니다.
- 0:42 예를 들어, '오늘 저녁 공원에서 만나'와 같은 평문 메시지에서 시작하여
- 0:47 이것을 이해할 수 없는 암호문으로 바꾸려고 합니다.
- 0:51 하지만 대화 상대방은 해독할 수 있어야 합니다.
- 0:55 가장 오래된 기술 중 하나는 시저 암호(César cipher)라고 불리는 것입니다.
- 0:59 유명한 로마 장군에 의해 대중화되었다고 전해지기 때문이죠.
- 1:03 아이디어는 단순히 알파벳의 모든 글자를 특정 양만큼 이동시키는 것입니다.
- 1:08 예를 들어, 3만큼 이동시키면 A는 D로 바뀌고
- 1:12 B는 E로, C는 F로 바뀌는 식입니다.
- 1:15 W는 Z가 되고, XYZ는 A, B, C가 될 때까지 말이죠.
- 1:20 이렇게 하면 메시지는 완전히 뒤섞인 것처럼 보이지만
- 1:23 대화 상대방은 아무 문제 없이 메시지를 재구성할 수 있습니다.
- 1:27 역방향으로 이동시키면 되니까요.
- 1:30 하지만 이 기술은 상당히 피상적입니다.
- 1:32 만약 스파이가 메시지가 이런 방식으로 암호화되었다는 것을 알아낸다면
- 1:36 시도해 볼 수 있는 이동 가능성은 26가지밖에 없으며, 사실상 25가지에 불과합니다.
- 1:41 따라서 그는 모든 가능성을 빠르게 시험하여 비밀 메시지를 알아낼 것입니다.
- 1:46 시저 암호 방식보다 더 견고하게 만들려면
- 1:49 치환 암호(substitution cipher)라고 불리는 것을 사용할 수 있습니다.
- 1:53 이것은 알파벳의 각 글자를
- 1:56 다른 글자로 바꾸는 것이지만, 특별한 논리는 없습니다.
- 1:59 메시지를 암호화하고 해독하려면 전체 변환 테이블을 알아야 합니다.
- 2:05 그리고 이것은 매우 효과적입니다. 이번에는 26 팩토리얼(factorial 26) 가지의 가능성이 있기 때문입니다.
- 2:10 즉, 10억의 10억의 10억 정도의 경우의 수입니다.
- 2:13 하지만 그럼에도 불구하고, 우리는 이러한 치환 암호를 매우 잘 해독할 수 있습니다.
- 2:18 글자의 빈도와 그 연결에 대한 통계를 내는 방식으로 말이죠.
- 2:22 예를 들어, E를 나타내는 글자는 항상 같기 때문에
- 2:25 충분히 긴 프랑스어 메시지에서는 쉽게 식별할 수 있습니다.
- 2:30 A나 S와 같은 자주 사용되는 글자들도 마찬가지입니다.
- 2:34 저는 이전에 이런 종류의 암호를 해독하는 방법에 대한 비디오를 만들었습니다.
- 2:38 자동화된 방식으로 매우 빠르게 말이죠.
- 2:40 마르코프 연쇄 몬테카를로(Markov Chain Monte Carlo) 방법이라고 불리는 것을 사용하여요.
- 2:45 이러한 공격을 막기 위해서는 다른 종류의 암호화를 시도해야 합니다.
- 2:50 한 가지 옵션은 예를 들어, 글자 이동을 지시할 키워드를 사용하는 것입니다.
- 2:56 'jardin'이라는 단어를 예로 들어, 메시지 아래에 써봅시다.
- 3:00 단어의 각 글자는 알파벳에서의 위치에 따라 이동량을 나타낼 것입니다.
- 3:06 J는 9, A는 0, R은 17 등과 같이 말이죠.
- 3:10 그리고 각 이동량을 메시지의 글자에 적용합니다.
- 3:15 R을 9만큼 이동시키면 A가 되고, E를 0만큼 이동시키면 E가 되며,
- 3:19 N을 17만큼 이동시키면 역시 E가 되는 식입니다.
- 3:23 그리고 모든 작업을 마칠 때까지 필요한 만큼 키워드를 반복합니다.
- 3:29 메시지를 받는 사람이 키를 가지고 있다면, 그에게는 문제가 되지 않습니다.
- 3:33 이동량을 빼기만 하면 되니까요.
- 3:36 이 방법의 장점은, 보시다시피 원본 메시지의 두 개의 E가
- 3:40 암호화된 메시지에서는 다른 글자로 표현된다는 것입니다.
- 3:44 반대로, 암호화된 메시지의 같은 글자가
- 3:47 원본 메시지에서는 두 개의 다른 글자를 나타낼 수도 있습니다.
- 3:51 따라서 이는 통계적 접근 방식을 사용하는 공격을 상당히 방해할 것입니다.
- 3:56 이 방법이 충분히 견고하려면, 물론 충분히 긴 키워드를 사용해야 합니다.
- 4:01 하지만 사실 진짜 단어일 필요도 없습니다.
- 4:04 무작위로 선택된 긴 문자열일 수도 있습니다.
- 4:08 이를 암호화 키라고 부릅니다.
- 4:11 이 키는 발신자가 메시지를 암호화하고 수신자가 메시지를 해독할 수 있게 해줍니다.
- 4:17 이 기술의 큰 문제는 두 사람이 이런 식으로 통신하고 싶을 때,
- 4:22 어느 시점에 사용할 키에 대해 합의해야 한다는 것입니다.
- 4:27 CIA가 현장에 요원을 파견하는 경우라면 문제가 없습니다.
- 4:31 출발 전에 미리 키를 합의할 수 있습니다.
- 4:39 하지만 물리적으로 만날 수 없는 두 사람이 원거리에 있다면,
- 4:45 전화 통화만 하거나 인터넷으로 메시지를 주고받는다면,
- 4:49 어떻게 비밀 암호화 키를 정할 수 있을까요?
- 4:54 둘 중 한 명이 키를 결정하고 다른 사람에게
- 4:59 “우리 그냥 이 키를 사용하자”라고 쓸 수는 없습니다.
- 5:01 그 메시지가 가로채이면 스파이가 당연히 키를 알게 될 것이기 때문입니다.
- 5:06 따라서 키에 대해 합의할 방법을 찾아야 합니다.
- 5:10 하지만 명시적으로 키를 작성하지 않고요.
- 5:13 이것을 키 교환 문제 또는 키 설정 문제라고 부릅니다.
- 5:18 잠재적으로 항상 도청당하고 있다는 것을 알면서도,
- 5:23 어떻게 원거리에서 공통 암호화 키에 합의할 수 있을까요?
- 5:27 언뜻 보기에는 거의 해결 불가능해 보입니다.
- 5:30 비밀리에 정보를 교환할 방법이 전혀 없다면,
- 5:34 어떻게 원거리에서 동일한 키에 합의할 수 있을까요?
- 5:37 호기심 많은 사람이 그 키를 알지 못하게 하면서요?
- 5:40 이 문제는 1976년 수학자 디피(Diffie)와 헬만(Hellman)이 해결했습니다.
- 5:47 일반적으로 암호학에서는 다음과 같이 설명합니다.
- 5:52 전통적으로 앨리스(Alice)와 밥(Bob)이라고 불리는 두 사람이 있다고 가정해 봅시다.
- 5:56 이들은 이전에 서로 본 적도, 이야기한 적도 없지만,
- 5:59 보안되지 않은 회선을 통해 원거리에서 통신할 수 있습니다.
- 6:03 게다가, 보통 이브(Eve)라고 불리는 한 사람이
- 6:06 바로 이 회선에 연결하여
- 6:09 그 안에서 오가는 모든 것을 가로챌 수 있습니다.
- 6:13 앨리스와 밥은 어떻게 이브가 키를 알지 못하게 하면서
- 6:17 공통 키에 합의할 수 있을까요?
- 6:20 불가능해 보입니다!
- 6:23 시작하기 전에 한 가지 덧붙이자면,
- 6:25 디피-헬만 방식에서 키는 단어나 문자열이 아니라,
- 6:29 숫자입니다.
- 6:31 사실, 크게 달라지는 것은 없습니다.
- 6:33 하나를 다른 하나로 만드는 것은 매우 쉽습니다.
- 6:36 앨리스와 밥이 숫자 키를 결정하기 위해 어떻게 진행하는지 보여드리기 위해,
- 6:41 먼저 작동하지 않는 방법으로 부드럽게 시작하겠지만,
- 6:45 이것이 우리에게 길을 열어줄 것입니다.
- 6:47 앨리스와 밥이 서로 전화해서 함께 기본 숫자를 결정한다고 가정해 봅시다.
- 6:52 이 숫자를 G라고 부르겠습니다.
- 6:54 그들이 G를 17로 선택했다고 해봅시다.
- 6:56 그리고 당연히 회선은 보안되지 않으므로,
- 6:58 이브는 모든 것을 듣고 이 G 값을 기록합니다.
- 7:02 다음으로, 앨리스와 밥은 각자 비밀 숫자를 선택합니다.
- 7:07 앨리스는 A, 밥은 B로 표기합니다.
- 7:10 그들은 각자 자신의 비밀 숫자에 공통 숫자 G를 곱할 것입니다.
- 7:15 앨리스는 G 곱하기 A를, 밥은 G 곱하기 B를 만들 것입니다.
- 7:19 앨리스가 4를 선택하고 밥이 6을 선택하면, 각각 68과 102가 됩니다.
- 7:24 그리고 그들은 이 곱셈의 결과를 서로에게 전달합니다.
- 7:28 앨리스는 G 곱하기 A를 밥에게 보내고, 밥은 G 곱하기 B를 앨리스에게 보냅니다.
- 7:33 그리고 이것은 보안 없이 이루어집니다.
- 7:35 따라서 여기서도 이브는 이 값들을 알고 있습니다.
- 7:38 마지막으로, 각자는 방금 받은 숫자에
- 7:42 자신의 비밀 숫자를 곱합니다.
- 7:44 앨리스는 G 곱하기 B 곱하기 A를 만드는데, 이는 408이 됩니다.
- 7:49 그리고 밥은 G 곱하기 A 곱하기 B를 만드는데, 이것도 당연히 408이 됩니다.
- 7:53 자, 이제 그들은 이 공통된 결과를 사용하기로 결정할 수 있습니다.
- 7:57 암호화 키로 사용됩니다.
- 7:59 이 프로토콜을 사용하면 결국 각자 같은 숫자를 갖게 될 것입니다.
- 8:03 G 곱하기 A 곱하기 B.
- 8:05 그들은 공통 키에 동의했습니다.
- 8:08 하지만 이 키가 어떤 순간에도 명시적으로 전송되지 않았습니다.
- 8:13 보안되지 않은 회선을 통해 말이죠.
- 8:15 그들은 어떤 순간에도 서로에게 숫자 408을 전달하지 않았습니다.
- 8:20 문제는, 보시다시피 이브는 G가 17이라는 것을 알고 있고,
- 8:24 G 곱하기 A가 68이고 G 곱하기 B가 102라는 것도 알고 있다는 것입니다.
- 8:28 여기서부터 이브가 찾아내는 것은 매우 쉽습니다.
- 8:31 앨리스와 밥의 비밀 숫자를 말이죠.
- 8:33 예를 들어, A는 G A를 G로 나누어 얻을 수 있습니다.
- 8:37 여기서 68을 17로 나누면 4가 나옵니다.
- 8:39 따라서 이브는 문제없이 전체 키를 스스로 재구성할 수 있습니다.
- 8:44 제가 방금 제안한 방법은 좋지 않습니다.
- 8:47 키가 명시적으로 전송되지 않더라도,
- 8:50 이브는 쉽게 키를 다시 만들 수 있는 충분한 정보를 가지고 있기 때문입니다.
- 8:54 이 문제를 우회하기 위해 더 복잡한 변형을 시도해 봅시다.
- 8:58 공통 숫자 G와 비밀 숫자 A, B는 그대로 유지하지만,
- 9:02 이번에는 곱셈 대신 거듭제곱을 사용할 것입니다.
- 9:06 즉, 앨리스는 G의 A제곱을 만들고,
- 9:10 그것을 밥에게 보냅니다. 그리고 밥은 G의 B제곱을 만들고,
- 9:13 그것을 앨리스에게 다시 보냅니다.
- 9:16 그리고 각자 자신의 비밀 숫자로 거듭제곱을 합니다.
- 9:20 따라서 앨리스는 (G의 B제곱)의 A제곱을 하고,
- 9:23 밥은 (G의 A제곱)의 B제곱을 합니다.
- 9:26 그리고 다시, 이 프로토콜을 사용하면 결국 같은 결과를 얻게 될 것입니다.
- 9:30 G의 (A 곱하기 B)제곱,
- 9:32 즉, 회선을 통해 명시적으로 전달하지 않고도 공통 키를 얻는 것입니다.
- 9:36 이브는 자신이 가로챈 것만 알고 있습니다.
- 9:40 즉, G, G의 A제곱, G의 B제곱입니다.
- 9:43 하지만 다시 말하지만, 이 정보만으로도 이브는 해결할 수 있습니다.
- 9:47 만약 이브가 G의 A제곱을 알고 있다면,
- 9:50 그것의 로그를 취할 수 있습니다.
- 9:52 그것은 A 곱하기 G의 로그와 같습니다.
- 9:55 그리고 나서 G의 로그로 나누면,
- 9:58 A를 분리할 수 있습니다.
- 9:59 따라서 다시, 이브는 비밀 숫자를 쉽게 재구성할 수 있고,
- 10:03 그 결과 공통 키도 알 수 있습니다.
- 10:04 여전히 안 됩니다.
- 10:06 문제의 근본적인 원인은 앨리스와 밥이
- 10:09 매번 자신의 비밀 숫자를 위장하려고 한다는 것입니다.
- 10:12 G와 어떤 식으로든 섞어서 말이죠.
- 10:15 하지만 매번 이브는 이 혼합을 풀어내고
- 10:18 비밀 숫자를 찾아낼 수 있습니다.
- 10:20 곱셈을 사용하면 이브는 나눗셈을 사용할 수 있습니다.
- 10:23 거듭제곱을 사용하면 이브는 로그를 사용합니다.
- 10:27 이 아이디어가 작동하려면 혼합 연산이 필요합니다.
- 10:30 앨리스와 밥에게는 쉽지만,
- 10:32 이브에게는 거의 역전 불가능한 연산 말이죠.
- 10:35 이것을 암호학에서는 단방향 함수라고 부릅니다.
- 10:39 음, 이전 시도에서 하나를 만들 수 있습니다.
- 10:44 단지 하나의 요소, 즉 모듈로를 추가함으로써 말이죠.
- 10:53 모듈로는 계산하는 연산입니다.
- 10:55 어떤 숫자로 정수 나눗셈을 했을 때의 나머지를 말이죠.
- 10:58 예를 들어, 17 모듈로 3은 2입니다.
- 11:01 왜냐하면 17을 3으로 정수 나눗셈을 하면,
- 11:04 몫은 5이고 나머지는 2가 남기 때문입니다.
- 11:06 마찬가지로, 14 모듈로 5는 4입니다.
- 11:09 또는 42 모듈로 6은 0입니다. 등등.
- 11:12 디피-헬만(Diffie-Hellman) 방법의 아이디어는
- 11:14 P라는 숫자를 선택하는 것입니다.
- 11:16 앨리스와 밥이 G처럼 공개적으로 서로에게 알리는 P를 선택하고,
- 11:19 제 예시에서처럼 정확히
- 11:22 거듭제곱을 사용하되, 이번에는
- 11:24 각 연산 후에 P로 나눈 나머지를 적용하는 것입니다.
- 11:28 즉, 앨리스는 자신의 비밀 숫자 A를 사용하여,
- 11:30 G의 A제곱을 P로 나눈 나머지를 계산하여 밥에게 보냅니다.
- 11:35 밥은 자신의 비밀 숫자 B를 사용하여 G의 B제곱을 P로 나눈 나머지를 계산하여 앨리스에게 보냅니다.
- 11:40 그리고 각자는 자신의 비밀 숫자의 거듭제곱을 적용하고
- 11:44 다시 P로 나눈 나머지를 취합니다.
- 11:46 여기서 바로 보이지는 않겠지만,
- 11:48 이렇게 하면 결국 정확히 같은 숫자를 갖게 됩니다.
- 11:53 이는 사실 G의 (A 곱하기 B)제곱을 P로 나눈 나머지입니다.
- 11:57 참고로, 고등학교에서 MathExpert 과정을 듣는 학생들은
- 11:59 합동식을 사용하여 이를 증명해 볼 수 있습니다.
- 12:02 이전과 거의 같지만, 각 연산 후에 P로 나눈 나머지를 적용하는 이 기술 덕분에,
- 12:09 앨리스와 밥은 다시 한번 공통 키에 합의하는 데 성공할 것입니다.
- 12:13 명시적으로 키를 주고받지 않고도 말이죠.
- 12:16 그런데 이브에게는 무엇이 달라질까요?
- 12:19 이브는 자신이 가진 정보에서 A나 B를 다시 추출하여
- 12:23 이전처럼 키를 재구성할 수 없을까요?
- 12:26 아닙니다. 모든 대화를 가로채는 사람이라 할지라도,
- 12:31 이것은 풀기가 매우 매우 복잡해집니다.
- 12:34 나머지가 모든 것을 뒤섞어 놓기 때문입니다.
- 12:38 수학적으로, G, P, 그리고 G의 A제곱을 P로 나눈 나머지를 알고 있더라도,
- 12:44 A를 찾아내는 것은 매우 어렵습니다.
- 12:47 나머지를 포함한 거듭제곱 연산은 역연산이 매우 어렵습니다.
- 12:51 우리가 원했던 대로 단방향 연산인 셈이죠.
- 12:54 원하시면 예시를 통해 볼 수 있습니다.
- 12:56 P는 17, G는 5라고 해봅시다.
- 12:59 앨리스와 밥은 이 값들을 공개적으로 합의합니다.
- 13:02 따라서 이브는 이 두 값을 완벽하게 알고 있습니다.
- 13:05 앨리스는 자신의 비밀 숫자로 4를 선택하고,
- 13:09 밥은 6을 선택합니다.
- 13:11 앨리스는 5의 4제곱을 계산하여 625를 얻고,
- 13:14 17로 나눈 나머지를 취하면 13이 남습니다.
- 13:17 밥도 마찬가지로 5의 6제곱을 계산하고,
- 13:20 17로 나눈 나머지를 취하면 2가 됩니다.
- 13:22 그리고 각자는 그 결과를 상대방에게 보내고, 상대방은 자신의 비밀 숫자로 거듭제곱을 적용합니다.
- 13:26 앨리스는 2의 4제곱을 17로 나눈 나머지를 취하면 16이 됩니다.
- 13:30 밥은 13의 6제곱을 17로 나눈 나머지를 취하면 역시 16이 됩니다.
- 13:34 따라서 두 통신 당사자에게는 공통 키가 생겼습니다.
- 13:38 이브는 물론 P가 17이고 G가 5라는 것을 알고 있지만,
- 13:43 중간 값으로 13과 2만 가지고 있습니다.
- 13:47 예를 들어 앨리스의 비밀 숫자 A를 찾으려면,
- 13:50 5에 거듭제곱으로 적용했을 때
- 13:54 17로 나눈 나머지가 13이 되는 숫자를 찾아야 합니다.
- 13:57 겉보기에는 그렇지 않지만, 이것은 매우 어려운 방정식입니다.
- 14:01 해를 찾기 위해 풀어야 하는 연산은
- 14:04 바로 이산 로그 문제라고 불립니다.
- 14:07 이전의 거듭제곱만 사용한 방법에서는,
- 14:10 이브는 간단한 로그를 적용하여 해결할 수 있었습니다.
- 14:13 이제 나머지가 있기 때문에 이산 로그를 풀어야 하는데,
- 14:17 이론적으로는 가능하지만 실제로는 매우 번거롭습니다.
- 14:21 거의 모든 가능성을 시도해야 합니다.
- 14:24 매우 복잡하다고 말했지만, 그래도 약간 주의해야 할 점이 있습니다.
- 14:28 어떤 숫자를 P로 나눈 나머지를 취하면, 결과는 반드시 0과 P-1 사이가 됩니다.
- 14:34 그것은 정수 나눗셈의 나머지입니다.
- 14:37 이브가 테스트할 수 있는 최대한 많은 다른 가능성을 원한다면,
- 14:42 먼저 P를 가능한 한 크게 잡아야 합니다.
- 14:45 하지만 그게 다가 아닙니다. P를 잘 선택해야 하고,
- 14:48 특히 그에 맞는 G를 잘 선택해야 합니다.
- 14:51 예를 들어 설명해 드리겠습니다.
- 14:53 P를 15, G를 4로 잡으면,
- 14:57 최종 키는 G의 AB제곱 모듈로 P가 될 것이라는 것을 압니다.
- 15:01 즉, G의 어떤 제곱 모듈로 P가 됩니다.
- 15:04 G의 다양한 제곱 모듈로 P의 값을 살펴볼 수 있습니다.
- 15:09 제가 선택한 값으로, G의 1제곱 모듈로 P는 4이고,
- 15:12 G의 2제곱 모듈로 P는 1이고,
- 15:14 G의 3제곱 모듈로 P는 4이고,
- 15:16 G의 4제곱 모듈로 P는 1입니다. 이런 식으로요.
- 15:20 P를 15로 선택했음에도 불구하고,
- 15:23 G의 제곱은 항상 1 또는 4로 떨어집니다.
- 15:27 그래서 이브가 시도해야 할 15가지 가능한 키가 있다고 생각했지만,
- 15:31 실제로는 2개밖에 없습니다.
- 15:33 이런 상황은 반드시 피해야 합니다.
- 15:36 왜냐하면 이렇게 가능성의 공간을 줄이면,
- 15:39 우리의 키를 해독하려는 이브의 작업을 상당히 쉽게 만들어주기 때문입니다.
- 15:44 다행히 해결책이 있습니다.
- 15:46 이상적인 방법은 P를 소수로 선택하고,
- 15:50 G를 P에 대한 원시근이라고 부르는 숫자로 선택하는 것입니다.
- 15:55 원시근이란 G를
- 15:58 1부터 P-1까지의 모든 제곱으로 올리면,
- 16:01 1부터 P-1까지의 모든 가능한 숫자를 찾을 수 있다는 의미입니다.
- 16:05 따라서 우리는 최대한 많은 가능성이 있는 경우에 놓이게 될 것입니다.
- 16:09 예를 들어 볼 수 있습니다.
- 16:11 예를 들어 P가 13일 때, 제가 증명해 보이진 않겠지만,
- 16:14 원시근은 2, 6, 7, 11뿐입니다.
- 16:18 따라서 G를 6으로 잡으면,
- 16:20 6의 13 모듈로 제곱은 1부터 12까지 잘 퍼져 나갑니다. 완벽하죠.
- 16:25 하지만 G를 5로 잡으면 잘 작동하지 않습니다.
- 16:27 왜냐하면 제곱이 5, 12, 8, 1에서만 반복되기 때문입니다.
- 16:31 따라서 12가지 대신 4가지 가능성만 있습니다.
- 16:35 그러므로 G를 선택할 때,
- 16:38 우리가 선택한 P의 원시근을 잘 선택하는 것이 중요합니다.
- 16:42 이러한 작은 주의사항들을 지키면,
- 16:44 디피-헬만 알고리즘의 핵심을 얻게 됩니다.
- 16:47 이 알고리즘은 공개 채널에서 공통 암호화 키를 결정하는 문제를 해결합니다.
- 16:52 공개 채널에 있을 때 말이죠.
- 16:54 이 알고리즘은 1976년에 처음 발표되었고,
- 16:57 이듬해 미국에서 특허를 받았습니다.
- 16:59 하지만 다행히도 이제는 공공 영역에 있으며,
- 17:02 인터넷 통신의 상당 부분을 보안하는 데 매우 널리 사용됩니다.
- 17:08 따라서 두 컴퓨터가 암호화된 통신 채널을 설정해야 할 때,
- 17:13 데이터가 네트워크에 평문으로 전송되지 않도록 하기 위해,
- 17:16 종종 디피-헬만 알고리즘의 변형을 사용합니다.
- 17:20 그리고 이 원리는 특히 TLS 프로토콜을 보안하며,
- 17:24 이는 여러분이 웹사이트를 방문할 때 대부분의 경우 뒤에 있습니다.
- 17:28 그러니 디피-헬만에게 감사합니다.
- 17:31 그럼에도 불구하고, 언제나 그렇듯이 이 방법도 완전히 뚫을 수 없는 것은 아닙니다.
- 17:35 예를 들어, 이브가 앨리스와 밥의 신원을 도용하지 못하도록 주의해야 합니다.
- 17:41 그렇게 되면 이브는 앨리스에게는 밥인 척하고, 밥에게는 앨리스인 척하여
- 17:44 둘 사이에 끼어들 수 있게 됩니다.
- 17:47 그러면 이브에게는 모든 것이 열려 있는 셈입니다.
- 17:50 이러한 위험 외에도, 우리는 또한 다음을 확인해야 합니다.
- 17:52 앨리스와 밥이 각자 비밀 숫자를 선택할 때,
- 17:56 이브가 쉽게 알아낼 수 없도록 말이죠.
- 17:59 따라서 이상적으로는 그들이 선택을 해야 합니다.
- 18:02 좋은 난수 생성기를 사용하여 말이죠.
- 18:06 그리고 사실, 난수 생성기를 만드는 방법에 대한 이 질문은,
- 18:10 다음 에피소드의 아주 좋은 주제가 될 것 같네요.
- 18:13 영상을 시청해 주셔서 감사합니다.
- 18:15 앞으로의 게시물을 놓치지 않도록 구독해주세요.
- 18:17 Science Étonnante 디스코드에 참여해주세요.
- 18:20 링크는 설명란에 있습니다.
- 18:22 그리고 새로운 영상으로 곧 다시 찾아뵙겠습니다.
- 18:24 다음에 또 만나요!
- 0:00 Chào mọi người, hôm nay chúng ta sẽ nói về một kỹ thuật mật mã đáng kinh ngạc
- 0:05 cho phép hai người trao đổi bí mật với nhau
- 0:08 ngay cả khi họ liên tục bị một điệp viên nghe lén.
- 0:12 Phương pháp này, được gọi là thuật toán Diffie-Hellman
- 0:16 có vẻ khá khó tin
- 0:18 và những lần đầu tiên tôi nghe về nó
- 0:20 tôi đã nghĩ rằng một kỹ thuật như vậy không thể tồn tại.
- 0:24 Thế nhưng, chúng ta sẽ thấy rằng nó thực sự hoạt động.
- 0:31 Nếu hai người muốn trao đổi một tin nhắn một cách bí mật nhất
- 0:36 bạn sẽ nói với tôi rằng điều đó dễ dàng, chỉ cần mã hóa tin nhắn.
- 0:39 Về mặt kỹ thuật, chúng ta gọi đó là một hoạt động mã hóa.
- 0:42 Chúng ta bắt đầu với một tin nhắn rõ ràng, ví dụ: hẹn gặp tối nay tại công viên
- 0:47 và chúng ta sẽ cố gắng biến nó thành một mớ hỗn độn không thể hiểu được
- 0:51 nhưng có thể được giải mã bởi người đối thoại của chúng ta.
- 0:55 Một trong những kỹ thuật lâu đời nhất là cái mà chúng ta gọi là mã dịch Caesar
- 0:59 vì nó được cho là đã được phổ biến bởi vị tướng La Mã nổi tiếng.
- 1:03 Ý tưởng chỉ đơn giản là dịch chuyển tất cả các chữ cái trong bảng chữ cái một lượng nhất định.
- 1:08 Ví dụ, nếu chúng ta dịch chuyển 3 đơn vị, chúng ta thay A bằng D
- 1:12 B bằng E, C bằng F, v.v.
- 1:15 cho đến W trở thành Z và XYZ trở thành A, B và C.
- 1:20 Với điều này, tin nhắn dường như hoàn toàn bị xáo trộn
- 1:23 nhưng người đối thoại của chúng ta có thể dễ dàng khôi phục nó
- 1:27 bằng cách áp dụng phép dịch chuyển ngược lại.
- 1:30 Tuy nhiên, kỹ thuật này khá nông cạn.
- 1:32 Nếu một điệp viên đoán được rằng tin nhắn đã được mã hóa theo cách này
- 1:36 hắn ta chỉ có 26 khả năng dịch chuyển để thử, và thực ra chỉ có 25.
- 1:41 Và do đó, hắn ta sẽ nhanh chóng thử tất cả cho đến khi tìm ra tin nhắn bí mật.
- 1:46 Để làm cho phương pháp này mạnh mẽ hơn phương pháp Caesar
- 1:49 chúng ta có thể sử dụng cái gọi là mã hóa thay thế.
- 1:53 Nó bao gồm việc thay thế mỗi chữ cái trong bảng chữ cái
- 1:56 bằng một chữ cái khác nhưng không theo logic cụ thể nào.
- 1:59 Để mã hóa và giải mã tin nhắn, chúng ta cần biết toàn bộ bảng chuyển đổi.
- 2:05 Và điều này rất hiệu quả, vì lần này có 26 giai thừa khả năng
- 2:10 tức là khoảng một tỷ tỷ tỷ.
- 2:13 Nhưng dù vậy, chúng ta cũng biết cách phá vỡ các mã hóa thay thế này rất tốt
- 2:18 bằng cách thống kê tần suất các chữ cái và chuỗi của chúng.
- 2:22 Ví dụ, vì luôn là cùng một chữ cái đại diện cho E
- 2:25 trên một tin nhắn tiếng Pháp đủ dài, chúng ta dễ dàng xác định được nó.
- 2:30 Và tương tự đối với các chữ cái thường gặp như A hoặc S, v.v.
- 2:34 Tôi cũng đã làm một video về cách phá vỡ loại mã hóa này
- 2:38 rất nhanh chóng một cách tự động
- 2:40 bằng cách sử dụng cái gọi là phương pháp Monte Carlo chuỗi Markov.
- 2:45 Để tự bảo vệ khỏi những cuộc tấn công này, chúng ta phải thử một loại mã hóa khác.
- 2:50 Một lựa chọn, ví dụ, là sử dụng một từ khóa sẽ quy định các dịch chuyển chữ cái.
- 2:56 Hãy lấy từ
- 3:00 Mỗi chữ cái trong từ sẽ đại diện cho một dịch chuyển tùy thuộc vào vị trí của nó trong bảng chữ cái.
- 3:06 J là 9, A là 0, R là 17, v.v.
- 3:10 Và sau đó chúng ta áp dụng mỗi dịch chuyển cho các chữ cái trong tin nhắn của chúng ta.
- 3:15 R chúng ta dịch chuyển 9 đơn vị, nó thành A, E chúng ta dịch chuyển 0 đơn vị, nó thành E,
- 3:19 N chúng ta dịch chuyển 17 đơn vị, nó cũng trở thành E, v.v.
- 3:23 Và chúng ta lặp lại từ khóa nhiều lần nếu cần, cho đến khi hoàn thành tất cả.
- 3:29 Nếu người nhận tin nhắn có khóa, điều đó không gây ra vấn đề gì cho họ,
- 3:33 chỉ cần trừ đi các dịch chuyển.
- 3:36 Lợi ích của phương pháp này, bạn thấy đấy, là hai chữ E trong tin nhắn gốc
- 3:40 sẽ được đại diện bởi các chữ cái khác nhau trong tin nhắn đã mã hóa.
- 3:44 Và ngược lại, cùng một chữ cái trong tin nhắn đã mã hóa
- 3:47 có thể đại diện cho hai chữ cái khác nhau trong tin nhắn gốc.
- 3:51 Và điều này sẽ gây khó khăn đáng kể cho các cuộc tấn công sử dụng phương pháp thống kê.
- 3:56 Để phương pháp đủ mạnh, tất nhiên phải sử dụng một từ khóa đủ dài.
- 4:01 Nhưng thực ra nó thậm chí không cần phải là một từ thật.
- 4:04 Nó có thể đơn giản là một chuỗi dài các chữ cái được chọn ngẫu nhiên,
- 4:08 mà chúng ta sẽ gọi là khóa mã hóa.
- 4:11 Nó sẽ cho phép cả người gửi mã hóa tin nhắn và người nhận giải mã nó.
- 4:17 Vấn đề lớn của kỹ thuật này là nếu hai người muốn liên lạc theo cách này,
- 4:22 họ phải, tại một thời điểm nào đó, thống nhất về khóa sẽ sử dụng.
- 4:27 Vậy nếu CIA cử một đặc vụ ra thực địa, thì không có vấn đề gì,
- 4:31 họ có thể thống nhất một khóa trước, trước khi khởi hành.
- 4:39 Nhưng nếu có hai người ở xa không có khả năng gặp mặt trực tiếp,
- 4:45 nếu chúng ta chỉ gọi điện thoại hoặc gửi tin nhắn qua internet,
- 4:49 làm thế nào để thiết lập một khóa mã hóa bí mật?
- 4:54 Không thể chỉ một trong hai người quyết định một khóa và viết cho người kia
- 4:59 « chúng ta cứ dùng khóa thông thường ».
- 5:01 Bởi vì nếu tin nhắn đó bị chặn, điệp viên sẽ biết khóa, hiển nhiên rồi.
- 5:06 Vì vậy, cần tìm một cách để thống nhất một khóa,
- 5:10 nhưng không bao giờ thực sự viết nó ra một cách rõ ràng.
- 5:13 Đây được gọi là vấn đề trao đổi khóa, hoặc thiết lập khóa.
- 5:18 Làm thế nào để thống nhất từ xa một khóa mã hóa chung,
- 5:23 biết rằng chúng ta có thể bị nghe lén liên tục?
- 5:27 Thoạt nhìn, điều này dường như gần như không thể giải quyết được.
- 5:30 Nếu chúng ta không có cách nào để trao đổi thông tin một cách bí mật,
- 5:34 làm thế nào chúng ta có thể thống nhất từ xa một khóa giống nhau
- 5:37 mà không để một kẻ tò mò nào đó cũng biết được?
- 5:40 Đây là vấn đề mà các nhà toán học Diffie và Hellman đã giải quyết vào năm 1976.
- 5:47 Theo truyền thống, trong mật mã học, chúng ta mô tả mọi thứ như sau.
- 5:52 Hãy tưởng tượng hai người, theo truyền thống được gọi là Alice và Bob,
- 5:56 những người chưa từng gặp mặt hay nói chuyện trước đây,
- 5:59 nhưng có thể liên lạc từ xa qua một đường truyền không được bảo mật.
- 6:03 Hơn nữa, chúng ta có một người, thường được gọi là Eve,
- 6:06 người đã kết nối vào đường truyền này
- 6:09 và có thể thu được mọi thứ sẽ được nói trên đó.
- 6:13 Làm thế nào Alice và Bob có thể thống nhất một khóa chung
- 6:17 mà không để Eve biết được khóa đó?
- 6:20 Điều đó dường như không thể!
- 6:23 Một lưu ý nhỏ trước khi bắt đầu.
- 6:25 Trong phương pháp Diffie-Hellman, khóa sẽ không phải là một từ hay một chuỗi chữ cái,
- 6:29 mà là một con số.
- 6:31 Về cơ bản, điều đó không thay đổi nhiều.
- 6:33 Rất dễ dàng để tạo ra cái này từ cái kia.
- 6:36 Để cho bạn thấy Alice và Bob có thể tiến hành như thế nào để quyết định một khóa số,
- 6:41 tôi sẽ bắt đầu từ từ bằng một phương pháp không hoạt động,
- 6:45 nhưng sẽ đưa chúng ta đi đúng hướng.
- 6:47 Hãy tưởng tượng Alice và Bob gọi điện cho nhau và cùng nhau quyết định một số cơ sở
- 6:52 mà chúng ta sẽ gọi là G.
- 6:54 Giả sử họ chọn G bằng 17.
- 6:56 Và hiển nhiên, đường truyền không được bảo mật,
- 6:58 nên Eve nghe thấy mọi thứ và ghi lại giá trị G này.
- 7:02 Sau đó, Alice và Bob mỗi người chọn một số bí mật riêng,
- 7:07 mà chúng ta ký hiệu là A cho Alice và B cho Bob.
- 7:10 Sau đó, mỗi người sẽ nhân số bí mật của mình với số chung G.
- 7:15 Alice sẽ tạo ra số G nhân A và Bob tạo ra số G nhân B.
- 7:19 Nếu Alice chọn 4 và Bob chọn 6, thì sẽ là 68 và 102.
- 7:24 Sau đó, họ thông báo cho người kia kết quả của phép nhân này.
- 7:28 Alice gửi G nhân A cho Bob, và Bob gửi G nhân B cho Alice.
- 7:33 Và điều này được thực hiện mà không có bảo mật.
- 7:35 Vì vậy, ở đây, một lần nữa, Eve biết các giá trị này.
- 7:38 Và cuối cùng, bước cuối cùng, mỗi người nhân số mà mình vừa nhận được
- 7:42 với số bí mật của riêng mình.
- 7:44 Alice do đó tạo ra số G nhân B nhân A, sẽ là 408,
- 7:49 và Bob tạo ra số G nhân A nhân B, cũng sẽ là 408, hiển nhiên rồi.
- 7:53 Và thế là, bây giờ họ có thể quyết định sử dụng kết quả chung này
- 7:57 làm khóa mã hóa.
- 7:59 Bạn thấy rằng với giao thức này, cuối cùng mỗi bên sẽ có cùng một số,
- 8:03 G nhân A nhân B.
- 8:05 Vì vậy, họ đã thống nhất về một khóa chung,
- 8:08 nhưng không có lúc nào khóa này được truyền rõ ràng
- 8:13 qua đường truyền không an toàn.
- 8:15 Không lúc nào họ trao đổi với nhau số 408.
- 8:20 Vấn đề, bạn thấy đấy, là Eve biết G, đó là 17,
- 8:24 nhưng cũng biết G nhân A là 68, và G nhân B là 102.
- 8:28 Từ đó, rất dễ dàng để cô ấy tìm lại
- 8:31 các số bí mật của Alice và Bob.
- 8:33 Ví dụ, A có được bằng cách chia G A cho G,
- 8:37 ở đây 68 chia 17, ta được 4.
- 8:39 Và do đó Eve có thể dễ dàng tự mình khôi phục lại khóa hoàn chỉnh.
- 8:44 Vì vậy, phương pháp tôi vừa đề xuất không hiệu quả lắm,
- 8:47 vì ngay cả khi khóa không được truyền rõ ràng,
- 8:50 Eve có đủ thông tin để dễ dàng tạo lại nó.
- 8:54 Để cố gắng khắc phục vấn đề này, hãy thử một biến thể phức tạp hơn.
- 8:58 Chúng ta giữ số chung G và các số bí mật A và B,
- 9:02 nhưng lần này chúng ta sẽ dùng lũy thừa thay vì phép nhân.
- 9:06 Điều đó có nghĩa là Alice tạo ra số G mũ A,
- 9:10 mà cô ấy gửi cho Bob, và Bob tạo ra G mũ B,
- 9:13 mà anh ấy gửi lại cho cô ấy.
- 9:16 Và sau đó, mỗi người lấy lũy thừa với số bí mật của riêng mình.
- 9:20 Vì vậy Alice làm G mũ B mũ A,
- 9:23 trong khi Bob làm G mũ A mũ B.
- 9:26 Và một lần nữa, với giao thức này, cuối cùng họ sẽ có cùng một kết quả,
- 9:30 G mũ A nhân B,
- 9:32 do đó là một khóa chung mà không bao giờ được truyền rõ ràng qua đường truyền.
- 9:36 Eve, về phần mình, chỉ biết những gì cô ấy đã chặn được,
- 9:40 cụ thể là G, G mũ A và G mũ B.
- 9:43 Chỉ là một lần nữa, cô ấy có thể giải quyết được chỉ với những thông tin này.
- 9:47 Nếu Eve biết số G mũ A,
- 9:50 cô ấy có thể lấy logarit của nó,
- 9:52 bằng A nhân logarit của G.
- 9:55 Và sau đó, bằng cách chia cho logarit của G,
- 9:58 cô ấy có thể tách A ra.
- 9:59 Vì vậy, một lần nữa, cô ấy có thể dễ dàng khôi phục các số bí mật,
- 10:03 và do đó là khóa chung.
- 10:04 Vẫn không được.
- 10:06 Nguồn gốc cơ bản của vấn đề là Alice và Bob
- 10:09 mỗi lần đều cố gắng che giấu số bí mật của mình
- 10:12 bằng cách trộn nó với G.
- 10:15 Nhưng mỗi lần, Eve đều có thể gỡ bỏ sự pha trộn này
- 10:18 và tìm lại các số bí mật.
- 10:20 Nếu chúng ta dùng phép nhân, Eve có thể dùng phép chia.
- 10:23 Nếu chúng ta dùng lũy thừa, Eve dùng logarit.
- 10:27 Để ý tưởng này hoạt động, cần có một phép toán trộn
- 10:30 mà Alice và Bob dễ dàng thực hiện,
- 10:32 nhưng gần như không thể đảo ngược đối với Eve.
- 10:35 Đây là cái mà trong mật mã học gọi là hàm một chiều.
- 10:39 Chà, chúng ta có thể tạo ra một cái từ nỗ lực trước đây của mình
- 10:44 bằng cách thêm một thành phần nữa, đó là modulo.
- 10:53 Modulo là một phép toán tính toán
- 10:55 phần dư của phép chia nguyên cho một số.
- 10:58 Ví dụ, 17 modulo 3, kết quả là 2.
- 11:01 Bởi vì nếu bạn thực hiện phép chia nguyên 17 cho 3,
- 11:04 bạn sẽ được 5 và còn dư 2.
- 11:06 Tương tự, 14 modulo 5, kết quả là 4.
- 11:09 Hoặc 42 modulo 6, kết quả là 0, v.v.
- 11:12 Ý tưởng của phương pháp Diffie-Hellman,
- 11:14 là chọn một số P
- 11:16 mà Alice và Bob công khai trao đổi, giống như G,
- 11:19 và sau đó làm chính xác như trong ví dụ của tôi,
- 11:22 với các lũy thừa, nhưng lần này,
- 11:24 sau mỗi phép toán, chúng ta sẽ áp dụng modulo P.
- 11:28 Nghĩa là, với số bí mật A của mình,
- 11:30 Alice tính G mũ A modulo P và gửi cho Bob.
- 11:35 Bob, về phần mình, tính G mũ B modulo P và gửi cho Alice.
- 11:40 Và sau đó, mỗi người áp dụng lũy thừa của số bí mật của mình
- 11:44 và lại lấy modulo P.
- 11:46 Và ở đây, điều đó không nhất thiết phải rõ ràng,
- 11:48 nhưng khi làm như vậy, cuối cùng họ sẽ có chính xác cùng một số,
- 11:53 thực chất là G mũ A nhân B modulo P.
- 11:57 Thật ra, những ai học MathExpert ở năm cuối cấp 3
- 11:59 có thể thử chứng minh điều này bằng các phép đồng dư.
- 12:02 Nhờ kỹ thuật này, gần giống với kỹ thuật trước,
- 12:06 nhưng áp dụng modulo P sau mỗi phép toán,
- 12:09 Alice và Bob sẽ lại thành công trong việc thống nhất một khóa chung,
- 12:13 mà không bao giờ công khai truyền nó.
- 12:16 Chỉ là đối với Eve, điều này thay đổi gì?
- 12:19 Liệu cô ta có thể lại trích xuất A hoặc B từ thông tin mà cô ta có
- 12:23 và tái tạo khóa như trước không?
- 12:26 À không, bởi vì đối với một người thậm chí chặn tất cả các cuộc trò chuyện,
- 12:31 việc giải mã trở nên rất rất phức tạp,
- 12:34 do modulo đã làm mọi thứ trở nên lẫn lộn.
- 12:38 Về mặt toán học, ngay cả khi biết G, P và G mũ A modulo P,
- 12:44 rất khó để tìm lại A.
- 12:47 Phép toán lũy thừa với modulo rất khó đảo ngược.
- 12:51 Đây là một phép toán một chiều, đúng như chúng ta mong muốn.
- 12:54 Chúng ta có thể xem qua một ví dụ nếu bạn muốn.
- 12:56 Hãy lấy P bằng 17 và G bằng 5,
- 12:59 mà Alice và Bob đã công khai thống nhất.
- 13:02 Vì vậy, Eve hoàn toàn biết về hai giá trị này.
- 13:05 Alice chọn số bí mật của mình, giả sử là 4,
- 13:09 và Bob chọn 6.
- 13:11 Alice lấy 5 mũ 4, kết quả là 625,
- 13:14 và lấy modulo 17, còn lại 13.
- 13:17 Tương tự đối với Bob, anh ấy tính 5 mũ 6,
- 13:20 lấy modulo 17, kết quả là 2.
- 13:22 Và mỗi người gửi kết quả cho người kia, người đó áp dụng lũy thừa của riêng mình.
- 13:26 Alice lấy 2 mũ 4 modulo 17, kết quả là 16.
- 13:30 Bob tính 13 mũ 6 modulo 17, kết quả cũng là 16.
- 13:34 Vậy là chúng ta có một khóa chung cho cả hai bên.
- 13:38 Về phần mình, Eve biết P bằng 17 và G bằng 5, tất nhiên rồi,
- 13:43 nhưng chỉ có 13 và 2 làm giá trị trung gian.
- 13:47 Để tìm lại A, ví dụ, số bí mật của Alice,
- 13:50 cô ta phải tìm một số mà khi áp dụng làm lũy thừa cho 5,
- 13:54 sẽ cho lại 13 modulo 17.
- 13:57 Và nghe có vẻ không như vậy, nhưng đây là một phương trình rất khó.
- 14:01 Phép toán mà chúng ta phải giải để tìm ra lời giải,
- 14:04 đó là cái mà chúng ta gọi là bài toán logarit rời rạc.
- 14:07 Trong phương pháp trước của tôi chỉ với các lũy thừa,
- 14:10 Eve đã giải quyết được bằng cách áp dụng một logarit đơn giản.
- 14:13 Bây giờ, do modulo, phải giải logarit rời rạc,
- 14:17 điều này có thể về mặt lý thuyết, nhưng rất tốn công trong thực tế.
- 14:21 Hầu như phải thử tất cả các khả năng.
- 14:24 Vậy tôi nói rằng nó rất phức tạp, nhưng vẫn cần phải cẩn thận một chút.
- 14:28 Khi chúng ta lấy một số modulo P, kết quả chắc chắn nằm giữa 0 và P-1.
- 14:34 Đó là phần dư của một phép chia số nguyên.
- 14:37 Vì vậy, nếu chúng ta muốn có tối đa các khả năng khác nhau để Eve thử nghiệm,
- 14:42 thì trước tiên chúng ta phải chọn một P lớn nhất có thể.
- 14:45 Nhưng chưa hết, chúng ta cũng phải chọn nó thật tốt,
- 14:48 và đặc biệt là chọn G phù hợp với nó.
- 14:51 Tôi sẽ minh họa điều này bằng một ví dụ.
- 14:53 Nếu tôi lấy P bằng 15 và G bằng 4,
- 14:57 chúng ta biết rằng khóa cuối cùng sẽ là G mũ AB modulo P,
- 15:01 tức là G mũ một số nào đó modulo P.
- 15:04 Và chúng ta có thể xem các giá trị khác nhau của G mũ modulo P là bao nhiêu.
- 15:09 Với lựa chọn giá trị của tôi, G mũ 1 modulo P là 4,
- 15:12 G mũ 2 modulo P là 1,
- 15:14 G mũ 3 modulo P là 4,
- 15:16 G mũ 4 modulo P là 1, v.v.
- 15:20 Chúng ta nhận ra rằng mặc dù đã chọn P bằng 15,
- 15:23 các lũy thừa của G luôn rơi vào 1 hoặc 4.
- 15:27 Vì vậy, chúng ta tưởng rằng có 15 khóa khả thi mà Eve phải thử,
- 15:31 nhưng chúng ta chỉ có 2.
- 15:33 Tuyệt đối phải tránh tình huống này,
- 15:36 vì khi giảm không gian khả năng như vậy,
- 15:39 chúng ta tạo điều kiện thuận lợi đáng kể cho Eve, người đang tìm cách phá khóa của chúng ta.
- 15:44 May mắn thay, có một giải pháp.
- 15:46 Lý tưởng nhất là chọn một số P là số nguyên tố,
- 15:50 và một số G là cái mà chúng ta gọi là căn nguyên thủy modulo P.
- 15:55 Một căn nguyên thủy có nghĩa là nếu bạn nâng G
- 15:58 lên tất cả các lũy thừa từ 1 đến P-1,
- 16:01 bạn sẽ tìm thấy tất cả các số khả thi từ 1 đến P-1.
- 16:05 Vì vậy, chúng ta sẽ ở trong một trường hợp có tối đa các khả năng.
- 16:09 Chúng ta có thể thấy điều đó qua một ví dụ.
- 16:11 Với P bằng 13, chẳng hạn, tôi sẽ không chứng minh cho bạn,
- 16:14 nhưng các căn nguyên thủy chỉ là 2, 6, 7 và 11.
- 16:18 Vì vậy, nếu chúng ta lấy G bằng 6,
- 16:20 các lũy thừa của 6 modulo 13 trải đều từ 1 đến 12, thật hoàn hảo.
- 16:25 Nhưng với G bằng 5, nó không hoạt động tốt,
- 16:27 vì các lũy thừa chỉ lặp lại trên 5, 12, 8 và 1.
- 16:31 Vì vậy, chỉ có 4 khả năng thay vì 12.
- 16:35 Do đó, điều quan trọng là phải chọn G thật tốt
- 16:38 một căn nguyên thủy của số P mà chúng ta đã chọn.
- 16:42 Với những biện pháp phòng ngừa nhỏ này,
- 16:44 chúng ta có được bản chất của thuật toán Diffie-Hellman,
- 16:47 do đó giải quyết vấn đề xác định một khóa mã hóa chung
- 16:52 khi chúng ta đang ở trên một kênh công cộng.
- 16:54 Thuật toán này lần đầu tiên được công bố vào năm 1976
- 16:57 và được cấp bằng sáng chế tại Hoa Kỳ vào năm sau.
- 16:59 Nhưng may mắn thay, giờ đây nó đã thuộc phạm vi công cộng
- 17:02 và nó được sử dụng rất rộng rãi để bảo mật
- 17:05 phần lớn các giao tiếp trên Internet.
- 17:08 Do đó, khi hai máy tính cần thiết lập
- 17:11 một kênh liên lạc được mã hóa,
- 17:13 để dữ liệu của bạn không bị truyền đi dưới dạng văn bản rõ ràng trên mạng,
- 17:16 họ thường sử dụng một biến thể của thuật toán Diffie-Hellman.
- 17:20 Và chính nguyên tắc này đã bảo mật giao thức TLS,
- 17:24 nằm đằng sau hầu hết các lượt truy cập mà bạn thực hiện trên các trang web.
- 17:28 Vì vậy, cảm ơn Diffie-Hellman.
- 17:31 Tuy nhiên, như mọi khi, phương pháp này cũng không hoàn toàn bất khả xâm phạm.
- 17:35 Ví dụ, phải cẩn thận để Eve không thể
- 17:38 giả mạo danh tính của Alice và Bob.
- 17:41 Điều đó sẽ cho phép cô ta chen vào giữa hai người
- 17:44 bằng cách giả làm Bob trong mắt Alice và ngược lại.
- 17:47 Và khi đó, Eve có thể tự do làm gì tùy thích.
- 17:50 Ngoài rủi ro này, chúng ta cũng phải đảm bảo
- 17:52 khi Alice và Bob mỗi người chọn số bí mật của riêng họ,
- 17:56 Ève không thể dễ dàng đoán được.
- 17:59 Và vì vậy, lý tưởng nhất là họ nên đưa ra lựa chọn của mình
- 18:02 bằng cách sử dụng một trình tạo số ngẫu nhiên tốt.
- 18:06 Và nhân tiện, câu hỏi về cách tạo ra một trình tạo ngẫu nhiên này,
- 18:10 tôi nghĩ rằng đó sẽ là một chủ đề rất hay cho tập tiếp theo.
- 18:13 Cảm ơn bạn đã theo dõi video.
- 18:15 Hãy đăng ký để không bỏ lỡ các bài đăng trong tương lai.
- 18:17 Hãy tham gia cùng tôi trên Discord của Science Étonnante,
- 18:20 tôi sẽ để liên kết trong phần mô tả.
- 18:22 Và hẹn gặp lại bạn sớm trong một video mới.
- 18:24 Hẹn gặp lại!
Cette vidéo explore en détail l'algorithme de Diffie-Hellman, une technique révolutionnaire en cryptographie qui permet à deux personnes d'établir une clé de chiffrement secrète commune, même si toutes leurs communications sont interceptées par un espion. Le narrateur commence par introduire le problème de l'échange de clés en examinant des méthodes de chiffrement plus anciennes et plus simples, telles que le chiffrement de César, le chiffrement par substitution et le chiffrement par mot-clé. Il démontre leurs vulnérabilités, notamment la facilité avec laquelle un espion peut les déchiffrer, soulignant ainsi la nécessité d'une méthode plus robuste pour l'échange de clés. Le cœur de la vidéo est dédié à l'explication progressive de l'algorithme de Diffie-Hellman. Le narrateur utilise l'analogie d'Alice, Bob et Eve pour illustrer le scénario. Il présente d'abord des tentatives infructueuses basées sur la multiplication et l'exponentiation simple, expliquant pourquoi ces approches échouent : l'espion Eve peut facilement inverser les opérations (division et logarithme) pour retrouver les secrets partagés. La solution réside dans l'introduction d'une "fonction à sens unique", facile à calculer mais extrêmement difficile à inverser. Cette fonction est réalisée en combinant l'exponentiation avec l'opération modulo. Le narrateur explique comment Alice et Bob peuvent choisir publiquement un nombre premier P et une racine primitive G, puis utiliser leurs nombres secrets respectifs (A et B) pour calculer des valeurs intermédiaires (G^A mod P et G^B mod P) qu'ils échangent publiquement. En appliquant ensuite leur propre secret à la valeur reçue, ils aboutissent tous deux à la même clé secrète (G^(A*B) mod P) sans jamais l'avoir explicitement transmise. La difficulté pour Eve de retrouver les secrets d'Alice et Bob réside dans le "problème du logarithme discret", qui est pratiquement insoluble pour de grands nombres sans essayer toutes les possibilités. La vidéo insiste sur l'importance de bien choisir les paramètres P (un grand nombre premier) et G (une racine primitive modulo P) pour garantir la sécurité de l'algorithme. Enfin, le narrateur aborde les applications concrètes de Diffie-Hellman, notamment son rôle crucial dans la sécurisation du protocole TLS, qui est à la base de la plupart des communications sécurisées sur Internet. Il mentionne également certaines limites, comme la vulnérabilité aux attaques de l'homme du milieu si l'identité des parties n'est pas vérifiée, et la nécessité de bons générateurs de nombres aléatoires pour les secrets A et B.
字幕のタイミング
字幕と音声がずれていますか? ここでタイミングを調整できます:
マイナス = 字幕を早く/プラス = 遅く表示。この端末に、動画やクリップごとに個別に保存されます。
誤りを報告する
問題点をお知らせください。すべての報告を確認しています。
コメント 0件
最初のコメントを投稿してみましょう。