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

3
00:00:04,000 --> 00:00:07,000
[Detta är CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Möt 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
Lyckligtvis för Alice har Bob också ögonen för henne.

7
00:00:15,030 --> 00:00:17,700
Tyvärr för deras spirande romans,

8
00:00:17,700 --> 00:00:20,580
inte bara ogillar Alice föräldrar av Bob,

9
00:00:20,580 --> 00:00:23,820
men Alice bästa vän, Evelyn, har en hemlig fruktdryck på Bob

10
00:00:23,820 --> 00:00:27,290
och själviskt vill hålla isär dem till varje pris.

11
00:00:27,290 --> 00:00:31,280
Om du vill skicka hemliga meddelanden till varandra att Alice föräldrar inte kan förstå,

12
00:00:31,280 --> 00:00:34,140
>> Alice och Bob har använt en Caesar chiffer,

13
00:00:34,140 --> 00:00:37,410
som fungerar genom att flytta alfabetet med ett visst antal bokstäver

14
00:00:37,410 --> 00:00:39,800
som ett sätt att generera en ny alfabet.

15
00:00:39,800 --> 00:00:44,130
Varje bokstav i det ursprungliga alfabetet sedan ersätts med motsvarande bokstav

16
00:00:44,130 --> 00:00:46,920
i den skiftade nya alfabetet.

17
00:00:46,920 --> 00:00:50,240
Alice favorit nummer är 3, som Bob vet,

18
00:00:50,240 --> 00:00:52,450
så hon använder 3 som sin nyckel.

19
00:00:52,450 --> 00:00:55,430
När hon flyttar det engelska alfabetet med 3 bokstäver,

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

21
00:01:00,680 --> 00:01:02,670
och så vidare.

22
00:01:02,670 --> 00:01:07,460
>> När hon får till slutet av alfabetet - till bokstäverna X, Y och Z -

23
00:01:07,460 --> 00:01:09,970
Hon sveper runt tillbaka till början av alfabetet

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

25
00:01:14,850 --> 00:01:18,550
Så när Alice går att kryptera sin hemliga budskap till Bob,

26
00:01:18,550 --> 00:01:21,520
nämligen "Möt mig i parken vid 11:00,"

27
00:01:21,520 --> 00:01:23,790
Hon gör bara lämpliga substitutioner.

28
00:01:23,790 --> 00:01:30,900
M blir P blir E H, och så vidare tills hon okrypterade oformaterad text

29
00:01:30,900 --> 00:01:34,350
omvandlas till krypterad chiffertext:

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

31
00:01:37,280 --> 00:01:39,370
är definitivt inte den mest romantiska klingande,

32
00:01:39,370 --> 00:01:41,650
men Alice tror att det kommer att göra.

33
00:01:41,650 --> 00:01:45,140
>> Alice ger meddelandet till Evelyn leverera till Bob hus.

34
00:01:45,140 --> 00:01:50,030
Men Evelyn tar istället tillbaka till sitt rum och försöker knäcka koden.

35
00:01:50,030 --> 00:01:55,470
En av de första saker Evelyn meddelanden är att bokstaven H förekommer 7 gånger i meddelandet,

36
00:01:55,470 --> 00:01:58,930
många fler gånger än någon annan bokstav.

37
00:01:58,930 --> 00:02:01,960
Att veta att bokstaven E är den vanligaste på engelska,

38
00:02:01,960 --> 00:02:05,390
förekommer nästan 13% av tiden,

39
00:02:05,390 --> 00:02:09,910
Evelyn gissar att H har ersatts för E för att göra den hemliga meddelandet

40
00:02:09,910 --> 00:02:14,030
och försöker med hjälp av en nyckel 3 att dekryptera det.

41
00:02:14,030 --> 00:02:19,700
>> Inom några minuter, siffror Evelyn ut Alice planer och elakt kallar Alice föräldrar.

42
00:02:19,700 --> 00:02:22,700
Hade Alice och Bob tagit CS50, skulle de ha känt till detta

43
00:02:22,700 --> 00:02:25,750
frekvens-analys attack mot Caesar chiffer,

44
00:02:25,750 --> 00:02:28,310
vilket gör att den kan brytas ganska snabbt.

45
00:02:28,310 --> 00:02:32,590
De skulle också ha vetat att chiffret är lätt föremål för en brute-force attack,

46
00:02:32,590 --> 00:02:35,940
där Evelyn kunde har försökt alla möjliga 25 tangenter,

47
00:02:35,940 --> 00:02:38,440
eller förskjutningar av det engelska alfabetet,

48
00:02:38,440 --> 00:02:40,490
För att dechiffrera meddelandet.

49
00:02:40,490 --> 00:02:43,710
Varför 25 tangenter och inte 26?

50
00:02:43,710 --> 00:02:49,010
>> Tja, försök flytta en bokstav med 26 positioner, och du kommer att se varför.

51
00:02:49,010 --> 00:02:52,280
Hur som helst skulle en brute-force attack tagit Evelyn lite längre

52
00:02:52,280 --> 00:02:56,070
men inte tillräckligt länge för att hålla henne från att motarbeta Alice och Bob planer,

53
00:02:56,070 --> 00:02:58,660
speciellt om Evelyn har hjälp av en dator

54
00:02:58,660 --> 00:03:02,640
vilket kan rippa genom alla 25 fall i ett ögonblick.

55
00:03:02,640 --> 00:03:06,170
Så detta problem plågas också andra som använde Caesar chiffer,

56
00:03:06,170 --> 00:03:10,300
och därför människor började experimentera med mer komplexa substitution chiffer

57
00:03:10,300 --> 00:03:14,190
som använder flera skift värden i stället för bara en.

58
00:03:14,190 --> 00:03:18,080
En av de mest välkända av dessa kallas Vigenère chiffer.

59
00:03:18,080 --> 00:03:19,980
Hur får vi flera skift värderingar?

60
00:03:19,980 --> 00:03:24,630
Tja, i stället för att använda ett antal som nyckeln använder vi ett ord för nyckeln.

61
00:03:24,630 --> 00:03:27,940
Vi kommer att använda varje bokstav i nyckeln för att generera ett antal,

62
00:03:27,940 --> 00:03:33,670
och effekten är att vi kommer att ha flera Caesar chiffer-stil nycklar för att flytta bokstäver.

63
00:03:33,670 --> 00:03:36,620
>> Låt oss se hur det fungerar genom att kryptera Alice budskap till Bob:

64
00:03:36,620 --> 00:03:39,010
Möt mig i parken vid 11:00

65
00:03:39,010 --> 00:03:42,610
Jag personligen tycker bacon är läcker,

66
00:03:42,610 --> 00:03:44,480
så låt oss använda det som nyckeln.

67
00:03:44,480 --> 00:03:48,220
Om vi ​​tar budskapet i dess okrypterat, vanlig textformat,

68
00:03:48,220 --> 00:03:51,020
ser vi att det är 25 bokstäver långa.

69
00:03:51,020 --> 00:03:55,020
Bacon har bara 5 bokstäver, så vi måste upprepa det 5 gånger

70
00:03:55,020 --> 00:03:57,200
att göra det matchar längden av klartext.

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 undan, om antalet bokstäver i klartext

73
00:04:02,300 --> 00:04:05,780
inte dela rent av antalet bokstäver i nyckeln,

74
00:04:05,780 --> 00:04:08,260
Vi avslutar bara den sista upprepning av vår nyckel tidigt,

75
00:04:08,260 --> 00:04:11,800
endast med de bokstäver som vi behövde för att göra allting stämmer.

76
00:04:11,800 --> 00:04:14,590
Nu går vi om att hitta de skiftvärden.

77
00:04:14,590 --> 00:04:19,100
>> Vi ska göra detta genom att använda läget för varje bokstav i vår nyckel - bacon -

78
00:04:19,100 --> 00:04:21,560
i A till Z alfabetet.

79
00:04:21,560 --> 00:04:26,060
Eftersom vi är datavetare, vill vi börja räkna på noll i stället för 1,

80
00:04:26,060 --> 00:04:30,230
så vi kommer att säga att läget för den första bokstaven i bacon - B -

81
00:04:30,230 --> 00:04:33,840
är i position 1 i den noll-indexerade A till Z alfabetet,

82
00:04:33,840 --> 00:04:38,300
inte 2, och placeringen av A är noll, inte 1.

83
00:04:38,300 --> 00:04:42,450
Med hjälp av denna algoritm kan vi hitta skift värden för varje bokstav.

84
00:04:42,450 --> 00:04:45,330
>> Att kryptera klartext och generera chiffertext,

85
00:04:45,330 --> 00:04:49,070
Vi skiftar bara varje bokstav i klartext med angivet belopp,

86
00:04:49,070 --> 00:04:54,140
precis som vi gör med Caesar chiffer, omslag från Z till A om det behövs.

87
00:04:54,140 --> 00:04:57,880
M blir skiftas med 1 plats för att bli N.

88
00:04:57,880 --> 00:05:02,350
Den första E skiftar inte alls, men vi skiftar den andra E med 2 platser till G

89
00:05:02,350 --> 00:05:06,200
och T med 14 platser till H.

90
00:05:06,200 --> 00:05:08,610
Om vi ​​arbetar igenom klartext, hamnar vi med,

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
Igen, inte mycket romantisk klingande men definitivt kryptiskt.

93
00:05:16,620 --> 00:05:19,750
Om Alice och Bob hade vetat om Vigenère chiffer,

94
00:05:19,750 --> 00:05:23,330
skulle de ha varit säker från Evelyns nyfikna ögon?

95
00:05:23,330 --> 00:05:24,870
Vad tycker du?

96
00:05:24,870 --> 00:05:27,450
Skulle du vill logga in på ditt bankkonto om din bank beslutat att använda

97
00:05:27,450 --> 00:05:32,720
>> Vigenère chiffer för att kryptera din kommunikation med lösenord som din nyckel?

98
00:05:32,720 --> 00:05:34,810
Om jag var du, skulle jag inte.

99
00:05:34,810 --> 00:05:38,720
Och medan Evelyn skulle hållas upptagen länge nog för Alice och Bob att få sina möta upp,

100
00:05:38,720 --> 00:05:41,600
det är inte värt det för Alice och Bob att chans det.

101
00:05:41,600 --> 00:05:45,780
Vigenère chiffer är relativt lätt att bryta om du vet längden på nyckeln

102
00:05:45,780 --> 00:05:48,490
för då kan du behandla den krypterade chiffertext

103
00:05:48,490 --> 00:05:52,840
som en produkt av ett fåtal sammanvävda Caesar chiffer.

104
00:05:52,840 --> 00:05:55,950
>> Hitta längden på nyckeln är inte särskilt svårt heller.

105
00:05:55,950 --> 00:06:00,520
Om den ursprungliga klartext meddelandet är långt nog att vissa ord förekommer flera gånger,

106
00:06:00,520 --> 00:06:04,420
så småningom kommer du se upprepning dyka upp i den krypterade chiffertext,

107
00:06:04,420 --> 00:06:10,010
som i detta exempel, där du ser visas MONCY två gånger.

108
00:06:10,010 --> 00:06:13,800
Dessutom kan du utföra en brute-force attack mot chiffer.

109
00:06:13,800 --> 00:06:17,220
Detta tar betydligt längre tid än en brute-force attack mot Caesar chiffer,

110
00:06:17,220 --> 00:06:20,670
vilket kan göras nästan omedelbart med en dator

111
00:06:20,670 --> 00:06:27,130
eftersom istället för 25 fall kontrollera att du har 26 ⁿ - 1 möjligheter,

112
00:06:27,130 --> 00:06:29,580
där n är längden av den okända nyckeln.

113
00:06:29,580 --> 00:06:34,040
>> Detta beror på att varje bokstav i nyckeln kan vara vilken som helst av de 26 bokstäverna,

114
00:06:34,040 --> 00:06:38,280
A till Z, och en smart person skulle försöka använda en nyckel som inte kan hittas i ett lexikon,

115
00:06:38,280 --> 00:06:44,280
vilket innebär att du måste testa alla de konstiga bokstavskombinationer, som ZXXXFF,

116
00:06:44,280 --> 00:06:47,690
och inte bara ett par hundra tusen ord i ordlistan.

117
00:06:47,690 --> 00:06:53,200
Minus 1 kommer in i matten eftersom du inte vill använda en nyckel med endast A är,

118
00:06:53,200 --> 00:06:56,200
eftersom med vår noll-indexerad alfabet som skulle ge dig samma effekt

119
00:06:56,200 --> 00:06:59,620
som använder en Caesar chiffer med en nyckel noll.

120
00:06:59,620 --> 00:07:04,120
Hur som helst, 26 ⁿ - blir 1 stor ganska snabbt,

121
00:07:04,120 --> 00:07:08,080
men medan du definitivt inte vill försöka bryta ett chiffer för hand på detta sätt,

122
00:07:08,080 --> 00:07:11,080
detta är definitivt genomförbart med en dator.

123
00:07:11,080 --> 00:07:14,030
Lyckligtvis för Alice och Bob, och för internetbanker,

124
00:07:14,030 --> 00:07:17,890
kryptografer har utvecklat säkrare sätt att kryptera hemliga meddelanden

125
00:07:17,890 --> 00:07:19,690
från nyfikna ögon.

126
00:07:19,690 --> 00:07:22,400
>> Men det är ett ämne för en annan tid.

127
00:07:22,400 --> 00:07:26,210
Mitt namn är Nate Hardison. Detta är CS50.