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
Pojďme se podívat na RSA, široce používaný algoritmus pro šifrování dat.

5
00:00:11,000 --> 00:00:16,000
Šifrovací algoritmy jako Caesar a Vigenère kódy nejsou příliš bezpečné.

6
00:00:16,000 --> 00:00:20,000
S Caesara, útočník potřebuje pouze vyzkoušet 25 různých klíčů

7
00:00:20,000 --> 00:00:22,000
dostat zprávu na prostý text.

8
00:00:22,000 --> 00:00:25,000
Zatímco Vigenère kód je bezpečnější než Caesara

9
00:00:25,000 --> 00:00:28,000
vzhledem k větší hledání prostor pro klíče, jednou útočník

10
00:00:28,000 --> 00:00:30,000
ví, délku klíče v Vigenère kód,

11
00:00:30,000 --> 00:00:34,000
, které mohou být stanovena prostřednictvím analýzy vzorků v šifrovaných textu,

12
00:00:34,000 --> 00:00:38,000
Vigenère kód není to, že mnohem bezpečnější než Caesara.

13
00:00:38,000 --> 00:00:42,000
RSA, na druhé straně, není náchylné k útokům, jako je tento.

14
00:00:42,000 --> 00:00:45,000
Caesarova šifra a Vigenère kód používat stejný klíč

15
00:00:45,000 --> 00:00:47,000
jak šifrovat a dešifrovat zprávy.

16
00:00:47,000 --> 00:00:51,000
Tato vlastnost dělá Tyto šifry symetrické klíčových algoritmů.

17
00:00:51,000 --> 00:00:54,000
Základním problémem symmetric klíčové algoritmy

18
00:00:54,000 --> 00:00:57,000
je to, že oni se spoléhají na jedné straně a šifrování a odeslání zprávy

19
00:00:57,000 --> 00:00:59,000
a jeden přijímající a dešifrování zprávy

20
00:00:59,000 --> 00:01:03,000
se již dohodli předem na klíč budou oba používat.

21
00:01:03,000 --> 00:01:06,000
Ale máme trochu problém při spuštění zde.

22
00:01:06,000 --> 00:01:10,000
Jak 2 počítače, které chtějí komunikovat vytvořit tajný klíč mezi nimi?

23
00:01:10,000 --> 00:01:16,000
Pokud klíč musí být tajná, pak potřebujeme způsob, jak šifrovat a dešifrovat klíč.

24
00:01:16,000 --> 00:01:18,000
Pokud vše, co máme, je symetrický klíč kryptografie

25
00:01:18,000 --> 00:01:21,000
pak jsme právě přišli zpět do stejného problému.

26
00:01:21,000 --> 00:01:25,000
RSA, na druhé straně, používá dvojice klíčů,

27
00:01:25,000 --> 00:01:28,000
jeden pro šifrování a jiný pro dešifrování.

28
00:01:28,000 --> 00:01:32,000
Jedním z nich je tzv. veřejný klíč, a druhý je soukromý klíč.

29
00:01:32,000 --> 00:01:34,000
Veřejný klíč je použit k zašifrování zprávy.

30
00:01:34,000 --> 00:01:38,000
Jak asi tušíte podle názvu, můžeme podělit o naše veřejný klíč s

31
00:01:38,000 --> 00:01:43,000
někdo chceme, aniž by byla ohrožena bezpečnost šifrované zprávě.

32
00:01:43,000 --> 00:01:45,000
Zprávy šifrována pomocí veřejného klíče

33
00:01:45,000 --> 00:01:49,000
lze dešifrovat pouze s odpovídajícím privátním klíčem.

34
00:01:49,000 --> 00:01:53,000
I když můžete sdílet váš veřejný klíč, měli byste mít svůj soukromý klíč v tajnosti.

61
00:01:55,000 --> 00:01:58,000
a to pouze soukromý klíč může být použit k dešifrování zpráv

62
00:01:58,000 --> 00:02:02,000
pokud 2 uživatelé chtějí poslat zprávy šifrované pomocí RSA

63
00:02:02,000 --> 00:02:07,000
tam a zpět oba uživatelé musí mít svou vlastní veřejné a soukromé klíče.

64
00:02:07,000 --> 00:02:10,000
Zprávy od uživatele 1 až 2 uživateli

65
00:02:10,000 --> 00:02:15,000
používat pouze uživatelské 2 klíčovou pár, a zprávy od uživatele 2 k uživateli 1

66
00:02:15,000 --> 00:02:17,000
používat pouze uživatelské 1 klíčovou dvojici.

67
00:02:17,000 --> 00:02:21,000
Skutečnost, že jsou 2 samostatné klíče k šifrování a dešifrování zpráv

68
00:02:21,000 --> 00:02:24,000
dělá RSA asymetrický klíčový algoritmus.

69
00:02:24,000 --> 00:02:28,000
Nepotřebujeme k zašifrování veřejný klíč, aby se odeslat ji do jiného počítače

70
00:02:28,000 --> 00:02:31,000
, protože klíč je veřejný stejně.

71
00:02:31,000 --> 00:02:33,000
To znamená, že RSA nemá stejný spouštěcí problém

72
00:02:33,000 --> 00:02:36,000
jako symmetric klíčové algoritmy.

73
00:02:36,000 --> 00:02:39,000
Takže když chci odeslat zprávu pomocí RSA šifrování

74
00:02:39,000 --> 00:02:42,000
Robymu, budu muset nejprve Rob veřejný klíč.

75
00:02:42,000 --> 00:02:47,000
Chcete-li generovat dvojici klíčů, Rob musí vybrat 2 velká prvočísla.

76
00:02:47,000 --> 00:02:50,000
Tato čísla budou použita v obou veřejných a soukromých klíčů,

77
00:02:50,000 --> 00:02:54,000
ale veřejný klíč bude používat pouze produkt těchto 2 čísel,

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

79
00:02:56,000 --> 00:02:59,000
Poté, co jsem šifrována zprávu pomocí Rob veřejný klíč

80
00:02:59,000 --> 00:03:01,000
Mohu poslat zprávu Rob.

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

82
00:03:05,000 --> 00:03:09,000
Veřejný klíč, pamatujte, používal produkt 2 prvočísel.

83
00:03:09,000 --> 00:03:12,000
Tento výrobek pak musí mít pouze 2 faktory,

84
00:03:12,000 --> 00:03:16,000
které se dějí, že jsou čísla, která tvoří soukromý klíč.

85
00:03:16,000 --> 00:03:20,000
Aby bylo možné dešifrovat zprávy, bude RSA použijte tento soukromý klíč

86
00:03:20,000 --> 00:03:25,000
nebo čísla násobí společně v procesu vytváření veřejného klíče.

87
00:03:25,000 --> 00:03:28,000
Vzhledem k tomu, že je výpočetně těžké faktoru se počet

88
00:03:28,000 --> 00:03:32,000
používá ve veřejném klíči do 2 čísla používaných v privátním klíčem

89
00:03:32,000 --> 00:03:36,000
je to těžké pro útočníkovi zjistit soukromého klíče

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

91
00:03:39,000 --> 00:03:43,000
Teď pojďme do některých nižších úrovní detailů RSA.

92
00:03:43,000 --> 00:03:46,000
Podívejme se nejprve, jak můžeme vytvořit dvojici klíčů.

93
00:03:46,000 --> 00:03:49,000
Za prvé, budeme potřebovat 2 prvočísla.

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

95
00:03:52,000 --> 00:03:56,000
Při výběru p a q, v praxi bychom pseudorandomly vytvářet

96
00:03:56,000 --> 00:03:59,000
velké množství a pak použít test pro určení, zda

97
00:03:59,000 --> 00:04:02,000
tato čísla jsou pravděpodobně připravit.

98
00:04:02,000 --> 00:04:05,000
Můžeme si ponechat generování náhodných čísel znovu a znovu

99
00:04:05,000 --> 00:04:08,000
až budeme mít 2 prvočísla, které můžeme použít.

100
00:04:08,000 --> 00:04:15,000
Zde pojďme vybrat p = 23 a q = 43.

101
00:04:15,000 --> 00:04:19,000
Pamatujte si, že v praxi by p a q být mnohem větší čísla.

102
00:04:19,000 --> 00:04:22,000
Pokud je nám známo, že čím větší čísla, tím je těžší

103
00:04:22,000 --> 00:04:25,000
bezva zašifrovanou zprávu.

104
00:04:25,000 --> 00:04:29,000
Ale je to také dražší pro šifrování a dešifrování zpráv.

105
00:04:29,000 --> 00:04:33,000
Dnes se často doporučuje, aby p a q jsou alespoň 1024 bitů,

106
00:04:33,000 --> 00:04:37,000
která staví na každé číslo na více než 300 desetinných míst.

107
00:04:37,000 --> 00:04:40,000
Ale budeme vybírat tyto malé čísla pro tento příklad.

108
00:04:40,000 --> 00:04:43,000
Teď budeme násobit p a q společně získat třetí číslo,

109
00:04:43,000 --> 00:04:45,000
které budeme nazývat n.

110
00:04:45,000 --> 00:04:55,000
V našem případě, n = 23 * 43, který = 989.

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

112
00:04:58,000 --> 00:05:02,000
Další budeme násobit p - 1 s q - 1

113
00:05:02,000 --> 00:05:05,000
získat čtvrté číslo, které budeme nazývat m.

114
00:05:05,000 --> 00:05:15,000
V našem případě, m = 22 * ​​42, který = 924.

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

116
00:05:18,000 --> 00:05:22,000
Teď budeme potřebovat číslo e, která je nesoudělná m

117
00:05:22,000 --> 00:05:25,000
a méně než m..

118
00:05:25,000 --> 00:05:28,000
Dvě čísla jsou nesoudělná, nebo coprime

119
00:05:28,000 --> 00:05:33,000
pokud jen pozitivní celé číslo, které dělí obě rovnoměrně je 1.

120
00:05:33,000 --> 00:05:37,000
Jinými slovy, největší společný dělitel E a M

121
00:05:37,000 --> 00:05:39,000
musí být 1.

122
00:05:39,000 --> 00:05:44,000
V praxi, to je společné pro e být prvočíslo 65537

123
00:05:44,000 --> 00:05:48,000
tak dlouho, jak je toto číslo se nestane být faktor m..

124
00:05:48,000 --> 00:05:53,000
Pro naše klíče, budeme vybírat e = 5

125
00:05:53,000 --> 00:05:57,000
od 5 je nesoudělná 924.

126
00:05:57,000 --> 00:06:01,000
Nakonec, budeme potřebovat jeden větší počet, který budeme nazývat d.

127
00:06:01,000 --> 00:06:11,000
D musí být nějaká hodnota, která splňuje rovnici de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
To m mod znamená budeme používat něco, co nazývá modulární aritmetika.

129
00:06:17,000 --> 00:06:21,000
V modulární aritmetice, jednou číslo dostane vyšší než některé horní mez

130
00:06:21,000 --> 00:06:24,000
to se zalomí zpět k 0.

131
00:06:24,000 --> 00:06:27,000
Hodiny, například, používá modulární aritmetiku.

132
00:06:27,000 --> 00:06:31,000
Minutu po 01:59, například, je 2:00,

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

134
00:06:33,000 --> 00:06:36,000
Minutová ručička se omotal kolem 0

135
00:06:36,000 --> 00:06:39,000
po dosažení horní hranice 60.

136
00:06:39,000 --> 00:06:46,000
Takže můžeme říci, 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 veřejné klíč bude dvojice e a n

139
00:07:02,000 --> 00:07:09,000
kde v tomto případě je e 5 a n je 989.

140
00:07:09,000 --> 00:07:15,000
Naše vlastní klíč bude dvojice d a n,

141
00:07:15,000 --> 00:07:22,000
která je v našem případě 185 a 989.

142
00:07:22,000 --> 00:07:25,000
Všimněte si, že náš původní prvočísla p a q se nezobrazí

143
00:07:25,000 --> 00:07:29,000
kdekoli v našich soukromých nebo veřejných klíčů.

144
00:07:29,000 --> 00:07:33,000
Nyní, když máme pár klíčů, pojďme se podívat na to, jak můžeme zašifrovat

145
00:07:33,000 --> 00:07:36,000
a dešifrovat zprávy.

146
00:07:36,000 --> 00:07:38,000
Chci poslat zprávu Rob,

147
00:07:38,000 --> 00:07:42,000
tak on bude tím, kdo k vygenerování této dvojice klíčů.

148
00:07:42,000 --> 00:07:46,000
Zeptám se Rob jeho veřejného klíče, který budu používat

149
00:07:46,000 --> 00:07:48,000
k zašifrování zprávy poslat k němu.

150
00:07:48,000 --> 00:07:53,000
Pamatujte si, že je to naprosto v pořádku Rob sdílet jeho veřejný klíč se mnou.

151
00:07:53,000 --> 00:07:56,000
Ale to by nebylo v pořádku sdílet svůj soukromý klíč.

152
00:07:56,000 --> 00:08:00,000
Nemám ponětí, co jeho soukromý klíč je.

153
00:08:00,000 --> 00:08:03,000
Můžeme porušit zprávu m do několika kousky

154
00:08:03,000 --> 00:08:07,000
všechny menší než n a potom zašifrovat každý z těchto bloků.

155
00:08:07,000 --> 00:08:12,000
Budeme-li zašifrovat řetězec CS50, které můžeme rozdělit 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 účelem šifrování můj vzkaz, budu muset převést do

158
00:08:17,000 --> 00:08:20,000
nějaký druh numerické reprezentace.

159
00:08:20,000 --> 00:08:25,000
Pojďme zřetězit hodnoty ASCII s postavami v mé zprávě.

160
00:08:25,000 --> 00:08:28,000
Aby bylo možné šifrování danou zprávu m

161
00:08:28,000 --> 00:08:37,000
Budu se muset počítat c = m na e (mod n).

162
00:08:37,000 --> 00:08:40,000
Ale m musí být menší než n,

163
00:08:40,000 --> 00:08:45,000
jinak celá zpráva nemůže být vyjádřena modulo n.

164
00:08:45,000 --> 00:08:49,000
Můžeme rozdělit m až do několika bloků, z nichž všechny jsou menší než n,

165
00:08:49,000 --> 00:08:52,000
a šifrovat každý z těchto bloků.

166
00:08:52,000 --> 00:09:03,000
Šifrování každý z těchto bloků, dostaneme c1 = 67 k 5 (mod 989)

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

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

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

170
00:09:18,000 --> 00:09:26,000
Pro našeho třetího bloku máme 53 na 5 (mod 989)

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

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

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

174
00:09:43,000 --> 00:09:48,000
Nyní můžeme poslat přes tyto šifrované hodnoty Rob.

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

176
00:09:58,000 --> 00:10:01,000
Zatímco naše poselství je v letu, pojďme se ještě jednou podívat

177
00:10:01,000 --> 00:10:07,000
na to, jak jsme se dostali, že hodnotu d.

178
00:10:07,000 --> 00:10:17,000
Naše číslo d potřebné k uspokojení 5d = 1 (mod 924).

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

180
00:10:24,000 --> 00:10:28,000
Vzhledem k tomu, 2 celá čísla a, b, rozšířená Euclidean algoritmus

181
00:10:28,000 --> 00:10:33,000
může být použit k nalezení největšího společného dělitele těchto 2 čísel.

182
00:10:33,000 --> 00:10:37,000
To bude také dát nám další 2 čísla, x a y,

183
00:10:37,000 --> 00:10:47,000
které splňují rovnici ax + by = největší společný dělitel a a b.

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

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

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

187
00:10:56,000 --> 00:10:59,000
již víme, že tato čísla jsou coprime.

188
00:10:59,000 --> 00:11:03,000
Jejich největší společný dělitel je 1.

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

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

191
00:11:17,000 --> 00:11:22,000
Ale pokud nás však zajímá pouze o všem modulo 924

192
00:11:22,000 --> 00:11:25,000
pak můžeme přetáhnout - 924y.

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

194
00:11:27,000 --> 00:11:31,000
Pokud minutová ručička je na 1 a pak přesně 10 hodin projít,

195
00:11:31,000 --> 00:11:35,000
víme, že minutová ručička bude stále na 1.

196
00:11:35,000 --> 00:11:39,000
Zde začínáme na 1 a pak zabalit kolem přesně 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 tady to x je stejný jako v d jsme hledali dříve,

200
00:11:55,000 --> 00:11:58,000
takže pokud budeme používat rozšířené Euclidean algoritmus

201
00:11:58,000 --> 00:12:04,000
a stáhni číslo x, že je to číslo bychom měli používat jako náš d..

202
00:12:04,000 --> 00:12:07,000
Nyní pojďme spustit rozšířený euklidovský algoritmus pro = 5

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

204
00:12:11,000 --> 00:12:14,000
Použijeme metodu nazvanou tabulka metoda.

205
00:12:14,000 --> 00:12:21,000
Naše tabulka bude mít 4 sloupce, x, y, d, a k.

206
00:12:21,000 --> 00:12:23,000
Náš stůl začíná s 2 řádky.

207
00:12:23,000 --> 00:12:28,000
V první řadě máme 1, 0, pak se naše hodnota, která je 5,

208
00:12:28,000 --> 00:12:37,000
a naše druhá řada je 0, 1, a naše hodnota pro B, který je 924.

209
00:12:37,000 --> 00:12:40,000
Hodnota 4. sloupce, k, bude výsledek

210
00:12:40,000 --> 00:12:45,000
dělení hodnotu d na řádku nad ním s hodnotou d

211
00:12:45,000 --> 00:12:49,000
na stejném řádku.

212
00:12:49,000 --> 00:12:56,000
Máme 5 děleno 924 je 0 s nějakým zbytkem.

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
Nyní se hodnota každého jiného buňky bude hodnota z buněk 2 řadách nad ní

215
00:13:05,000 --> 00:13:09,000
minus hodnota na řádku nad ním časy k..

216
00:13:09,000 --> 00:13:11,000
Pojďme začít s d v 3. řadě.

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

218
00:13:19,000 --> 00:13:25,000
Pak máme 0-1 * 0, což je 0

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

220
00:13:30,000 --> 00:13:33,000
Není to tak zlé, takže se pojďme přesunout na další řádek.

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

222
00:13:36,000 --> 00:13:43,000
924 děleno 5 = 184 s nějakým zbytkem,

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

224
00:13:46,000 --> 00:13:54,000
Nyní 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
Dobře, pojďme udělat další řádek.

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

228
00:14:10,000 --> 00:14:15,000
5 děleno 4 = 1 s nějakým zbytkem.

229
00:14:15,000 --> 00:14:17,000
Pojďme vyplnit v ostatních sloupcích.

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
Podívejme se, co naše další hodnota součinitele bude.

234
00:14:35,000 --> 00:14:40,000
No, vypadá to, že máme 4 děleno 1, což je 4.

235
00:14:40,000 --> 00:14:43,000
V tomto případě, kdy jsme vydělením 1 tak, že k je rovna

236
00:14:43,000 --> 00:14:50,000
hodnota d ve výše uvedeném řádku znamená, že skončíme s naším algoritmem.

237
00:14:50,000 --> 00:14:58,000
Můžeme vidět, že máme x = 185, y = -1 v posledním řádku.

238
00:14:58,000 --> 00:15:00,000
Pojďme se nyní vrátit k našemu původnímu cíli.

239
00:15:00,000 --> 00:15:04,000
Řekli jsme, že hodnota x v důsledku provozu tohoto algoritmu

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

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

242
00:15:15,000 --> 00:15:20,000
, což znamená, že se mají hodnotu 185 pro d.

243
00:15:20,000 --> 00:15:23,000
Skutečnost, že d = 1 v posledním řádku

244
00:15:23,000 --> 00:15:26,000
ověří, že e byla coprime k m..

245
00:15:26,000 --> 00:15:30,000
Pokud by tomu tak nebylo 1, pak budeme muset vybrat nového e.

246
00:15:30,000 --> 00:15:33,000
Nyní se podíváme, jestli Rob získal mou zprávu.

247
00:15:33,000 --> 00:15:35,000
Když mi někdo pošle šifrovanou zprávu

248
00:15:35,000 --> 00:15:38,000
tak dlouho, jak jsem držel jsem soukromý klíč v tajnosti

249
00:15:38,000 --> 00:15:41,000
Jsem jediný, kdo může dešifrovat zprávu.

250
00:15:41,000 --> 00:15:46,000
Chcete-li dešifrovat kus c mohu vypočítat původní zprávu

251
00:15:46,000 --> 00:15:53,000
je rovna bloku až d moci (mod n).

252
00:15:53,000 --> 00:15:57,000
Pamatujte si, že d a n jsou z mého soukromého klíče.

253
00:15:57,000 --> 00:16:01,000
Chcete-li získat kompletní zprávu z jeho kousky jsme dešifrovat každý blok

254
00:16:01,000 --> 00:16:04,000
a zřetězit výsledky.

255
00:16:04,000 --> 00:16:08,000
Přesně tak, jak bezpečný je RSA?

256
00:16:08,000 --> 00:16:10,000
Pravdou je, že nevíme.

257
00:16:10,000 --> 00:16:14,000
Bezpečnost je založena na tom, jak dlouho to bude trvat, aby útočník bezva zprávu

258
00:16:14,000 --> 00:16:16,000
šifrován pomocí RSA.

259
00:16:16,000 --> 00:16:19,000
Pamatujte si, že útočník má přístup k vašemu veřejný klíč,

260
00:16:19,000 --> 00:16:21,000
který obsahuje jak e a n.

261
00:16:21,000 --> 00:16:26,000
Pokud útočník dokáže faktor N do svých 2 připraví, p a q,

262
00:16:26,000 --> 00:16:30,000
pak by mohla vypočítat d pomocí rozšířeného Euclidean algoritmus.

263
00:16:30,000 --> 00:16:35,000
To jí dává soukromý klíč, který může být použit k dešifrování žádné zprávy.

264
00:16:35,000 --> 00:16:38,000
Ale jak rychle můžeme vytknout celá čísla?

265
00:16:38,000 --> 00:16:41,000
Opět, nevíme.

266
00:16:41,000 --> 00:16:43,000
Nikdo našel rychlý způsob, jak to udělat,

267
00:16:43,000 --> 00:16:46,000
To znamená, že vzhledem k dostatečně velká n

268
00:16:46,000 --> 00:16:49,000
to by se útočníkovi nereálně dlouho

269
00:16:49,000 --> 00:16:51,000
započítávat číslo.

270
00:16:51,000 --> 00:16:54,000
Pokud někdo odhalil rychlý způsob factoringových celých čísel

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

272
00:16:57,000 --> 00:17:01,000
Ale i když faktorizace celého čísla je ve své podstatě pomalé

273
00:17:01,000 --> 00:17:04,000
RSA algoritmus mohl ještě mít nějakou vadu v tom

274
00:17:04,000 --> 00:17:07,000
, která umožňuje snadné dešifrování zpráv.

275
00:17:07,000 --> 00:17:10,000
Nikdo našel a odhalil tak chybu ještě,

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 mohl někdo být venku čtení všech dat zašifrovány pomocí RSA.

278
00:17:17,000 --> 00:17:19,000
Je tu další kousek o ochraně osobních vydání.

279
00:17:19,000 --> 00:17:23,000
Pokud Tommy zašifruje nějakou zprávu pomocí veřejného klíče svůj

280
00:17:23,000 --> 00:17:26,000
a útočník zašifruje stejný zprávu pomocí veřejného klíče svůj

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

282
00:17:29,000 --> 00:17:32,000
a tak vím, co Tommy šifrovány.

283
00:17:32,000 --> 00:17:36,000
Aby se tomu zabránilo, jsou zprávy obvykle čalouněny s náhodnými bity

284
00:17:36,000 --> 00:17:39,000
před zašifrován tak, že stejná zpráva zašifrována

285
00:17:39,000 --> 00:17:44,000
vícekrát bude vypadat jinak, pokud polstrování na zprávy se liší.

286
00:17:44,000 --> 00:17:47,000
Ale nezapomeňte, jak máme rozdělit zpráv na kousky

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

288
00:17:50,000 --> 00:17:52,000
Čalounění na kusy znamená, že možná budeme muset rozdělit věci do

289
00:17:52,000 --> 00:17:57,000
do ještě větší kousky od polstrovaný bloku musí být menší než n..

290
00:17:57,000 --> 00:18:01,000
Šifrování a dešifrování jsou poměrně drahé s RSA,

291
00:18:01,000 --> 00:18:05,000
a tak museli rozbít zprávu do mnoha kousky může být velmi nákladné.

292
00:18:05,000 --> 00:18:09,000
Pokud velký objem dat musí být šifrována a dešifrována

293
00:18:09,000 --> 00:18:12,000
můžeme spojit výhody symmetric klíčové algoritmy

294
00:18:12,000 --> 00:18:16,000
s těmi RSA dostat i bezpečnost a efektivitu.

295
00:18:16,000 --> 00:18:18,000
I když nepůjdeme do toho tady,

296
00:18:18,000 --> 00:18:23,000
AES je symetrický algoritmus klíče jako Vigenère a Caesar šifry

297
00:18:23,000 --> 00:18:25,000
ale mnohem těžší prasknout.

298
00:18:25,000 --> 00:18:30,000
Samozřejmě, nemůžeme použít AES bez stanovení sdíleného tajného klíče

299
00:18:30,000 --> 00:18:34,000
mezi 2 systémy, a my jsme viděli problém s tím předtím.

300
00:18:34,000 --> 00:18:40,000
Ale teď můžeme použít RSA založit sdíleného tajného klíče mezi 2 systémy.

301
00:18:40,000 --> 00:18:43,000
Zavoláme počítač odesílání dat odesílatele

302
00:18:43,000 --> 00:18:46,000
a počítač přijímající údaje přijímače.

303
00:18:46,000 --> 00:18:49,000
Přijímač má pár RSA klíčů a odešle

304
00:18:49,000 --> 00:18:51,000
veřejný klíč odesílatele.

305
00:18:51,000 --> 00:18:54,000
Odesílatel generuje klíč AES,

306
00:18:54,000 --> 00:18:57,000
zašifruje s přijímačem RSA veřejného klíče,

307
00:18:57,000 --> 00:19:00,000
a odešle klíč AES k přijímači.

308
00:19:00,000 --> 00:19:04,000
Přijímač dešifruje zprávu s RSA privátním klíčem.

309
00:19:04,000 --> 00:19:09,000
Odesílatel i příjemce mají nyní společný klíče AES mezi nimi.

310
00:19:09,000 --> 00:19:14,000
AES, což je mnohem rychlejší při šifrování a dešifrování, než RSA,

311
00:19:14,000 --> 00:19:18,000
lze nyní použít pro šifrování velkých objemů dat a poslat je do přijímače,

312
00:19:18,000 --> 00:19:21,000
kdo může dešifrovat pomocí stejného klíče.

313
00:19:21,000 --> 00:19:26,000
AES, což je mnohem rychlejší při šifrování a dešifrování, než RSA,

314
00:19:26,000 --> 00:19:30,000
lze nyní použít pro šifrování velkých objemů dat a poslat je do přijímače,

315
00:19:30,000 --> 00:19:32,000
kdo může dešifrovat pomocí stejného klíče.

316
00:19:32,000 --> 00:19:36,000
Jsme jen potřebovali RSA přenést sdílený klíč.

317
00:19:36,000 --> 00:19:40,000
Už nepotřebujeme používat RSA vůbec.

318
00:19:40,000 --> 00:19:46,000
Vypadá to, že jsem dostal zprávu.

319
00:19:46,000 --> 00:19:49,000
Nezáleží na tom, jestli někdo přečíst, co je na papírové letadlo předtím, než jsem ho chytil

320
00:19:49,000 --> 00:19:55,000
protože jsem jediný, kdo má soukromý klíč.

321
00:19:55,000 --> 00:19:57,000
Pojďme dešifrovat každý z bloků ve zprávě.

322
00:19:57,000 --> 00:20:07,000
První blok, 658, jsme zvýšit na d síle, která je 185,

323
00:20:07,000 --> 00:20:18,000
mod n, které je 989, je rovna 67,

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

325
00:20:24,000 --> 00:20:31,000
Nyní, na druhé bloku.

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

327
00:20:35,000 --> 00:20:41,000
které jsme zvýšit na 185. moci,

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

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

330
00:20:57,000 --> 00:21:06,000
Nyní za třetí bloku, který má hodnotu 799, zvýšíme na 185,

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

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

333
00:21:24,000 --> 00:21:30,000
Nyní pro poslední kus, který 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 se rovná 48, což je hodnota znaku 0 v ASCII.

336
00:21:51,000 --> 00:21:57,000
Mé jméno 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. [Smích]

340
00:22:14,000 --> 00:22:17,000
Na všech.