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

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden] [Tommy MacWilliam] [Universitato Harvard]

3
00:00:04,000 --> 00:00:07,000
[Jen CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Ni rigardu RSA, vaste uzata algoritmo por encrypting datumoj.

5
00:00:11,000 --> 00:00:16,000
Ĉifrado algoritmoj kiel Cezaro kaj Vigenère ĉifroj estas ne tre sekura.

6
00:00:16,000 --> 00:00:20,000
Kun la cezaro kodita, atacante nur bezonas provi 25 malsamaj ŝlosiloj

7
00:00:20,000 --> 00:00:22,000
por ricevi la mesaĝon de simpla teksto.

8
00:00:22,000 --> 00:00:25,000
Dum la Vigenère estas pli sekura ol la cezaro kodita

9
00:00:25,000 --> 00:00:28,000
pro la pli grandaj serĉo spaco por klavoj, fojo atacante

10
00:00:28,000 --> 00:00:30,000
konas la longecon de la ŝlosilon en Vigenère,

11
00:00:30,000 --> 00:00:34,000
kiu povas esti difinita per analizo de ŝablonoj en la kodita teksto,

12
00:00:34,000 --> 00:00:38,000
la Vigenère ne estas tiel multe pli sekura ol la cezaro ĉifro.

13
00:00:38,000 --> 00:00:42,000
RSA, aliflanke, ne estas vundebla al atakoj kiel ĉi tio.

14
00:00:42,000 --> 00:00:45,000
Cezaro kodita kaj Vigenère uzi la saman ŝlosilon

15
00:00:45,000 --> 00:00:47,000
al ambaŭ ĉifri kaj malĉifri mesaĝon.

16
00:00:47,000 --> 00:00:51,000
Ĉi tiu propraĵo faras tiuj koditaj simetriaj ŝlosilaj algoritmoj.

17
00:00:51,000 --> 00:00:54,000
Fundamenta problemo kun simetria ŝlosilo algoritmoj

18
00:00:54,000 --> 00:00:57,000
estas ke ili fidas la encrypting kaj sendante la mesaĝon

19
00:00:57,000 --> 00:00:59,000
kaj la ricevo kaj decrypting la mesaĝo

20
00:00:59,000 --> 00:01:03,000
esti jam konsentis antaŭenirita sur la klavo ili ambaŭ uzas.

21
00:01:03,000 --> 00:01:06,000
Sed ni havas iom de lanĉo problemon ĉi tie.

22
00:01:06,000 --> 00:01:10,000
Kiel 2 komputiloj kiuj volas komuniki establi sekreta ŝlosilo inter ili?

23
00:01:10,000 --> 00:01:16,000
Se la ŝlosilo devas esti sekreta, do ni bezonas vojon por kodi kaj deĉifri la ŝlosilon.

24
00:01:16,000 --> 00:01:18,000
Se ĉiuj ni havas estas simetria ŝlosila ĉifriko

25
00:01:18,000 --> 00:01:21,000
tiam ni ĵus revenis al la sama problemo.

26
00:01:21,000 --> 00:01:25,000
RSA, aliflanke, uzas paron de klavoj,

27
00:01:25,000 --> 00:01:28,000
unu por ĉifrado kaj alia por malĉifro.

28
00:01:28,000 --> 00:01:32,000
Unu estas nomata la publika ŝlosilo, kaj la alia estas la privata ŝlosilo.

29
00:01:32,000 --> 00:01:34,000
La publika ŝlosilo estas uzata por kodi mesaĝojn.

30
00:01:34,000 --> 00:01:38,000
Kiel vi eble konjektas por lia nomo, oni povas dividi niajn publika ŝlosilo kun

31
00:01:38,000 --> 00:01:43,000
neniu ni volas sen kompromiti la sekurecon de ĉifrita mesaĝo.

32
00:01:43,000 --> 00:01:45,000
Mesaĝoj ĉifrita uzante publikan ŝlosilon

33
00:01:45,000 --> 00:01:49,000
nur povas deĉifrita kun lia responda privata ŝlosilo.

34
00:01:49,000 --> 00:01:53,000
Dum vi povas dividi viajn publika ŝlosilo, vi devus ĉiam subteni viajn privatajn ŝlosilo sekreto.

61
00:01:55,000 --> 00:01:58,000
kaj nur la privata ŝlosilo povas esti uzata por malĉifri mesaĝojn

62
00:01:58,000 --> 00:02:02,000
se 2 uzantoj volas sendi mesaĝojn ĉifrita kun RSA

63
00:02:02,000 --> 00:02:07,000
tien kaj reen ambaŭ uzantoj bezonas havi sian propran publikaj kaj privataj ŝlosilo paron.

64
00:02:07,000 --> 00:02:10,000
Mesaĝoj de uzanto 1 ĝis uzanto 2

65
00:02:10,000 --> 00:02:15,000
nur uzi uzanto 2 La ŝlosila paro, kaj mesaĝoj de uzanto 2 al uzanto 1

66
00:02:15,000 --> 00:02:17,000
nur uzi uzanto 1-oj ŝlosilo paron.

67
00:02:17,000 --> 00:02:21,000
La fakto ke estas 2 apartaj klavoj por kodi kaj deĉifri mesaĝojn

68
00:02:21,000 --> 00:02:24,000
faras RSA nesimetria ŝlosila algoritmo.

69
00:02:24,000 --> 00:02:28,000
Ni ne bezonas por kodi la publika ŝlosilo por sendi ĝin al alia komputilo

70
00:02:28,000 --> 00:02:31,000
ekde la klavo estas publika ĉiuokaze.

71
00:02:31,000 --> 00:02:33,000
Tio signifas, ke RSA ne havas la saman problemon lanĉo

72
00:02:33,000 --> 00:02:36,000
kiel la simetria ŝlosilo algoritmoj.

73
00:02:36,000 --> 00:02:39,000
Do se mi volas sendi mesaĝon uzante RSA ĉifrado

74
00:02:39,000 --> 00:02:42,000
al Rob, mi unue bezonas Rob publika ŝlosilo.

75
00:02:42,000 --> 00:02:47,000
Por generi paro de klavoj, Rob bezonas repreni 2 grandaj primoj.

76
00:02:47,000 --> 00:02:50,000
Ĉi tiuj numeroj estos uzata en ambaŭ la publika kaj privata klavoj,

77
00:02:50,000 --> 00:02:54,000
sed la publika ŝlosilo nur uzi la produkton de tiuj 2 nombroj,

78
00:02:54,000 --> 00:02:56,000
ne la nombra sin.

79
00:02:56,000 --> 00:02:59,000
Iam mi ĉifrita la mesaĝon uzante Rob publika ŝlosilo

80
00:02:59,000 --> 00:03:01,000
Mi povas sendi la mesaĝon al Rob.

81
00:03:01,000 --> 00:03:05,000
Por komputilo, faktoranta nombroj estas malmola problemo.

82
00:03:05,000 --> 00:03:09,000
La publika ŝlosilo, memoru, uzita la produkto de 2 primoj.

83
00:03:09,000 --> 00:03:12,000
Tiu produkto devas tiam havi nur 2 faktoroj,

84
00:03:12,000 --> 00:03:16,000
kiu hazarde estas la numeroj, kiuj konsistigas la privata ŝlosilo.

85
00:03:16,000 --> 00:03:20,000
Por deĉifri la mesaĝon, RSA uzos ĉi privata ŝlosilo

86
00:03:20,000 --> 00:03:25,000
aŭ la numeroj multiplikita kune en la procezo de kreado la publika ŝlosilo.

87
00:03:25,000 --> 00:03:28,000
Ĉar estas kompute peza al faktorigi la nombro

88
00:03:28,000 --> 00:03:32,000
uzata en publika ŝlosila en la 2 nombroj uzita en la privata ŝlosilo

89
00:03:32,000 --> 00:03:36,000
ĝi estas malfacila por atacante elŝeligi la privata ŝlosilo

90
00:03:36,000 --> 00:03:39,000
ke estos necesa por deĉifri la mesaĝon.

91
00:03:39,000 --> 00:03:43,000
Nun ni iru al iu malsupera nivelo detaloj de RSA.

92
00:03:43,000 --> 00:03:46,000
Ni unue vidu kiel ni povas generi paro de ŝlosiloj.

93
00:03:46,000 --> 00:03:49,000
Unue, ni bezonos 2 primoj.

94
00:03:49,000 --> 00:03:52,000
Ni vokos tiuj 2 nombroj p kaj q.

95
00:03:52,000 --> 00:03:56,000
Por repreni p kaj q, en la praktiko ni pseudorandomly generi

96
00:03:56,000 --> 00:03:59,000
grandaj nombroj kaj tiam uzi testo por determini ĉu aŭ ne

97
00:03:59,000 --> 00:04:02,000
tiuj nombroj estas probable primo.

98
00:04:02,000 --> 00:04:05,000
Ni povas gardi generi hazardaj nombroj denove kaj denove

99
00:04:05,000 --> 00:04:08,000
gxis ni havas 2 primoj ke ni povas uzi.

100
00:04:08,000 --> 00:04:15,000
Jen ni elektu p = 23 kaj q = 43.

101
00:04:15,000 --> 00:04:19,000
Memoru, en la praktiko, p kaj q devas esti multe pli granda nombro.

102
00:04:19,000 --> 00:04:22,000
Koncerne ni scias, la pli granda la nombroj, la pli malfacila estas

103
00:04:22,000 --> 00:04:25,000
por fendi ĉifrita mesaĝo.

104
00:04:25,000 --> 00:04:29,000
Sed estas ankaŭ pli multekosta por kodi kaj deĉifri mesaĝojn.

105
00:04:29,000 --> 00:04:33,000
Hodiaŭ ĝi estas ofte rekomendis ke p kaj q estas almenaŭ 1024 bitoj,

106
00:04:33,000 --> 00:04:37,000
kiu metas ĉiun numeron ĉe super 300 decimaloj.

107
00:04:37,000 --> 00:04:40,000
Sed ni elektu tiujn malgrandajn numerojn por ĉi tiu ekzemplo.

108
00:04:40,000 --> 00:04:43,000
Nun ni multigos p kaj q kune akiri 3rd numeron,

109
00:04:43,000 --> 00:04:45,000
kiuj ni vokos n.

110
00:04:45,000 --> 00:04:55,000
En nia kazo, n = 23 * 43, kiu = 989.

111
00:04:55,000 --> 00:04:58,000
Ni n = 989.

112
00:04:58,000 --> 00:05:02,000
Sekva ni multigos p - 1 kun q - 1

113
00:05:02,000 --> 00:05:05,000
akiri 4th nombro, kiun ni nomas m.

114
00:05:05,000 --> 00:05:15,000
En nia kazo, m = 22 * ​​42, kiu = 924.

115
00:05:15,000 --> 00:05:18,000
Ni havas m = 924.

116
00:05:18,000 --> 00:05:22,000
Nun ni bezonas nombro e kiu estas prima al m

117
00:05:22,000 --> 00:05:25,000
kaj malpli ol m.

118
00:05:25,000 --> 00:05:28,000
Du nombroj estas relative primo aŭ interprimo

119
00:05:28,000 --> 00:05:33,000
se la sola pozitiva entjero kiu dividas ilin ambaŭ egale estas 1.

120
00:05:33,000 --> 00:05:37,000
En aliaj vortoj, la plej granda komuna divizoro de e kaj m

121
00:05:37,000 --> 00:05:39,000
devas esti 1.

122
00:05:39,000 --> 00:05:44,000
En la praktiko, estas komuna por e esti la prima 65537

123
00:05:44,000 --> 00:05:48,000
tiel longe kiel ĉi numero ne hazarde estas faktoro de m.

124
00:05:48,000 --> 00:05:53,000
Por nia klavoj, ni elektu kaj = 5

125
00:05:53,000 --> 00:05:57,000
ekde 5 estas relative primo al 924.

126
00:05:57,000 --> 00:06:01,000
Fine, ni bezonos pli da, kiujn ni vokos d.

127
00:06:01,000 --> 00:06:11,000
D devas esti iu valoro kiu kontentigas la ekvacion de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Ĉi mod m signifas ni uzos iun nomita modula aritmetiko.

129
00:06:17,000 --> 00:06:21,000
En modula aritmetiko, unufoje nombro prenas pli altaj ol iu supera baro

130
00:06:21,000 --> 00:06:24,000
ĝi envolver reen ĉirkaŭ al 0.

131
00:06:24,000 --> 00:06:27,000
Horloĝo, ekzemple, uzas modula aritmetiko.

132
00:06:27,000 --> 00:06:31,000
Unu minuton poste 1:59, ekzemple, estas 2:00,

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

134
00:06:33,000 --> 00:06:36,000
La minuto mano envolvis ĉirkaŭ al 0

135
00:06:36,000 --> 00:06:39,000
sur atingi supera baro de 60.

136
00:06:39,000 --> 00:06:46,000
Do, ni povas diri 60 estas ekvivalento al 0 (_mod_ 60)

137
00:06:46,000 --> 00:06:57,000
kaj 125 estas ekvivalenta al 65 estas ekvivalenta al 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Nia publika ŝlosilo estos la paro e kaj n

139
00:07:02,000 --> 00:07:09,000
kie en ĉi tiu kazo e estas 5 kaj n estas 989.

140
00:07:09,000 --> 00:07:15,000
Nia privata ŝlosilo estos la paro d kaj n,

141
00:07:15,000 --> 00:07:22,000
kiu en nia kazo estas 185 kaj 989.

142
00:07:22,000 --> 00:07:25,000
Rimarku ke nia originala primoj p kaj q ne aperas

143
00:07:25,000 --> 00:07:29,000
ie ajn en nia privata aŭ publika klavoj.

144
00:07:29,000 --> 00:07:33,000
Nun ke ni havas niajn paro de klavoj, ni rigardu kiel ni povas ĉifri

145
00:07:33,000 --> 00:07:36,000
kaj malĉifri mesaĝon.

146
00:07:36,000 --> 00:07:38,000
Mi volas sendi mesaĝon al Rob,

147
00:07:38,000 --> 00:07:42,000
do li estos por generi ĉi ŝlosila paro.

148
00:07:42,000 --> 00:07:46,000
Do mi petos al Rob por lia publika ŝlosilo, kiun mi uzas

149
00:07:46,000 --> 00:07:48,000
por kodi mesaĝon por sendi al li.

150
00:07:48,000 --> 00:07:53,000
Memoru, estas tute bone por Rob dividi sian publikan ŝlosilon kun mi.

151
00:07:53,000 --> 00:07:56,000
Sed tio ne estus bone por dividi lia privata ŝlosilo.

152
00:07:56,000 --> 00:08:00,000
Mi ne havas ajnan ideon kion lia privata ŝlosilo estas.

153
00:08:00,000 --> 00:08:03,000
Ni povas rompi nian mesaĝon m supren en pluraj pecoj

154
00:08:03,000 --> 00:08:07,000
ĉiuj malgrandaj ol n kaj tiam ĉifri ĉiu de tiuj pecoj.

155
00:08:07,000 --> 00:08:12,000
Ni ĉifri la kordo CS50, kiun ni povas rompi en 4 pecoj,

156
00:08:12,000 --> 00:08:14,000
unu po litero.

157
00:08:14,000 --> 00:08:17,000
Por kodi mia mesaĝo, mi devas konverti ĝin en

158
00:08:17,000 --> 00:08:20,000
ia nombra prezento.

159
00:08:20,000 --> 00:08:25,000
Ni concatenate la ASCII valoroj kun la gravuloj en mia mesaĝo.

160
00:08:25,000 --> 00:08:28,000
Por kodi donita mesaĝo m

161
00:08:28,000 --> 00:08:37,000
Mi bezonos komputi c = m al la e (mod n).

162
00:08:37,000 --> 00:08:40,000
Sed m ​​devas esti pli malgranda ol n,

163
00:08:40,000 --> 00:08:45,000
alie la plenan mesaĝon ne povas esti esprimita module n.

164
00:08:45,000 --> 00:08:49,000
Ni povas rompi m supren en pluraj pecoj, ĉiuj el kiuj estas pli malgrandaj ol n,

165
00:08:49,000 --> 00:08:52,000
kaj ĉifri ĉiu de tiuj pecoj.

166
00:08:52,000 --> 00:09:03,000
Encrypting ĉiu el tiuj pecoj, ni preni c1 = 67 al la 5 (mod 989)

167
00:09:03,000 --> 00:09:06,000
kio = 658.

168
00:09:06,000 --> 00:09:15,000
Por nia dua bloko ni havas 83 al la 5 (mod 989)

169
00:09:15,000 --> 00:09:18,000
kio = 15.

170
00:09:18,000 --> 00:09:26,000
Por nia tria bloko ni havas 53 al la 5 (mod 989)

171
00:09:26,000 --> 00:09:30,000
kio = 799.

172
00:09:30,000 --> 00:09:39,000
Kaj fine, por nia lasta bloko ni havas 48 al la 5 (mod 989)

173
00:09:39,000 --> 00:09:43,000
kio = 975.

174
00:09:43,000 --> 00:09:48,000
Nun ni povas sendi super tiuj koditaj valoroj al Rob.

175
00:09:54,000 --> 00:09:58,000
Ĉi tie vi iros, Rob.

176
00:09:58,000 --> 00:10:01,000
Dum nia mesaĝo estas en flugo, ni prenu alian rigardon

177
00:10:01,000 --> 00:10:07,000
ĉe kio ni akiris tiun valoron por d.

178
00:10:07,000 --> 00:10:17,000
Nia nombro d bezonataj por satigi 5d = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
Tio igas d la multiplika inverso de 5 module 924.

180
00:10:24,000 --> 00:10:28,000
Donita 2 entjeroj a kaj b, la etendita Eŭklida algoritmo

181
00:10:28,000 --> 00:10:33,000
povas esti uzata por trovi la plej granda komuna divizoro de tiuj 2 entjeroj.

182
00:10:33,000 --> 00:10:37,000
Ĝi ankaŭ donas al ni 2 aliaj nombroj, x kaj y,

183
00:10:37,000 --> 00:10:47,000
kiuj kontentigas la ekvacion ax + by = la plej granda komuna divizoro de a kaj b.

184
00:10:47,000 --> 00:10:49,000
Kiel tiu ĉi helpi nin?

185
00:10:49,000 --> 00:10:52,000
Nu, ŝtopanta en e = 5 por

186
00:10:52,000 --> 00:10:56,000
kaj m = 924 por b

187
00:10:56,000 --> 00:10:59,000
ni jam scias ke ĉi tiuj nombroj estas interprimoj.

188
00:10:59,000 --> 00:11:03,000
Ilia plej granda komuna divizoro estas 1.

189
00:11:03,000 --> 00:11:09,000
Ĉi tiu donas ni 5x + 924y = 1

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

191
00:11:17,000 --> 00:11:22,000
Sed se ni nur zorgas pri ĉio module 924

192
00:11:22,000 --> 00:11:25,000
tiam ni povas faligi la - 924y.

193
00:11:25,000 --> 00:11:27,000
Pensu reen al la horloĝo.

194
00:11:27,000 --> 00:11:31,000
Se la minuto mano estas la 1 kaj poste ĝuste 10 horoj pasas,

195
00:11:31,000 --> 00:11:35,000
ni konas la minuto mano estos ankoraŭ esti sur la 1.

196
00:11:35,000 --> 00:11:39,000
Ĉi tie ni starti je 1 kaj tiam envolver ĉirkaŭ ĝuste y tempoj,

197
00:11:39,000 --> 00:11:41,000
do ni ankoraŭ esti je 1.

198
00:11:41,000 --> 00:11:49,000
Ni havas 5x = 1 (mod 924).

199
00:11:49,000 --> 00:11:55,000
Kaj tie ĉi x estas la sama kiel la d ni serĉas antaŭe,

200
00:11:55,000 --> 00:11:58,000
do se ni uzas la etendita Eŭklida algoritmo

201
00:11:58,000 --> 00:12:04,000
atingi tiun nombro x, jen la nombro ni devus uzi kiel nia d.

202
00:12:04,000 --> 00:12:07,000
Nun ni kuras la etendita Eŭklida algoritmo por a = 5

203
00:12:07,000 --> 00:12:11,000
kaj b = 924.

204
00:12:11,000 --> 00:12:14,000
Ni uzu metodon nomata tablo metodo.

205
00:12:14,000 --> 00:12:21,000
Nia tablo havos 4 kolumnoj, x, y, d, kaj k.

206
00:12:21,000 --> 00:12:23,000
Nia tablo dividu kun 2 vicoj.

207
00:12:23,000 --> 00:12:28,000
En la unua vico ni havas 1, 0, tiam nia valoro de, kiu estas 5,

208
00:12:28,000 --> 00:12:37,000
kaj nia dua vico estas 0, 1, kaj nia valoro por b, kiu estas 924.

209
00:12:37,000 --> 00:12:40,000
La valoro de la 4a kolumno, k, estos la rezulto

210
00:12:40,000 --> 00:12:45,000
la dividadon de la valoro de d en la vico super ĝi kun la valoro de d

211
00:12:45,000 --> 00:12:49,000
en la sama vico.

212
00:12:49,000 --> 00:12:56,000
Ni havas 5 dividite per 924 estas 0 kun iu restaĵo.

213
00:12:56,000 --> 00:12:59,000
Tio signifas ke ni havas k = 0.

214
00:12:59,000 --> 00:13:05,000
Nun la valoro de ĉiu alia ĉelo estos la valoro de la ĉelo 2 vicojn super ĝi

215
00:13:05,000 --> 00:13:09,000
minus la valoro de la vico super ĝi tempoj k.

216
00:13:09,000 --> 00:13:11,000
Ni komencu per d en la 3a linio.

217
00:13:11,000 --> 00:13:19,000
Ni havas 5 - 924 * 0 = 5.

218
00:13:19,000 --> 00:13:25,000
Ni tuj havi 0 - 1 * 0 kio estas 0

219
00:13:25,000 --> 00:13:30,000
kaj 1 - 0 * 0 kiu estas 1.

220
00:13:30,000 --> 00:13:33,000
Ne tro malbona, do ni movi al la venonta vico.

221
00:13:33,000 --> 00:13:36,000
Unue ni bezonas nian valoron de k.

222
00:13:36,000 --> 00:13:43,000
924 dividite per 5 = 184 kun iuj resto,

223
00:13:43,000 --> 00:13:46,000
tial nia valoro por k estas 184.

224
00:13:46,000 --> 00:13:54,000
Nun 924 - 5 * 184 = 4.

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

226
00:14:05,000 --> 00:14:07,000
Bone, ni do la sekva vico.

227
00:14:07,000 --> 00:14:10,000
Nia valoro de k estos 1 ĉar

228
00:14:10,000 --> 00:14:15,000
5 dividita per 4 = 1 kun iuj ceteraj.

229
00:14:15,000 --> 00:14:17,000
Ni plenigu la aliaj kolumnoj.

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
Kaj 1 - 184 * 1 estas 185.

233
00:14:33,000 --> 00:14:35,000
Ni vidu kion nia venonta valoro de k estus.

234
00:14:35,000 --> 00:14:40,000
Nu, tio aspektas kiel ni havas 4 dividite per 1, kiu estas 4.

235
00:14:40,000 --> 00:14:43,000
En ĉi tiu kazo kie ni dividanta per 1 tia ke k estas egala al

236
00:14:43,000 --> 00:14:50,000
la valoro de d en la supra vico signifas ke ni faris kun niaj algoritmo.

237
00:14:50,000 --> 00:14:58,000
Ni povas vidi ĉi tie ke ni havi x = 185 kaj y = -1 en la lasta vico.

238
00:14:58,000 --> 00:15:00,000
Ni nun revenu al nia originala celo.

239
00:15:00,000 --> 00:15:04,000
Ni diris, ke la valoro de x kiel rezulto de kuri ĉi tiu algoritmo

240
00:15:04,000 --> 00:15:08,000
estus la multiplika inverso de a (mod b).

241
00:15:08,000 --> 00:15:15,000
Tio signifas ke 185 estas la multiplika inverso de 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
kio signifas, ke ni havas valoro de 185 por d.

243
00:15:20,000 --> 00:15:23,000
La fakto ke d = 1 en la lasta vico

244
00:15:23,000 --> 00:15:26,000
kontrolu ke TTT estis interprimo al m.

245
00:15:26,000 --> 00:15:30,000
Se ne estus 1 tiam ni devus elekti novan kaj.

246
00:15:30,000 --> 00:15:33,000
Nun ni vidu se Rob ricevis mian mesagxon.

247
00:15:33,000 --> 00:15:35,000
Kiam iu sendas al mi ĉifrita mesaĝo

248
00:15:35,000 --> 00:15:38,000
tiel longe, kiel mi observis mian privata ŝlosilo sekreta

249
00:15:38,000 --> 00:15:41,000
Mi estas la sola kiu povas deĉifri la mesaĝon.

250
00:15:41,000 --> 00:15:46,000
Por malĉifri eron c mi povas kalkuli la originala mesaĝo

251
00:15:46,000 --> 00:15:53,000
estas egala al la bloko al d povo (mod n).

252
00:15:53,000 --> 00:15:57,000
Memoru ke d kaj n estas el mia privata ŝlosilo.

253
00:15:57,000 --> 00:16:01,000
Por ricevi plenan mesaĝon de lia pecoj ni malĉifri ĉiu bloko

254
00:16:01,000 --> 00:16:04,000
kaj concatenate la rezultojn.

255
00:16:04,000 --> 00:16:08,000
Ĝuste kiel sekura estas RSA?

256
00:16:08,000 --> 00:16:10,000
La vero estas, ni ne scias.

257
00:16:10,000 --> 00:16:14,000
Sekureco estas bazita sur kiom longe necesus atacante por fendi mesaĝon

258
00:16:14,000 --> 00:16:16,000
kodita kun RSA.

259
00:16:16,000 --> 00:16:19,000
Memoru ke atakanto havas aliron al via publika ŝlosilo,

260
00:16:19,000 --> 00:16:21,000
kiu enhavas ambaŭ e kaj n.

261
00:16:21,000 --> 00:16:26,000
Se la atakanto sukcesas faktoro n enen ĝia 2 primoj, p kaj q,

262
00:16:26,000 --> 00:16:30,000
tiam ŝi povus kalkuli d uzanta la etendita Eŭklida algoritmo.

263
00:16:30,000 --> 00:16:35,000
Tio donas al ŝi la privata ŝlosilo, kiun oni povas uzi por deĉifri ajna mesaĝo.

264
00:16:35,000 --> 00:16:38,000
Sed kiel rapide oni povas faktorigi entjeroj?

265
00:16:38,000 --> 00:16:41,000
Denove, ni ne scias.

266
00:16:41,000 --> 00:16:43,000
Neniu trovita rapida maniero fari ĝin,

267
00:16:43,000 --> 00:16:46,000
kio signifas ke donita sufiĉe granda n

268
00:16:46,000 --> 00:16:49,000
necesus atacante unrealistically longa

269
00:16:49,000 --> 00:16:51,000
al faktorigi la nombron.

270
00:16:51,000 --> 00:16:54,000
Se iu malkaŝis rapida vojo de faktoranta entjeroj

271
00:16:54,000 --> 00:16:57,000
RSA estus rompita.

272
00:16:57,000 --> 00:17:01,000
Sed eĉ se entjera faktorigo estas propre malrapida

273
00:17:01,000 --> 00:17:04,000
la RSA algoritmo povus ankoraŭ havas iujn difekto en ĝi

274
00:17:04,000 --> 00:17:07,000
kiu permesas por facila malĉifro de mesaĝoj.

275
00:17:07,000 --> 00:17:10,000
Neniu trovita kaj malkaŝis tian difekton tamen,

276
00:17:10,000 --> 00:17:12,000
sed tio ne signifas unu ne ekzistas.

277
00:17:12,000 --> 00:17:17,000
En teorio, iu povus tie legi cxiujn datumoj kodita kun RSA.

278
00:17:17,000 --> 00:17:19,000
Ekzistas alia iom de privacidad temo.

279
00:17:19,000 --> 00:17:23,000
Se Tommy encrypts iuj mesaĝon per mia publika ŝlosilo

280
00:17:23,000 --> 00:17:26,000
kaj atakanto encrypts la saman mesaĝon per mia publika ŝlosilo

281
00:17:26,000 --> 00:17:29,000
la atakanto vidos ke la 2 mesaĝoj identa

282
00:17:29,000 --> 00:17:32,000
kaj tiel scii kion Tommy ĉifrita.

283
00:17:32,000 --> 00:17:36,000
Por malhelpi tion, mesaĝoj estas tipe vatitaj kun hazarda bitoj

284
00:17:36,000 --> 00:17:39,000
antaŭ esti ĉifrita por ke la sama mesaĝo ĉifrita

285
00:17:39,000 --> 00:17:44,000
plurfoje aspektos malsamaj dum la Plenigado sur la mesaĝo estas malsama.

286
00:17:44,000 --> 00:17:47,000
Sed memoru kiom ni devas dividi mesaĝojn en pecoj

287
00:17:47,000 --> 00:17:50,000
tiel ke ĉiu bloko estas pli malgranda ol n?

288
00:17:50,000 --> 00:17:52,000
Plenigado la pecoj signifas ke ni devas dividi aĵojn

289
00:17:52,000 --> 00:17:57,000
en ankoraŭ pli pecojn de la vatita chunk devas esti pli malgranda ol n.

290
00:17:57,000 --> 00:18:01,000
Ĉifrado kaj malĉifro estas relative multekostaj kun RSA,

291
00:18:01,000 --> 00:18:05,000
kaj tiel bezoni por rompi mesaĝon en multajn pecojn eblas tre peniga.

292
00:18:05,000 --> 00:18:09,000
Se granda volumo de datumoj bezonas esti kodita kaj deĉifrita

293
00:18:09,000 --> 00:18:12,000
ni povas kombini la profitoj de simetria ŝlosilo algoritmoj

294
00:18:12,000 --> 00:18:16,000
kun tiuj de RSA akiri ambaŭ sekureco kaj efikeco.

295
00:18:16,000 --> 00:18:18,000
Kvankam ni ne iros en ĝin ĉi tie,

296
00:18:18,000 --> 00:18:23,000
AES estas simetria ŝlosilo algoritmo kiel la Vigenère kaj Cezaro ĉifroj

297
00:18:23,000 --> 00:18:25,000
sed multe pli malfacila por fendi.

298
00:18:25,000 --> 00:18:30,000
Kompreneble, ni ne povas uzi AES sen establi dividita sekreta ŝlosilo

299
00:18:30,000 --> 00:18:34,000
inter la 2 sistemoj, kaj ni vidis la problemon kun tiu antaŭe.

300
00:18:34,000 --> 00:18:40,000
Sed nun ni povas uzi RSA por establi la dividita sekreta ŝlosilo inter la 2 sistemoj.

301
00:18:40,000 --> 00:18:43,000
Ni vokos la komputilo sendas la informon de la sendinto

302
00:18:43,000 --> 00:18:46,000
kaj la komputilo ricevis la datumojn de la ricevilo.

303
00:18:46,000 --> 00:18:49,000
La ricevilo havas RSA ŝlosilo paro kaj sendas

304
00:18:49,000 --> 00:18:51,000
la publika ŝlosilo al la sendinto.

305
00:18:51,000 --> 00:18:54,000
La sendinto generas AES ŝlosilo,

306
00:18:54,000 --> 00:18:57,000
encrypts ĝin kun la ricevilo de RSA publikan ŝlosilon,

307
00:18:57,000 --> 00:19:00,000
kaj sendas la AES ŝlosilo al la ricevilo.

308
00:19:00,000 --> 00:19:04,000
La ricevilo decrypts la mesaĝon kun lia RSA privata ŝlosilo.

309
00:19:04,000 --> 00:19:09,000
Tiel la sendinto kaj la ricevilo havas nun dividita AES ŝlosilo inter ili.

310
00:19:09,000 --> 00:19:14,000
AES, kiu estas multe pli rapida, je ĉifrado kaj malĉifro ol RSA,

311
00:19:14,000 --> 00:19:18,000
povas nun esti uzata por kodi la grandaj volumoj de datumoj kaj sendi ilin al la ricevilo,

312
00:19:18,000 --> 00:19:21,000
kiu povas deĉifri uzante la saman ŝlosilon.

313
00:19:21,000 --> 00:19:26,000
AES, kiu estas multe pli rapida, je ĉifrado kaj malĉifro ol RSA,

314
00:19:26,000 --> 00:19:30,000
povas nun esti uzata por kodi la grandaj volumoj de datumoj kaj sendi ilin al la ricevilo,

315
00:19:30,000 --> 00:19:32,000
kiu povas deĉifri uzante la saman ŝlosilon.

316
00:19:32,000 --> 00:19:36,000
Ni nur bezonas RSA kopii la dividis ŝlosilo.

317
00:19:36,000 --> 00:19:40,000
Ni ne plu bezonas uzi RSA ajn.

318
00:19:40,000 --> 00:19:46,000
Ĝi aspektas kiel Mi havas mesaĝon.

319
00:19:46,000 --> 00:19:49,000
Ne gravas se iu legas kio estas sur la papero aviadilo antaux mi kaptis ĝin

320
00:19:49,000 --> 00:19:55,000
ĉar mi estas la sola kun la privata ŝlosilo.

321
00:19:55,000 --> 00:19:57,000
Ni deĉifri ĉiu el la pecoj en la mesaĝo.

322
00:19:57,000 --> 00:20:07,000
La unua bloko, 658, ni levas al la d potencon, kiu estas 185,

323
00:20:07,000 --> 00:20:18,000
mod n, kiu estas 989, egalas al 67,

324
00:20:18,000 --> 00:20:24,000
kiu estas la litero C en ASCII.

325
00:20:24,000 --> 00:20:31,000
Nun, sur la dua bloko.

326
00:20:31,000 --> 00:20:35,000
La dua bloko havas valoro 15,

327
00:20:35,000 --> 00:20:41,000
kiuj ni supreniri la 185th potenco,

328
00:20:41,000 --> 00:20:51,000
mod 989, kaj ĉi tiu estas egala al 83

329
00:20:51,000 --> 00:20:57,000
kiu estas la litero S en ASCII.

330
00:20:57,000 --> 00:21:06,000
Nun por la tria bloko, kiu havas valoro 799, ni levas al 185,

331
00:21:06,000 --> 00:21:17,000
mod 989, kaj ĉi tiu estas egala al 53,

332
00:21:17,000 --> 00:21:24,000
kiu estas la valoro de la karaktero 5 en ASCII.

333
00:21:24,000 --> 00:21:30,000
Nun por la lasta bloko, kiu havas valoro 975,

334
00:21:30,000 --> 00:21:41,000
ni supreniri 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
kaj ĉi tiu estas egala al 48, kio estas valoro de la karaktero 0 en ASCII.

336
00:21:51,000 --> 00:21:57,000
Mia nomo estas Rob Bowden, kaj ĉi tiu estas CS50.

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

338
00:22:06,000 --> 00:22:08,000
RSA ajn.

339
00:22:08,000 --> 00:22:14,000
RSA ajn. [Ridado]

340
00:22:14,000 --> 00:22:17,000
Tute ne.