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
[To je CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Seznamte se Alice.

5
00:00:09,000 --> 00:00:11,260
Alice má zamilovanost na Boba.

6
00:00:11,260 --> 00:00:15,030
Naštěstí pro Alici, Bob má také oči pro ni.

7
00:00:15,030 --> 00:00:17,700
Bohužel pro jejich nadějnou romantika,

8
00:00:17,700 --> 00:00:20,580
nejenže Aliciny rodiče nesouhlasí Boba,

9
00:00:20,580 --> 00:00:23,820
Ale Alice je nejlepší přítel, Evelyn, má tajnou zamilovanost Bob

10
00:00:23,820 --> 00:00:27,290
a sobecky chce udržet je od sebe za každou cenu.

11
00:00:27,290 --> 00:00:31,280
Chcete-li odeslat tajné zprávy ke každému jiný že Aliciny rodiče nemohou pochopit,

12
00:00:31,280 --> 00:00:34,140
>> Alice a Bob byly pomocí Caesarova šifra,

13
00:00:34,140 --> 00:00:37,410
který pracuje tím, že přesouvá na abecedu určitého počtu písmen

14
00:00:37,410 --> 00:00:39,800
jako způsob, jak generovat novou abecedu.

15
00:00:39,800 --> 00:00:44,130
Každé písmeno v původní abecedy je pak nahrazena odpovídajícím písmenem

16
00:00:44,130 --> 00:00:46,920
v novém posunuté abecedy.

17
00:00:46,920 --> 00:00:50,240
Alicin oblíbené číslo je 3, které Bob ví,

18
00:00:50,240 --> 00:00:52,450
tak ona používá 3 jako její klíč.

19
00:00:52,450 --> 00:00:55,430
Když se posune anglickou abecedu o 3 písmena,

20
00:00:55,430 --> 00:01:00,680
Stává D, B se E, C se F,

21
00:01:00,680 --> 00:01:02,670
a tak dále.

22
00:01:02,670 --> 00:01:07,460
>> Když se dostane do konce abecedy - na písmena X, Y a Z -

23
00:01:07,460 --> 00:01:09,970
prostě se zalomí kolem zpět na začátek abecedy

24
00:01:09,970 --> 00:01:14,850
a náhražky X s A, Y s B, a Z s C.

25
00:01:14,850 --> 00:01:18,550
Takže když Alice jde k zašifrování její tajnou zprávu Bobovi,

26
00:01:18,550 --> 00:01:21,520
jmenovitě "Sejdeme se v parku v jedenáct hod.,"

27
00:01:21,520 --> 00:01:23,790
prostě dělá příslušné náhrady.

28
00:01:23,790 --> 00:01:30,900
M se stává P, E stává H, a tak dále, dokud ji nešifrované prostého textu zprávy

29
00:01:30,900 --> 00:01:34,350
je zapnutý do šifrovaných šifrovaného textu:

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

31
00:01:37,280 --> 00:01:39,370
rozhodně není nejromantičtější znějící,

32
00:01:39,370 --> 00:01:41,650
ale Alice se domnívají, že to bude dělat.

33
00:01:41,650 --> 00:01:45,140
>> Alice dává zprávu Evelyn dodat do domu Boba.

34
00:01:45,140 --> 00:01:50,030
Ale místo toho, Evelyn bere ji zpět do svého pokoje a snaží se rozluštit kód.

35
00:01:50,030 --> 00:01:55,470
Jeden z prvních věcí Evelyn oznámení, že písmeno H vyskytuje 7 krát ve zprávě,

36
00:01:55,470 --> 00:01:58,930
mnoho více časů než jakékoli jiné písmeno.

37
00:01:58,930 --> 00:02:01,960
S vědomím, že písmeno E je nejvíce obyčejný v anglickém jazyce,

38
00:02:01,960 --> 00:02:05,390
vyskytující téměř 13% času,

39
00:02:05,390 --> 00:02:09,910
Evelyn hádá, že H byl substituted pro E, aby tajnou zprávu

40
00:02:09,910 --> 00:02:14,030
a snaží pomocí klíče 3 k dešifrování.

41
00:02:14,030 --> 00:02:19,700
>> Během několika minut, Evelyn vyřeší plány Alice a zlověstně volá Alici rodiče.

42
00:02:19,700 --> 00:02:22,700
Kdyby Alice a Bob pořízena CS50, by poznali toto

43
00:02:22,700 --> 00:02:25,750
frekvenční analýza útok na Caesara,

44
00:02:25,750 --> 00:02:28,310
který umožňuje, aby se porušovala poměrně rychle.

45
00:02:28,310 --> 00:02:32,590
Měly by také vědět, že šifra je snadno podléhá brute-force útoku,

46
00:02:32,590 --> 00:02:35,940
kdy Evelyn se mohl pokusit všech možných 25 kláves,

47
00:02:35,940 --> 00:02:38,440
nebo posuny anglické abecedy,

48
00:02:38,440 --> 00:02:40,490
za účelem dešifrovat zprávy.

49
00:02:40,490 --> 00:02:43,710
Proč 25 kláves a ne 26?

50
00:02:43,710 --> 00:02:49,010
>> No, zkuste posunutí žádný dopis o 26 pozic, a uvidíte proč.

51
00:02:49,010 --> 00:02:52,280
Každopádně by brute-force útok vzali Evelyn trochu déle

52
00:02:52,280 --> 00:02:56,070
ale ne dost dlouho na to, aby jí z narušily Alice a Bob se plány,

53
00:02:56,070 --> 00:02:58,660
zejména v případě, Evelyn má pomocí počítače

54
00:02:58,660 --> 00:03:02,640
které by mohly prorazit všech 25 případech v okamžiku.

55
00:03:02,640 --> 00:03:06,170
Takže, tento problém také sužován ostatní, kteří používají na Caesara,

56
00:03:06,170 --> 00:03:10,300
a proto lidé začali experimentovat s více komplexními substitučních šifer

57
00:03:10,300 --> 00:03:14,190
že použití více směn hodnot namísto jedné.

58
00:03:14,190 --> 00:03:18,080
Jedním z nejvíce dobře-známé z nich se nazývá Vigenère kód.

59
00:03:18,080 --> 00:03:19,980
Jak jsme se dostali vícesměnném hodnot?

60
00:03:19,980 --> 00:03:24,630
No, místo toho, aby používal čísla jako klíč, používáme slovo pro klíč.

61
00:03:24,630 --> 00:03:27,940
Budeme používat každý dopis v klíči pro generování čísla,

62
00:03:27,940 --> 00:03:33,670
a efekt je, že budeme mít více Caesara stylu klíče pro řazení písmen.

63
00:03:33,670 --> 00:03:36,620
>> Pojďme se podívat, jak to funguje pomocí šifrování Alicin zprávu Bobovi:

64
00:03:36,620 --> 00:03:39,010
Sejdeme se v parku v jedenáct dopoledne

65
00:03:39,010 --> 00:03:42,610
Já osobně, myslím, že slanina je vynikající,

66
00:03:42,610 --> 00:03:44,480
takže se pojďme použít jako klíč.

67
00:03:44,480 --> 00:03:48,220
Vezmeme-li si zprávu v jeho nešifrované, formátu prostého textu,

68
00:03:48,220 --> 00:03:51,020
vidíme, že je to 25 znaků dlouhé.

69
00:03:51,020 --> 00:03:55,020
Bacon má jen 5 písmen, takže musíme opakovat to 5 krát

70
00:03:55,020 --> 00:03:57,200
aby to odpovídalo délce prostého textu.

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

72
00:03:59,880 --> 00:04:02,300
Jako krátký stranou, v případě, že počet písmen v prostém textu

73
00:04:02,300 --> 00:04:05,780
nerozdělila čistě podle počtu písmen v klíči,

74
00:04:05,780 --> 00:04:08,260
jsme prostě skončit konečné opakování našich hlavních brzy,

75
00:04:08,260 --> 00:04:11,800
použít pouze písmena, které jsme potřebovali, aby se vše sladit.

76
00:04:11,800 --> 00:04:14,590
Teď půjdeme o nalezení řazení hodnot.

77
00:04:14,590 --> 00:04:19,100
>> Budeme-li to provést pomocí pozici každého dopisu našeho klíče - slanina -

78
00:04:19,100 --> 00:04:21,560
v A do Z abecedy.

79
00:04:21,560 --> 00:04:26,060
Vzhledem k tomu, že jsme počítačoví odborníci, jsme chtěli začít počítat od nuly místo 1,

80
00:04:26,060 --> 00:04:30,230
takže budeme říkat, že pozice prvního dopisu slaniny - B -

81
00:04:30,230 --> 00:04:33,840
je v pozici 1 v nulové indexovaný na abeceda Z,

82
00:04:33,840 --> 00:04:38,300
ne 2, a postavení je nula, není 1.

83
00:04:38,300 --> 00:04:42,450
Pomocí tohoto algoritmu, můžeme najít posuvné hodnoty pro každé písmeno.

84
00:04:42,450 --> 00:04:45,330
>> Chcete-li zašifrovat prostý text a vytvářet šifrovaný text,

85
00:04:45,330 --> 00:04:49,070
jsme jen posun každý dopis v prostém textu podle zadaného množství,

86
00:04:49,070 --> 00:04:54,140
stejně jako my s šifrou Caesar, balení od Z zpět na potřeby.

87
00:04:54,140 --> 00:04:57,880
M dostane posunul o 1 místo, aby se stala N.

88
00:04:57,880 --> 00:05:02,350
První E neřadí vůbec, ale posuneme druhý E o 2 místa k G

89
00:05:02,350 --> 00:05:06,200
a T od 14 míst na H.

90
00:05:06,200 --> 00:05:08,610
Pokud budeme pracovat přes prostý text, skončíme s,

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

92
00:05:12,580 --> 00:05:16,620
Opět platí, že není moc romantický znějící, ale rozhodně záhadné.

93
00:05:16,620 --> 00:05:19,750
Pokud Alice a Bob věděl o Vigenère šifra,

94
00:05:19,750 --> 00:05:23,330
by byli v bezpečí před zvědavýma očima Evelyn?

95
00:05:23,330 --> 00:05:24,870
Co si myslíte?

96
00:05:24,870 --> 00:05:27,450
Chtěli byste se přihlásit do svého bankovního účtu, pokud vaše banka se rozhodla použít

97
00:05:27,450 --> 00:05:32,720
>> Vigenère kód pro zašifrování komunikace pomocí hesla jako klíče?

98
00:05:32,720 --> 00:05:34,810
Kdybych byl tebou, tak bych to.

99
00:05:34,810 --> 00:05:38,720
A zatímco Evelyn může být obsazeno dlouho dost pro Alici a Boba, aby jejich splnění-up,

100
00:05:38,720 --> 00:05:41,600
nestojí to za to pro Alice a Bob se šance, že.

101
00:05:41,600 --> 00:05:45,780
Vigenère kód je relativně snadné prolomit, pokud víte, délku klíče

102
00:05:45,780 --> 00:05:48,490
protože pak můžete léčit šifrované šifrovaný text

103
00:05:48,490 --> 00:05:52,840
jako součin několika propletených šifer Caesar.

104
00:05:52,840 --> 00:05:55,950
>> Nalezení délku klíče není příliš těžké, a to buď.

105
00:05:55,950 --> 00:06:00,520
Pokud původní plain-text zprávy je dostatečně dlouhá, že některá slova se vyskytují vícekrát,

106
00:06:00,520 --> 00:06:04,420
nakonec uvidíte opakování oříznutí v šifrované šifrovaný text,

107
00:06:04,420 --> 00:06:10,010
jako v tomto příkladu, kde je vidět MONCY objeví dvakrát.

108
00:06:10,010 --> 00:06:13,800
Navíc, můžete provést brute-force útoku na šifru.

109
00:06:13,800 --> 00:06:17,220
To však trvat podstatně déle, než brute-force útoku na šifru Caesar,

110
00:06:17,220 --> 00:06:20,670
které může být provedeno téměř okamžitě s počítačem

111
00:06:20,670 --> 00:06:27,130
protože místo 25 případů pro kontrolu máš 26 ⁿ - 1 možností,

112
00:06:27,130 --> 00:06:29,580
kde n je délka neznámého klíče.

113
00:06:29,580 --> 00:06:34,040
>> To je proto, že každé písmeno v klíči mohl být některý z 26 písmen,

114
00:06:34,040 --> 00:06:38,280
A až Z, a inteligentní osoba se pokusí použít klíč, který nelze nalézt ve slovníku,

115
00:06:38,280 --> 00:06:44,280
což znamená, že se bude muset testovat všechny podivných kombinace písmen, jako ZXXXFF,

116
00:06:44,280 --> 00:06:47,690
a ne jen pár 100.000 slov ve slovníku.

117
00:06:47,690 --> 00:06:53,200
Minus 1 přichází do matematiky, protože byste nechtěli použít klíč s pouze to,

118
00:06:53,200 --> 00:06:56,200
protože s naší nulovou indexované abecedy, která by vám stejný účinek

119
00:06:56,200 --> 00:06:59,620
as pomocí šifry Caesar s klíčem nula.

120
00:06:59,620 --> 00:07:04,120
Každopádně, 26 ⁿ - 1 se zvětší poměrně rychle,

121
00:07:04,120 --> 00:07:08,080
ale když určitě nebude chtít vyzkoušet lámání šifry ručně tímto způsobem,

122
00:07:08,080 --> 00:07:11,080
to je určitě proveditelné s počítačem.

123
00:07:11,080 --> 00:07:14,030
Naštěstí pro Alici a Boba, a pro on-line bankovnictví,

124
00:07:14,030 --> 00:07:17,890
cryptographers vyvinuli bezpečnější způsoby, jak pro šifrování tajných zpráv

125
00:07:17,890 --> 00:07:19,690
před zvědavýma očima.

126
00:07:19,690 --> 00:07:22,400
>> Nicméně, to je téma na jiný čas.

127
00:07:22,400 --> 00:07:26,210
Mé jméno je Nate Hardison. To je CS50.