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