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

2
00:00:02,000 --> 00:00:04,000
[Роб Bowden] [Томи MacWilliam] [Харвардския университет]

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
Алгоритми за криптиране като Цезар и Vigenère шифри не са много сигурни.

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
Докато шифър Vigenère е по-сигурен от шифър на Цезар

9
00:00:25,000 --> 00:00:28,000
поради по-голямо търсене на място за ключове, след като хакер

10
00:00:28,000 --> 00:00:30,000
знае дължина на ключа в шифър Vigenère,

11
00:00:30,000 --> 00:00:34,000
, които могат да бъдат определени чрез анализ на моделите в криптирания текст,

12
00:00:34,000 --> 00:00:38,000
шифъра Vigenère не е, че много по-сигурна от шифър на Цезар.

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

14
00:00:42,000 --> 00:00:45,000
Цезар шифър и Vigenère шифър използват един и същ ключ

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
Как два компютри, които искат да общуват установява на таен ключ между тях?

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
ако искате да изпращате съобщения криптирани с RSA 2 потребители

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
Фактът, че има две отделни ключове за криптиране и декриптиране съобщения

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
Да генерира двойка ключове, Роб трябва да вземем две големи прости числа.

76
00:02:47,000 --> 00:02:50,000
Тези номера ще бъдат използвани и в двете публични и частни ключове,

77
00:02:50,000 --> 00:02:54,000
но на публичния ключ ще използвате само продукт на тези две числа,

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
Публичния ключ, не забравяйте, използва продукт на две прости числа.

83
00:03:09,000 --> 00:03:12,000
Този продукт трябва да има само два фактора,

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
в публичен ключ в два номера, използвани в частния ключ

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
Първо, ще имаме нужда от две прости числа.

94
00:03:49,000 --> 00:03:52,000
Ще наричаме тези две числа Р и Q.

95
00:03:52,000 --> 00:03:56,000
За да получите Р и Q, на практика ние ще pseudorandomly генерира

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
докато имаме две прости числа, които можем да използваме.

100
00:04:08,000 --> 00:04:15,000
Тук нека изберем р = 23 и Q = 43.

101
00:04:15,000 --> 00:04:19,000
Не забравяйте, че на практика, Р и Q трябва да бъде много по-големи номера.

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

113
00:05:02,000 --> 00:05:05,000
да получи 4-ти номер, който ще се обадим m.

114
00:05:05,000 --> 00:05:15,000
В нашия случай, m = 22 * ​​42 = 924.

115
00:05:15,000 --> 00:05:18,000
Имаме m = 924.

116
00:05:18,000 --> 00:05:22,000
Сега ще имаме нужда от номер, който е сравнително премиер m

117
00:05:22,000 --> 00:05:25,000
и по-малко от m.

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
толкова дълго, колкото този брой не се случи, да бъде фактор на m.

124
00:05:48,000 --> 00:05:53,000
За ключовете ни, ние ще вземем E = 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 (МО m).

128
00:06:11,000 --> 00:06:17,000
Това m Министерството на отбраната означава, че ние ще използваме нещо, което се нарича модулна аритметика.

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, например, е 02: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
Забележете, че нашата оригинална PRIMES р и р не се появяват

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
Тогава аз ще попитам Роб за публичния му ключ, който ще използвам

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
Ние може да се счупят m съобщение на няколко части

154
00:08:03,000 --> 00:08:07,000
всички по-малки от N и след това криптира всеки един от тези парчета.

155
00:08:07,000 --> 00:08:12,000
Ще криптиране на низ CS50, които можем да се разделят на четири парчета,

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
За да шифровате даден m съобщение

161
00:08:28,000 --> 00:08:37,000
Аз ще трябва да се изчисли C = m д (МО н).

162
00:08:37,000 --> 00:08:40,000
Но m трябва да бъде по-малък от N,

163
00:08:40,000 --> 00:08:45,000
или иначе пълната съобщение не може да бъде изразена по модул N.

164
00:08:45,000 --> 00:08:49,000
Ние може да се счупят m на няколко части, всички от които са по-малки от N,

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
как имаме тази стойност за г.

178
00:10:07,000 --> 00:10:17,000
Нашият номер е необходима за изпълнение 5D = 1 (МО 924).

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

180
00:10:24,000 --> 00:10:28,000
Като се имат предвид две числа А и Б, разширеното евклидово алгоритъм

181
00:10:28,000 --> 00:10:33,000
може да се използва, за да открие най-големия общ делител на тези две числа.

182
00:10:33,000 --> 00:10:37,000
Тя също така ще ни даде два други номера, х и у,

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
и m = 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, а след това увийте около точно Y пъти,

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
така че ако използваме разширен Euclidean алгоритъм

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
и б = 924.

204
00:12:11,000 --> 00:12:14,000
Ние ще използваме метод, наречен таблицата метод.

205
00:12:14,000 --> 00:12:21,000
Нашата маса ще има четири колони, X, Y, D, и к.

206
00:12:21,000 --> 00:12:23,000
Нашата маса започва с два реда.

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
за разделяне на стойността на г в реда над него със стойността на г

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
Сега стойността на всяка друга клетка ще бъде стойността на клетъчните два реда над него

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

216
00:13:09,000 --> 00:13:11,000
Нека започнем с г в 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
В този случай, когато сме се дели на една такава, че к е равна на

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

237
00:14:50,000 --> 00:14:58,000
Ние можем да видим, че тук имаме х = 185 и Y = -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 (МО деветстотин двадесет и четири)

242
00:15:15,000 --> 00:15:20,000
което означава, че имат стойност от 185 г.

243
00:15:20,000 --> 00:15:23,000
Фактът, че г = 1 в последния ред

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

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
За да декодирате парче в мога да изчислите оригиналното съобщение

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
Ако нападателят успява да вземе предвид N в своите две прости числа, Р и Q,

262
00:16:26,000 --> 00:16:30,000
след това тя може да се изчисли г използвате разширеното евклидово алгоритъм.

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
нападателя ще видите, че две съобщения са идентични

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
така, че всяко парче е по-малък от N?

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

289
00:17:52,000 --> 00:17:57,000
още повече парчета от тапицираната парче трябва да бъде по-малък от N.

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 е симетричен алгоритъм като Vigenère и Цезар шифри

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
между две системи, и ние видяхме проблема с това преди.

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

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
Министерството на отбраната N, която е 989, е равен на 67,

324
00:20:18,000 --> 00:20:24,000
което е буквата C в 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
На всички.