1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Віженер Cipher]

2
00:00:02,000 --> 00:00:04,000
[Nate Хардісон - Гарвардський університет]

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
не тільки батьки Аліси не схвалюють Боб,

9
00:00:20,580 --> 00:00:23,820
але кращий друг Аліси, Евелін, є таємниця закохана в Боб

10
00:00:23,820 --> 00:00:27,290
і егоїстично хоче зберегти їх один від одного за всяку ціну.

11
00:00:27,290 --> 00:00:31,280
Для передачі секретних повідомлень один одному, що батьки Аліси не можу зрозуміти,

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
Улюблений номер Аліси 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
Стає D, B стає E, C стає 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 з A, Y з B, і Z з C.

25
00:01:14,850 --> 00:01:18,550
Так що, коли Аліса відправляється в шифрувати свої таємні повідомлення Бобу,

26
00:01:18,550 --> 00:01:21,520
а саме: "Зустрінь мене в парк на 11 ранку»,

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

28
00:01:23,790 --> 00:01:30,900
M стає P, E стає 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
>> Аліса дає повідомлення для Евеліна доставити на будинок Боба.

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
Знаючи, що буква Е є найбільш поширеним в англійській мові,

38
00:02:01,960 --> 00:02:05,390
відбувається майже 13% часу,

39
00:02:05,390 --> 00:02:09,910
Евелін припускає, що H була замінена E для того, щоб зробити таємне повідомлення

40
00:02:09,910 --> 00:02:14,030
і намагається за допомогою ключа від 3 до розшифровки.

41
00:02:14,030 --> 00:02:19,700
>> Через кілька хвилин, Евелін з'ясовує плани Аліси і злобно називає батьки Аліси.

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
але не досить довго, щоб утримати її від зриву Аліси і Боба плани,

53
00:02:56,070 --> 00:02:58,660
особливо якщо Евелін має допомоги комп'ютера

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
Один з найвідоміших з них називається Віженер шифр.

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 ранку

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
так що ми збираємося сказати, що положення першої літери бекон - B -

81
00:04:30,230 --> 00:04:33,840
знаходиться в положенні 1 в нуль-індексований за алфавітом Z,

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
M отримує зрушать на 1 місце, щоб стати N.

88
00:04:57,880 --> 00:05:02,350
Перша E не зрушується на всіх, але ми зрушуємо другий E на 2 місця для G

89
00:05:02,350 --> 00:05:06,200
і T на 14 місць для H.

90
00:05:06,200 --> 00:05:08,610
Якщо ми будемо працювати через звичайний текст, ми в підсумку,

91
00:05:08,610 --> 00:05:12,580
"Negh ZF AV HUF pcfx BT gzrwep Оз".

92
00:05:12,580 --> 00:05:16,620
Знову ж таки, не дуже романтично звучить, але безумовно загадковим.

93
00:05:16,620 --> 00:05:19,750
Якщо Аліса і Боб знав про Віженер шифр,

94
00:05:19,750 --> 00:05:23,330
б вони були в безпеці від цікавих очей Евелін?

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
>> Шифр Віженер для шифрування зв'язку з використанням пароля в якості ключа?

98
00:05:32,720 --> 00:05:34,810
Якби я був тобою, я б не став.

99
00:05:34,810 --> 00:05:38,720
І в той час Евелін може бути зайнятий досить довго для Аліси і Боба, щоб їх зустріти в експлуатацію,

100
00:05:38,720 --> 00:05:41,600
воно того не варто для Аліси і Боба, щоб ризикувати.

101
00:05:41,600 --> 00:05:45,780
Шифр Віженер відносно легко розбити, якщо ви знаєте довжину ключа

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
де п довжини невідомого ключа.

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
це, безумовно, здійснимі за допомогою комп'ютера.

123
00:07:11,080 --> 00:07:14,030
На щастя для Аліси і Боба, а також для онлайн-банкінгу,

124
00:07:14,030 --> 00:07:17,890
криптографи розробили більш безпечні способи для шифрування секретних повідомлень

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
Мене звати Нейт Хардісон. Це CS50.