1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [RSA]

2
00:00:02,000 --> 00:00:04,000
[Rob Боуден] [Tommy MacWilliam] [Harvard University]

3
00:00:04,000 --> 00:00:07,000
[Это CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Давайте взглянем на RSA, широко используемый алгоритм шифрования данных.

5
00:00:11,000 --> 00:00:16,000
Алгоритмы шифрования, как Цезаря и Виженера шифры не очень безопасно.

6
00:00:16,000 --> 00:00:20,000
С шифр Цезаря, злоумышленнику нужно только попробовать 25 различных ключей

7
00:00:20,000 --> 00:00:22,000
чтобы получить текст сообщения.

8
00:00:22,000 --> 00:00:25,000
В то время как шифр Виженера является более безопасной, чем шифр Цезаря

9
00:00:25,000 --> 00:00:28,000
из-за большего пространства поиска для ключей, если злоумышленник

10
00:00:28,000 --> 00:00:30,000
знает, что длина ключа в шифра Виженера,

11
00:00:30,000 --> 00:00:34,000
что может быть определено с помощью анализа закономерностей в зашифрованный текст,

12
00:00:34,000 --> 00:00:38,000
Шифр Виженера не намного более безопасным, чем шифр Цезаря.

13
00:00:38,000 --> 00:00:42,000
RSA, с другой стороны, не уязвимы для атак подобного.

14
00:00:42,000 --> 00:00:45,000
Шифр Цезаря и Виженера Шифр ​​использовать тот же ключ

15
00:00:45,000 --> 00:00:47,000
для шифрования и расшифровки сообщений.

16
00:00:47,000 --> 00:00:51,000
Это свойство делает эти шифры алгоритмы симметричного ключа.

17
00:00:51,000 --> 00:00:54,000
Основная проблема с симметричным ключом Алгоритмы

18
00:00:54,000 --> 00:00:57,000
является то, что они полагаются на одной шифрование и отправка сообщений

19
00:00:57,000 --> 00:00:59,000
и тот, получения и расшифровки сообщения

20
00:00:59,000 --> 00:01:03,000
к уже договорились заранее на ключ, то они будут использовать.

21
00:01:03,000 --> 00:01:06,000
Но у нас есть немного проблем с запуском здесь.

22
00:01:06,000 --> 00:01:10,000
Как 2 компьютера, которые хотят общаться создании секретного ключа между ними?

23
00:01:10,000 --> 00:01:16,000
Если ключ должен быть тайным, то нам нужен способ для шифрования и дешифрования ключа.

24
00:01:16,000 --> 00:01:18,000
Если все мы имеем, является симметричным ключом

25
00:01:18,000 --> 00:01:21,000
Затем мы только возвращаемся к той же проблеме.

26
00:01:21,000 --> 00:01:25,000
RSA, с другой стороны, использует пару ключей,

27
00:01:25,000 --> 00:01:28,000
один для шифрования, а другой для расшифровки.

28
00:01:28,000 --> 00:01:32,000
Одна из них называется открытым ключом, а другой закрытым ключом.

29
00:01:32,000 --> 00:01:34,000
Открытый ключ используется для шифрования сообщений.

30
00:01:34,000 --> 00:01:38,000
Как можно догадаться по его названию, мы можем поделиться нашим открытым ключом с

31
00:01:38,000 --> 00:01:43,000
кого мы хотим без ущерба для безопасности зашифрованное сообщение.

32
00:01:43,000 --> 00:01:45,000
Сообщения шифруются с помощью открытого ключа

33
00:01:45,000 --> 00:01:49,000
могут быть расшифрованы только с помощью соответствующего закрытого ключа.

34
00:01:49,000 --> 00:01:53,000
В то время как вы можете поделиться своим открытым ключом, вы всегда должны иметь личные секретный ключ.

61
00:01:55,000 --> 00:01:58,000
и только закрытый ключ может быть использован для расшифровки сообщений

62
00:01:58,000 --> 00:02:02,000
если 2 пользователи хотят, чтобы отправить сообщения, зашифрованные RSA

63
00:02:02,000 --> 00:02:07,000
вперед и назад, как пользователи должны иметь свои собственные государственные и частные пары ключей.

64
00:02:07,000 --> 00:02:10,000
Сообщения от пользователей с 1 по пользователь 2

65
00:02:10,000 --> 00:02:15,000
использовать только пара ключей пользователя 2, и сообщений от пользователей 2 к пользователю 1

66
00:02:15,000 --> 00:02:17,000
использовать только пара ключей пользователя 1.

67
00:02:17,000 --> 00:02:21,000
Дело в том, что есть 2 отдельные ключи для шифрования и расшифровки сообщений

68
00:02:21,000 --> 00:02:24,000
RSA делает асимметричных ключей алгоритма.

69
00:02:24,000 --> 00:02:28,000
Нам не нужно, чтобы зашифровать открытым ключом для того, чтобы отправить его на другой компьютер

70
00:02:28,000 --> 00:02:31,000
С ключевым является общественным любом случае.

71
00:02:31,000 --> 00:02:33,000
Это означает, что RSA не имеют тот же проблема запуска

72
00:02:33,000 --> 00:02:36,000
как симметричный ключ алгоритма.

73
00:02:36,000 --> 00:02:39,000
Так что, если я хочу отправить сообщение с помощью шифрования RSA

74
00:02:39,000 --> 00:02:42,000
Робу, я в первую очередь необходимо открытого ключа Роба.

75
00:02:42,000 --> 00:02:47,000
Для генерации пары ключей, Роб необходимо выбрать 2 больших простых чисел.

76
00:02:47,000 --> 00:02:50,000
Эти цифры будут использоваться как в открытых и закрытых ключей,

77
00:02:50,000 --> 00:02:54,000
но открытый ключ будет использовать только продукт этих 2 номера,

78
00:02:54,000 --> 00:02:56,000
Не сами числа.

79
00:02:56,000 --> 00:02:59,000
Как только я зашифровал сообщение, используя открытый ключ Роба

80
00:02:59,000 --> 00:03:01,000
Я могу отправить сообщение Роб.

81
00:03:01,000 --> 00:03:05,000
Для компьютера, факторинг чисел является трудной задачей.

82
00:03:05,000 --> 00:03:09,000
Открытый ключ, помните, использовали продукт из 2 простых чисел.

83
00:03:09,000 --> 00:03:12,000
Этот продукт должен то есть только 2 фактора,

84
00:03:12,000 --> 00:03:16,000
которые, случается, цифры, которые составляют закрытый ключ.

85
00:03:16,000 --> 00:03:20,000
Для того, чтобы расшифровать сообщение, RSA будет использовать этот секретный ключ

86
00:03:20,000 --> 00:03:25,000
или числа перемножаются в процессе создания открытого ключа.

87
00:03:25,000 --> 00:03:28,000
Потому что это вычислительно трудно разложить число

88
00:03:28,000 --> 00:03:32,000
использовать в открытых ключей в 2 чисел, используемых в закрытый ключ

89
00:03:32,000 --> 00:03:36,000
это трудно для злоумышленника, чтобы выяснить закрытого ключа

90
00:03:36,000 --> 00:03:39,000
, которые будут необходимы для расшифровки сообщения.

91
00:03:39,000 --> 00:03:43,000
Теперь давайте войдем в некоторых низком уровне детали RSA.

92
00:03:43,000 --> 00:03:46,000
Давайте сначала посмотрим, как мы можем генерировать пары ключей.

93
00:03:46,000 --> 00:03:49,000
Во-первых, нам нужно 2 простых числа.

94
00:03:49,000 --> 00:03:52,000
Мы называем эти 2 числа р и ц.

95
00:03:52,000 --> 00:03:56,000
Для того, чтобы подобрать р и д, на практике мы будем генерировать псевдослучайно

96
00:03:56,000 --> 00:03:59,000
больших количествах, а затем использовать тест для определения является ли

97
00:03:59,000 --> 00:04:02,000
эти цифры, вероятно, простое.

98
00:04:02,000 --> 00:04:05,000
Мы можем держать генерации случайных чисел снова и снова

99
00:04:05,000 --> 00:04:08,000
до тех пор пока у нас есть 2 простых чисел, мы можем использовать.

100
00:04:08,000 --> 00:04:15,000
Вот давайте выберем р = 23 и Q = 43.

101
00:04:15,000 --> 00:04:19,000
Помните, что на практике, р и д должна быть гораздо большем количестве.

102
00:04:19,000 --> 00:04:22,000
Насколько мы знаем, чем больше число, тем труднее

103
00:04:22,000 --> 00:04:25,000
для взлома зашифрованных сообщений.

104
00:04:25,000 --> 00:04:29,000
Но это также более дорогим для шифрования и расшифровки сообщений.

105
00:04:29,000 --> 00:04:33,000
Сегодня это часто рекомендуется, чтобы р и д по крайней мере 1024 бит,

106
00:04:33,000 --> 00:04:37,000
который ставит каждый номер в более чем 300 десятичных цифр.

107
00:04:37,000 --> 00:04:40,000
Но мы выберем этих небольших количествах для этого примера.

108
00:04:40,000 --> 00:04:43,000
Теперь мы умножим р и д вместе, чтобы получить 3-й номер,

109
00:04:43,000 --> 00:04:45,000
который мы будем называть п.

110
00:04:45,000 --> 00:04:55,000
В нашем случае N = 23 * 43, = 989.

111
00:04:55,000 --> 00:04:58,000
Мы N = 989.

112
00:04:58,000 --> 00:05:02,000
Далее мы умножим р - 1 с д - 1

113
00:05:02,000 --> 00:05:05,000
чтобы получить 4-й номер, который мы будем называть м.

114
00:05:05,000 --> 00:05:15,000
В нашем случае М = 22 * ​​42, = 924.

115
00:05:15,000 --> 00:05:18,000
Мы имеем т = 924.

116
00:05:18,000 --> 00:05:22,000
Теперь нам нужно число е, что является относительно простым с м

117
00:05:22,000 --> 00:05:25,000
и менее метров.

118
00:05:25,000 --> 00:05:28,000
Два числа, взаимно простые или взаимно

119
00:05:28,000 --> 00:05:33,000
если только положительное целое число, которое делит их обоих равномерно 1.

120
00:05:33,000 --> 00:05:37,000
Иными словами, наибольший общий делитель е и т

121
00:05:37,000 --> 00:05:39,000
должна быть 1.

122
00:05:39,000 --> 00:05:44,000
На практике, это общие для электронного быть простым числом 65537

123
00:05:44,000 --> 00:05:48,000
тех пор, пока это число не оказаться фактором м.

124
00:05:48,000 --> 00:05:53,000
Для наших ключей, мы выберем е = 5

125
00:05:53,000 --> 00:05:57,000
С 5 взаимно простое с 924.

126
00:05:57,000 --> 00:06:01,000
Наконец, мы должны будем еще один номер, который мы будем называть г.

127
00:06:01,000 --> 00:06:11,000
D должно быть некоторое значение, которое удовлетворяет уравнению де = 1 (той т).

128
00:06:11,000 --> 00:06:17,000
Это м мод означает мы будем использовать то, что называется модулярной арифметики.

129
00:06:17,000 --> 00:06:21,000
В модульной арифметики, когда рядом оказывается выше некоторого верхняя граница

130
00:06:21,000 --> 00:06:24,000
она будет обернуть обратно к 0.

131
00:06:24,000 --> 00:06:27,000
Часы, например, использует модульную арифметику.

132
00:06:27,000 --> 00:06:31,000
Через минуту после 1:59, например, 2:00,

133
00:06:31,000 --> 00:06:33,000
Не 1:60.

134
00:06:33,000 --> 00:06:36,000
Минутная стрелка была обернута вокруг до 0

135
00:06:36,000 --> 00:06:39,000
при достижении верхней границы 60.

136
00:06:39,000 --> 00:06:46,000
Таким образом, мы можем сказать, 60 это эквивалентно 0 (мода 60)

137
00:06:46,000 --> 00:06:57,000
и 125 эквивалентно 65 эквивалентно 5 (мода 60).

138
00:06:57,000 --> 00:07:02,000
Наш открытый ключ будет электронной пары и п

139
00:07:02,000 --> 00:07:09,000
где в данном случае е-5 и п 989.

140
00:07:09,000 --> 00:07:15,000
Наш частный ключ будет пара г и н,

141
00:07:15,000 --> 00:07:22,000
которая в нашем случае составляет 185 и 989.

142
00:07:22,000 --> 00:07:25,000
Обратите внимание, что наши оригинальные простых р и д не появляются

143
00:07:25,000 --> 00:07:29,000
в любом месте нашей частной или государственной ключи.

144
00:07:29,000 --> 00:07:33,000
Теперь, когда у нас есть пара ключей, давайте посмотрим, как мы можем зашифровать

145
00:07:33,000 --> 00:07:36,000
и расшифровать сообщение.

146
00:07:36,000 --> 00:07:38,000
Я хочу послать сообщение Роб,

147
00:07:38,000 --> 00:07:42,000
так что он будет один для создания этого ключа.

148
00:07:42,000 --> 00:07:46,000
Тогда я спрошу Rob за его открытый ключ, который я буду использовать

149
00:07:46,000 --> 00:07:48,000
Для шифрования сообщения, чтобы отправить его.

150
00:07:48,000 --> 00:07:53,000
Помните, что это совершенно нормально для Роба поделиться своим открытым ключом со мной.

151
00:07:53,000 --> 00:07:56,000
Но это не было бы хорошо, чтобы поделиться своим закрытым ключом.

152
00:07:56,000 --> 00:08:00,000
Я не имею никакого представления, что его закрытый ключ.

153
00:08:00,000 --> 00:08:03,000
Мы можем разбить наши сообщения м на несколько кусков

154
00:08:03,000 --> 00:08:07,000
Все меньше п, а затем зашифровать каждый из этих кусков.

155
00:08:07,000 --> 00:08:12,000
Мы будем шифровать строку CS50, которые мы можем разбить на 4 кусков,

156
00:08:12,000 --> 00:08:14,000
по одному в письме.

157
00:08:14,000 --> 00:08:17,000
Для того, чтобы зашифровать свое послание, мне нужно, чтобы преобразовать его в

158
00:08:17,000 --> 00:08:20,000
своего рода числового представления.

159
00:08:20,000 --> 00:08:25,000
Давайте объединить ASCII значения с символами в моем сообщении.

160
00:08:25,000 --> 00:08:28,000
Для того, чтобы зашифровать данное сообщение м.

161
00:08:28,000 --> 00:08:37,000
Мне нужно вычислить с = м к е (той п).

162
00:08:37,000 --> 00:08:40,000
Но м должно быть меньше, чем п,

163
00:08:40,000 --> 00:08:45,000
или же полное сообщение не может быть выражено по модулю п.

164
00:08:45,000 --> 00:08:49,000
Мы можем разбить м на несколько кусков, каждый из которых меньше, чем п,

165
00:08:49,000 --> 00:08:52,000
и шифровать каждый из этих кусков.

166
00:08:52,000 --> 00:09:03,000
Шифрование каждый из этих кусков, мы получаем c1 = 67 до 5 (мод 989)

167
00:09:03,000 --> 00:09:06,000
который = 658.

168
00:09:06,000 --> 00:09:15,000
Для нашего второго блока мы имеем 83 до 5 (мод 989)

169
00:09:15,000 --> 00:09:18,000
который = 15.

170
00:09:18,000 --> 00:09:26,000
Для нашего третьего блока у нас есть 53 до 5 (мод 989)

171
00:09:26,000 --> 00:09:30,000
который = 799.

172
00:09:30,000 --> 00:09:39,000
И, наконец, для нашего последний кусок у нас есть 48 до 5 (мод 989)

173
00:09:39,000 --> 00:09:43,000
который = 975.

174
00:09:43,000 --> 00:09:48,000
Теперь мы можем написать за эти зашифрованные значения Роб.

175
00:09:54,000 --> 00:09:58,000
Здесь вы идете, Роб.

176
00:09:58,000 --> 00:10:01,000
В то время как наши сообщения в полете, давайте еще раз посмотрим

177
00:10:01,000 --> 00:10:07,000
на то, как мы получили, что значение D.

178
00:10:07,000 --> 00:10:17,000
Наш номер D, необходимый для удовлетворения 5D = 1 (той 924).

179
00:10:17,000 --> 00:10:24,000
Это делает г мультипликативного обратного из 5 по модулю 924.

180
00:10:24,000 --> 00:10:28,000
Учитывая, 2 целых чисел, а, б, расширенный алгоритм Евклида

181
00:10:28,000 --> 00:10:33,000
может быть использован, чтобы найти наибольший общий делитель этих 2 целых чисел.

182
00:10:33,000 --> 00:10:37,000
Это также даст нам 2 других номера, х и у,

183
00:10:37,000 --> 00:10:47,000
, что удовлетворяет уравнению ах + Ьу = наибольший общий делитель а и Ь.

184
00:10:47,000 --> 00:10:49,000
Как это нам поможет?

185
00:10:49,000 --> 00:10:52,000
Ну, подключив е = 5 для

186
00:10:52,000 --> 00:10:56,000
и т = 924 для б

187
00:10:56,000 --> 00:10:59,000
Мы уже знаем, что эти числа взаимно просты.

188
00:10:59,000 --> 00:11:03,000
Их наибольший общий делитель равен 1.

189
00:11:03,000 --> 00:11:09,000
Это дает нам 5x + 924y = 1

190
00:11:09,000 --> 00:11:17,000
или 5x = 1 - 924y.

191
00:11:17,000 --> 00:11:22,000
Но если мы заботимся только о все по модулю 924

192
00:11:22,000 --> 00:11:25,000
Затем можно опустить - 924y.

193
00:11:25,000 --> 00:11:27,000
Вспомните часы.

194
00:11:27,000 --> 00:11:31,000
Если минутная стрелка на 1, а затем ровно в 10 часов пройдет,

195
00:11:31,000 --> 00:11:35,000
мы знаем, что минутная стрелка все равно будет на 1.

196
00:11:35,000 --> 00:11:39,000
Здесь начинаются с 1, а затем обернуть вокруг именно у раза,

197
00:11:39,000 --> 00:11:41,000
таким образом, мы все еще будем в 1.

198
00:11:41,000 --> 00:11:49,000
У нас есть 5x = 1 (той 924).

199
00:11:49,000 --> 00:11:55,000
И вот эта х так же, как г мы искали прежде,

200
00:11:55,000 --> 00:11:58,000
Таким образом, если мы используем расширенный алгоритм Евклида

201
00:11:58,000 --> 00:12:04,000
чтобы получить это число х, это число мы должны использовать как наша г.

202
00:12:04,000 --> 00:12:07,000
Теперь давайте запустим расширенный алгоритм Евклида для = 5

203
00:12:07,000 --> 00:12:11,000
и B = 924.

204
00:12:11,000 --> 00:12:14,000
Мы будем использовать метод, называемый таблицей метод.

205
00:12:14,000 --> 00:12:21,000
Наша таблица будет иметь 4 колонки, х, у, г, а к.

206
00:12:21,000 --> 00:12:23,000
Наш стол начинается с 2 ряда.

207
00:12:23,000 --> 00:12:28,000
В первом ряду у нас есть 1, 0, то наше значение, которое является 5,

208
00:12:28,000 --> 00:12:37,000
и наша вторая строка 0, 1, и наше значение б, который является 924.

209
00:12:37,000 --> 00:12:40,000
Стоимость 4-го столбца, к, будет результат

210
00:12:40,000 --> 00:12:45,000
деления значения D в строке выше его значение D

211
00:12:45,000 --> 00:12:49,000
на той же строке.

212
00:12:49,000 --> 00:12:56,000
У нас есть 5 деленное на 924 = 0 с некоторым остатком.

213
00:12:56,000 --> 00:12:59,000
Это означает, что мы имеем к = 0.

214
00:12:59,000 --> 00:13:05,000
Теперь стоимость каждой другой клетке будет значение ячейки 2 ряда выше

215
00:13:05,000 --> 00:13:09,000
минус значение строки над ним к раз.

216
00:13:09,000 --> 00:13:11,000
Давайте начнем с D в 3-м ряду.

217
00:13:11,000 --> 00:13:19,000
У нас есть 5 - 924 * 0 = 5.

218
00:13:19,000 --> 00:13:25,000
Далее мы имеем 0 - 1 * 0, равная 0

219
00:13:25,000 --> 00:13:30,000
и 1 - 0 * 0, что составляет 1.

220
00:13:30,000 --> 00:13:33,000
Не слишком плохо, так что давайте перейдем к следующей строке.

221
00:13:33,000 --> 00:13:36,000
Во-первых, нам нужно наше значение к.

222
00:13:36,000 --> 00:13:43,000
924 делим на 5 = 184 с некоторым остатком,

223
00:13:43,000 --> 00:13:46,000
таким образом, наши значения для К 184.

224
00:13:46,000 --> 00:13:54,000
Сейчас 924 - 5 * 184 = 4.

225
00:13:54,000 --> 00:14:05,000
1 - 0 * 184 1 и 0 - 1 * 184 -184.

226
00:14:05,000 --> 00:14:07,000
Ладно, давайте сделаем следующую строку.

227
00:14:07,000 --> 00:14:10,000
Наши значение к будет 1, так как

228
00:14:10,000 --> 00:14:15,000
5 делится на 4 = 1 с некоторым остатком.

229
00:14:15,000 --> 00:14:17,000
Давайте заполним в других колонках.

230
00:14:17,000 --> 00:14:21,000
5 - 4 * 1 = 1.

231
00:14:21,000 --> 00:14:25,000
0 - 1 * 1 = -1.

232
00:14:25,000 --> 00:14:33,000
И 1 - 184 * 1 185.

233
00:14:33,000 --> 00:14:35,000
Давайте посмотрим, что наша следующая величина к будет.

234
00:14:35,000 --> 00:14:40,000
Что ж, похоже, у нас есть 4 разделен на 1, что на 4.

235
00:14:40,000 --> 00:14:43,000
В этом случае, когда мы делением на 1 такой, что к равно

236
00:14:43,000 --> 00:14:50,000
Значение D в приведенной выше строке означает, что мы сделали с нашим алгоритмом.

237
00:14:50,000 --> 00:14:58,000
Мы видим здесь, что мы имеем х = 185, у = -1 в последнем ряду.

238
00:14:58,000 --> 00:15:00,000
Давайте теперь вернемся к нашей первоначальной цели.

239
00:15:00,000 --> 00:15:04,000
Мы сказали, что значение х в результате выполнения этого алгоритма

240
00:15:04,000 --> 00:15:08,000
будет мультипликативным обратным (той б).

241
00:15:08,000 --> 00:15:15,000
Это означает, что 185 является мультипликативным обратным 5 (мод 924)

242
00:15:15,000 --> 00:15:20,000
Это означает, что у нас есть значение 185 для г.

243
00:15:20,000 --> 00:15:23,000
Тот факт, что D = 1 в последней строке

244
00:15:23,000 --> 00:15:26,000
проверяет, что е было взаимно просто с м.

245
00:15:26,000 --> 00:15:30,000
Если бы это было не 1, то мы должны были бы выбрать новый электронный.

246
00:15:30,000 --> 00:15:33,000
Теперь давайте посмотрим, если Роб получил мое сообщение.

247
00:15:33,000 --> 00:15:35,000
Когда кто-то посылает мне зашифрованное сообщение

248
00:15:35,000 --> 00:15:38,000
тех пор, как я держал мой закрытый ключ тайну

249
00:15:38,000 --> 00:15:41,000
Я единственный, кто может расшифровать сообщение.

250
00:15:41,000 --> 00:15:46,000
Для расшифровки блока с I можно вычислить исходное сообщение

251
00:15:46,000 --> 00:15:53,000
равно кусок в г Мощность (той п).

252
00:15:53,000 --> 00:15:57,000
Помните, что г и п от моего закрытого ключа.

253
00:15:57,000 --> 00:16:01,000
Чтобы получить полное сообщение из кусков мы расшифровать каждый кусок

254
00:16:01,000 --> 00:16:04,000
и объединить результаты.

255
00:16:04,000 --> 00:16:08,000
Точно, как обеспечивается безопасность RSA?

256
00:16:08,000 --> 00:16:10,000
Правда, мы не знаем.

257
00:16:10,000 --> 00:16:14,000
Безопасность на основе, как долго это займет злоумышленнику взломать сообщение

258
00:16:14,000 --> 00:16:16,000
зашифрованные с RSA.

259
00:16:16,000 --> 00:16:19,000
Помните, что злоумышленник имеет доступ к вашим открытым ключом,

260
00:16:19,000 --> 00:16:21,000
который содержит е и п.

261
00:16:21,000 --> 00:16:26,000
Если злоумышленнику удается разложить п на своих 2 простых числа, р и д,

262
00:16:26,000 --> 00:16:30,000
тогда она могла бы рассчитывать D с помощью расширенного алгоритма Евклида.

263
00:16:30,000 --> 00:16:35,000
Это дает ей секретный ключ, который может быть использован для расшифровки сообщения.

264
00:16:35,000 --> 00:16:38,000
Но как быстро мы можем разложить целые числа?

265
00:16:38,000 --> 00:16:41,000
Опять же, мы не знаем.

266
00:16:41,000 --> 00:16:43,000
Никто не нашел быстрый способ сделать это,

267
00:16:43,000 --> 00:16:46,000
Это означает, что данный достаточно больших п

268
00:16:46,000 --> 00:16:49,000
потребуется злоумышленнику нереально долго

269
00:16:49,000 --> 00:16:51,000
на множители числа.

270
00:16:51,000 --> 00:16:54,000
Если кто-то показал быстрый способ факторизации целых чисел

271
00:16:54,000 --> 00:16:57,000
RSA будет нарушена.

272
00:16:57,000 --> 00:17:01,000
Но даже если целочисленной факторизации по сути своей медленной

273
00:17:01,000 --> 00:17:04,000
RSA алгоритм может еще есть какой-то изъян в нем

274
00:17:04,000 --> 00:17:07,000
, что позволяет легко расшифровки сообщений.

275
00:17:07,000 --> 00:17:10,000
Никто не нашел и показал такой изъян не менее,

276
00:17:10,000 --> 00:17:12,000
но это не означает, что не существует.

277
00:17:12,000 --> 00:17:17,000
В теории, кто-то может быть там читать все данные, зашифрованные с RSA.

278
00:17:17,000 --> 00:17:19,000
Там другая немного вопрос конфиденциальности.

279
00:17:19,000 --> 00:17:23,000
Если Томми шифрует некоторые сообщения, используя мой открытый ключ

280
00:17:23,000 --> 00:17:26,000
и злоумышленник шифрует сообщение, используя тот же мой открытый ключ

281
00:17:26,000 --> 00:17:29,000
Злоумышленник увидит, что 2 сообщения идентичны

282
00:17:29,000 --> 00:17:32,000
и, следовательно, знаем, что Томми зашифрованы.

283
00:17:32,000 --> 00:17:36,000
Для того, чтобы предотвратить это, сообщения, как правило, дополняются случайными битами

284
00:17:36,000 --> 00:17:39,000
Перед зашифрованы так, что то же самое сообщение, зашифрованное

285
00:17:39,000 --> 00:17:44,000
несколько раз будет выглядеть по-разному тех пор, как обивка на сообщение разные.

286
00:17:44,000 --> 00:17:47,000
Но помню, как мы должны разделить сообщения на куски

287
00:17:47,000 --> 00:17:50,000
так, чтобы каждый кусок меньше, чем п?

288
00:17:50,000 --> 00:17:52,000
Padding куски означает, что мы, возможно, придется разделить вещи

289
00:17:52,000 --> 00:17:57,000
в еще более кусков, так как мягкий кусок должен быть меньше, чем л.

290
00:17:57,000 --> 00:18:01,000
Шифрование и дешифрование являются относительно дорогими с RSA,

291
00:18:01,000 --> 00:18:05,000
и поэтому нуждаются, чтобы разбить сообщение на множество кусков может быть очень дорогостоящим.

292
00:18:05,000 --> 00:18:09,000
Если большой объем данных должен быть зашифрован и расшифрован

293
00:18:09,000 --> 00:18:12,000
мы можем объединить преимущества симметричного ключа Алгоритмы

294
00:18:12,000 --> 00:18:16,000
с теми RSA, чтобы получить безопасность и эффективность.

295
00:18:16,000 --> 00:18:18,000
Хотя мы не будем вдаваться в это здесь,

296
00:18:18,000 --> 00:18:23,000
AES является симметричным ключом, алгоритм, как Виженера и Цезаря шифры

297
00:18:23,000 --> 00:18:25,000
но гораздо сложнее взломать.

298
00:18:25,000 --> 00:18:30,000
Конечно, мы не можем использовать AES без создания общего секретного ключа

299
00:18:30,000 --> 00:18:34,000
между 2 системами, и мы увидели проблемы с этим раньше.

300
00:18:34,000 --> 00:18:40,000
Но теперь мы можем использовать RSA для установления общего секретного ключа между 2 системами.

301
00:18:40,000 --> 00:18:43,000
Мы будем называть компьютер отправки данных отправителя

302
00:18:43,000 --> 00:18:46,000
и компьютера получения данных приемником.

303
00:18:46,000 --> 00:18:49,000
Приемник имеет пару ключей RSA и посылает

304
00:18:49,000 --> 00:18:51,000
открытый ключ отправителя.

305
00:18:51,000 --> 00:18:54,000
Отправитель генерирует ключ AES,

306
00:18:54,000 --> 00:18:57,000
шифрует его с помощью открытого ключа RSA приемника,

307
00:18:57,000 --> 00:19:00,000
и отправляет ключ AES в приемник.

308
00:19:00,000 --> 00:19:04,000
Приемник расшифровывает сообщение с помощью своего закрытого ключа RSA.

309
00:19:04,000 --> 00:19:09,000
И отправитель и получатель теперь есть ключ AES между ними.

310
00:19:09,000 --> 00:19:14,000
AES, который является гораздо быстрее шифрования и дешифрования, чем RSA,

311
00:19:14,000 --> 00:19:18,000
Теперь можно использовать для шифрования больших объемов данных и отправить их на приемник,

312
00:19:18,000 --> 00:19:21,000
кто может расшифровать, используя тот же ключ.

313
00:19:21,000 --> 00:19:26,000
AES, который является гораздо быстрее шифрования и дешифрования, чем RSA,

314
00:19:26,000 --> 00:19:30,000
Теперь можно использовать для шифрования больших объемов данных и отправить их на приемник,

315
00:19:30,000 --> 00:19:32,000
кто может расшифровать, используя тот же ключ.

316
00:19:32,000 --> 00:19:36,000
Мы просто нуждались RSA для передачи общего ключа.

317
00:19:36,000 --> 00:19:40,000
Нам больше не нужно использовать RSA вообще.

318
00:19:40,000 --> 00:19:46,000
Похоже, я получил сообщение.

319
00:19:46,000 --> 00:19:49,000
Это не имеет значения, если кто читал, что на бумажный самолетик, прежде чем я поймал его

320
00:19:49,000 --> 00:19:55,000
потому что я единственный с закрытым ключом.

321
00:19:55,000 --> 00:19:57,000
Давайте расшифровка каждого из кусков в сообщении.

322
00:19:57,000 --> 00:20:07,000
Первый кусок, 658, мы поднимаем до уровня Д власть, которая составляет 185,

323
00:20:07,000 --> 00:20:18,000
мод п, что 989, равна 67,

324
00:20:18,000 --> 00:20:24,000
которая является буква С в ASCII.

325
00:20:24,000 --> 00:20:31,000
Теперь, на втором блоке.

326
00:20:31,000 --> 00:20:35,000
Второй блок имеет значение 15,

327
00:20:35,000 --> 00:20:41,000
которые мы поднимаем на 185-й власти,

328
00:20:41,000 --> 00:20:51,000
мод 989, а это равно 83

329
00:20:51,000 --> 00:20:57,000
которая является письме S в ASCII.

330
00:20:57,000 --> 00:21:06,000
Теперь в третий кусок, который имеет значение 799, мы поднимаем до 185,

331
00:21:06,000 --> 00:21:17,000
мод 989, а это равно 53,

332
00:21:17,000 --> 00:21:24,000
которая является значение символа 5 в ASCII.

333
00:21:24,000 --> 00:21:30,000
Теперь за последний кусок, который имеет значение 975,

334
00:21:30,000 --> 00:21:41,000
мы поднимаем до 185, мод 989,

335
00:21:41,000 --> 00:21:51,000
а это равно 48, что значение символа 0 в ASCII.

336
00:21:51,000 --> 00:21:57,000
Меня зовут Боб Боуден, и это CS50.

337
00:21:57,000 --> 00:22:00,000
[CS50.TV]

338
00:22:06,000 --> 00:22:08,000
RSA вообще.

339
00:22:08,000 --> 00:22:14,000
RSA вообще. [Смех]

340
00:22:14,000 --> 00:22:17,000
На всех.