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 Universiteit]

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

4
00:00:07,000 --> 00:00:11,000
Kom ons neem 'n blik op die RSA, 'n wyd gebruik word algoritme vir die versleutelen van data.

5
00:00:11,000 --> 00:00:16,000
Enkripsie-algoritmes soos Caesar en Vigenère getalle is nie baie veilig is.

6
00:00:16,000 --> 00:00:20,000
Met die keiser cipher, 'n aanvaller moet slegs 25 verskillende sleutels om te probeer

7
00:00:20,000 --> 00:00:22,000
die boodskap se gewone teks te kry.

8
00:00:22,000 --> 00:00:25,000
Terwyl die Vigenère cipher is meer veilig as die keiser cipher

9
00:00:25,000 --> 00:00:28,000
as gevolg van die groter search ruimte vir sleutels, een keer 'n aanvaller

10
00:00:28,000 --> 00:00:30,000
ken die lengte van die sleutel in 'n Vigenère cipher,

11
00:00:30,000 --> 00:00:34,000
wat bepaal kan word deur middel van 'n analise van patrone in die geïnkripteer teks,

12
00:00:34,000 --> 00:00:38,000
die Vigenère cipher is nie veel meer veilig as die keiser cipher.

13
00:00:38,000 --> 00:00:42,000
RSA, aan die ander kant, is nie kwesbaar vir aanvalle soos hierdie.

14
00:00:42,000 --> 00:00:45,000
Die keiser cipher en Vigenère cipher gebruik dieselfde sleutel

15
00:00:45,000 --> 00:00:47,000
aan beide enkripteer en dekripteer 'n boodskap.

16
00:00:47,000 --> 00:00:51,000
Hierdie eienskap maak die getalle simmetriese sleutel algoritmes.

17
00:00:51,000 --> 00:00:54,000
'N fundamentele probleem met simmetriese sleutel algoritmes

18
00:00:54,000 --> 00:00:57,000
is dat hulle staatmaak op die een versleuteling en die stuur van die boodskap

19
00:00:57,000 --> 00:00:59,000
en die een wat die boodskap ontvang en decrypten

20
00:00:59,000 --> 00:01:03,000
reeds ooreengekom vooraf op die sleutel sal hulle albei gebruik.

21
00:01:03,000 --> 00:01:06,000
Maar ons het 'n bietjie van 'n opstart probleem hier.

22
00:01:06,000 --> 00:01:10,000
Hoe vestig 2 rekenaars wat wil om te kommunikeer nie 'n geheime sleutel tussen hulle?

23
00:01:10,000 --> 00:01:16,000
As die sleutel geheim moet wees, dan moet ons 'n manier om te enkripteer en dekripteer die sleutel.

24
00:01:16,000 --> 00:01:18,000
As alles wat ons het is 'n simmetriese sleutel kriptografie

25
00:01:18,000 --> 00:01:21,000
dan het ons kom nou net terug na dieselfde probleem.

26
00:01:21,000 --> 00:01:25,000
RSA, aan die ander kant, maak gebruik van 'n paar van die sleutels,

27
00:01:25,000 --> 00:01:28,000
een vir enkripsie en 'n ander vir dekripsie.

28
00:01:28,000 --> 00:01:32,000
Een daarvan is die openbare sleutel genoem, en die ander is die private sleutel.

29
00:01:32,000 --> 00:01:34,000
Die publieke sleutel word gebruik om boodskappe te enkripteer.

30
00:01:34,000 --> 00:01:38,000
As jy dalk raai deur sy naam, kan ons ons publieke sleutel deel met

31
00:01:38,000 --> 00:01:43,000
iemand wat ons wil sonder om die sekuriteit van 'n geïnkripteer boodskap.

32
00:01:43,000 --> 00:01:45,000
Boodskappe geïnkripteer met behulp van 'n publieke sleutel

33
00:01:45,000 --> 00:01:49,000
kan slegs Ontcijferde met sy ooreenstemmende private sleutel.

34
00:01:49,000 --> 00:01:53,000
Terwyl jy kan deel jou publieke sleutel, moet jy altyd jou private sleutel geheim hou.

61
00:01:55,000 --> 00:01:58,000
en slegs die private sleutel kan gebruik word om te decrypt boodskappe

62
00:01:58,000 --> 00:02:02,000
as 2 gebruikers wil boodskappe stuur geïnkripteer met RSA

63
00:02:02,000 --> 00:02:07,000
heen en weer beide gebruikers nodig het om hul eie openbare en private sleutel paar te hê.

64
00:02:07,000 --> 00:02:10,000
Boodskappe van gebruiker 1 na gebruiker 2

65
00:02:10,000 --> 00:02:15,000
gebruik slegs gebruiker 2 se sleutel paar, en boodskappe van gebruiker 2 na gebruiker 1

66
00:02:15,000 --> 00:02:17,000
gebruik slegs gebruiker 1 se sleutel paar.

67
00:02:17,000 --> 00:02:21,000
Die feit dat daar is 2 aparte sleutels te enkripteer en decrypt boodskappe

68
00:02:21,000 --> 00:02:24,000
maak RSA 'n asimmetriese sleutel algoritme.

69
00:02:24,000 --> 00:02:28,000
Ons hoef nie die publieke sleutel enkripteer ten einde dit te stuur na 'n ander rekenaar

70
00:02:28,000 --> 00:02:31,000
aangesien die sleutel is om die openbare elk geval.

71
00:02:31,000 --> 00:02:33,000
Dit beteken dat die RSA nie dieselfde opstart probleem

72
00:02:33,000 --> 00:02:36,000
as die simmetriese sleutel algoritmes.

73
00:02:36,000 --> 00:02:39,000
So as ek wil 'n boodskap te stuur met RSA-enkripsie

74
00:02:39,000 --> 00:02:42,000
te beroof, sal ek eers Rob se publieke sleutel.

75
00:02:42,000 --> 00:02:47,000
'N paar sleutels te genereer, Rob 2 groot priemgetalle te kies.

76
00:02:47,000 --> 00:02:50,000
Hierdie getalle sal gebruik word in beide die openbare en private sleutels,

77
00:02:50,000 --> 00:02:54,000
maar die publieke sleutel sal slegs gebruik die produk van dié 2 getalle,

78
00:02:54,000 --> 00:02:56,000
nie die getalle self.

79
00:02:56,000 --> 00:02:59,000
Sodra ek die boodskap het geïnkripteer met behulp van Rob se publieke sleutel

80
00:02:59,000 --> 00:03:01,000
Ek kan stuur die boodskap aan Rob.

81
00:03:01,000 --> 00:03:05,000
Vir 'n rekenaar, factoring nommers is 'n harde probleem.

82
00:03:05,000 --> 00:03:09,000
Die publieke sleutel, onthou, gebruik die produk van 2 priemgetalle.

83
00:03:09,000 --> 00:03:12,000
Hierdie produk moet dan net 2 faktore,

84
00:03:12,000 --> 00:03:16,000
wat gebeur met die getalle wat die private sleutel.

85
00:03:16,000 --> 00:03:20,000
Ten einde die boodskap dekripteer, sal die RSA gebruik om hierdie private sleutel

86
00:03:20,000 --> 00:03:25,000
of die getalle met mekaar vermenigvuldig word in die proses van die skep van die publieke sleutel.

87
00:03:25,000 --> 00:03:28,000
Want dit is computationeel moeilik om die nommer aan 'n faktorontleding

88
00:03:28,000 --> 00:03:32,000
wat gebruik word in 'n publieke sleutel in die 2 getalle wat gebruik word in die private sleutel

89
00:03:32,000 --> 00:03:36,000
dit is moeilik vir 'n aanvaller die private sleutel om uit te vind

90
00:03:36,000 --> 00:03:39,000
wat nodig sal wees om die boodskap te dekripteer.

91
00:03:39,000 --> 00:03:43,000
Nou, laat ons gaan in 'n laer vlak besonderhede van die RSA.

92
00:03:43,000 --> 00:03:46,000
Laat ons eers sien hoe ons kan 'n paar sleutels te genereer.

93
00:03:46,000 --> 00:03:49,000
Eerstens, moet ons 2 priemgetalle.

94
00:03:49,000 --> 00:03:52,000
Ons noem hierdie 2 getalle p en q.

95
00:03:52,000 --> 00:03:56,000
Ten einde op te tel P en Q, in die praktyk sou ons pseudorandomly genereer

96
00:03:56,000 --> 00:03:59,000
groot getalle en gebruik dan 'n toets om te bepaal of

97
00:03:59,000 --> 00:04:02,000
die getalle is waarskynlik prima.

98
00:04:02,000 --> 00:04:05,000
Ons kan aanhou om ewekansige getalle te genereer oor en oor weer

99
00:04:05,000 --> 00:04:08,000
totdat ons het 2 primes wat ons kan gebruik.

100
00:04:08,000 --> 00:04:15,000
Hier laat haal p = 23 en q = 43.

101
00:04:15,000 --> 00:04:19,000
Onthou, in die praktyk, behoort p en q veel groter getalle.

102
00:04:19,000 --> 00:04:22,000
Sover ons weet, hoe groter die nommers, hoe moeiliker is dit

103
00:04:22,000 --> 00:04:25,000
'n geïnkripteer boodskap te kraak.

104
00:04:25,000 --> 00:04:29,000
Maar dit is ook duurder om te Encrypt en decrypt boodskappe.

105
00:04:29,000 --> 00:04:33,000
Vandag is dit dikwels aanbeveel dat P en Q is ten minste 1024 stukkies,

106
00:04:33,000 --> 00:04:37,000
wat sit elke getal op meer as 300 desimale syfers.

107
00:04:37,000 --> 00:04:40,000
Maar ons sal hierdie klein getalle kies vir hierdie voorbeeld.

108
00:04:40,000 --> 00:04:43,000
Nou sal ons vermenigvuldig p en q saam 'n 3de nommer te kry,

109
00:04:43,000 --> 00:04:45,000
wat ons sal noem.

110
00:04:45,000 --> 00:04:55,000
In ons geval, n = 23 * 43, wat = 989.

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

112
00:04:58,000 --> 00:05:02,000
Volgende sal ons vermenigvuldig p - 1 met q - 1

113
00:05:02,000 --> 00:05:05,000
'n 4de nommer, wat ons noem m te verkry.

114
00:05:05,000 --> 00:05:15,000
In ons geval, m = 22 * ​​42, wat = 924.

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

116
00:05:18,000 --> 00:05:22,000
Nou sal ons moet 'n aantal e wat relatief priem is m

117
00:05:22,000 --> 00:05:25,000
en minder as m.

118
00:05:25,000 --> 00:05:28,000
Twee getalle relatief priem is of coprime

119
00:05:28,000 --> 00:05:33,000
as die enigste positiewe heelgetal wat gesplitste hulle albei eweredig is 1.

120
00:05:33,000 --> 00:05:37,000
Met ander woorde, die grootste gemene deler van e en m

121
00:05:37,000 --> 00:05:39,000
moet wees 1.

122
00:05:39,000 --> 00:05:44,000
In die praktyk, is dit algemeen vir e die priemgetal 65.537

123
00:05:44,000 --> 00:05:48,000
so lank as wat hierdie getal nie gebeur met 'n faktor van m.

124
00:05:48,000 --> 00:05:53,000
Vir ons sleutels, sal ons kies e = 5

125
00:05:53,000 --> 00:05:57,000
sedert 5 is relatief priem tot 924.

126
00:05:57,000 --> 00:06:01,000
Ten slotte, moet ons nog een nommer, wat ons noem d.

127
00:06:01,000 --> 00:06:11,000
D moet 'n waarde wat die vergelyking bevredig de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Hierdie mod m gee te kenne dat ons sal iets genoem modulêre rekenkunde gebruik.

129
00:06:17,000 --> 00:06:21,000
In modulêre rekenkunde, kry een keer 'n aantal hoër as sommige bogrens

130
00:06:21,000 --> 00:06:24,000
sal dit om terug te draai na 0.

131
00:06:24,000 --> 00:06:27,000
'N klok, byvoorbeeld, modulêre rekenkunde gebruik.

132
00:06:27,000 --> 00:06:31,000
Een minuut na 01:59, byvoorbeeld, is 02:00,

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

134
00:06:33,000 --> 00:06:36,000
Die minuut hand toegedraai rondom 0

135
00:06:36,000 --> 00:06:39,000
op die bereiking van 'n bogrens van 60.

136
00:06:39,000 --> 00:06:46,000
Dus, kan ons sê 60 is gelyk aan 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
en 125 is gelykstaande aan 65 is gelykstaande aan 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Ons publieke sleutel sal die paar e en n

139
00:07:02,000 --> 00:07:09,000
waar in hierdie geval e is 5 en n 989.

140
00:07:09,000 --> 00:07:15,000
Ons private sleutel sal wees om die paar D en N,

141
00:07:15,000 --> 00:07:22,000
wat in ons geval is 185 en 989.

142
00:07:22,000 --> 00:07:25,000
Let daarop dat ons oorspronklike primes p en q nie vertoon

143
00:07:25,000 --> 00:07:29,000
oral in ons privaat-of openbare sleutels.

144
00:07:29,000 --> 00:07:33,000
Nou dat ons ons paar sleutels, Kom ons neem 'n blik op hoe ons kan enkripteer

145
00:07:33,000 --> 00:07:36,000
en decrypt 'n boodskap.

146
00:07:36,000 --> 00:07:38,000
Ek wil 'n boodskap te stuur na Rob,

147
00:07:38,000 --> 00:07:42,000
sodat hy sal die een hierdie sleutel paar te genereer.

148
00:07:42,000 --> 00:07:46,000
Dan sal ek vra Rob vir sy publieke sleutel, wat ek sal gebruik

149
00:07:46,000 --> 00:07:48,000
'n boodskap te stuur aan hom te enkripteer.

150
00:07:48,000 --> 00:07:53,000
Onthou, dit is heeltemal goed vir Rob sy publieke sleutel met my te deel.

151
00:07:53,000 --> 00:07:56,000
Maar dit sou nie oukei wees sy private sleutel te deel.

152
00:07:56,000 --> 00:08:00,000
Ek het nie 'n idee wat sy private sleutel is.

153
00:08:00,000 --> 00:08:03,000
Ons kan ons boodskap m breek in verskeie stukke

154
00:08:03,000 --> 00:08:07,000
alle kleiner is as n en dan enkripteer elkeen van daardie stukke.

155
00:08:07,000 --> 00:08:12,000
Ons sal enkripteer die string CS50, wat ons kan breek in 4 stukke,

156
00:08:12,000 --> 00:08:14,000
een per brief.

157
00:08:14,000 --> 00:08:17,000
In om my boodskap te enkripteer, sal ek nodig het om dit te omskep in '

158
00:08:17,000 --> 00:08:20,000
'n soort van numeriese verteenwoordiging.

159
00:08:20,000 --> 00:08:25,000
Kom ons koppel die ASCII-waardes met die karakters in my boodskap.

160
00:08:25,000 --> 00:08:28,000
Ten einde 'n bepaalde boodskap m te enkripteer

161
00:08:28,000 --> 00:08:37,000
Ek sal c = m na die e (mod n) te bereken.

162
00:08:37,000 --> 00:08:40,000
Maar m moet kleiner wees as n,

163
00:08:40,000 --> 00:08:45,000
of anders sal die volle boodskap kan nie uitgedruk word modulo n.

164
00:08:45,000 --> 00:08:49,000
Ons kan breek m in verskeie stukke, wat almal kleiner is as n,

165
00:08:49,000 --> 00:08:52,000
en elkeen van daardie stukke enkripteer.

166
00:08:52,000 --> 00:09:03,000
Enkripteer van elk van hierdie stukke, kry ons c1 = 67 aan die 5 (mod 989)

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

168
00:09:06,000 --> 00:09:15,000
Vir ons tweede stuk het ons 83 tot die 5 (mod 989)

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

170
00:09:18,000 --> 00:09:26,000
Vir ons derde stuk het ons 53 tot die 5 (mod 989)

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

172
00:09:30,000 --> 00:09:39,000
En ten slotte, vir ons laaste stuk het ons 48 tot die 5 (mod 989)

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

174
00:09:43,000 --> 00:09:48,000
Nou het ons kan stuur oor hierdie geïnkripteer waardes na Rob.

175
00:09:54,000 --> 00:09:58,000
Hier gaan jy, Rob.

176
00:09:58,000 --> 00:10:01,000
Terwyl ons boodskap in vlug is, laat ons kyk weer na

177
00:10:01,000 --> 00:10:07,000
hoe ons het dat waarde vir d.

178
00:10:07,000 --> 00:10:17,000
Ons nommer d nodig 5d = 1 (mod 924) te voldoen.

179
00:10:17,000 --> 00:10:24,000
Dit maak d die multiplikatiewe inverse van 5 modulo 924.

180
00:10:24,000 --> 00:10:28,000
Gegewe 2 heelgetalle, a en b, die uitgebreide Euklidiese algoritme

181
00:10:28,000 --> 00:10:33,000
kan gebruik word om die grootste gemene deler van hierdie 2 heelgetalle te vind.

182
00:10:33,000 --> 00:10:37,000
Dit sal ook ons ​​2 ander getalle, x en y,

183
00:10:37,000 --> 00:10:47,000
wat voldoen aan die vergelyking ax + by = die grootste gemene deler van a en b.

184
00:10:47,000 --> 00:10:49,000
Hoe dit ons help?

185
00:10:49,000 --> 00:10:52,000
Wel, steek in e = 5 vir 'n

186
00:10:52,000 --> 00:10:56,000
en m = 924 vir b

187
00:10:56,000 --> 00:10:59,000
ons reeds weet dat hierdie getalle coprime is.

188
00:10:59,000 --> 00:11:03,000
Hul grootste gemene deler is 1.

189
00:11:03,000 --> 00:11:09,000
Dit gee ons 5x + 924y = 1

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

191
00:11:17,000 --> 00:11:22,000
Maar as ons net sorg oor alles modulo 924

192
00:11:22,000 --> 00:11:25,000
dan kan ons drop die 924y.

193
00:11:25,000 --> 00:11:27,000
Dink terug aan die klok.

194
00:11:27,000 --> 00:11:31,000
As die minuut hand is op 1 en dan presies 10 uur slaag,

195
00:11:31,000 --> 00:11:35,000
ons weet die minuut hand nog sal wees op die 1.

196
00:11:35,000 --> 00:11:39,000
Hier het ons begin op 1 en dan draai om presies y tye,

197
00:11:39,000 --> 00:11:41,000
so ons sal nog steeds by 1.

198
00:11:41,000 --> 00:11:49,000
Ons het 'n 5x = 1 (mod 924).

199
00:11:49,000 --> 00:11:55,000
En hier x is dieselfde as die d wat ons is op soek na voor,

200
00:11:55,000 --> 00:11:58,000
so as ons die uitgebreide Euklidiese algoritme

201
00:11:58,000 --> 00:12:04,000
hierdie getal x te kry, dit is die getal wat ons moet gebruik as ons d.

202
00:12:04,000 --> 00:12:07,000
Laat ons nou loop die uitgebreide Euklidiese algoritme vir 'n = 5

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

204
00:12:11,000 --> 00:12:14,000
Ons sal gebruik maak van 'n metode om die tabel-metode genoem.

205
00:12:14,000 --> 00:12:21,000
Ons tafel 4 kolomme, x, y, d, en k sal hê.

206
00:12:21,000 --> 00:12:23,000
Ons tafel begin af met 2 rye.

207
00:12:23,000 --> 00:12:28,000
Ons het in die eerste ry 1, 0, dan is ons waarde van a, wat 5,

208
00:12:28,000 --> 00:12:37,000
en ons tweede ry is 0, 1 en ons waarde vir b, wat is 924.

209
00:12:37,000 --> 00:12:40,000
Die waarde van die 4de kolom, k, sal die gevolg wees

210
00:12:40,000 --> 00:12:45,000
die verdeling van die waarde van d in die ry bo dit met die waarde van d

211
00:12:45,000 --> 00:12:49,000
op dieselfde ry.

212
00:12:49,000 --> 00:12:56,000
Ons het 5 gedeel deur 924 0 met 'n paar res.

213
00:12:56,000 --> 00:12:59,000
Dit beteken dat ons k = 0.

214
00:12:59,000 --> 00:13:05,000
Nou is die waarde van elke ander sel sal die waarde van die sel 2 rye bokant dit wees

215
00:13:05,000 --> 00:13:09,000
minus die waarde van die ry bokant dit keer k.

216
00:13:09,000 --> 00:13:11,000
Kom ons begin met d in die 3de ry.

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

218
00:13:19,000 --> 00:13:25,000
Volgende het ons 0 - 1 * 0 wat 0

219
00:13:25,000 --> 00:13:30,000
en 1 - 0 * 0 wat 1.

220
00:13:30,000 --> 00:13:33,000
Nie te sleg nie, so laat ons beweeg op na die volgende ry.

221
00:13:33,000 --> 00:13:36,000
Eerstens moet ons ons waarde van k.

222
00:13:36,000 --> 00:13:43,000
924 gedeel deur 5 = 184 met 'n paar res,

223
00:13:43,000 --> 00:13:46,000
sodat ons waarde vir k is 184.

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

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

226
00:14:05,000 --> 00:14:07,000
Alle reg, laat ons doen die volgende ry.

227
00:14:07,000 --> 00:14:10,000
Ons waarde van k sal 1 omdat

228
00:14:10,000 --> 00:14:15,000
5 4 = 1 gedeel deur met 'n paar res.

229
00:14:15,000 --> 00:14:17,000
Kom ons vul in die ander kolomme.

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

233
00:14:33,000 --> 00:14:35,000
Kom ons kyk wat ons volgende waarde van k sou wees.

234
00:14:35,000 --> 00:14:40,000
Wel, dit lyk asof ons 4 gedeel deur 1, wat is 4.

235
00:14:40,000 --> 00:14:43,000
So dat k in hierdie geval waar ons deel deur 1 is gelyk aan

236
00:14:43,000 --> 00:14:50,000
die waarde van d in die bogenoemde ry beteken dat ons klaar is met ons algoritme.

237
00:14:50,000 --> 00:14:58,000
Ons kan hier sien dat ons x = 185 en y = -1 in die laaste ry.

238
00:14:58,000 --> 00:15:00,000
Kom ons kom nou terug na ons oorspronklike doel.

239
00:15:00,000 --> 00:15:04,000
Ons het gesê dat die waarde van x as 'n gevolg van die uitvoer van hierdie algoritme

240
00:15:04,000 --> 00:15:08,000
die multiplikatiewe inverse van 'n (mod b).

241
00:15:08,000 --> 00:15:15,000
Dit beteken dat 185 is die multiplikatiewe inverse van 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
wat beteken dat ons 'n waarde van 185 vir d.

243
00:15:20,000 --> 00:15:23,000
Die feit dat d = 1 in die laaste ry

244
00:15:23,000 --> 00:15:26,000
verifieer dat die e is coprime na m.

245
00:15:26,000 --> 00:15:30,000
As dit nie was 1 dan sou ons 'n nuwe e te kies.

246
00:15:30,000 --> 00:15:33,000
Nou laat ons kyk of Rob my boodskap ontvang het.

247
00:15:33,000 --> 00:15:35,000
Wanneer iemand stuur vir my 'n geënkripteerde boodskap

248
00:15:35,000 --> 00:15:38,000
so lank as wat ek my private sleutel bewaar 'n geheim

249
00:15:38,000 --> 00:15:41,000
Ek is die enigste een wat kan dekripteer die boodskap.

250
00:15:41,000 --> 00:15:46,000
Te dekripteer 'n stuk c Ek kan die oorspronklike boodskap bereken

251
00:15:46,000 --> 00:15:53,000
is gelyk aan die stuk d krag (mod n).

252
00:15:53,000 --> 00:15:57,000
Onthou dat D en N is van my private sleutel.

253
00:15:57,000 --> 00:16:01,000
'N volledige boodskap te kry van sy stukke wat ons dekripteer elke stuk

254
00:16:01,000 --> 00:16:04,000
en koppel die resultate.

255
00:16:04,000 --> 00:16:08,000
Presies hoe veilig is die RSA?

256
00:16:08,000 --> 00:16:10,000
Die waarheid is, weet ons nie.

257
00:16:10,000 --> 00:16:14,000
Security is gebaseer op hoe lank dit sou 'n aanvaller 'n boodskap neem om te kraak

258
00:16:14,000 --> 00:16:16,000
geïnkripteer met RSA.

259
00:16:16,000 --> 00:16:19,000
Onthou dat 'n aanvaller het toegang tot jou publieke sleutel,

260
00:16:19,000 --> 00:16:21,000
waarin beide e en n.

261
00:16:21,000 --> 00:16:26,000
Indien die aanvaller bestuur n faktor in sy 2 primes, P en Q,

262
00:16:26,000 --> 00:16:30,000
dan het sy d kon bereken deur gebruik te maak van die uitgebreide Euklidiese algoritme.

263
00:16:30,000 --> 00:16:35,000
Dit gee haar die private sleutel wat kan dekripteer wat gebruik word om enige boodskap.

264
00:16:35,000 --> 00:16:38,000
Maar hoe vinnig kan ons heelgetalle faktor?

265
00:16:38,000 --> 00:16:41,000
Weereens, weet ons nie.

266
00:16:41,000 --> 00:16:43,000
Niemand het 'n vinnige manier om dit te doen,

267
00:16:43,000 --> 00:16:46,000
wat beteken dat, gegee wat groot genoeg is n

268
00:16:46,000 --> 00:16:49,000
dit sou 'n aanvaller onrealisties lank neem

269
00:16:49,000 --> 00:16:51,000
die nommer aan 'n faktorontleding.

270
00:16:51,000 --> 00:16:54,000
As iemand 'n vinnige manier van factoring heelgetalle geopenbaar

271
00:16:54,000 --> 00:16:57,000
RSA sal gebreek word nie.

272
00:16:57,000 --> 00:17:01,000
Maar selfs as integer faktorisering is inherent stadig

273
00:17:01,000 --> 00:17:04,000
die RSA-algoritme kan nog 'n fout in die

274
00:17:04,000 --> 00:17:07,000
wat voorsiening maak vir maklike dekripsie van die boodskappe.

275
00:17:07,000 --> 00:17:10,000
Niemand is gevind en openbaar so 'n fout nie,

276
00:17:10,000 --> 00:17:12,000
maar dit beteken nie dat 'n mens nie bestaan ​​nie.

277
00:17:12,000 --> 00:17:17,000
In teorie, kan iemand uit die lees van alle data geïnkripteer met RSA.

278
00:17:17,000 --> 00:17:19,000
Daar is nog 'n bietjie van 'n privaatheid probleem.

279
00:17:19,000 --> 00:17:23,000
As Tommy codeert 'n boodskap met my publieke sleutel

280
00:17:23,000 --> 00:17:26,000
en 'n aanvaller versleutelt die dieselfde boodskap met my publieke sleutel

281
00:17:26,000 --> 00:17:29,000
die aanvaller sal sien dat die 2 boodskappe is identies

282
00:17:29,000 --> 00:17:32,000
en dus weet wat Tommy geïnkripteer.

283
00:17:32,000 --> 00:17:36,000
Ten einde dit te voorkom, is tipies boodskappe bepolsterd met random stukkies

284
00:17:36,000 --> 00:17:39,000
voordat dit geïnkripteer sodat dieselfde boodskap geïnkripteer

285
00:17:39,000 --> 00:17:44,000
verskeie kere so lank sal anders lyk as die padding op die boodskap is anders.

286
00:17:44,000 --> 00:17:47,000
Maar onthou hoe ons boodskappe in stukke te verdeel

287
00:17:47,000 --> 00:17:50,000
sodat elke stuk kleiner is as n?

288
00:17:50,000 --> 00:17:52,000
Padding die stukke beteken dat ons kan hê om dinge te verdeel

289
00:17:52,000 --> 00:17:57,000
in selfs meer stukke sedert die opgestopte stuk moet wees kleiner as n.

290
00:17:57,000 --> 00:18:01,000
Enkripsie en dekripsie is relatief duur met RSA,

291
00:18:01,000 --> 00:18:05,000
en so hoef te breek 'n boodskap in baie stukke kan baie duur wees.

292
00:18:05,000 --> 00:18:09,000
As 'n groot volume van data moet word geïnkripteer en Ontcijferde

293
00:18:09,000 --> 00:18:12,000
ons kan kombineer die voordele van die simmetriese sleutel algoritmes

294
00:18:12,000 --> 00:18:16,000
met dié van die RSA beide veiligheid en doeltreffendheid te kry.

295
00:18:16,000 --> 00:18:18,000
Alhoewel ons sal hier nie inkom nie,

296
00:18:18,000 --> 00:18:23,000
AES is 'n simmetriese sleutel algoritme soos die Vigenère en Caesar getalle

297
00:18:23,000 --> 00:18:25,000
maar baie moeiliker om te kraak.

298
00:18:25,000 --> 00:18:30,000
Van die kursus, kan ons nie gebruik AES sonder die stigting van 'n gedeelde geheime sleutel

299
00:18:30,000 --> 00:18:34,000
tussen die 2 stelsels, en ons het die probleem met dit voor.

300
00:18:34,000 --> 00:18:40,000
Maar nou is ons RSA die gedeelde geheime sleutel tussen die 2 stelsels kan gebruik om vas te stel.

301
00:18:40,000 --> 00:18:43,000
Ons sal noem die rekenaar stuur van die data die sender

302
00:18:43,000 --> 00:18:46,000
en die rekenaar die data ontvang die ontvanger.

303
00:18:46,000 --> 00:18:49,000
Die ontvanger het 'n RSA sleutel paar en stuur

304
00:18:49,000 --> 00:18:51,000
die publieke sleutel na die sender.

305
00:18:51,000 --> 00:18:54,000
Die sender genereer 'n AES-sleutel,

306
00:18:54,000 --> 00:18:57,000
versleutelt dit met die ontvanger se RSA publieke sleutel,

307
00:18:57,000 --> 00:19:00,000
en stuur die AES sleutel tot die ontvanger.

308
00:19:00,000 --> 00:19:04,000
Die ontvanger dekripteer die boodskap met die RSA private sleutel.

309
00:19:04,000 --> 00:19:09,000
Beide die sender en die ontvanger het nou 'n gedeelde AES sleutel tussen hulle.

310
00:19:09,000 --> 00:19:14,000
AES, wat is baie vinniger op enkripsie en dekripsie as RSA,

311
00:19:14,000 --> 00:19:18,000
kan nou gebruik word om die groot volumes van data te enkripteer en stuur dit aan die ontvanger,

312
00:19:18,000 --> 00:19:21,000
wat kan dekripteer deur gebruik te maak van die dieselfde sleutel.

313
00:19:21,000 --> 00:19:26,000
AES, wat is baie vinniger op enkripsie en dekripsie as RSA,

314
00:19:26,000 --> 00:19:30,000
kan nou gebruik word om die groot volumes van data te enkripteer en stuur dit aan die ontvanger,

315
00:19:30,000 --> 00:19:32,000
wat kan dekripteer deur gebruik te maak van die dieselfde sleutel.

316
00:19:32,000 --> 00:19:36,000
Ons het net nodig om die RSA die gedeelde sleutel te dra.

317
00:19:36,000 --> 00:19:40,000
Ons hoef nie meer RSA te gebruik.

318
00:19:40,000 --> 00:19:46,000
Dit lyk soos ek het 'n boodskap.

319
00:19:46,000 --> 00:19:49,000
Dit maak nie saak as iemand lees wat op die papier vliegtuig is voordat ek dit gevang

320
00:19:49,000 --> 00:19:55,000
want ek is die enigste een met die private sleutel.

321
00:19:55,000 --> 00:19:57,000
Kom ons decrypt elk van die stukke in die boodskap.

322
00:19:57,000 --> 00:20:07,000
Die eerste stuk, 658, samel ons die d krag, wat 185,

323
00:20:07,000 --> 00:20:18,000
modulo n, wat 989, is gelyk aan 67,

324
00:20:18,000 --> 00:20:24,000
wat is die letter C in ASCII.

325
00:20:24,000 --> 00:20:31,000
Nou, op die tweede stuk.

326
00:20:31,000 --> 00:20:35,000
Die tweede stuk waarde 15,

327
00:20:35,000 --> 00:20:41,000
wat ons maak aan die 185 mag,

328
00:20:41,000 --> 00:20:51,000
mod 989, en dit is gelyk aan 83

329
00:20:51,000 --> 00:20:57,000
wat is die letter S in ASCII.

330
00:20:57,000 --> 00:21:06,000
Nou vir die derde stuk, wat 'n waarde 799, ons verhoog tot 185,

331
00:21:06,000 --> 00:21:17,000
mod 989, en dit is gelyk aan 53,

332
00:21:17,000 --> 00:21:24,000
wat is die waarde van die karakter 5 in ASCII.

333
00:21:24,000 --> 00:21:30,000
Nou vir die laaste stuk, wat 'n waarde 975,

334
00:21:30,000 --> 00:21:41,000
ons verhoog tot 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
en dit is gelyk aan 48, wat is die waarde van die karakter 0 in ASCII.

336
00:21:51,000 --> 00:21:57,000
My naam is Rob Bowden, en dit is CS50.

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

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

339
00:22:08,000 --> 00:22:14,000
RSA at all. [Lag]

340
00:22:14,000 --> 00:22:17,000
At all.