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 University]

3
00:00:04,000 --> 00:00:07,000
[Dette er CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Svarende til Alice.

5
00:00:09,000 --> 00:00:11,260
Alice har en crush på Bob.

6
00:00:11,260 --> 00:00:15,030
Heldigvis for Alice, Bob har også øje for hende.

7
00:00:15,030 --> 00:00:17,700
Desværre for deres spirende romance,

8
00:00:17,700 --> 00:00:20,580
ikke kun Alices forældre misbilliger Bob,

9
00:00:20,580 --> 00:00:23,820
men Alice bedste ven, Evelyn, har en hemmelig crush på Bob

10
00:00:23,820 --> 00:00:27,290
og egoistisk ønsker at holde dem fra hinanden på alle omkostninger.

11
00:00:27,290 --> 00:00:31,280
For at sende hemmelige beskeder til hinanden, at Alices forældre ikke kan forstå,

12
00:00:31,280 --> 00:00:34,140
>> Alice og Bob har brugt en Caesar cipher,

13
00:00:34,140 --> 00:00:37,410
der virker ved forskydning alfabetet af et vist antal bogstaver

14
00:00:37,410 --> 00:00:39,800
som en måde at generere et nyt alfabet.

15
00:00:39,800 --> 00:00:44,130
Hvert bogstav i det oprindelige alfabet derefter erstattet af dens tilsvarende brev

16
00:00:44,130 --> 00:00:46,920
i det nye forskudt alfabet.

17
00:00:46,920 --> 00:00:50,240
Alices favorit nummer er 3, som Bob ved,

18
00:00:50,240 --> 00:00:52,450
så hun bruger 3 som hendes nøgle.

19
00:00:52,450 --> 00:00:55,430
Da hun flytter det engelske alfabet med 3 bogstaver,

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

21
00:01:00,680 --> 00:01:02,670
og så videre.

22
00:01:02,670 --> 00:01:07,460
>> Når hun kommer til slutningen af ​​alfabetet - til bogstaverne X, Y og Z -

23
00:01:07,460 --> 00:01:09,970
hun bare vikles rundt tilbage til begyndelsen af ​​alfabetet

24
00:01:09,970 --> 00:01:14,850
og erstatninger X med A, Y med B, og Z med C.

25
00:01:14,850 --> 00:01:18,550
Så da Alice går til at kryptere sin hemmelige besked til Bob,

26
00:01:18,550 --> 00:01:21,520
nemlig "Mød mig i parken ved 11:00,"

27
00:01:21,520 --> 00:01:23,790
hun bare gør de nødvendige udskiftninger.

28
00:01:23,790 --> 00:01:30,900
M bliver P, E bliver H, og så videre indtil hendes ukrypteret meddelelse i almindelig tekst

29
00:01:30,900 --> 00:01:34,350
omdannes til krypteret cipher tekst:

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

31
00:01:37,280 --> 00:01:39,370
er bestemt ikke den mest romantiske klingende,

32
00:01:39,370 --> 00:01:41,650
men Alice tror, ​​at det vil gøre.

33
00:01:41,650 --> 00:01:45,140
>> Alice giver besked til Evelyn til at levere til Bobs hus.

34
00:01:45,140 --> 00:01:50,030
Men Evelyn i stedet tager det tilbage til hendes værelse og forsøger at knække koden.

35
00:01:50,030 --> 00:01:55,470
En af de første ting, Evelyn bekendtgørelser er, at bogstavet H optræder 7 gange i meddelelsen,

36
00:01:55,470 --> 00:01:58,930
mange flere gange end nogen anden bogstav.

37
00:01:58,930 --> 00:02:01,960
Vel vidende, at bogstavet E er den mest almindelige i det engelske sprog,

38
00:02:01,960 --> 00:02:05,390
forekommer næsten 13% af tiden,

39
00:02:05,390 --> 00:02:09,910
Evelyn gætter på, at H er erstattet af E for at gøre den hemmelige meddelelse

40
00:02:09,910 --> 00:02:14,030
og forsøger ved hjælp af en nøgle på 3 for at dekryptere den.

41
00:02:14,030 --> 00:02:19,700
>> Inden for få minutter, tal Evelyn ud Alice planer og ondt kalder Alices forældre.

42
00:02:19,700 --> 00:02:22,700
Havde Alice og Bob taget CS50, ville de have vidst det

43
00:02:22,700 --> 00:02:25,750
frekvens-analyse angreb på Caesar cipher,

44
00:02:25,750 --> 00:02:28,310
som tillader den at blive brudt ganske hurtigt.

45
00:02:28,310 --> 00:02:32,590
De ville også have vidst, at cipher er nemt underlagt en brute-force angreb,

46
00:02:32,590 --> 00:02:35,940
hvorved Evelyn kunne have prøvet alle de mulige 25 taster,

47
00:02:35,940 --> 00:02:38,440
eller forskydninger af det engelske alfabet,

48
00:02:38,440 --> 00:02:40,490
for at dekryptere meddelelsen.

49
00:02:40,490 --> 00:02:43,710
Hvorfor 25 taster, og ikke 26?

50
00:02:43,710 --> 00:02:49,010
>> Tja, prøv at flytte helst bogstav med 26 positioner, og du vil se hvorfor.

51
00:02:49,010 --> 00:02:52,280
Anyway, ville en brute-force angreb har taget Evelyn lidt længere

52
00:02:52,280 --> 00:02:56,070
men ikke længe nok til at holde hende fra at modarbejde Alice og Bob planer,

53
00:02:56,070 --> 00:02:58,660
især hvis Evelyn har hjælp af en computer

54
00:02:58,660 --> 00:03:02,640
som kunne rip gennem alle 25 sager på et øjeblik.

55
00:03:02,640 --> 00:03:06,170
Så dette problem også plaget andre, der brugte den Caesar cipher,

56
00:03:06,170 --> 00:03:10,300
og derfor folk begyndte at eksperimentere med mere komplekse substitution ciphers

57
00:03:10,300 --> 00:03:14,190
at brugen af ​​flere skift værdier i stedet for kun én.

58
00:03:14,190 --> 00:03:18,080
Et af de mest kendte af disse kaldes Vigenère cipher.

59
00:03:18,080 --> 00:03:19,980
Hvordan får vi flere skift værdier?

60
00:03:19,980 --> 00:03:24,630
Nå, i stedet for at bruge et nummer som nøgle, bruger vi et ord for nøglen.

61
00:03:24,630 --> 00:03:27,940
Vi vil bruge hvert bogstav i nøglen til at generere et nummer,

62
00:03:27,940 --> 00:03:33,670
og effekten er, at vi vil have flere Caesar cipher-tasterne til at flytte breve.

63
00:03:33,670 --> 00:03:36,620
>> Lad os se, hvordan det fungerer ved at kryptere Alices besked til Bob:

64
00:03:36,620 --> 00:03:39,010
Mød mig på park ved 11:00

65
00:03:39,010 --> 00:03:42,610
Jeg, personligt, mener bacon er lækre,

66
00:03:42,610 --> 00:03:44,480
så lad os bruge det som nøgle.

67
00:03:44,480 --> 00:03:48,220
Hvis vi tager budskabet i sin ukrypteret, almindelig tekst format,

68
00:03:48,220 --> 00:03:51,020
vi se, at det er 25 bogstaver.

69
00:03:51,020 --> 00:03:55,020
Bacon har kun 5 bogstaver, så vi er nødt til at gentage det 5 gange

70
00:03:55,020 --> 00:03:57,200
at gøre det svarer til længden af ​​klartekst.

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

72
00:03:59,880 --> 00:04:02,300
Som en kort side, hvis antallet af breve i klartekst

73
00:04:02,300 --> 00:04:05,780
ikke dividere rent med antallet af bogstaver i nøglen,

74
00:04:05,780 --> 00:04:08,260
vi bare ende den endelige gentagelse af vores nøgle tidligt,

75
00:04:08,260 --> 00:04:11,800
bruger kun de breve, vi havde brug for at få det hele passer sammen.

76
00:04:11,800 --> 00:04:14,590
Nu går vi om at finde de skiftværdier.

77
00:04:14,590 --> 00:04:19,100
>> Vi vil gøre dette ved hjælp af placeringen af ​​hvert bogstav i vores nøgle - bacon -

78
00:04:19,100 --> 00:04:21,560
i A til Z alfabet.

79
00:04:21,560 --> 00:04:26,060
Da vi er dataloger, vi gerne begynde at tælle ved nul i stedet for 1,

80
00:04:26,060 --> 00:04:30,230
så vil vi sige, at placeringen af ​​det første bogstav i bacon - B -

81
00:04:30,230 --> 00:04:33,840
er i position 1 i nul-indekseret A til Z alfabet,

82
00:04:33,840 --> 00:04:38,300
ikke 2, og positionen af ​​A er nul, ikke 1.

83
00:04:38,300 --> 00:04:42,450
Under anvendelse af denne algoritme, kan vi finde skift værdier for hvert bogstav.

84
00:04:42,450 --> 00:04:45,330
>> Til at kryptere almindelig tekst og generere cipher tekst,

85
00:04:45,330 --> 00:04:49,070
vi bare flytte hvert bogstav i klartekst med den angivne mængde,

86
00:04:49,070 --> 00:04:54,140
ligesom vi gør med Cæsar cipher, indpakning fra Z tilbage til A, hvis det er nødvendigt.

87
00:04:54,140 --> 00:04:57,880
M bliver forskydes med 1 sted at blive N.

88
00:04:57,880 --> 00:05:02,350
Den første E ikke skifter på alle, men vi flytter den anden E med 2 pladser til G

89
00:05:02,350 --> 00:05:06,200
og T med 14 pladser til H.

90
00:05:06,200 --> 00:05:08,610
Hvis vi arbejder gennem almindelig tekst, vi ender med,

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

92
00:05:12,580 --> 00:05:16,620
Igen, ikke meget romantisk klingende men absolut kryptisk.

93
00:05:16,620 --> 00:05:19,750
Hvis Alice og Bob havde kendt til Vigenère cipher,

94
00:05:19,750 --> 00:05:23,330
ville de have været sikkert fra Evelyns nysgerrige øjne?

95
00:05:23,330 --> 00:05:24,870
Hvad mener du?

96
00:05:24,870 --> 00:05:27,450
Vil du ønsker at logge ind på din bankkonto, hvis din bank besluttede at bruge

97
00:05:27,450 --> 00:05:32,720
>> Vigenère cipher at kryptere din kommunikation ved hjælp af din adgangskode som din nøgle?

98
00:05:32,720 --> 00:05:34,810
Hvis jeg var dig, ville jeg ikke.

99
00:05:34,810 --> 00:05:38,720
Og mens Evelyn kunne holdes travlt længe nok til Alice og Bob at få deres møde op,

100
00:05:38,720 --> 00:05:41,600
det er ikke det værd for Alice og Bob at chance det.

101
00:05:41,600 --> 00:05:45,780
Vigenère cipher er forholdsvis let at bryde, hvis du kender længden af ​​nøglen

102
00:05:45,780 --> 00:05:48,490
fordi så kan du behandle den krypterede cipher tekst

103
00:05:48,490 --> 00:05:52,840
som produktet af et par sammenflettede Cæsar ciphers.

104
00:05:52,840 --> 00:05:55,950
>> Finde længden af ​​nøglen er ikke frygtelig hårdt, enten.

105
00:05:55,950 --> 00:06:00,520
Hvis den oprindelige klartekst-meddelelsen er lang nok til, at nogle ord forekommer flere gange,

106
00:06:00,520 --> 00:06:04,420
sidste ende vil du se gentagelse dukker op i den krypterede cifferliste tekst,

107
00:06:04,420 --> 00:06:10,010
som i dette eksempel, MONCY hvor du kan se optræder to gange.

108
00:06:10,010 --> 00:06:13,800
Derudover kan du udføre en brute-force angreb på cipher.

109
00:06:13,800 --> 00:06:17,220
Det tager betydeligt længere tid end en brute-force angreb på Caesar cipher,

110
00:06:17,220 --> 00:06:20,670
hvilket kan gøres næsten øjeblikkeligt med en computer

111
00:06:20,670 --> 00:06:27,130
siden i stedet for 25 tilfælde at kontrollere du har fået 26 ⁿ - 1 muligheder,

112
00:06:27,130 --> 00:06:29,580
hvor n er længden af ​​ukendt nøgle.

113
00:06:29,580 --> 00:06:34,040
>> Dette skyldes, at hvert bogstav i nøglen kunne være enhver af de 26 bogstaver,

114
00:06:34,040 --> 00:06:38,280
A til Z, og et smart person ville forsøge at anvende en nøgle, der ikke kan findes i en ordbog,

115
00:06:38,280 --> 00:06:44,280
hvilket betyder, at du er nødt til at teste alle de underlige bogstavkombinationer, ligesom ZXXXFF,

116
00:06:44,280 --> 00:06:47,690
og ikke bare et par hundrede tusind ord i ordbogen.

117
00:06:47,690 --> 00:06:53,200
Den minus 1 kommer ind i matematik, fordi du ikke ønsker at bruge en nøgle med kun A'er,

118
00:06:53,200 --> 00:06:56,200
siden med vores nul-indekseret alfabet, som vil give dig den samme effekt

119
00:06:56,200 --> 00:06:59,620
som bruger en Caesar cipher med en nøgle på nul.

120
00:06:59,620 --> 00:07:04,120
Anyway, 26 ⁿ - ikke 1 få stor ret hurtigt,

121
00:07:04,120 --> 00:07:08,080
men mens du absolut ikke ønsker at prøve at bryde en cipher med hånden på denne måde,

122
00:07:08,080 --> 00:07:11,080
dette er absolut doable med en computer.

123
00:07:11,080 --> 00:07:14,030
Heldigvis for Alice og Bob, og for online banking,

124
00:07:14,030 --> 00:07:17,890
kryptografer har udviklet mere sikre måder at kryptere hemmelige beskeder

125
00:07:17,890 --> 00:07:19,690
mod nysgerrige blikke.

126
00:07:19,690 --> 00:07:22,400
>> Men det er et emne til en anden gang.

127
00:07:22,400 --> 00:07:26,210
Mit navn er Nate Hardison. Det er CS50.