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] [Harvard University]

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

4
00:00:07,000 --> 00:00:11,000
Poďme sa pozrieť na RSA, široko používaný algoritmus pre šifrovanie dát.

5
00:00:11,000 --> 00:00:16,000
Šifrovacie algoritmy ako Caesar a Vigenère kódy nie sú príliš bezpečné.

6
00:00:16,000 --> 00:00:20,000
S Caesara, útočník potrebuje len vyskúšať 25 rôznych kľúčov

7
00:00:20,000 --> 00:00:22,000
dostať správu na obyčajný text.

8
00:00:22,000 --> 00:00:25,000
Kým Vigenère kód je bezpečnejšie ako Caesara

9
00:00:25,000 --> 00:00:28,000
vzhľadom k väčšej hľadanie priestor pre kľúče, raz útočník

10
00:00:28,000 --> 00:00:30,000
vie, dĺžku kľúča v Vigenère kód,

11
00:00:30,000 --> 00:00:34,000
, Ktoré môžu byť stanovená prostredníctvom analýzy vzoriek v šifrovaných textu,

12
00:00:34,000 --> 00:00:38,000
Vigenère kód nie je to, že oveľa bezpečnejšie ako Caesara.

13
00:00:38,000 --> 00:00:42,000
RSA, na druhej strane, nie je náchylné k útokom, ako je tento.

14
00:00:42,000 --> 00:00:45,000
Caesar kód a Vigenère kód používať rovnaký kľúč

15
00:00:45,000 --> 00:00:47,000
ako šifrovať a dešifrovať správy.

16
00:00:47,000 --> 00:00:51,000
Táto vlastnosť robí Tieto šifry symetrické kľúčových algoritmov.

17
00:00:51,000 --> 00:00:54,000
Základným problémom symetrická kľúčové algoritmy

18
00:00:54,000 --> 00:00:57,000
je to, že oni sa spoliehajú na jednej strane a šifrovanie a odoslanie správy

19
00:00:57,000 --> 00:00:59,000
a jeden prijímajúci a dešifrovanie správy

20
00:00:59,000 --> 00:01:03,000
sa už dohodli vopred na kľúč budú obaja používať.

21
00:01:03,000 --> 00:01:06,000
Ale máme trochu problém pri spustení tu.

22
00:01:06,000 --> 00:01:10,000
Ako 2 počítače, ktoré chcú komunikovať vytvoriť tajný kľúč medzi nimi?

23
00:01:10,000 --> 00:01:16,000
Ak kľúč musí byť tajná, potom potrebujeme spôsob, ako šifrovať a dešifrovať kľúč.

24
00:01:16,000 --> 00:01:18,000
Ak všetko, čo máme, je symetrický kľúč kryptografia

25
00:01:18,000 --> 00:01:21,000
potom sme práve prišli späť do rovnakého problému.

26
00:01:21,000 --> 00:01:25,000
RSA, na druhej strane, používa dvojica kľúčov,

27
00:01:25,000 --> 00:01:28,000
jeden pre šifrovanie a iný pre dešifrovanie.

28
00:01:28,000 --> 00:01:32,000
Jedným z nich je tzv verejný kľúč, a druhý je súkromný kľúč.

29
00:01:32,000 --> 00:01:34,000
Verejný kľúč slúži na šifrovanie správ.

30
00:01:34,000 --> 00:01:38,000
Ako asi tušíte podľa názvu, môžeme podeliť o naše verejný kľúč s

31
00:01:38,000 --> 00:01:43,000
niekto chceme, bez toho, aby bola ohrozená bezpečnosť šifrované správe.

32
00:01:43,000 --> 00:01:45,000
Správy šifrovaná pomocou verejného kľúča

33
00:01:45,000 --> 00:01:49,000
dá dešifrovať iba so zodpovedajúcim privátnym kľúčom.

34
00:01:49,000 --> 00:01:53,000
Aj keď môžete zdieľať váš verejný kľúč, mali by ste mať svoj súkromný kľúč v tajnosti.

61
00:01:55,000 --> 00:01:58,000
a to iba súkromný kľúč môže byť použitý na dešifrovanie správ

62
00:01:58,000 --> 00:02:02,000
ak 2 užívatelia chcú poslať správy šifrované pomocou RSA

63
00:02:02,000 --> 00:02:07,000
tam a späť obaja užívatelia musia mať svoju vlastnú verejné a súkromné ​​kľúče.

64
00:02:07,000 --> 00:02:10,000
Správy od užívateľa 1 až 2 užívateľovi

65
00:02:10,000 --> 00:02:15,000
používať iba užívateľské 2 kľúčovú pár, a správy od užívateľa 2 k užívateľovi 1

66
00:02:15,000 --> 00:02:17,000
používať iba Užívateľ 1 je dvojica kľúčov.

67
00:02:17,000 --> 00:02:21,000
Skutočnosť, že sú 2 samostatné kľúče na šifrovanie a dešifrovanie správ

68
00:02:21,000 --> 00:02:24,000
robí RSA asymetrický kľúčový algoritmus.

69
00:02:24,000 --> 00:02:28,000
Nepotrebujeme na zašifrovanie verejný kľúč, aby sa odoslať ju do iného počítača

70
00:02:28,000 --> 00:02:31,000
, Pretože kľúč je verejný rovnako.

71
00:02:31,000 --> 00:02:33,000
To znamená, že RSA nemá rovnaký spúšťací problém

72
00:02:33,000 --> 00:02:36,000
ako symetrická kľúčové algoritmy.

73
00:02:36,000 --> 00:02:39,000
Takže keď chcem odoslať správu pomocou RSA šifrovanie

74
00:02:39,000 --> 00:02:42,000
Robymu, budem musieť najprv Rob verejný kľúč.

75
00:02:42,000 --> 00:02:47,000
Ak chcete generovať dvojicu kľúčov, Rob musí vybrať 2 veľké prvočísla.

76
00:02:47,000 --> 00:02:50,000
Tieto čísla budú použité v oboch verejných a súkromných kľúčov,

77
00:02:50,000 --> 00:02:54,000
ale verejný kľúč bude používať iba produkt týchto 2 čísel,

78
00:02:54,000 --> 00:02:56,000
nie samotná čísla.

79
00:02:56,000 --> 00:02:59,000
Potom, čo som šifrovaná správu pomocou Rob verejný kľúč

80
00:02:59,000 --> 00:03:01,000
Môžem poslať správu Rob.

81
00:03:01,000 --> 00:03:05,000
U počítača, factoring čísla je ťažký problém.

82
00:03:05,000 --> 00:03:09,000
Verejný kľúč, pamätajte, používal produkt 2 prvočísel.

83
00:03:09,000 --> 00:03:12,000
Tento výrobok musí mať iba 2 faktory,

84
00:03:12,000 --> 00:03:16,000
ktoré sa dejú, že sú čísla, ktoré tvorí súkromný kľúč.

85
00:03:16,000 --> 00:03:20,000
Aby bolo možné dešifrovať správy, bude RSA použite tento súkromný kľúč

86
00:03:20,000 --> 00:03:25,000
alebo čísla násobí spoločne v procese vytvárania verejného kľúča.

87
00:03:25,000 --> 00:03:28,000
Vzhľadom k tomu, že je výpočtovo ťažké faktora sa počet

88
00:03:28,000 --> 00:03:32,000
používa vo verejnej kľúča do 2 čísla používaných v súkromnom kľúči

89
00:03:32,000 --> 00:03:36,000
je to ťažké pre útočníkovi zistiť súkromného kľúča

90
00:03:36,000 --> 00:03:39,000
že bude nutné dešifrovať správy.

91
00:03:39,000 --> 00:03:43,000
Teraz poďme do niektorých nižších úrovní detailov RSA.

92
00:03:43,000 --> 00:03:46,000
Pozrime sa najprv, ako môžeme vytvoriť dvojicu kľúčov.

93
00:03:46,000 --> 00:03:49,000
Po prvé, budeme potrebovať 2 prvočísla.

94
00:03:49,000 --> 00:03:52,000
Zavoláme tieto 2 čísla p a q.

95
00:03:52,000 --> 00:03:56,000
Pri výbere p a q, v praxi by sme pseudorandomly vytvárať

96
00:03:56,000 --> 00:03:59,000
veľké množstvo a potom použiť test na určenie, či

97
00:03:59,000 --> 00:04:02,000
tieto čísla sú pravdepodobne pripraviť.

98
00:04:02,000 --> 00:04:05,000
Môžeme si ponechať generovanie náhodných čísel znovu a znovu

99
00:04:05,000 --> 00:04:08,000
až budeme mať 2 prvočísla, ktoré môžeme použiť.

100
00:04:08,000 --> 00:04:15,000
Tu poďme vybrať p = 23 a q = 43.

101
00:04:15,000 --> 00:04:19,000
Pamätajte si, že v praxi by p a q byť oveľa väčšie čísla.

102
00:04:19,000 --> 00:04:22,000
Pokiaľ je nám známe, že čím väčšie čísla, tým ťažšie je

103
00:04:22,000 --> 00:04:25,000
bezva zašifrovanú správu.

104
00:04:25,000 --> 00:04:29,000
Ale je to aj drahšie pre šifrovanie a dešifrovanie správ.

105
00:04:29,000 --> 00:04:33,000
Dnes sa často odporúča, aby p a q sú aspoň 1024 bitov,

106
00:04:33,000 --> 00:04:37,000
ktorá stavia na každé číslo na viac ako 300 desatinných miest.

107
00:04:37,000 --> 00:04:40,000
Ale budeme vyberať tieto malé čísla pre tento príklad.

108
00:04:40,000 --> 00:04:43,000
Teraz budeme násobiť p a q spoločne získať tretie číslo,

109
00:04:43,000 --> 00:04:45,000
ktoré budeme nazývať n

110
00:04:45,000 --> 00:04:55,000
V našom prípade, n = 23 * 43, ktorý = 989.

111
00:04:55,000 --> 00:04:58,000
Sme N = 989.

112
00:04:58,000 --> 00:05:02,000
Ďalšie budeme násobiť p - 1 s q - 1

113
00:05:02,000 --> 00:05:05,000
získať štvrté číslo, ktoré budeme nazývať m

114
00:05:05,000 --> 00:05:15,000
V našom prípade, m = 22 * ​​42, ktorý = 924.

115
00:05:15,000 --> 00:05:18,000
Máme m = 924.

116
00:05:18,000 --> 00:05:22,000
Teraz budeme potrebovať číslo e, ktorá je nesúdeliteľné m

117
00:05:22,000 --> 00:05:25,000
a menej ako m.

118
00:05:25,000 --> 00:05:28,000
Dve čísla sú nesúdeliteľné, alebo coprime

119
00:05:28,000 --> 00:05:33,000
ak len pozitívne celé číslo, ktoré delí obe rovnomerne je 1.

120
00:05:33,000 --> 00:05:37,000
Inými slovami, najväčší spoločný deliteľ E a M

121
00:05:37,000 --> 00:05:39,000
musí byť 1.

122
00:05:39,000 --> 00:05:44,000
V praxi, to je spoločné pre e byť prvočíslo 65537

123
00:05:44,000 --> 00:05:48,000
tak dlho, ako je toto číslo sa nestane byť faktor m.

124
00:05:48,000 --> 00:05:53,000
Pre našich kľúče, budeme vyberať e = 5

125
00:05:53,000 --> 00:05:57,000
od 5 je nesúdeliteľné 924.

126
00:05:57,000 --> 00:06:01,000
Nakoniec, budeme potrebovať jeden väčší počet, ktorý budeme nazývať d

127
00:06:01,000 --> 00:06:11,000
D musí byť nejaká hodnota, ktorá spĺňa rovnicu de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
To m mod znamená budeme používať niečo, čo nazýva modulárny aritmetika.

129
00:06:17,000 --> 00:06:21,000
V modulárnej aritmetike, raz číslo dostane vyšší ako niektoré hornú hranicu

130
00:06:21,000 --> 00:06:24,000
to sa zalomia späť k 0.

131
00:06:24,000 --> 00:06:27,000
Hodiny, napríklad, používa modulárny aritmetiku.

132
00:06:27,000 --> 00:06:31,000
Minútu po 01:59, napríklad, je 2:00,

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

134
00:06:33,000 --> 00:06:36,000
Minútová ručička sa omotal okolo 0

135
00:06:36,000 --> 00:06:39,000
po dosiahnutí hornej hranice 60.

136
00:06:39,000 --> 00:06:46,000
Takže môžeme povedať, 60 je ekvivalentná 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
a 125 je ekvivalent k 65 je ekvivalentná 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Naše verejné kľúč bude dvojica e a n

139
00:07:02,000 --> 00:07:09,000
kde v tomto prípade je e 5 a n je 989.

140
00:07:09,000 --> 00:07:15,000
Naše vlastné kľúč bude dvojica d a n,

141
00:07:15,000 --> 00:07:22,000
ktorá je v našom prípade 185 a 989.

142
00:07:22,000 --> 00:07:25,000
Všimnite si, že náš pôvodný prvočísla p a q sa nezobrazí

143
00:07:25,000 --> 00:07:29,000
kdekoľvek v našich súkromných alebo verejných kľúčov.

144
00:07:29,000 --> 00:07:33,000
Teraz, keď máme pár kľúčov, poďme sa pozrieť na to, ako môžeme zašifrovať

145
00:07:33,000 --> 00:07:36,000
a dešifrovať správy.

146
00:07:36,000 --> 00:07:38,000
Chcem poslať správu Rob,

147
00:07:38,000 --> 00:07:42,000
tak on bude tým, kto k vygenerovanie tejto dvojice kľúčov.

148
00:07:42,000 --> 00:07:46,000
Spýtam sa Rob jeho verejného kľúča, ktorý budem používať

149
00:07:46,000 --> 00:07:48,000
na zašifrovanie správy poslať k nemu.

150
00:07:48,000 --> 00:07:53,000
Pamätajte si, že je to úplne v poriadku Rob zdieľať jeho verejný kľúč so mnou.

151
00:07:53,000 --> 00:07:56,000
Ale to by nebolo v poriadku zdieľať svoj súkromný kľúč.

152
00:07:56,000 --> 00:08:00,000
Nemám potuchy, čo jeho súkromný kľúč je.

153
00:08:00,000 --> 00:08:03,000
Môžeme porušiť správu m do niekoľkých kúsky

154
00:08:03,000 --> 00:08:07,000
všetky menšie ako n a potom zašifrovať každý z týchto blokov.

155
00:08:07,000 --> 00:08:12,000
Ak budeme zašifrovať reťazec CS50, ktoré môžeme rozdeliť do 4 kusy,

156
00:08:12,000 --> 00:08:14,000
jeden na písmeno.

157
00:08:14,000 --> 00:08:17,000
Za účelom šifrovanie môj vzkaz, budem musieť previesť do

158
00:08:17,000 --> 00:08:20,000
nejaký druh numerickej reprezentácie.

159
00:08:20,000 --> 00:08:25,000
Poďme zreťaziť hodnoty ASCII s postavami v mojej správe.

160
00:08:25,000 --> 00:08:28,000
Aby bolo možné šifrovanie danú správu m

161
00:08:28,000 --> 00:08:37,000
Budem sa musieť počítať c = m na e (mod n).

162
00:08:37,000 --> 00:08:40,000
Ale m musí byť menšie ako n,

163
00:08:40,000 --> 00:08:45,000
inak celá správa nemôže byť vyjadrená modulo n

164
00:08:45,000 --> 00:08:49,000
Môžeme rozdeliť m až do niekoľkých blokov, z ktorých všetky sú menšie ako n,

165
00:08:49,000 --> 00:08:52,000
a šifrovať každý z týchto blokov.

166
00:08:52,000 --> 00:09:03,000
Šifrovanie každý z týchto blokov, dostaneme c1 = 67 k 5 (mod 989)

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

168
00:09:06,000 --> 00:09:15,000
Pre nášho druhého bloku máme 83 na 5 (mod 989)

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

170
00:09:18,000 --> 00:09:26,000
Pre nášho tretieho bloku máme 53 na 5 (mod 989)

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

172
00:09:30,000 --> 00:09:39,000
A konečne, pre náš posledný kus máme 48 na 5 (mod 989)

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

174
00:09:43,000 --> 00:09:48,000
Teraz môžeme poslať cez tieto šifrované hodnoty Rob.

175
00:09:54,000 --> 00:09:58,000
Tu to máš, Robe.

176
00:09:58,000 --> 00:10:01,000
Kým naše posolstvo je v lete, poďme sa ešte raz pozrieť

177
00:10:01,000 --> 00:10:07,000
na to, ako sme sa dostali, že hodnotu d

178
00:10:07,000 --> 00:10:17,000
Naše číslo d potrebné na uspokojenie 5d = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
To je d multiplikatívnej inverzný 5 modulo 924.

180
00:10:24,000 --> 00:10:28,000
Vzhľadom k tomu, 2 celé čísla a, b, rozšírená Euclidean algoritmus

181
00:10:28,000 --> 00:10:33,000
môže byť použitý na nájdenie najväčšieho spoločného deliteľa týchto 2 čísel.

182
00:10:33,000 --> 00:10:37,000
To bude tiež dať nám ďalšie 2 čísla, x a y,

183
00:10:37,000 --> 00:10:47,000
ktoré spĺňajú rovnicu ax + by = najväčší spoločný deliteľ a a b

184
00:10:47,000 --> 00:10:49,000
Ako to pomôže nám?

185
00:10:49,000 --> 00:10:52,000
No, zasunutím e = 5 pre

186
00:10:52,000 --> 00:10:56,000
a m = 924 pre b

187
00:10:56,000 --> 00:10:59,000
už vieme, že tieto čísla sú coprime.

188
00:10:59,000 --> 00:11:03,000
Ich najväčší spoločný deliteľ je 1.

189
00:11:03,000 --> 00:11:09,000
To nám dáva 5x + 924y = 1

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

191
00:11:17,000 --> 00:11:22,000
Ale ak nás však zaujíma iba o všetkom modulo 924

192
00:11:22,000 --> 00:11:25,000
potom môžeme pretiahnuť - 924y.

193
00:11:25,000 --> 00:11:27,000
Spomeňte si na hodiny.

194
00:11:27,000 --> 00:11:31,000
Ak minútová ručička je na 1 a potom presne 10 hodín prejsť,

195
00:11:31,000 --> 00:11:35,000
vieme, že minútová ručička bude stále na 1.

196
00:11:35,000 --> 00:11:39,000
Tu začíname na 1 a potom zabaliť okolo presne y časy,

197
00:11:39,000 --> 00:11:41,000
takže budeme stále v 1.

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

199
00:11:49,000 --> 00:11:55,000
A tu to x je rovnaký ako v d sme hľadali skôr,

200
00:11:55,000 --> 00:11:58,000
takže ak budeme používať rozšírené Euclidean algoritmus

201
00:11:58,000 --> 00:12:04,000
a získajte tento číslo x, že je to číslo by sme mali používať ako náš d.

202
00:12:04,000 --> 00:12:07,000
Teraz poďme spustiť rozšírený Euclidean algoritmus pre = 5

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

204
00:12:11,000 --> 00:12:14,000
Použijeme metódu nazvanú tabuľka metóda.

205
00:12:14,000 --> 00:12:21,000
Naša tabuľka bude mať 4 stĺpce, x, y, d, a k

206
00:12:21,000 --> 00:12:23,000
Náš stôl začína s 2 riadky.

207
00:12:23,000 --> 00:12:28,000
V prvom rade máme 1, 0, potom sa naša hodnota, ktorá je 5,

208
00:12:28,000 --> 00:12:37,000
a naša druhá rada je 0, 1, a naša hodnota pre B, ktorý je 924.

209
00:12:37,000 --> 00:12:40,000
Hodnota 4. stĺpca, k, bude výsledok

210
00:12:40,000 --> 00:12:45,000
delenie hodnotu d na riadku nad ním s hodnotou d

211
00:12:45,000 --> 00:12:49,000
na rovnakom riadku.

212
00:12:49,000 --> 00:12:56,000
Máme 5 deleno 924 je 0 s nejakým zvyškom.

213
00:12:56,000 --> 00:12:59,000
To znamená, že máme k = 0.

214
00:12:59,000 --> 00:13:05,000
Teraz sa hodnota každého iného bunky bude hodnota bunky 2 radoch nad ňou

215
00:13:05,000 --> 00:13:09,000
mínus hodnota na riadku nad ním časy k.

216
00:13:09,000 --> 00:13:11,000
Poďme začať s d v 3. rade.

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

218
00:13:19,000 --> 00:13:25,000
Potom máme 0-1 * 0, čo je 0

219
00:13:25,000 --> 00:13:30,000
a 1 - 0 * 0, ktorá je 1.

220
00:13:30,000 --> 00:13:33,000
Nie je to tak zlé, takže sa poďme presunúť na ďalší riadok.

221
00:13:33,000 --> 00:13:36,000
Najprv musíme našu hodnotu k.

222
00:13:36,000 --> 00:13:43,000
924 deleno 5 = 184 s nejakým zvyškom,

223
00:13:43,000 --> 00:13:46,000
takže naša hodnota k je 184.

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

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

226
00:14:05,000 --> 00:14:07,000
Dobre, poďme urobiť ďalší riadok.

227
00:14:07,000 --> 00:14:10,000
Naša hodnota k bude 1, pretože

228
00:14:10,000 --> 00:14:15,000
5 deleno 4 = 1 s nejakým zvyškom.

229
00:14:15,000 --> 00:14:17,000
Poďme vyplniť v ostatných stĺpcoch.

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

233
00:14:33,000 --> 00:14:35,000
Pozrime sa, čo naše ďalšie hodnota súčiniteľa bude.

234
00:14:35,000 --> 00:14:40,000
No, vyzerá to, že máme 4 delené 1, čo je 4.

235
00:14:40,000 --> 00:14:43,000
V tomto prípade, keď sme delením 1 tak, že k je rovná

236
00:14:43,000 --> 00:14:50,000
hodnota d vo vyššie uvedenom riadku znamená, že skončíme s naším algoritmom.

237
00:14:50,000 --> 00:14:58,000
Môžeme vidieť, že máme x = 185, y = -1 v poslednom riadku.

238
00:14:58,000 --> 00:15:00,000
Poďme sa teraz vrátiť k nášmu pôvodnému cieľu.

239
00:15:00,000 --> 00:15:04,000
Povedali sme, že hodnota x v dôsledku prevádzky tohto algoritmu

240
00:15:04,000 --> 00:15:08,000
by multiplikatívnej inverzné k (mod b).

241
00:15:08,000 --> 00:15:15,000
To znamená, že 185 je multiplikatívnej inverzný 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
, Čo znamená, že sa majú hodnotu 185 pre d

243
00:15:20,000 --> 00:15:23,000
Skutočnosť, že d = 1 v poslednom riadku

244
00:15:23,000 --> 00:15:26,000
overí, že e bola coprime k m.

245
00:15:26,000 --> 00:15:30,000
Ak by tomu tak nebolo 1, potom budeme musieť vybrať nového e

246
00:15:30,000 --> 00:15:33,000
Teraz sa pozrieme, či Rob získal moju správu.

247
00:15:33,000 --> 00:15:35,000
Keď mi niekto pošle šifrovanú správu

248
00:15:35,000 --> 00:15:38,000
tak dlho, ako som držal som súkromný kľúč v tajnosti

249
00:15:38,000 --> 00:15:41,000
Som jediný, kto môže dešifrovať správy.

250
00:15:41,000 --> 00:15:46,000
Ak chcete dešifrovať kus c môžem vypočítať pôvodnú správu

251
00:15:46,000 --> 00:15:53,000
je rovná bloku na d moci (mod n).

252
00:15:53,000 --> 00:15:57,000
Pamätajte si, že d a n sú z môjho súkromného kľúča.

253
00:15:57,000 --> 00:16:01,000
Ak chcete získať kompletnú správu z jeho kúsky sme dešifrovať každý blok

254
00:16:01,000 --> 00:16:04,000
a zreťaziť výsledky.

255
00:16:04,000 --> 00:16:08,000
Presne tak, ako bezpečný je RSA?

256
00:16:08,000 --> 00:16:10,000
Pravdou je, že nevieme.

257
00:16:10,000 --> 00:16:14,000
Bezpečnosť je založená na tom, ako dlho to bude trvať, aby útočník bezva správu

258
00:16:14,000 --> 00:16:16,000
šifrovaný pomocou RSA.

259
00:16:16,000 --> 00:16:19,000
Pamätajte si, že útočník má prístup k vášmu verejný kľúč,

260
00:16:19,000 --> 00:16:21,000
ktorý obsahuje ako e a n

261
00:16:21,000 --> 00:16:26,000
Ak útočník dokáže faktor N do svojich 2 pripraví, p a q,

262
00:16:26,000 --> 00:16:30,000
potom by mohla vypočítať d pomocou rozšíreného Euclidean algoritmus.

263
00:16:30,000 --> 00:16:35,000
To jej dáva súkromný kľúč, ktorý môže byť použitý na dešifrovanie žiadne správy.

264
00:16:35,000 --> 00:16:38,000
Ale ako rýchlo môžeme vytknúť celé čísla?

265
00:16:38,000 --> 00:16:41,000
Opäť, nevieme.

266
00:16:41,000 --> 00:16:43,000
Nikto našiel rýchly spôsob, ako to urobiť,

267
00:16:43,000 --> 00:16:46,000
To znamená, že vzhľadom na dostatočne veľká n

268
00:16:46,000 --> 00:16:49,000
to by sa útočníkovi nereálne dlho

269
00:16:49,000 --> 00:16:51,000
započítavať číslo.

270
00:16:51,000 --> 00:16:54,000
Ak niekto odhalil rýchly spôsob factoringových celých čísel

271
00:16:54,000 --> 00:16:57,000
RSA by byť rozbitý.

272
00:16:57,000 --> 00:17:01,000
Ale aj keď faktorizace celého čísla je vo svojej podstate pomalé

273
00:17:01,000 --> 00:17:04,000
RSA algoritmus mohol ešte mať nejakú vadu v tom

274
00:17:04,000 --> 00:17:07,000
, Ktorá umožňuje ľahké dešifrovanie správ.

275
00:17:07,000 --> 00:17:10,000
Nikto našiel a odhalil tak chybu ešte,

276
00:17:10,000 --> 00:17:12,000
ale to neznamená že neexistuje.

277
00:17:12,000 --> 00:17:17,000
Teoreticky by mohol niekto byť vonku čítanie všetkých dát zašifrované pomocou RSA.

278
00:17:17,000 --> 00:17:19,000
Je tu ďalší kúsok o ochrane osobných vydanie.

279
00:17:19,000 --> 00:17:23,000
Ak Tommy zašifruje nejakú správu pomocou verejného kľúča svoj

280
00:17:23,000 --> 00:17:26,000
a útočník zašifruje rovnaký správu pomocou verejného kľúča svoj

281
00:17:26,000 --> 00:17:29,000
útočník uvidí, že 2 správy sú totožné

282
00:17:29,000 --> 00:17:32,000
a tak viem, čo Tommy šifrované.

283
00:17:32,000 --> 00:17:36,000
Aby sa tomu zabránilo, sú správy zvyčajne čalúnené s náhodnými bity

284
00:17:36,000 --> 00:17:39,000
pred zašifrovaný tak, že rovnaká správa zašifrované

285
00:17:39,000 --> 00:17:44,000
viackrát bude vyzerať inak, ak polstrovanie na správy sa líšia.

286
00:17:44,000 --> 00:17:47,000
Ale nezabudnite, ako máme rozdeliť správ na kúsky

287
00:17:47,000 --> 00:17:50,000
tak, že každý blok je menšie ako n?

288
00:17:50,000 --> 00:17:52,000
Čalúnenie na kusy znamená, že možno budeme musieť rozdeliť veci do

289
00:17:52,000 --> 00:17:57,000
do ešte väčšie kúsky od polstrovaný bloku musí byť menší ako n.

290
00:17:57,000 --> 00:18:01,000
Šifrovanie a dešifrovanie sú pomerne drahé s RSA,

291
00:18:01,000 --> 00:18:05,000
a tak museli rozbiť správu do mnohých kúsky môže byť veľmi nákladné.

292
00:18:05,000 --> 00:18:09,000
Ak veľký objem dát musí byť šifrované a dešifrované

293
00:18:09,000 --> 00:18:12,000
môžeme spojiť výhody symetrická kľúčové algoritmy

294
00:18:12,000 --> 00:18:16,000
s tými RSA dostať aj bezpečnosť a efektivitu.

295
00:18:16,000 --> 00:18:18,000
Aj keď nepôjdeme do toho tu,

296
00:18:18,000 --> 00:18:23,000
AES je symetrický algoritmus kľúča ako Vigenère a Caesar šifry

297
00:18:23,000 --> 00:18:25,000
ale oveľa ťažšie prasknúť.

298
00:18:25,000 --> 00:18:30,000
Samozrejme, nemôžeme použiť AES bez stanovenia zdieľaného tajného kľúča

299
00:18:30,000 --> 00:18:34,000
medzi 2 systémy, a my sme videli problém s tým predtým.

300
00:18:34,000 --> 00:18:40,000
Ale teraz môžeme použiť RSA založiť zdieľaného tajného kľúča medzi 2 systémy.

301
00:18:40,000 --> 00:18:43,000
Zavoláme počítač odosielanie dát odosielateľa

302
00:18:43,000 --> 00:18:46,000
a počítač prijímajúci údaje prijímača.

303
00:18:46,000 --> 00:18:49,000
Prijímač má pár RSA kľúčov a odošle

304
00:18:49,000 --> 00:18:51,000
verejný kľúč odosielateľa.

305
00:18:51,000 --> 00:18:54,000
Odosielateľ generuje kľúč AES,

306
00:18:54,000 --> 00:18:57,000
zašifruje s prijímačom RSA verejného kľúča,

307
00:18:57,000 --> 00:19:00,000
a odošle kľúč AES k prijímaču.

308
00:19:00,000 --> 00:19:04,000
Prijímač dešifruje správu s RSA privátnym kľúčom.

309
00:19:04,000 --> 00:19:09,000
Odosielateľ aj príjemca majú teraz spoločný kľúča AES medzi nimi.

310
00:19:09,000 --> 00:19:14,000
AES, čo je oveľa rýchlejší pri šifrovanie a dešifrovanie, ako RSA,

311
00:19:14,000 --> 00:19:18,000
možno teraz použiť pre šifrovanie veľkých objemov dát a poslať ich do prijímača,

312
00:19:18,000 --> 00:19:21,000
kto môže dešifrovať pomocou rovnakého kľúča.

313
00:19:21,000 --> 00:19:26,000
AES, čo je oveľa rýchlejší pri šifrovanie a dešifrovanie, ako RSA,

314
00:19:26,000 --> 00:19:30,000
možno teraz použiť pre šifrovanie veľkých objemov dát a poslať ich do prijímača,

315
00:19:30,000 --> 00:19:32,000
kto môže dešifrovať pomocou rovnakého kľúča.

316
00:19:32,000 --> 00:19:36,000
Sme len potrebovali RSA preniesť zdieľaný kľúč.

317
00:19:36,000 --> 00:19:40,000
Už nepotrebujeme používať RSA vôbec.

318
00:19:40,000 --> 00:19:46,000
Vyzerá to, že som dostal správu.

319
00:19:46,000 --> 00:19:49,000
Nezáleží na tom, či niekto prečítať, čo je na papierové lietadlo predtým, než som ho chytil

320
00:19:49,000 --> 00:19:55,000
pretože som jediný, kto má súkromný kľúč.

321
00:19:55,000 --> 00:19:57,000
Poďme dešifrovať každý z blokov v správe.

322
00:19:57,000 --> 00:20:07,000
Prvý blok, 658, sme zvýšiť na d sile, ktorá je 185,

323
00:20:07,000 --> 00:20:18,000
mod n, ktoré je 989, je rovná 67,

324
00:20:18,000 --> 00:20:24,000
ktorý je písmeno C v ASCII.

325
00:20:24,000 --> 00:20:31,000
Teraz, na druhej bloku.

326
00:20:31,000 --> 00:20:35,000
Druhý blok má hodnotu 15,

327
00:20:35,000 --> 00:20:41,000
ktoré sme zvýšiť na 185. moci,

328
00:20:41,000 --> 00:20:51,000
mod 989, a to sa rovná 83

329
00:20:51,000 --> 00:20:57,000
ktorý je písmeno S v ASCII.

330
00:20:57,000 --> 00:21:06,000
Teraz za tretie bloku, ktorý má hodnotu 799, zvýšime na 185,

331
00:21:06,000 --> 00:21:17,000
mod 989, a to sa rovná 53,

332
00:21:17,000 --> 00:21:24,000
čo je hodnota znaku 5 v ASCII.

333
00:21:24,000 --> 00:21:30,000
Teraz pre posledný kus, ktorý má hodnotu 975,

334
00:21:30,000 --> 00:21:41,000
chováme na 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
a to sa rovná 48, čo je hodnota znaku 0 v ASCII.

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

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

338
00:22:06,000 --> 00:22:08,000
RSA vôbec.

339
00:22:08,000 --> 00:22:14,000
RSA vôbec. [Smiech]

340
00:22:14,000 --> 00:22:17,000
Na všetkých.