1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Vigenère шифра]

2
00:00:02,000 --> 00:00:04,000
[Нејт Hardison - Универзитетот Харвард]

3
00:00:04,000 --> 00:00:07,000
[Ова е CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Среќавајте Алис.

5
00:00:09,000 --> 00:00:11,260
Алис е способна за Боб.

6
00:00:11,260 --> 00:00:15,030
За среќа за Алис, Боб, исто така, има очи за неа.

7
00:00:15,030 --> 00:00:17,700
За жал за младиот и надежен романса,

8
00:00:17,700 --> 00:00:20,580
не само што родителите на Alice одобруваат Боб,

9
00:00:20,580 --> 00:00:23,820
но најдобар пријател на Alice, Евелин, има тајна способна за Боб

10
00:00:23,820 --> 00:00:27,290
и себично сака да ги задржи, освен на сите трошоци.

11
00:00:27,290 --> 00:00:31,280
Да испрати тајни пораки едни на други дека родителите на Alice не можат да разберат,

12
00:00:31,280 --> 00:00:34,140
>> Алис и Боб се со користење на Цезар шифра,

13
00:00:34,140 --> 00:00:37,410
која работи со менувањето на азбуката од одреден број на букви

14
00:00:37,410 --> 00:00:39,800
како начин да се генерираат нови азбука.

15
00:00:39,800 --> 00:00:44,130
Секоја буква во оригиналната азбука потоа се заменети со соодветните писмо

16
00:00:44,130 --> 00:00:46,920
во новата префрли писмо.

17
00:00:46,920 --> 00:00:50,240
Омилен број на Alice е 3, која Боб знае,

18
00:00:50,240 --> 00:00:52,450
па таа користи 3 како нејзиниот клуч.

19
00:00:52,450 --> 00:00:55,430
Кога таа ја префрла Македонски писмо од 3 букви,

20
00:00:55,430 --> 00:01:00,680
А станува Д, Б станува Е, Ц станува F,

21
00:01:00,680 --> 00:01:02,670
и така натаму.

22
00:01:02,670 --> 00:01:07,460
>> Кога таа добива на крајот на азбуката - на писма X, Y и Z -

23
00:01:07,460 --> 00:01:09,970
таа само обвива околу назад кон почетокот на азбуката

24
00:01:09,970 --> 00:01:14,850
и замени X со А, Ц со Б, и Z со C.

25
00:01:14,850 --> 00:01:18,550
Значи, кога Алис оди за да го криптирате нејзината тајна порака до Боб,

26
00:01:18,550 --> 00:01:21,520
имено "се запознае со мене во паркот во 11:00"

27
00:01:21,520 --> 00:01:23,790
таа само ја прави соодветни замени.

28
00:01:23,790 --> 00:01:30,900
М станува П, Е станува H и така натаму се до нејзината енкриптирани обичен текст порака

29
00:01:30,900 --> 00:01:34,350
е претворен во шифрирана шифра текст:

30
00:01:34,350 --> 00:01:37,280
"Phhw тел DW wkh sdun DW hohyhq ДП"

31
00:01:37,280 --> 00:01:39,370
дефинитивно не е најстариот романтични труба,

32
00:01:39,370 --> 00:01:41,650
но Алис веруваат дека тоа ќе го стори.

33
00:01:41,650 --> 00:01:45,140
>> Alice дава порака до Евелин да се достави до куќата на Боб.

34
00:01:45,140 --> 00:01:50,030
Но, Евелин наместо тоа враќа назад во нејзината соба и се обидува да се бори на код.

35
00:01:50,030 --> 00:01:55,470
Една од првите работи Евелин известувања е дека писмото H јавува 7 пати во пораката,

36
00:01:55,470 --> 00:01:58,930
многу повеќе пати отколку било која друга буква.

37
00:01:58,930 --> 00:02:01,960
Знаејќи дека буквата E е најчестиот на англиски јазик,

38
00:02:01,960 --> 00:02:05,390
случуваат речиси 13% од времето,

39
00:02:05,390 --> 00:02:09,910
Евелин нагаѓања дека H е замена за Е, со цел да се направи тајна порака

40
00:02:09,910 --> 00:02:14,030
и се обидува со помош на клучот на 3 да ја дешифрирате.

41
00:02:14,030 --> 00:02:19,700
>> Рок од неколку минути, Евелин фигури планови на Alice и подмолно повикува родителите на Alice.

42
00:02:19,700 --> 00:02:22,700
Ја Алис и Боб земени CS50, тие ќе се знае на овој

43
00:02:22,700 --> 00:02:25,750
фреквенција анализа напад на Цезар шифра,

44
00:02:25,750 --> 00:02:28,310
што овозможува таа да биде скршен доста брзо.

45
00:02:28,310 --> 00:02:32,590
Тие, исто така, ќе се знае дека шифра е лесно предмет на брутална сила напад,

46
00:02:32,590 --> 00:02:35,940
при што Евелин можел да се обиде на сите можни 25 копчиња,

47
00:02:35,940 --> 00:02:38,440
или промени на англиска латиница,

48
00:02:38,440 --> 00:02:40,490
со цел да се дешифрира пораката.

49
00:02:40,490 --> 00:02:43,710
Зошто 25 клучеви и да не 26?

50
00:02:43,710 --> 00:02:49,010
>> Па, обидете се менува било која буква со 26 места, и ќе видите зошто.

51
00:02:49,010 --> 00:02:52,280
Како и да е, една брутална сила напад би ги презеле Евелин малку подолго

52
00:02:52,280 --> 00:02:56,070
но не доволно долго за да ја заштити од thwarting Алис и планови Боб,

53
00:02:56,070 --> 00:02:58,660
особено ако Evelyn нема помош на компјутер

54
00:02:58,660 --> 00:03:02,640
кои би можеле да дупат сите 25 случаи во еден момент.

55
00:03:02,640 --> 00:03:06,170
Значи, овој проблем исто така, се соочува други кои се користат на Цезар шифра,

56
00:03:06,170 --> 00:03:10,300
и затоа луѓето почна да експериментира со посложени замена шифри

57
00:03:10,300 --> 00:03:14,190
кои користат повеќе смена вредности наместо на само еден.

58
00:03:14,190 --> 00:03:18,080
Еден од најпознатите од нив е наречен Vigenère број.

59
00:03:18,080 --> 00:03:19,980
Како да ја добиете повеќе смена вредности?

60
00:03:19,980 --> 00:03:24,630
Па, наместо користење на голем број како клуч, ние ги користиме збор за клучот.

61
00:03:24,630 --> 00:03:27,940
Ќе искористиме секоја буква во клучните да се генерираат голем број,

62
00:03:27,940 --> 00:03:33,670
и ефектот е дека ќе имаме повеќе Цезар шифра стил клучеви за менувањето букви.

63
00:03:33,670 --> 00:03:36,620
>> Ајде да видиме како тоа функционира со шифрирање порака Алис да Боб:

64
00:03:36,620 --> 00:03:39,010
Среќавајте мене во паркот во 11:00

65
00:03:39,010 --> 00:03:42,610
Јас, лично, мислам сланина е вкусно,

66
00:03:42,610 --> 00:03:44,480
па ајде го користат како клуч.

67
00:03:44,480 --> 00:03:48,220
Ако го земеме порака во енкриптирани, обичен текст формат,

68
00:03:48,220 --> 00:03:51,020
ќе видиме дека таа е 25 букви.

69
00:03:51,020 --> 00:03:55,020
Сланина има само 5 букви, па ние треба да го повтори 5 пати

70
00:03:55,020 --> 00:03:57,200
да се направи тоа одговара на должината на обичен текст.

71
00:03:57,200 --> 00:03:59,880
>> Сланина сланина сланина сланина сланина.

72
00:03:59,880 --> 00:04:02,300
Како краток настрана, ако бројот на букви во обичен текст

73
00:04:02,300 --> 00:04:05,780
не делат чисто од бројот на букви во клучот,

74
00:04:05,780 --> 00:04:08,260
ние едноставно се стави крај на финалето повторување на нашиот клучен рано,

75
00:04:08,260 --> 00:04:11,800
со користење само на писма ни е потребно да се направи сè натпревар.

76
00:04:11,800 --> 00:04:14,590
Сега ние одиме за наоѓање на промена вредности.

77
00:04:14,590 --> 00:04:19,100
>> Ние ќе го правиме ова преку користење на позицијата на секоја буква од нашите клучни - сланина -

78
00:04:19,100 --> 00:04:21,560
во А до Ш писмо.

79
00:04:21,560 --> 00:04:26,060
Бидејќи ние сме компјутерски научници, ние сакале да започне броење на нула, наместо на 1,

80
00:04:26,060 --> 00:04:30,230
па ние ќе да се каже дека позицијата на првата буква од сланина - Б -

81
00:04:30,230 --> 00:04:33,840
е во положбата 1 во нулта-индексиран А до Ш писмо,

82
00:04:33,840 --> 00:04:38,300
не 2, и позицијата на е нула, а не 1.

83
00:04:38,300 --> 00:04:42,450
Користењето на овој алгоритам, ние може да се најдат на смена вредности за секоја буква.

84
00:04:42,450 --> 00:04:45,330
>> За да го криптирате обичен текст и генерира шифра текст,

85
00:04:45,330 --> 00:04:49,070
ние едноставно се префрлат секоја буква во обичен текст од одреден износ,

86
00:04:49,070 --> 00:04:54,140
исто како што направи со шифра Цезар, на обвивката од Z назад кон доколку е потребно.

87
00:04:54,140 --> 00:04:57,880
М добива префрлени од 1 место да стане Н

88
00:04:57,880 --> 00:05:02,350
Првиот Е не префрлува на сите, но ние се префрлат на втората Е за 2 места со G

89
00:05:02,350 --> 00:05:06,200
и Т од 14 места за Х

90
00:05:06,200 --> 00:05:08,610
Ако работиме преку обичен текст, на крајот ќе заврши со,

91
00:05:08,610 --> 00:05:12,580
"Negh ZF AV HUF pcfx БТ gzrwep мл."

92
00:05:12,580 --> 00:05:16,620
Повторно, не многу романтично-труба, но дефинитивно криптичната.

93
00:05:16,620 --> 00:05:19,750
Ако Алис и Боб знаеле за Vigenère шифра,

94
00:05:19,750 --> 00:05:23,330
тие би биле безбедни од prying очи на Evelyn?

95
00:05:23,330 --> 00:05:24,870
Што мислите?

96
00:05:24,870 --> 00:05:27,450
Дали сакате да се најавите во вашата банкарска сметка, ако вашата банка одлучи да го искористи

97
00:05:27,450 --> 00:05:32,720
>> Vigenère шифра за да го криптирате вашата комуникација користејќи ја вашата лозинка како клуч?

98
00:05:32,720 --> 00:05:34,810
Ако јас тебе, јас не би.

99
00:05:34,810 --> 00:05:38,720
И додека Евелин може да се чуваат зафатен доволно долго за Алис и Боб да имаат исполнуваат-up,

100
00:05:38,720 --> 00:05:41,600
тоа не е достоен за тоа за Алис и Боб да шанси.

101
00:05:41,600 --> 00:05:45,780
Vigenère шифра е релативно лесно да се скрши ако знаете должината на клучот

102
00:05:45,780 --> 00:05:48,490
затоа што тогаш можете да се третираат на енкриптирани шифра текст

103
00:05:48,490 --> 00:05:52,840
како производ на неколку испреплетени Цезар шифри.

104
00:05:52,840 --> 00:05:55,950
>> Наоѓање на должината на клучот не е страшно тешко, или.

105
00:05:55,950 --> 00:06:00,520
Ако оригиналниот обичен текст порака е доволно долго дека некои зборови се појавуваат повеќе пати,

106
00:06:00,520 --> 00:06:04,420
на крајот ќе видите повторување појавуваа во шифрирана шифра текст,

107
00:06:04,420 --> 00:06:10,010
како во овој пример, каде што ќе видите MONCY се појави двапати.

108
00:06:10,010 --> 00:06:13,800
Покрај тоа, можете да го извршите брутална сила напад на број.

109
00:06:13,800 --> 00:06:17,220
Ова не се значително подолго од една брутална сила напад врз шифра Цезар,

110
00:06:17,220 --> 00:06:20,670
која може да се направи речиси моментално со компјутер

111
00:06:20,670 --> 00:06:27,130
бидејќи наместо на 25 случаи за да се провери имаш 26 ⁿ - 1 можности,

112
00:06:27,130 --> 00:06:29,580
каде n е должината на непознат клуч.

113
00:06:29,580 --> 00:06:34,040
>> Тоа е затоа што секоја буква во клучните може да биде било кој од 26 букви,

114
00:06:34,040 --> 00:06:38,280
А преку Z, и паметен човек ќе се обиде да користи клуч, кој не може да се најде во речникот,

115
00:06:38,280 --> 00:06:44,280
што значи дека ќе треба да се тестираат сите чудни писмо комбинации, како ZXXXFF,

116
00:06:44,280 --> 00:06:47,690
а не само неколку стотици илјади зборови во речникот.

117
00:06:47,690 --> 00:06:53,200
На минус 1 доаѓа во математика затоа што не би сакал да го користите клучниот со само е,

118
00:06:53,200 --> 00:06:56,200
бидејќи со нашата нулта-индексиран писмо што ќе ви даде истиот ефект

119
00:06:56,200 --> 00:06:59,620
како со помош на шифра Цезар со клучот на нула.

120
00:06:59,620 --> 00:07:04,120
Како и да е, 26 ⁿ - 1 не се големи, а брзо,

121
00:07:04,120 --> 00:07:08,080
но додека вие дефинитивно не би сакал да се обиде кршење на шифра од страна на овој начин,

122
00:07:08,080 --> 00:07:11,080
ова е дефинитивно doable со компјутер.

123
00:07:11,080 --> 00:07:14,030
За среќа за Алис и Боб, како и за интернет банкарство,

124
00:07:14,030 --> 00:07:17,890
cryptographers имаат развиено посигурни начини за да го криптирате тајни пораки

125
00:07:17,890 --> 00:07:19,690
од љубопитните очи.

126
00:07:19,690 --> 00:07:22,400
>> Сепак, тоа е тема за некоја друга прилика.

127
00:07:22,400 --> 00:07:26,210
Моето име е Нејт Hardison. Ова е CS50.