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 * 1185.

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
На всіх.