1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Vigenère Cipher]

2
00:00:02,000 --> 00:00:04,000
[Nate Hardison - Université de Harvard]

3
00:00:04,000 --> 00:00:07,000
[C'est CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Rencontre avec Alice.

5
00:00:09,000 --> 00:00:11,260
Alice a le béguin pour Bob.

6
00:00:11,260 --> 00:00:15,030
Heureusement pour Alice, Bob a également yeux que pour elle.

7
00:00:15,030 --> 00:00:17,700
Malheureusement pour leur amour naissant,

8
00:00:17,700 --> 00:00:20,580
pas seulement les parents d'Alice au pays désapprouvent Bob,

9
00:00:20,580 --> 00:00:23,820
mais le meilleur ami d'Alice, Evelyn, a le béguin secret sur Bob

10
00:00:23,820 --> 00:00:27,290
et veut égoïstement de les séparer à tout prix.

11
00:00:27,290 --> 00:00:31,280
Pour envoyer des messages secrets à l'autre que les parents d'Alice ne peuvent pas comprendre,

12
00:00:31,280 --> 00:00:34,140
>> Alice et Bob ont été en utilisant un chiffrement de César,

13
00:00:34,140 --> 00:00:37,410
qui fonctionne en décalant l'alphabet par un certain nombre de lettres

14
00:00:37,410 --> 00:00:39,800
comme un moyen de générer un nouvel alphabet.

15
00:00:39,800 --> 00:00:44,130
Chaque lettre de l'alphabet d'origine est alors substituée par la lettre correspondante

16
00:00:44,130 --> 00:00:46,920
dans le nouvel alphabet décalé.

17
00:00:46,920 --> 00:00:50,240
Numéro préféré d'Alice est 3, qui sait Bob,

18
00:00:50,240 --> 00:00:52,450
alors elle utilise 3 comme sa clé.

19
00:00:52,450 --> 00:00:55,430
Quand elle se déplace de l'alphabet anglais par 3 lettres,

20
00:00:55,430 --> 00:01:00,680
A devient D, B devient E, C devient F,

21
00:01:00,680 --> 00:01:02,670
et ainsi de suite.

22
00:01:02,670 --> 00:01:07,460
>> Quand elle arrive à la fin de l'alphabet - les lettres X, Y et Z -

23
00:01:07,460 --> 00:01:09,970
elle enveloppe tout autour du début de l'alphabet

24
00:01:09,970 --> 00:01:14,850
et X substituts avec A, Y, avec B, C et Z avec

25
00:01:14,850 --> 00:01:18,550
Alors, quand Alice va crypter son message secret à Bob,

26
00:01:18,550 --> 00:01:21,520
à savoir «Rendez-vous au parc à onze heures»,

27
00:01:21,520 --> 00:01:23,790
elle fait juste les substitutions appropriées.

28
00:01:23,790 --> 00:01:30,900
M est P, E devient H, et ainsi de suite jusqu'à ce que son message non chiffré en texte clair

29
00:01:30,900 --> 00:01:34,350
est transformé en texte chiffré cryptée:

30
00:01:34,350 --> 00:01:37,280
"Phhw ph ps ps wkh sdun hohyhq dp"

31
00:01:37,280 --> 00:01:39,370
n'est certainement pas la plus romantique de résonance,

32
00:01:39,370 --> 00:01:41,650
mais Alice pense que ça va le faire.

33
00:01:41,650 --> 00:01:45,140
>> Alice donne le message à Evelyn de livrer à la maison de Bob.

34
00:01:45,140 --> 00:01:50,030
Mais Evelyn prend la place il retourna dans sa chambre et tente de déchiffrer le code.

35
00:01:50,030 --> 00:01:55,470
Une des premières choses que l'avis de Evelyn est que la lettre H apparaît 7 fois dans le message,

36
00:01:55,470 --> 00:01:58,930
beaucoup plus souvent que tout autre lettre.

37
00:01:58,930 --> 00:02:01,960
Sachant que la lettre E est la plus courante de la langue anglaise,

38
00:02:01,960 --> 00:02:05,390
produisent près de 13% du temps,

39
00:02:05,390 --> 00:02:09,910
Evelyn devine que H a été substitué pour E afin de rendre le message secret

40
00:02:09,910 --> 00:02:14,030
et tente en utilisant une clé de 3 à décrypter.

41
00:02:14,030 --> 00:02:19,700
>> Quelques minutes plus tard, Evelyn figure sur les plans d'Alice au pays et appelle méchamment les parents d'Alice.

42
00:02:19,700 --> 00:02:22,700
Alice et Bob avait pris CS50, ils auraient su de cette

43
00:02:22,700 --> 00:02:25,750
fréquence-analyse sur l'attaque chiffrement de César,

44
00:02:25,750 --> 00:02:28,310
ce qui lui permet d'être rompue assez rapidement.

45
00:02:28,310 --> 00:02:32,590
Ils auraient aussi connu que le chiffre est facilement l'objet d'une attaque par force brute,

46
00:02:32,590 --> 00:02:35,940
Evelyn lequel aurait pu essayer toutes les clés possibles des 25,

47
00:02:35,940 --> 00:02:38,440
ou des changements de l'alphabet anglais,

48
00:02:38,440 --> 00:02:40,490
afin de déchiffrer le message.

49
00:02:40,490 --> 00:02:43,710
Pourquoi 25 et non 26 touches?

50
00:02:43,710 --> 00:02:49,010
>> Eh bien, essayez de déplacer n'importe quelle lettre de 26 postes, et vous verrez pourquoi.

51
00:02:49,010 --> 00:02:52,280
Quoi qu'il en soit, une attaque par force brute aurait pris un peu plus longtemps Evelyn

52
00:02:52,280 --> 00:02:56,070
mais pas assez pour l'empêcher de contrecarrer les plans d'Alice et de Bob,

53
00:02:56,070 --> 00:02:58,660
surtout si Evelyn a l'aide d'un ordinateur

54
00:02:58,660 --> 00:03:02,640
qui pourrait déchirer tous les 25 cas en un instant.

55
00:03:02,640 --> 00:03:06,170
Donc, ce problème également en proie à d'autres qui ont utilisé le chiffre de César,

56
00:03:06,170 --> 00:03:10,300
et donc les gens ont commencé à expérimenter avec des chiffres de substitution plus complexes

57
00:03:10,300 --> 00:03:14,190
que l'utilisation de plusieurs valeurs de décalage au lieu d'un seul.

58
00:03:14,190 --> 00:03:18,080
L'un des plus connus d'entre eux est appelé chiffrement de Vigenère.

59
00:03:18,080 --> 00:03:19,980
Comment pouvons-nous obtenir des valeurs de plusieurs équipes?

60
00:03:19,980 --> 00:03:24,630
Eh bien, au lieu d'utiliser un certain nombre comme la clé, nous utilisons un mot pour la clé.

61
00:03:24,630 --> 00:03:27,940
Nous allons utiliser chaque lettre dans la clé pour générer un nombre,

62
00:03:27,940 --> 00:03:33,670
et l'effet est que nous allons avoir plusieurs César chiffrement de type clés pour le déplacement des lettres.

63
00:03:33,670 --> 00:03:36,620
>> Voyons comment cela fonctionne en cryptant le message d'Alice à Bob:

64
00:03:36,620 --> 00:03:39,010
Rendez-vous au parc de onze heures

65
00:03:39,010 --> 00:03:42,610
Personnellement, je pense que le bacon est délicieux,

66
00:03:42,610 --> 00:03:44,480
nous allons donc l'utiliser comme clé.

67
00:03:44,480 --> 00:03:48,220
Si nous prenons le message dans son clair, format texte brut,

68
00:03:48,220 --> 00:03:51,020
nous voyons que c'est 25 lettres de long.

69
00:03:51,020 --> 00:03:55,020
Bacon ne dispose que de 5 lettres, donc nous avons besoin de le répéter 5 fois

70
00:03:55,020 --> 00:03:57,200
pour le faire correspondre à la longueur du texte en clair.

71
00:03:57,200 --> 00:03:59,880
>> Bacon Bacon Bacon Bacon Bacon.

72
00:03:59,880 --> 00:04:02,300
Comme une brève parenthèse, si le nombre de lettres dans le texte

73
00:04:02,300 --> 00:04:05,780
ne divise pas proprement par le nombre de lettres dans la clé,

74
00:04:05,780 --> 00:04:08,260
nous venons de mettre fin à la répétition finale de la clé de notre enfance,

75
00:04:08,260 --> 00:04:11,800
en utilisant uniquement les lettres que nous avons besoin de faire tout à la hauteur.

76
00:04:11,800 --> 00:04:14,590
Maintenant, pouvons-nous trouver les valeurs de décalage.

77
00:04:14,590 --> 00:04:19,100
>> Nous allons le faire en utilisant la position de chaque lettre de notre clé - bacon -

78
00:04:19,100 --> 00:04:21,560
dans l'alphabet de A à Z.

79
00:04:21,560 --> 00:04:26,060
Puisque nous sommes des informaticiens, nous aimons commencer à compter à zéro au lieu de 1,

80
00:04:26,060 --> 00:04:30,230
Nous allons donc dire que la position de la première lettre de bacon - B -

81
00:04:30,230 --> 00:04:33,840
est en position 1 dans le Un index zéro à l'alphabet Z,

82
00:04:33,840 --> 00:04:38,300
pas 2, et la position de A est égale à zéro, pas 1.

83
00:04:38,300 --> 00:04:42,450
Grâce à cet algorithme, nous pouvons trouver les valeurs de décalage pour chaque lettre.

84
00:04:42,450 --> 00:04:45,330
>> Pour chiffrer le texte clair et générer du texte chiffré,

85
00:04:45,330 --> 00:04:49,070
nous venons de passer chaque lettre du texte en clair de la valeur spécifiée,

86
00:04:49,070 --> 00:04:54,140
comme nous le faisons avec le chiffrement de César, l'emballage de Z à A si nécessaire.

87
00:04:54,140 --> 00:04:57,880
M se décalée de 1 place pour devenir N.

88
00:04:57,880 --> 00:05:02,350
Le premier E ne se déplace pas du tout, mais nous passons par le second E à G 2 places

89
00:05:02,350 --> 00:05:06,200
et T par 14 places à H.

90
00:05:06,200 --> 00:05:08,610
Si nous travaillons à travers le texte, nous nous retrouvons avec,

91
00:05:08,610 --> 00:05:12,580
"Negh zf av huf pcfx bt gzrwep once"

92
00:05:12,580 --> 00:05:16,620
Encore une fois, pas très romantique, mais qui sonne vraiment énigmatique.

93
00:05:16,620 --> 00:05:19,750
Si Alice et Bob avait connu Vigenère chiffre,

94
00:05:19,750 --> 00:05:23,330
auraient-ils été à l'abri des regards indiscrets Evelyn?

95
00:05:23,330 --> 00:05:24,870
Que pensez-vous?

96
00:05:24,870 --> 00:05:27,450
Voudriez-vous vous connecter sur votre compte bancaire si votre banque a décidé d'utiliser

97
00:05:27,450 --> 00:05:32,720
>> Vigenère chiffrement pour crypter vos communications en utilisant votre mot de passe de votre clé?

98
00:05:32,720 --> 00:05:34,810
Si j'étais vous, je ne veux pas.

99
00:05:34,810 --> 00:05:38,720
Et tandis que Evelyn pourrait être occupé suffisamment longtemps pour que Alice et Bob d'avoir leur meet-up,

100
00:05:38,720 --> 00:05:41,600
ce n'est pas la peine pour Alice et Bob pour le hasard.

101
00:05:41,600 --> 00:05:45,780
Vigenère chiffre est relativement facile de se briser si vous connaissez la longueur de la clé

102
00:05:45,780 --> 00:05:48,490
car alors vous pouvez traiter le texte chiffré crypté

103
00:05:48,490 --> 00:05:52,840
comme le produit d'un système de chiffrement de César quelques entrelacées.

104
00:05:52,840 --> 00:05:55,950
>> Trouver la longueur de la clé n'est pas très difficile non plus.

105
00:05:55,950 --> 00:06:00,520
Si l'original en texte brut message est assez long pour que certains mots apparaissent plusieurs fois,

106
00:06:00,520 --> 00:06:04,420
vous finirez par voir la répétition surgissent dans le texte chiffré crypté,

107
00:06:04,420 --> 00:06:10,010
comme dans cet exemple, où l'on voit apparaître deux fois Moncy.

108
00:06:10,010 --> 00:06:13,800
En outre, vous pouvez effectuer une attaque par force brute sur le chiffre.

109
00:06:13,800 --> 00:06:17,220
Cela prend beaucoup plus de temps que d'une attaque par force brute sur le chiffre de César,

110
00:06:17,220 --> 00:06:20,670
qui peut se faire presque instantanément avec un ordinateur

111
00:06:20,670 --> 00:06:27,130
car au lieu de 25 cas pour vérifier que vous avez 26 ⁿ - 1 possibilités,

112
00:06:27,130 --> 00:06:29,580
où n est la longueur de la clé inconnue.

113
00:06:29,580 --> 00:06:34,040
>> C'est parce que chaque lettre de la clé pourrait être l'une des 26 lettres,

114
00:06:34,040 --> 00:06:38,280
A à Z, et une personne intelligente serait essayez d'utiliser une clé qui ne peut être trouvé dans un dictionnaire,

115
00:06:38,280 --> 00:06:44,280
ce qui signifie que vous aurez à tester toutes les combinaisons de lettres bizarres, comme ZXXXFF,

116
00:06:44,280 --> 00:06:47,690
et non seulement quelques cent mille mots dans le dictionnaire.

117
00:06:47,690 --> 00:06:53,200
Le moins 1 entre dans le calcul parce que vous ne voulez pas utiliser une clé avec seulement des A,

118
00:06:53,200 --> 00:06:56,200
car avec notre index zéro alphabet qui vous donnerait le même effet

119
00:06:56,200 --> 00:06:59,620
comme l'utilisation d'un algorithme de chiffrement avec une clé César de zéro.

120
00:06:59,620 --> 00:07:04,120
Quoi qu'il en soit, 26 ⁿ - 1 ne se grand assez rapidement,

121
00:07:04,120 --> 00:07:08,080
mais alors vous avez certainement ne voudrais pas essayer de casser un algorithme de chiffrement à la main de cette façon,

122
00:07:08,080 --> 00:07:11,080
c'est certainement faisable avec un ordinateur.

123
00:07:11,080 --> 00:07:14,030
Heureusement pour Alice et Bob, et pour les services bancaires en ligne,

124
00:07:14,030 --> 00:07:17,890
cryptographes ont développé des moyens plus sûrs pour crypter les messages secrets

125
00:07:17,890 --> 00:07:19,690
des regards indiscrets.

126
00:07:19,690 --> 00:07:22,400
>> Toutefois, c'est un sujet pour une autre fois.

127
00:07:22,400 --> 00:07:26,210
Mon nom est Nate Hardison. C'est CS50.