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] [Sveučilište Harvard]

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

4
00:00:07,000 --> 00:00:11,000
Idemo pogledati RSA, naširoko koristi algoritam za šifriranje podataka.

5
00:00:11,000 --> 00:00:16,000
Šifriranje algoritmi poput Cezara i Vigenère šifre nisu vrlo siguran.

6
00:00:16,000 --> 00:00:20,000
Uz Cezarova šifra, napadač samo treba probati 25 različite tipke

7
00:00:20,000 --> 00:00:22,000
dobiti poruku o običan tekst.

8
00:00:22,000 --> 00:00:25,000
Dok Vigenère šifra je sigurniji nego Cezarova šifra

9
00:00:25,000 --> 00:00:28,000
zbog većeg pretraživanje prostora za ključeve, nekad napadač

10
00:00:28,000 --> 00:00:30,000
zna duljinu ključa u Vigenère šifra,

11
00:00:30,000 --> 00:00:34,000
što se može utvrditi putem analize uzoraka u šifriranom tekstu,

12
00:00:34,000 --> 00:00:38,000
the Vigenère šifra nije da je puno više siguran od Cezarova šifra.

13
00:00:38,000 --> 00:00:42,000
RSA, s druge strane, nije ranjiv na napade kao što je ovaj.

14
00:00:42,000 --> 00:00:45,000
The Cezarova šifra i Vigenère šifra koristiti isti ključ

15
00:00:45,000 --> 00:00:47,000
na obje kriptirali i dešifriraju poruke.

16
00:00:47,000 --> 00:00:51,000
Ova nekretnina čini ove šifre simetrične ključnih algoritama.

17
00:00:51,000 --> 00:00:54,000
Temeljni problem s simetrične ključnih algoritama

18
00:00:54,000 --> 00:00:57,000
je da se oslanjaju na jedan kriptiranje i slanje poruke

19
00:00:57,000 --> 00:00:59,000
i jedan prima i dešifriranjem poruku

20
00:00:59,000 --> 00:01:03,000
da već dogovorena unaprijed na ključu oni će oboje koristiti.

21
00:01:03,000 --> 00:01:06,000
Ali imamo malo pokretanja problem ovdje.

22
00:01:06,000 --> 00:01:10,000
Kako dva računala koja žele komunicirati uspostaviti tajni ključ između njih?

23
00:01:10,000 --> 00:01:16,000
Ako je ključ mora biti tajna, onda trebamo način za šifriranje i dešifriranje tipke.

24
00:01:16,000 --> 00:01:18,000
Ako je sve što imamo je simetrični ključ kriptografija

25
00:01:18,000 --> 00:01:21,000
onda smo samo vratiti na isti problem.

26
00:01:21,000 --> 00:01:25,000
RSA, s druge strane, koristi par ključeva,

27
00:01:25,000 --> 00:01:28,000
jedan za šifriranje i drugi za dešifriranje.

28
00:01:28,000 --> 00:01:32,000
Jedna se zove javni ključ, a drugi je privatni ključ.

29
00:01:32,000 --> 00:01:34,000
Javni ključ se koristi za šifriranje poruka.

30
00:01:34,000 --> 00:01:38,000
Kao što ste mogli pogoditi po nazivu, možemo podijeliti naš javni ključ s

31
00:01:38,000 --> 00:01:43,000
tko želimo bez ugrožavanja sigurnosti šifriranom porukom.

32
00:01:43,000 --> 00:01:45,000
Poruke šifrirana koristeći javni ključ

33
00:01:45,000 --> 00:01:49,000
može biti samo dešifriraju s odgovarajućim privatnim ključem.

34
00:01:49,000 --> 00:01:53,000
Iako možete podijeliti svoj javni ključ, uvijek biste trebali držati svoj privatni ključ tajnu.

61
00:01:55,000 --> 00:01:58,000
i samo privatni ključ se može koristiti za dekriptiranje poruke

62
00:01:58,000 --> 00:02:02,000
ako dvije korisnici žele slati poruke šifrirane s RSA

63
00:02:02,000 --> 00:02:07,000
natrag i naprijed i korisnik morati imati svoj javni i privatni ključ par.

64
00:02:07,000 --> 00:02:10,000
Poruke iz jednog korisnika do korisnika 2

65
00:02:10,000 --> 00:02:15,000
koristiti samo Korisnik 2 je par ključeva i poruke od korisnika 2 na 1 korisnika

66
00:02:15,000 --> 00:02:17,000
koristiti samo Korisnik 1 ključ par.

67
00:02:17,000 --> 00:02:21,000
Činjenica da postoje dvije odvojene tipke za šifriranje i dešifriranje poruka

68
00:02:21,000 --> 00:02:24,000
čini RSA asimetrični ključ algoritam.

69
00:02:24,000 --> 00:02:28,000
Mi ne trebamo za šifriranje javnog ključa kako bi ga poslati na drugo računalo

70
00:02:28,000 --> 00:02:31,000
jer ključ je javni svejedno.

71
00:02:31,000 --> 00:02:33,000
To znači da RSA ne imati istu problema pri pokretanju

72
00:02:33,000 --> 00:02:36,000
kao simetrične ključnih algoritama.

73
00:02:36,000 --> 00:02:39,000
Dakle, ako želim poslati poruku koristeći RSA enkripciju

74
00:02:39,000 --> 00:02:42,000
to Rob, ja prvo ćete morati Rob je javni ključ.

75
00:02:42,000 --> 00:02:47,000
Za generiranje par ključeva, Rob treba pokupiti dvije velike prostih brojeva.

76
00:02:47,000 --> 00:02:50,000
Ove brojke će se koristiti u oba javnih i privatnih ključeva,

77
00:02:50,000 --> 00:02:54,000
ali javni ključ će koristiti samo proizvod tih dvaju brojeva,

78
00:02:54,000 --> 00:02:56,000
nisu brojevi sami.

79
00:02:56,000 --> 00:02:59,000
Jednom sam šifrirana poruka koristeći Rob je javni ključ

80
00:02:59,000 --> 00:03:01,000
Ja mogu poslati poruku Rob.

81
00:03:01,000 --> 00:03:05,000
Za računala, faktoring brojevi je težak problem.

82
00:03:05,000 --> 00:03:09,000
Javni ključ, sjetite se, koristio proizvod dva prostih brojeva.

83
00:03:09,000 --> 00:03:12,000
Ovaj proizvod onda mora imati samo dva faktora,

84
00:03:12,000 --> 00:03:16,000
koji se dogoditi da se brojevi koji čine privatni ključ.

85
00:03:16,000 --> 00:03:20,000
Kako bi dešifrirati poruku, RSA će koristiti ovaj privatni ključ

86
00:03:20,000 --> 00:03:25,000
ili brojevi množe zajedno u procesu stvaranja javni ključ.

87
00:03:25,000 --> 00:03:28,000
Budući da je računski teško faktor broj

88
00:03:28,000 --> 00:03:32,000
koriste u javnim ključem u dvije brojeva koji se koriste u privatnim ključem

89
00:03:32,000 --> 00:03:36,000
to je teško za napadač shvatiti privatni ključ

90
00:03:36,000 --> 00:03:39,000
koje će biti potrebno za dekriptiranje poruke.

91
00:03:39,000 --> 00:03:43,000
Sada idemo u nekim nižim razinama detalja RSA.

92
00:03:43,000 --> 00:03:46,000
Idemo prvi put vidjeti kako možemo generirati par ključeva.

93
00:03:46,000 --> 00:03:49,000
Prvo, mi ćemo morati dva prostih brojeva.

94
00:03:49,000 --> 00:03:52,000
Nazvat ćemo ove dvije brojke p i q.

95
00:03:52,000 --> 00:03:56,000
Kako odabrati p i q, u praksi smo pseudorandomly bi generirati

96
00:03:56,000 --> 00:03:59,000
veliki broj, a zatim koristiti test za utvrđivanje je li ili ne

97
00:03:59,000 --> 00:04:02,000
ti brojevi su vjerojatno premijera.

98
00:04:02,000 --> 00:04:05,000
Možemo zadržati generiranja slučajnih brojeva iznova i iznova

99
00:04:05,000 --> 00:04:08,000
dok imamo dva primes koje možemo koristiti.

100
00:04:08,000 --> 00:04:15,000
Ovdje ćemo pokupiti p = 23 i q = 43.

101
00:04:15,000 --> 00:04:19,000
Sjetite se, u praksi, p i q trebao biti puno veći broj.

102
00:04:19,000 --> 00:04:22,000
Koliko mi znamo, veći broj, to je teže

103
00:04:22,000 --> 00:04:25,000
ispucati šifriranu poruku.

104
00:04:25,000 --> 00:04:29,000
No, to je i skuplji za šifriranje i dešifriranje poruka.

105
00:04:29,000 --> 00:04:33,000
Danas se često preporučuje da p i q su najmanje 1024 bita,

106
00:04:33,000 --> 00:04:37,000
koji stavlja svaki broj na više od 300 decimalnih znamenki.

107
00:04:37,000 --> 00:04:40,000
No, mi ćemo pokupiti ove male brojeve za ovaj primjer.

108
00:04:40,000 --> 00:04:43,000
Sada ćemo pomnožiti p i q zajedno kako bi dobili treći broj,

109
00:04:43,000 --> 00:04:45,000
koje ćemo nazvati n.

110
00:04:45,000 --> 00:04:55,000
U našem slučaju, n = 23 * 43, koji = 989.

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

112
00:04:58,000 --> 00:05:02,000
Sljedeća ćemo pomnožiti P - 1 sa q - 1

113
00:05:02,000 --> 00:05:05,000
dobiti četvrti broj, koji ćemo nazvati m.

114
00:05:05,000 --> 00:05:15,000
U našem slučaju, m = 22 * ​​42, koji = 924.

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

116
00:05:18,000 --> 00:05:22,000
Sada ćemo morati brojčanu e koji je relativno premijera do m

117
00:05:22,000 --> 00:05:25,000
i manje od m.

118
00:05:25,000 --> 00:05:28,000
Dva su brojevi relativno premijera ili coprime

119
00:05:28,000 --> 00:05:33,000
ako je jedini pozitivni cijeli broj koji ih dijeli i ravnomjerno je 1.

120
00:05:33,000 --> 00:05:37,000
Drugim riječima, najveći zajednički djelitelj e i m

121
00:05:37,000 --> 00:05:39,000
mora biti jedan.

122
00:05:39,000 --> 00:05:44,000
U praksi, to je uobičajeno za e biti prost broj 65537

123
00:05:44,000 --> 00:05:48,000
dok je taj broj se ne dogodi da bude faktor metara.

124
00:05:48,000 --> 00:05:53,000
Za naše ključeva, mi ćemo pokupiti e = 5

125
00:05:53,000 --> 00:05:57,000
od 5 je relativno premijera na 924.

126
00:05:57,000 --> 00:06:01,000
Konačno, trebat ćemo još jedan broj, koji ćemo nazvati d..

127
00:06:01,000 --> 00:06:11,000
D mora biti neka vrijednost koja zadovoljava jednadžbu de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Ovaj mod m označava ćemo koristiti nešto što se zove modularna aritmetika.

129
00:06:17,000 --> 00:06:21,000
U modularnom aritmetikom, kad broj dobiva više nego neki gornja granica

130
00:06:21,000 --> 00:06:24,000
ona će završiti natrag oko 0.

131
00:06:24,000 --> 00:06:27,000
Sat, na primjer, koristi modularni aritmetiku.

132
00:06:27,000 --> 00:06:31,000
Jednu minutu nakon 01:59, na primjer, 02:00,

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

134
00:06:33,000 --> 00:06:36,000
Skazaljka je omotan oko 0

135
00:06:36,000 --> 00:06:39,000
nakon dostizanja gornju granicu od 60 godina.

136
00:06:39,000 --> 00:06:46,000
Dakle, možemo reći 60 je ekvivalent 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
i 125 je ekvivalent do 65 je ekvivalent 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Naš javni ključ će biti par e i n

139
00:07:02,000 --> 00:07:09,000
gdje je u ovom slučaju je e 5 i n je 989.

140
00:07:09,000 --> 00:07:15,000
Naš privatni ključ će biti par d i n,

141
00:07:15,000 --> 00:07:22,000
koja je u našem slučaju je 185 i 989.

142
00:07:22,000 --> 00:07:25,000
Uočite da naš izvorni primes p i q ne pojavljuju

143
00:07:25,000 --> 00:07:29,000
nigdje u našim privatnim ili javnim ključevima.

144
00:07:29,000 --> 00:07:33,000
Sada imamo par ključeva, ajmo pogledati kako možemo kodirati

145
00:07:33,000 --> 00:07:36,000
i dešifriranje poruka.

146
00:07:36,000 --> 00:07:38,000
Želim poslati poruku da Rob,

147
00:07:38,000 --> 00:07:42,000
tako da će on biti jedan generirati ovaj par ključeva.

148
00:07:42,000 --> 00:07:46,000
Onda ću pitati Rob za svoj javni ključ, koji ću koristiti

149
00:07:46,000 --> 00:07:48,000
za šifriranje poruku da pošalje k ​​njemu.

150
00:07:48,000 --> 00:07:53,000
Zapamtite, to je potpuno u redu za Rob podijeliti svoj javni ključ sa mnom.

151
00:07:53,000 --> 00:07:56,000
No, to ne bi bilo u redu da dijele njegov privatni ključ.

152
00:07:56,000 --> 00:08:00,000
Ja nemam pojma što je njegov privatni ključ je.

153
00:08:00,000 --> 00:08:03,000
Možemo slomiti našu m poruke na nekoliko komade

154
00:08:03,000 --> 00:08:07,000
sve manji od n, a zatim šifriranje svaki od tih komade.

155
00:08:07,000 --> 00:08:12,000
Mi ćemo kodirati niz CS50, što možemo razbiti u komade, 4

156
00:08:12,000 --> 00:08:14,000
jedan po pismu.

157
00:08:14,000 --> 00:08:17,000
Kako za šifriranje moju poruku, ja ću ga morati pretvoriti u

158
00:08:17,000 --> 00:08:20,000
neka vrsta numeričkom reprezentacije.

159
00:08:20,000 --> 00:08:25,000
Ajmo spojite ASCII vrijednosti s likovima u moje poruke.

160
00:08:25,000 --> 00:08:28,000
Kako za šifriranje dao m poruke

161
00:08:28,000 --> 00:08:37,000
Ja ću morati izračunati c = m do e (mod n).

162
00:08:37,000 --> 00:08:40,000
Ali m mora biti manji od n,

163
00:08:40,000 --> 00:08:45,000
inače puna poruka ne može se izraziti modulu n.

164
00:08:45,000 --> 00:08:49,000
Možemo razbiti m na nekoliko komade, koji su svi manji od n,

165
00:08:49,000 --> 00:08:52,000
i šifriranje svaki od tih komade.

166
00:08:52,000 --> 00:09:03,000
Šifriranje svaki od tih komade, dobili smo c1 = 67 do 5 (mod 989)

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

168
00:09:06,000 --> 00:09:15,000
Za naš drugi komad imamo 83 do 5 (mod 989)

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

170
00:09:18,000 --> 00:09:26,000
Za naš treći komad imamo 53 do 5 (mod 989)

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

172
00:09:30,000 --> 00:09:39,000
I na kraju, za našeg posljednjeg komad imamo 48 do 5 (mod 989)

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

174
00:09:43,000 --> 00:09:48,000
Sada možemo poslati preko ove šifrirane vrijednosti Rob.

175
00:09:54,000 --> 00:09:58,000
Evo, Rob.

176
00:09:58,000 --> 00:10:01,000
Iako je naša poruka je u letu, ajmo uzeti drugi izgled

177
00:10:01,000 --> 00:10:07,000
na koliko smo dobili tu vrijednost za d.

178
00:10:07,000 --> 00:10:17,000
Naš broj d potrebno zadovoljiti 5D = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
To čini d. multiplikativni inverz 5 modulo 924.

180
00:10:24,000 --> 00:10:28,000
S obzirom na dva cijela broja, A i B, proširena Euklidova algoritma

181
00:10:28,000 --> 00:10:33,000
se može koristiti kako bi pronašli najveći zajednički djelitelj tih dvaju brojeva.

182
00:10:33,000 --> 00:10:37,000
Također će nam dati dvije druge brojeve, X i Y,

183
00:10:37,000 --> 00:10:47,000
koji zadovoljavaju jednadžbu ax + by = najveći zajednički djelitelj od A i B.

184
00:10:47,000 --> 00:10:49,000
Kako nam to pomoći?

185
00:10:49,000 --> 00:10:52,000
Pa, uključivanjem u E = 5 za

186
00:10:52,000 --> 00:10:56,000
i m = 924 za b

187
00:10:56,000 --> 00:10:59,000
Već znamo da su ti brojevi su coprime.

188
00:10:59,000 --> 00:11:03,000
Njihov najveći zajednički djelitelj je 1.

189
00:11:03,000 --> 00:11:09,000
To nam daje 5x + 924y = 1

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

191
00:11:17,000 --> 00:11:22,000
Ali ako mi samo briga o svemu modulo 924

192
00:11:22,000 --> 00:11:25,000
onda možemo ispustiti - 924y.

193
00:11:25,000 --> 00:11:27,000
Think natrag na sat.

194
00:11:27,000 --> 00:11:31,000
Ako minuta ruka na jednoj, a zatim točno 10 sati prolaze,

195
00:11:31,000 --> 00:11:35,000
znamo minuta ruka će i dalje biti na jednom.

196
00:11:35,000 --> 00:11:39,000
Ovdje ćemo početi na jednom i onda zaokrenuti točno y puta,

197
00:11:39,000 --> 00:11:41,000
tako da smo i dalje ćete biti na jednom.

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

199
00:11:49,000 --> 00:11:55,000
I ovdje je ovo x je isti kao d smo bili u potrazi za prije,

200
00:11:55,000 --> 00:11:58,000
pa ako mi koristimo proširenu Euklidova algoritma

201
00:11:58,000 --> 00:12:04,000
da biste dobili ovaj broj x, to je broj bismo trebali koristiti kao naš d.

202
00:12:04,000 --> 00:12:07,000
Sada ćemo pokrenuti proširena Euklidova algoritma za a = 5

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

204
00:12:11,000 --> 00:12:14,000
Mi ćemo koristiti metodu zvanu tablica metoda.

205
00:12:14,000 --> 00:12:21,000
Naš stol će imati 4 stupce, X, Y, d, k.

206
00:12:21,000 --> 00:12:23,000
Naš stol započinje s dva reda.

207
00:12:23,000 --> 00:12:28,000
U prvom redu moramo 1, 0, tada je naša vrijednost, što je 5,

208
00:12:28,000 --> 00:12:37,000
i naš drugi red je 0, 1, i naša vrijednost za B, koji je 924.

209
00:12:37,000 --> 00:12:40,000
Vrijednost 4. stupcu, K, će biti rezultat

210
00:12:40,000 --> 00:12:45,000
podjele vrijednost D u redu iznad njega s vrijednosti d

211
00:12:45,000 --> 00:12:49,000
u istom retku.

212
00:12:49,000 --> 00:12:56,000
Imamo pet podijeljeno 924 je 0 s nekim ostatak.

213
00:12:56,000 --> 00:12:59,000
To znači da imamo k = 0.

214
00:12:59,000 --> 00:13:05,000
Sada vrijednost svake druge stanice će biti vrijednost staničnih 2 reda iznad njega

215
00:13:05,000 --> 00:13:09,000
minus vrijednost retka iznad nje puta k.

216
00:13:09,000 --> 00:13:11,000
Počnimo s d u 3. redu.

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

218
00:13:19,000 --> 00:13:25,000
Sljedeća imamo 0-1 * 0 koji je 0

219
00:13:25,000 --> 00:13:30,000
i 1-0 * 0 što je 1.

220
00:13:30,000 --> 00:13:33,000
Nije loše, pa krenimo na sljedeći red.

221
00:13:33,000 --> 00:13:36,000
Prvo moramo našu vrijednost k.

222
00:13:36,000 --> 00:13:43,000
924 podijeljeno 5 = 184 s nekim ostatak,

223
00:13:43,000 --> 00:13:46,000
tako da naša vrijednost za k je 184.

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

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

226
00:14:05,000 --> 00:14:07,000
U redu, idemo napraviti sljedeći redak.

227
00:14:07,000 --> 00:14:10,000
Naša vrijednost k će biti jedan, jer

228
00:14:10,000 --> 00:14:15,000
5 podijeljen 4 = 1 s nekim ostatak.

229
00:14:15,000 --> 00:14:17,000
Ajmo ispuniti u drugim stupcima.

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

233
00:14:33,000 --> 00:14:35,000
Idemo vidjeti što naš sljedeći vrijednost k će biti.

234
00:14:35,000 --> 00:14:40,000
Pa, to izgleda kao da smo četiri podijeljena jedan, što je četiri.

235
00:14:40,000 --> 00:14:43,000
U ovom slučaju gdje smo razdjelnom do 1. tako da je k jednak

236
00:14:43,000 --> 00:14:50,000
vrijednost d u gornjem redu znači da smo učinili s našim algoritam.

237
00:14:50,000 --> 00:14:58,000
Možemo vidjeti da se ovdje imamo x = 185 y = -1 i u zadnjem redu.

238
00:14:58,000 --> 00:15:00,000
Idemo sada vratiti našem izvornom cilja.

239
00:15:00,000 --> 00:15:04,000
Reći da je vrijednost od x kao rezultat trčanje ovaj algoritam

240
00:15:04,000 --> 00:15:08,000
će biti multiplikativni inverz a (mod b).

241
00:15:08,000 --> 00:15:15,000
To znači da je 185 multiplikativni inverz 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
što znači da ćemo imati vrijednost 185 za d.

243
00:15:20,000 --> 00:15:23,000
Činjenica da je d = 1 u zadnjem redu

244
00:15:23,000 --> 00:15:26,000
provjerava da e je coprime da m.

245
00:15:26,000 --> 00:15:30,000
Da nije bilo jednog onda bismo morali odabrati novu e.

246
00:15:30,000 --> 00:15:33,000
Sada ćemo vidjeti da li je Rob je dobio moju poruku.

247
00:15:33,000 --> 00:15:35,000
Kada vam netko pošalje mi šifriranu poruku

248
00:15:35,000 --> 00:15:38,000
dok sam držao moje privatni ključ tajnu

249
00:15:38,000 --> 00:15:41,000
Ja sam jedini koji može dekriptirati poruku.

250
00:15:41,000 --> 00:15:46,000
Za dekriptiranje komad c mogu izračunati izvornu poruku

251
00:15:46,000 --> 00:15:53,000
jednaka je komad do d snage (mod n).

252
00:15:53,000 --> 00:15:57,000
Sjetite se da je d i n su iz mog privatnog ključa.

253
00:15:57,000 --> 00:16:01,000
Da biste dobili punu poruku od svojih komade smo dešifrirati svaki komad

254
00:16:01,000 --> 00:16:04,000
i spojite rezultate.

255
00:16:04,000 --> 00:16:08,000
Točno kako je siguran RSA?

256
00:16:08,000 --> 00:16:10,000
Istina je, ne znamo.

257
00:16:10,000 --> 00:16:14,000
Sigurnost se temelji na tome koliko dugo će potrajati napadača ispucati poruku

258
00:16:14,000 --> 00:16:16,000
kodirana s RSA.

259
00:16:16,000 --> 00:16:19,000
Sjetite se da je napadač ima pristup vašem javnog ključa,

260
00:16:19,000 --> 00:16:21,000
koji sadrži i e i n.

261
00:16:21,000 --> 00:16:26,000
Ako napadač uspio uzet n u svoje dvije primes, p i q,

262
00:16:26,000 --> 00:16:30,000
onda je ona mogla izračunati d koristeći prošireni Euklidova algoritma.

263
00:16:30,000 --> 00:16:35,000
To joj daje privatni ključ, koji se može koristiti za dekriptiranje bilo koju poruku.

264
00:16:35,000 --> 00:16:38,000
No, koliko brzo možemo uzet cijeli brojevi?

265
00:16:38,000 --> 00:16:41,000
Opet, ne znamo.

266
00:16:41,000 --> 00:16:43,000
Nitko nije pronašao brzo način to rade,

267
00:16:43,000 --> 00:16:46,000
što znači da je dano dovoljno velik n

268
00:16:46,000 --> 00:16:49,000
da bi se napadač nerealno dugo

269
00:16:49,000 --> 00:16:51,000
za faktor broja.

270
00:16:51,000 --> 00:16:54,000
Ako je netko otkrio brz način factoring brojeva

271
00:16:54,000 --> 00:16:57,000
RSA bi biti slomljena.

272
00:16:57,000 --> 00:17:01,000
Ali čak i ako cijeli faktorizacija je inherentno spor

273
00:17:01,000 --> 00:17:04,000
RSA algoritam još uvijek može imati neki nedostatak u njemu

274
00:17:04,000 --> 00:17:07,000
koji omogućuje jednostavnu dešifriranje poruka.

275
00:17:07,000 --> 00:17:10,000
Nitko nije pronašao i otkrio takav propust ipak,

276
00:17:10,000 --> 00:17:12,000
ali to ne znači da netko ne postoji.

277
00:17:12,000 --> 00:17:17,000
U teoriji, netko bi mogao biti vani čita sve podatke kriptirani s RSA.

278
00:17:17,000 --> 00:17:19,000
Tu je još malo privatnosti pitanju.

279
00:17:19,000 --> 00:17:23,000
Ako Tommy šifrira neke poruke koristeći moj javni ključ

280
00:17:23,000 --> 00:17:26,000
i napadač šifrira istu poruku koristeći svoj javni ključ

281
00:17:26,000 --> 00:17:29,000
napadač će vidjeti da su dvije poruke su identične

282
00:17:29,000 --> 00:17:32,000
i tako znati što je Tommy kodiran.

283
00:17:32,000 --> 00:17:36,000
Kako bi se to spriječilo, poruke su obično podstavljena s slučajnih bitova

284
00:17:36,000 --> 00:17:39,000
prije kodiran, tako da je ista poruka kriptirani

285
00:17:39,000 --> 00:17:44,000
više puta će izgledati drugačije dok padding na poruke je drugačiji.

286
00:17:44,000 --> 00:17:47,000
Ali zapamtite kako moramo podijeliti poruke na komade

287
00:17:47,000 --> 00:17:50,000
tako da je svaki komad je manji od n?

288
00:17:50,000 --> 00:17:52,000
Padding the komade znači da ćemo morati podijeliti stvari

289
00:17:52,000 --> 00:17:57,000
na još više komade od podstavljene komad mora biti manji od n.

290
00:17:57,000 --> 00:18:01,000
Šifriranje i dešifriranje su relativno skup s RSA,

291
00:18:01,000 --> 00:18:05,000
i tako trebaju razbiti poruku u mnogim komade može biti vrlo skupo.

292
00:18:05,000 --> 00:18:09,000
Ako velika količina podataka treba biti kodiran i dešifriraju

293
00:18:09,000 --> 00:18:12,000
možemo kombinirati prednosti simetrične ključnih algoritama

294
00:18:12,000 --> 00:18:16,000
s onima RSA dobiti i sigurnost i učinkovitost.

295
00:18:16,000 --> 00:18:18,000
Iako nećemo ići u nju ovdje,

296
00:18:18,000 --> 00:18:23,000
AES je simetrični ključ algoritam kao Vigenère i Caesar šiframa

297
00:18:23,000 --> 00:18:25,000
ali mnogo teže ispucati.

298
00:18:25,000 --> 00:18:30,000
Naravno, ne možemo koristiti AES bez uspostave zajednički tajni ključ

299
00:18:30,000 --> 00:18:34,000
između dva sustava, a vidjeli smo problema s tim prije.

300
00:18:34,000 --> 00:18:40,000
No, sada možemo koristiti RSA uspostaviti zajednički tajni ključ između dva sustava.

301
00:18:40,000 --> 00:18:43,000
Mi ćemo pozvati računalo slanja podataka pošiljatelja

302
00:18:43,000 --> 00:18:46,000
i računalo prima podatke prijemnik.

303
00:18:46,000 --> 00:18:49,000
Prijemnik ima RSA par ključeva i šalje

304
00:18:49,000 --> 00:18:51,000
javni ključ pošiljatelja.

305
00:18:51,000 --> 00:18:54,000
Pošiljatelj generira AES ključ,

306
00:18:54,000 --> 00:18:57,000
to šifrira sa prijemnika RSA javni ključ,

307
00:18:57,000 --> 00:19:00,000
i šalje AES ključ na prijemnik.

308
00:19:00,000 --> 00:19:04,000
Prijemnik dekriptira poruku sa svojim privatnim ključem RSA.

309
00:19:04,000 --> 00:19:09,000
I pošiljatelj i primatelj sada imaju zajedničku AES ključ između njih.

310
00:19:09,000 --> 00:19:14,000
AES, što je mnogo brže šifriranje i dešifriranje nego RSA,

311
00:19:14,000 --> 00:19:18,000
sada se može koristiti za šifriranje velike količine podataka i poslati ih na prijemnik,

312
00:19:18,000 --> 00:19:21,000
tko može dekriptirati koristeći istu tipku.

313
00:19:21,000 --> 00:19:26,000
AES, što je mnogo brže šifriranje i dešifriranje nego RSA,

314
00:19:26,000 --> 00:19:30,000
sada se može koristiti za šifriranje velike količine podataka i poslati ih na prijemnik,

315
00:19:30,000 --> 00:19:32,000
tko može dekriptirati koristeći istu tipku.

316
00:19:32,000 --> 00:19:36,000
Mi samo potrebno RSA prenijeti zajednički ključ.

317
00:19:36,000 --> 00:19:40,000
Mi više ne trebate koristiti RSA uopće.

318
00:19:40,000 --> 00:19:46,000
Čini se kao da sam dobio poruku.

319
00:19:46,000 --> 00:19:49,000
To ne smeta ako netko pročitati ono što je na papiru aviona prije nego što sam ga uhvatio

320
00:19:49,000 --> 00:19:55,000
jer ja sam jedini s privatnim ključem.

321
00:19:55,000 --> 00:19:57,000
Ajmo dešifriranje svaki od komade u poruci.

322
00:19:57,000 --> 00:20:07,000
Prvi blok, 658, dižemo se d vlasti, što je 185,

323
00:20:07,000 --> 00:20:18,000
mod n, koji je 989, je jednaka 67,

324
00:20:18,000 --> 00:20:24,000
što je slovo C u ASCII.

325
00:20:24,000 --> 00:20:31,000
Sada, na drugo komad.

326
00:20:31,000 --> 00:20:35,000
Drugi blok ima vrijednost 15,

327
00:20:35,000 --> 00:20:41,000
koje smo podići na 185. vlast,

328
00:20:41,000 --> 00:20:51,000
mod 989, a to je jednako na 83

329
00:20:51,000 --> 00:20:57,000
što je slovo S u ASCII.

330
00:20:57,000 --> 00:21:06,000
Sada za treći blok, koji ima vrijednost 799, dižemo do 185,

331
00:21:06,000 --> 00:21:17,000
mod 989, a to je jednako 53,

332
00:21:17,000 --> 00:21:24,000
što je vrijednost znaka 5 u ASCII.

333
00:21:24,000 --> 00:21:30,000
Sada za zadnji komad, koja ima vrijednost 975,

334
00:21:30,000 --> 00:21:41,000
možemo podići na 185, 989, mod

335
00:21:41,000 --> 00:21:51,000
i to je jednaka do 48, što je vrijednost znakova 0 u ASCII.

336
00:21:51,000 --> 00:21:57,000
Moje ime je Rob Bowden, a ovo je CS50.

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

338
00:22:06,000 --> 00:22:08,000
RSA uopće.

339
00:22:08,000 --> 00:22:14,000
RSA uopće. [Smijeh]

340
00:22:14,000 --> 00:22:17,000
Na sve.