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 - Harvard Universiteit]

3
00:00:04,000 --> 00:00:07,000
[Hierdie is CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Ontmoet Alice.

5
00:00:09,000 --> 00:00:11,260
Alice het 'n drukgang op Bob.

6
00:00:11,260 --> 00:00:15,030
Gelukkig vir Alice, Bob het ook oë vir haar.

7
00:00:15,030 --> 00:00:17,700
Ongelukkig vir hulle ontluikende romanse,

8
00:00:17,700 --> 00:00:20,580
Alice se ouers nie net afkeur van Bob,

9
00:00:20,580 --> 00:00:23,820
maar Alice se beste vriend, Evelyn, het 'n geheime crush op Bob

10
00:00:23,820 --> 00:00:27,290
en wil selfsugtig om hulle uitmekaar te hou ten alle koste.

11
00:00:27,290 --> 00:00:31,280
Om geheime boodskappe te stuur aan mekaar dat Alice se ouers kan nie verstaan ​​nie,

12
00:00:31,280 --> 00:00:34,140
>> Alice en Bob het al met behulp van 'n keiser cipher,

13
00:00:34,140 --> 00:00:37,410
wat werk deur die verskuiwing van die alfabet deur 'n sekere aantal letters

14
00:00:37,410 --> 00:00:39,800
as 'n manier om 'n nuwe alfabet te genereer.

15
00:00:39,800 --> 00:00:44,130
Elke letter in die oorspronklike alfabet word dan vervang deur die ooreenstemmende letter

16
00:00:44,130 --> 00:00:46,920
in die nuwe verskuif alfabet.

17
00:00:46,920 --> 00:00:50,240
Alice se gunsteling nommer is 3, wat Bob weet,

18
00:00:50,240 --> 00:00:52,450
so sy gebruik 3 as haar sleutel.

19
00:00:52,450 --> 00:00:55,430
Toe sy skuif die Engelse alfabet deur 3 letters,

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

21
00:01:00,680 --> 00:01:02,670
en so meer.

22
00:01:02,670 --> 00:01:07,460
>> Wanneer sy aan die einde van die alfabet - die letters X, Y en Z -

23
00:01:07,460 --> 00:01:09,970
sy vou net om terug na die begin van die alfabet

24
00:01:09,970 --> 00:01:14,850
en plaasvervangers X met A, Y met B, en Z met C.

25
00:01:14,850 --> 00:01:18,550
So wanneer Alice gaan haar geheime boodskap te enkripteer Bob,

26
00:01:18,550 --> 00:01:21,520
naamlik "Ontmoet my by die park op 11:00,"

27
00:01:21,520 --> 00:01:23,790
sy maak net die toepaslike substitusies.

28
00:01:23,790 --> 00:01:30,900
M word P, E word H, en so aan totdat haar ongeënkripteerde plain text boodskap

29
00:01:30,900 --> 00:01:34,350
is aangeskakel in geïnkripteer cipher teks:

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

31
00:01:37,280 --> 00:01:39,370
is beslis nie die mees romantiese klinkende,

32
00:01:39,370 --> 00:01:41,650
maar Alice glo wat dit sal doen.

33
00:01:41,650 --> 00:01:45,140
>> Alice gee die boodskap aan Evelyn na Bob se huis te lewer.

34
00:01:45,140 --> 00:01:50,030
Maar Evelyn neem plaas dit terug na haar kamer en probeer om die kode te kraak.

35
00:01:50,030 --> 00:01:55,470
Een van die eerste dinge Evelyn kennisgewings is dat die letter H voorkom 7 keer in die boodskap,

36
00:01:55,470 --> 00:01:58,930
baie meer kere as enige ander letter.

37
00:01:58,930 --> 00:02:01,960
Wetende dat die letter E is die mees algemene in die Engelse taal,

38
00:02:01,960 --> 00:02:05,390
plaasgevind het byna 13% van die tyd,

39
00:02:05,390 --> 00:02:09,910
Evelyn raai dat H vir E is vervang ten einde die geheime boodskap te maak

40
00:02:09,910 --> 00:02:14,030
en probeer om met behulp van 'n sleutel van 3 te dekripteer.

41
00:02:14,030 --> 00:02:19,700
>> Binne minute, Evelyn figure uit Alice se planne en kwaad noem Alice se ouers.

42
00:02:19,700 --> 00:02:22,700
Het Alice en Bob geneem CS50, sou hulle geweet het van hierdie

43
00:02:22,700 --> 00:02:25,750
frekwensie-analise aanval op die keiser cipher,

44
00:02:25,750 --> 00:02:28,310
wat toelaat dat dit redelik vinnig gebreek word.

45
00:02:28,310 --> 00:02:32,590
Hulle sou ook geweet het dat die cipher maklik is onderhewig aan 'n brute krag aanval,

46
00:02:32,590 --> 00:02:35,940
waardeur Evelyn kon probeer het al van die moontlike 25 sleutels,

47
00:02:35,940 --> 00:02:38,440
of verskuiwings van die Engelse alfabet,

48
00:02:38,440 --> 00:02:40,490
ten einde die boodskap te ontsyfer.

49
00:02:40,490 --> 00:02:43,710
Waarom 25 sleutels en nie 26?

50
00:02:43,710 --> 00:02:49,010
>> Wel, probeer om die verskuiwing van 'n brief deur 26 posisies, en jy sal sien waarom.

51
00:02:49,010 --> 00:02:52,280
In elk geval, 'n brute krag aanval sou geneem het Evelyn 'n bietjie langer

52
00:02:52,280 --> 00:02:56,070
maar nie lank genoeg om haar te hou van die thwarting van Alice en Bob se planne,

53
00:02:56,070 --> 00:02:58,660
veral as Evelyn het die hulp van 'n rekenaar

54
00:02:58,660 --> 00:03:02,640
wat kan rip deur al 25 gevalle in 'n oomblik.

55
00:03:02,640 --> 00:03:06,170
So, hierdie probleem het ook ander wat die keiser cipher gebruik geteister,

56
00:03:06,170 --> 00:03:10,300
en dus mense het begin eksperimenteer met meer komplekse vervanging getalle

57
00:03:10,300 --> 00:03:14,190
wat gebruik verskeie verskuiwing waardes in plaas van net een.

58
00:03:14,190 --> 00:03:18,080
Een van die mees bekende van hierdie Vigenère cipher genoem.

59
00:03:18,080 --> 00:03:19,980
Hoe kry ons verskeie verschuiving waardes?

60
00:03:19,980 --> 00:03:24,630
Wel, in plaas van die gebruik van 'n getal as die sleutel, gebruik ons ​​'n woord vir die sleutel.

61
00:03:24,630 --> 00:03:27,940
Ons sal elke letter in die sleutel gebruik om 'n getal te genereer,

62
00:03:27,940 --> 00:03:33,670
en die effek is dat ons verskeie Caesar cipher-styl sleutels sal vir die verskuiwing van letters.

63
00:03:33,670 --> 00:03:36,620
>> Kom ons kyk hoe dit werk deur versleutelen Alice se boodskap Bob:

64
00:03:36,620 --> 00:03:39,010
Ontmoet my by die park op 11:00

65
00:03:39,010 --> 00:03:42,610
Ek, persoonlik, dink spek is heerlik,

66
00:03:42,610 --> 00:03:44,480
so laat gebruik as die sleutel.

67
00:03:44,480 --> 00:03:48,220
As ons die boodskap in sy ongeënkripteerde, plain-text formaat,

68
00:03:48,220 --> 00:03:51,020
sien ons dat dit is 25 letters lank.

69
00:03:51,020 --> 00:03:55,020
Bacon het slegs 5 letters, sodat ons nodig het om dit 5 keer te herhaal

70
00:03:55,020 --> 00:03:57,200
om dit te laat ooreenstem met die lengte van die plain text.

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

72
00:03:59,880 --> 00:04:02,300
'N kort ter syde stel, indien die aantal letters in die plain text

73
00:04:02,300 --> 00:04:05,780
nie skoon verdeel deur die aantal letters in die sleutel,

74
00:04:05,780 --> 00:04:08,260
ons net die einde van die laaste herhaling van ons belangrikste vroeg,

75
00:04:08,260 --> 00:04:11,800
met behulp van slegs die letters wat ons nodig het om te maak alles grootgeword het.

76
00:04:11,800 --> 00:04:14,590
Nou gaan ons oor die vind van die verskuiwing waardes.

77
00:04:14,590 --> 00:04:19,100
>> Ons gaan om dit te doen deur gebruik te maak van die posisie van elke letter van ons sleutel - spek -

78
00:04:19,100 --> 00:04:21,560
in die A tot Z alfabet.

79
00:04:21,560 --> 00:04:26,060
Aangesien ons rekenaar wetenskaplikes, ons wil om te begin tel by nul in plaas van 1,

80
00:04:26,060 --> 00:04:30,230
so ons gaan om te sê dat die posisie van die eerste letter van die spek - B -

81
00:04:30,230 --> 00:04:33,840
is in posisie 1 in die nul-indexed A tot Z alfabet,

82
00:04:33,840 --> 00:04:38,300
nie 2, en die posisie van 'n nul is nie 1.

83
00:04:38,300 --> 00:04:42,450
Die gebruik van hierdie algoritme, kan ons die verskuiwing waardes vir elke letter.

84
00:04:42,450 --> 00:04:45,330
>> Die gewone teks te enkripteer en genereer cipher teks,

85
00:04:45,330 --> 00:04:49,070
ons net skuif elke letter in die plain text deur die gespesifiseerde bedrag

86
00:04:49,070 --> 00:04:54,140
net soos ons met die keiser cipher, wikkel van Z terug aan A indien nodig.

87
00:04:54,140 --> 00:04:57,880
M kry verskuif deur 1 plek om N.

88
00:04:57,880 --> 00:05:02,350
Die eerste e nie op alle skuif, maar ons skuif die tweede E 2 plekke tot G

89
00:05:02,350 --> 00:05:06,200
en T deur 14 plekke tot H.

90
00:05:06,200 --> 00:05:08,610
As ons werk deur die plain text, ons eindig met

91
00:05:08,610 --> 00:05:12,580
"Negh ZF av HUF pcfx bt gzrwep oz."

92
00:05:12,580 --> 00:05:16,620
Weereens, nie baie romanties klink, maar beslis kriptiese.

93
00:05:16,620 --> 00:05:19,750
As Alice en Bob het bekend oor Vigenère cipher,

94
00:05:19,750 --> 00:05:23,330
sou hulle gewees het veilig van Evelyn se gierige oë?

95
00:05:23,330 --> 00:05:24,870
Wat dink jy?

96
00:05:24,870 --> 00:05:27,450
Sou jy wil om aan te meld in jou bankrekening as jou bank besluit om te gebruik

97
00:05:27,450 --> 00:05:32,720
>> Vigenère cipher jou kommunikasie te enkripteer met jou wagwoord as jou sleutel?

98
00:05:32,720 --> 00:05:34,810
As ek jy was, sou ek nie.

99
00:05:34,810 --> 00:05:38,720
En terwyl Evelyn kan gehou word lank genoeg besig vir Alice en Bob om hul ontmoet-up,

100
00:05:38,720 --> 00:05:41,600
dit is nie die moeite werd vir Alice en Bob kans.

101
00:05:41,600 --> 00:05:45,780
Vigenère cipher is relatief maklik om te breek as jy die lengte van die sleutel

102
00:05:45,780 --> 00:05:48,490
want dan kan jy die geïnkripteer cipher teks behandel

103
00:05:48,490 --> 00:05:52,840
as die produk van 'n paar verweef Caesar getalle.

104
00:05:52,840 --> 00:05:55,950
>> Vind die lengte van die sleutel is nie vreeslik moeilik nie.

105
00:05:55,950 --> 00:06:00,520
As die oorspronklike plain-text boodskap is lank genoeg dat sommige woorde kom verskeie kere,

106
00:06:00,520 --> 00:06:04,420
uiteindelik sal jy sien herhaling opduik in die geïnkripteer cipher teks,

107
00:06:04,420 --> 00:06:10,010
soos in hierdie voorbeeld, waar jy sien MONCY twee keer verskyn.

108
00:06:10,010 --> 00:06:13,800
Verder kan jy 'n brute krag aanval op die cipher verrig.

109
00:06:13,800 --> 00:06:17,220
Dit beteken neem aansienlik langer as 'n brute krag aanval op die keiser cipher,

110
00:06:17,220 --> 00:06:20,670
wat byna onmiddellik kan gedoen word met 'n rekenaar

111
00:06:20,670 --> 00:06:27,130
want in plaas van 25 gevalle om seker te maak jy 26 ⁿ het - 1 moontlikhede,

112
00:06:27,130 --> 00:06:29,580
waar n die lengte van die onbekende sleutel.

113
00:06:29,580 --> 00:06:34,040
>> Dit is omdat elke letter in die sleutel kan wees enige van die 26 letters,

114
00:06:34,040 --> 00:06:38,280
A deur Z, en 'n slim persoon sal probeer om 'n sleutel te gebruik wat nie gevind word in 'n woordeboek,

115
00:06:38,280 --> 00:06:44,280
wat beteken dat jy wil hê al die vreemde letter kombinasies, soos ZXXXFF te toets,

116
00:06:44,280 --> 00:06:47,690
en nie net 'n paar honderd duisend woorde in die woordeboek.

117
00:06:47,690 --> 00:06:53,200
Die minus 1 kom in die wiskunde, omdat jy nie wil hê om 'n sleutel te gebruik met net 'n is,

118
00:06:53,200 --> 00:06:56,200
want met ons zero-indexed alfabet wat jou sal gee jou dieselfde effek

119
00:06:56,200 --> 00:06:59,620
as die gebruik van 'n keiser cipher met 'n sleutel van nul.

120
00:06:59,620 --> 00:07:04,120
In elk geval, 26 ⁿ - nie 1 kry groot redelik vinnig,

121
00:07:04,120 --> 00:07:08,080
maar terwyl jy sal beslis nie wil om te probeer om te breek van 'n cipher met die hand op hierdie manier,

122
00:07:08,080 --> 00:07:11,080
dit is beslis uitvoerbaar met 'n rekenaar.

123
00:07:11,080 --> 00:07:14,030
Gelukkig vir Alice en Bob, en vir aanlyn bankdienste,

124
00:07:14,030 --> 00:07:17,890
cryptografen het ontwikkel meer veilige maniere om geheime boodskappe te enkripteer

125
00:07:17,890 --> 00:07:19,690
van die gierige oë.

126
00:07:19,690 --> 00:07:22,400
>> Maar dit is 'n onderwerp vir 'n ander tyd.

127
00:07:22,400 --> 00:07:26,210
My naam is Nate Hardison. Dit is CS50.