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.