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
[Dit is CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Laten we eens een kijkje nemen op RSA, een veel gebruikte algoritme voor het versleutelen van gegevens.

5
00:00:11,000 --> 00:00:16,000
Encryptie-algoritmen, zoals Caesar en Vigenère cijfers zijn niet erg veilig.

6
00:00:16,000 --> 00:00:20,000
Met de Caesar cipher, een aanvaller hoeft alleen om te proberen 25 verschillende sleutels

7
00:00:20,000 --> 00:00:22,000
om het bericht platte tekst te krijgen.

8
00:00:22,000 --> 00:00:25,000
Terwijl de Vigenère cijfer is veiliger dan de Caesar cipher

9
00:00:25,000 --> 00:00:28,000
vanwege de grotere zoekruimte voor sleutels, als een aanvaller

10
00:00:28,000 --> 00:00:30,000
kent de lengte van de sleutel in een Vigenère cipher,

11
00:00:30,000 --> 00:00:34,000
kan worden bepaald via een analyse van patronen in de versleutelde tekst,

12
00:00:34,000 --> 00:00:38,000
de Vigenère cijfer is niet veel veiliger dan de Caesar cipher.

13
00:00:38,000 --> 00:00:42,000
RSA, anderzijds, is niet gevoelig voor aanvallen als deze.

14
00:00:42,000 --> 00:00:45,000
De Caesar cipher en Vigenère cipher dezelfde sleutel gebruiken

15
00:00:45,000 --> 00:00:47,000
voor zowel coderen en decoderen van een bericht.

16
00:00:47,000 --> 00:00:51,000
Deze eigenschap maakt deze cijfers symmetrische sleutel algoritmen.

17
00:00:51,000 --> 00:00:54,000
Een fundamenteel probleem met symmetrische sleutel algoritmen

18
00:00:54,000 --> 00:00:57,000
is dat ze op de een vercijferinrichting en te verzenden

19
00:00:57,000 --> 00:00:59,000
en een ontvangende en decoderen van het bericht

20
00:00:59,000 --> 00:01:03,000
reeds zijn overeengekomen vooraf op de toets zullen ze beide gebruiken.

21
00:01:03,000 --> 00:01:06,000
Maar we hebben een beetje een opstartprobleem hier.

22
00:01:06,000 --> 00:01:10,000
Hoe twee computers die willen communiceren vaststelling van een geheime sleutel tussen hen?

23
00:01:10,000 --> 00:01:16,000
Als de sleutel moet geheim, dan moeten we een manier vinden om te coderen en decoderen van de sleutel.

24
00:01:16,000 --> 00:01:18,000
Als alles wat we hebben is symmetrische sleutel cryptografie

25
00:01:18,000 --> 00:01:21,000
dan hebben we gewoon terug naar het zelfde probleem.

26
00:01:21,000 --> 00:01:25,000
RSA, anderzijds, gebruikt een sleutelpaar,

27
00:01:25,000 --> 00:01:28,000
een voor codering en een voor decryptie.

28
00:01:28,000 --> 00:01:32,000
Heet de publieke sleutel en de andere is de private sleutel.

29
00:01:32,000 --> 00:01:34,000
De openbare sleutel wordt gebruikt om berichten te coderen.

30
00:01:34,000 --> 00:01:38,000
Zoals je kunt raden door zijn naam, kunnen we onze publieke sleutel delen met

31
00:01:38,000 --> 00:01:43,000
iedereen die we willen zonder afbreuk te doen aan de veiligheid van een gecodeerd bericht.

32
00:01:43,000 --> 00:01:45,000
Berichten gecodeerd met een publieke sleutel

33
00:01:45,000 --> 00:01:49,000
kunnen alleen worden gedecodeerd met de overeenkomstige prive sleutel.

34
00:01:49,000 --> 00:01:53,000
Terwijl u kunt uw publieke sleutel te delen, moet u altijd uw persoonlijke sleutel geheim.

61
00:01:55,000 --> 00:01:58,000
en alleen de private sleutel kan worden gebruikt voor het decoderen berichten

62
00:01:58,000 --> 00:02:02,000
als 2 gebruikers willen om berichten te verzenden gecodeerd met RSA

63
00:02:02,000 --> 00:02:07,000
heen en weer zowel de gebruikers nodig hebben om hun eigen publieke en private sleutelpaar hebben.

64
00:02:07,000 --> 00:02:10,000
Berichten van gebruiker 1 naar gebruiker 2

65
00:02:10,000 --> 00:02:15,000
alleen gebruik maken van de gebruiker 2's sleutelpaar, en berichten van gebruiker 2 naar gebruiker 1

66
00:02:15,000 --> 00:02:17,000
alleen gebruik maken van sleutelpaar gebruiker 1's.

67
00:02:17,000 --> 00:02:21,000
Het feit dat er twee afzonderlijke sleutels voor het coderen en decoderen van berichten

68
00:02:21,000 --> 00:02:24,000
maakt RSA een algoritme voor asymmetrische sleutels.

69
00:02:24,000 --> 00:02:28,000
We hoeven niet de openbare sleutel te versleutelen om het naar een andere computer

70
00:02:28,000 --> 00:02:31,000
omdat de sleutel is publiek toch.

71
00:02:31,000 --> 00:02:33,000
Dit betekent dat RSA niet hetzelfde opstartprobleem

72
00:02:33,000 --> 00:02:36,000
als de symmetrische sleutel algoritmen.

73
00:02:36,000 --> 00:02:39,000
Dus als ik een bericht met behulp van RSA-encryptie versturen

74
00:02:39,000 --> 00:02:42,000
aan Rob, ik moet eerst de publieke sleutel van Rob.

75
00:02:42,000 --> 00:02:47,000
Voor het genereren van een paar sleutels, Rob moet halen 2 grote priemgetallen.

76
00:02:47,000 --> 00:02:50,000
Deze nummers worden gebruikt in zowel de publieke als private sleutels,

77
00:02:50,000 --> 00:02:54,000
maar de publieke sleutel zal alleen gebruik maken van het product van deze 2 nummers,

78
00:02:54,000 --> 00:02:56,000
niet de getallen zelf.

79
00:02:56,000 --> 00:02:59,000
Zodra ik heb gecodeerd het bericht met behulp van de openbare sleutel van Rob

80
00:02:59,000 --> 00:03:01,000
Ik kan het bericht naar Rob.

81
00:03:01,000 --> 00:03:05,000
Voor een computer, factoring nummers is een moeilijk probleem.

82
00:03:05,000 --> 00:03:09,000
De publieke sleutel weet, gebruikt het product van twee priemgetallen.

83
00:03:09,000 --> 00:03:12,000
Dit product moet dan slechts twee factoren,

84
00:03:12,000 --> 00:03:16,000
die toevallig de getallen die het private sleutel.

85
00:03:16,000 --> 00:03:20,000
Om het bericht te ontcijferen, zal RSA Gebruik deze private sleutel

86
00:03:20,000 --> 00:03:25,000
of de getallen met elkaar vermenigvuldigd in het maken van de openbare sleutel.

87
00:03:25,000 --> 00:03:28,000
Omdat het rekenkundig moeilijk factor wordt het aantal

88
00:03:28,000 --> 00:03:32,000
gebruikt in een publieke sleutel in de 2 referentienummers in de private key

89
00:03:32,000 --> 00:03:36,000
het is moeilijk voor een aanvaller te achterhalen van de private sleutel

90
00:03:36,000 --> 00:03:39,000
dat nodig zal het bericht te ontcijferen.

91
00:03:39,000 --> 00:03:43,000
Laten we nu eens gaan in een aantal lager niveau details van RSA.

92
00:03:43,000 --> 00:03:46,000
Laten we eerst eens kijken hoe we een paar sleutels te genereren.

93
00:03:46,000 --> 00:03:49,000
Ten eerste, moeten we twee priemgetallen.

94
00:03:49,000 --> 00:03:52,000
We noemen deze 2 getallen p en q.

95
00:03:52,000 --> 00:03:56,000
Om p en q, neemt in de praktijk zouden we pseudorandomly genereren

96
00:03:56,000 --> 00:03:59,000
grote aantallen en gebruik vervolgens een test voor het bepalen van het al dan niet

97
00:03:59,000 --> 00:04:02,000
deze getallen zijn waarschijnlijk prime.

98
00:04:02,000 --> 00:04:05,000
We kunnen het genereren van willekeurige getallen te houden over en weer

99
00:04:05,000 --> 00:04:08,000
totdat we hebben 2 priemgetallen die we kunnen gebruiken.

100
00:04:08,000 --> 00:04:15,000
Hier laten we pick p = 23 en q = 43.

101
00:04:15,000 --> 00:04:19,000
Herinner in de praktijk moeten p en q veel grotere aantallen.

102
00:04:19,000 --> 00:04:22,000
Voor zover we weten, hoe groter de getallen, hoe moeilijker het is

103
00:04:22,000 --> 00:04:25,000
een versleuteld bericht kraken.

104
00:04:25,000 --> 00:04:29,000
Maar het is ook duurder om te coderen en decoderen van berichten.

105
00:04:29,000 --> 00:04:33,000
Vandaag de dag is vaak aanbevolen dat p en q zijn minstens 1024 bits,

106
00:04:33,000 --> 00:04:37,000
die legt elk nummer op meer dan 300 decimale cijfers.

107
00:04:37,000 --> 00:04:40,000
Maar we halen deze kleine aantallen voor dit voorbeeld.

108
00:04:40,000 --> 00:04:43,000
Nu we samen vermenigvuldigen p en q om een ​​3e nummer te krijgen,

109
00:04:43,000 --> 00:04:45,000
die we bellen n.

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

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

112
00:04:58,000 --> 00:05:02,000
Nu gaan we vermenigvuldigen p - 1 met q - 1

113
00:05:02,000 --> 00:05:05,000
naar een 4e nummer, dat we bellen m te verkrijgen.

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

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

116
00:05:18,000 --> 00:05:22,000
Nu gaan we behoefte aan een aantal e dat relatief priem om m

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

118
00:05:25,000 --> 00:05:28,000
Twee nummers zijn relatief priem of relatief priem

119
00:05:28,000 --> 00:05:33,000
als het enige positieve integer die hen scheidt beide gelijkmatig 1.

120
00:05:33,000 --> 00:05:37,000
Met andere woorden, de grootste gemene deler van e en m

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

122
00:05:39,000 --> 00:05:44,000
In de praktijk is het vaak voor e als de priemgetal 65537

123
00:05:44,000 --> 00:05:48,000
Zolang dit nummer niet toevallig een factor m bedragen.

124
00:05:48,000 --> 00:05:53,000
Voor onze sleutels, we halen e = 5

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

126
00:05:57,000 --> 00:06:01,000
Tot slot, moeten we nog een nummer, dat we bellen d.

127
00:06:01,000 --> 00:06:11,000
D moet een waarde die de vergelijking voldoet aan zijn de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Deze mod m betekent dat we zullen gebruiken iets genaamd modulaire rekenkunde.

129
00:06:17,000 --> 00:06:21,000
In modulaire rekenkunde, zodra een aantal wordt hoger dan sommige bovengrens

130
00:06:21,000 --> 00:06:24,000
het zal wrap terug rond naar 0.

131
00:06:24,000 --> 00:06:27,000
Een klok, gebruikt bijvoorbeeld modulaire rekenkunde.

132
00:06:27,000 --> 00:06:31,000
Een minuut na 1:59, is bijvoorbeeld 2:00,

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

134
00:06:33,000 --> 00:06:36,000
De minutenwijzer zijn rond naar 0

135
00:06:36,000 --> 00:06:39,000
bij het bereiken van een bovengrens van 60.

136
00:06:39,000 --> 00:06:46,000
Dus kunnen we zeggen 60 is gelijk aan 0 (mod 60)

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

138
00:06:57,000 --> 00:07:02,000
Onze publieke sleutel zal het paar e en n zijn

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

140
00:07:09,000 --> 00:07:15,000
De prive-sleutel zal het paar d en n,

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

142
00:07:22,000 --> 00:07:25,000
Merk op dat onze oorspronkelijke priemgetallen p en q niet verschijnen

143
00:07:25,000 --> 00:07:29,000
overal in onze private of publieke sleutels.

144
00:07:29,000 --> 00:07:33,000
Nu dat we onze paar toetsen hebben, laten we eens kijken hoe we kunnen coderen

145
00:07:33,000 --> 00:07:36,000
en decoderen van een bericht.

146
00:07:36,000 --> 00:07:38,000
Ik wil een bericht sturen naar Rob,

147
00:07:38,000 --> 00:07:42,000
dus hij zal de eerste om dit sleutelpaar genereren.

148
00:07:42,000 --> 00:07:46,000
Dan zal ik vragen Rob voor zijn publieke sleutel, die ik gebruik

149
00:07:46,000 --> 00:07:48,000
een bericht te sturen om hem te coderen.

150
00:07:48,000 --> 00:07:53,000
Vergeet niet, het is helemaal goed voor Rob om zijn publieke sleutel met mij te delen.

151
00:07:53,000 --> 00:07:56,000
Maar het zou niet goed is om zijn private sleutel te delen.

152
00:07:56,000 --> 00:08:00,000
Ik heb geen idee wat zijn prive-sleutel is.

153
00:08:00,000 --> 00:08:03,000
We kunnen breken onze boodschap m in meerdere stukken

154
00:08:03,000 --> 00:08:07,000
alle kleiner dan n en coderen elk van deze brokken.

155
00:08:07,000 --> 00:08:12,000
We coderen de string CS50, die we kunnen opbreken in 4 stukken,

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

157
00:08:14,000 --> 00:08:17,000
Met het oog op mijn bericht te versleutelen, zal ik nodig om het om te zetten in

158
00:08:17,000 --> 00:08:20,000
een soort numerieke weergave.

159
00:08:20,000 --> 00:08:25,000
Laten we samenvoegen van de ASCII-waarden met de personages in mijn boodschap.

160
00:08:25,000 --> 00:08:28,000
Om een ​​bepaald bericht m versleutelen

161
00:08:28,000 --> 00:08:37,000
Ik moet c = m berekenen de e (mod n).

162
00:08:37,000 --> 00:08:40,000
Maar m moet kleiner zijn dan n,

163
00:08:40,000 --> 00:08:45,000
of anders het volledige bericht kan niet worden uitgedrukt modulo n.

164
00:08:45,000 --> 00:08:49,000
We kunnen breken m in meerdere stukken, die kleiner zijn dan n,

165
00:08:49,000 --> 00:08:52,000
en coderen elk van deze brokken.

166
00:08:52,000 --> 00:09:03,000
Coderen elk van deze stukjes, krijgen we c1 = 67 naar de 5 (mod 989)

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

168
00:09:06,000 --> 00:09:15,000
Voor ons tweede stuk hebben we 83 tot en met de 5 (mod 989)

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

170
00:09:18,000 --> 00:09:26,000
Voor onze derde stuk hebben we 53 tot de 5 (mod 989)

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

172
00:09:30,000 --> 00:09:39,000
En tenslotte, voor onze laatste stuk hebben we 48 tot en met de 5 (mod 989)

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

174
00:09:43,000 --> 00:09:48,000
Nu kunnen we sturen deze gecodeerde waarden aan Rob.

175
00:09:54,000 --> 00:09:58,000
Hier ga je, Rob.

176
00:09:58,000 --> 00:10:01,000
Terwijl onze boodschap is tijdens de vlucht, laten we nog eens kijken

177
00:10:01,000 --> 00:10:07,000
hoe we die waarde voor d.

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

179
00:10:17,000 --> 00:10:24,000
Hierdoor d de multiplicatieve inverse modulo van 5 924.

180
00:10:24,000 --> 00:10:28,000
Gezien 2 gehele getallen a en b, de uitgebreide Euclidische algoritme

181
00:10:28,000 --> 00:10:33,000
kunnen worden gebruikt om de grootste gemene deler van deze twee getallen te vinden.

182
00:10:33,000 --> 00:10:37,000
Het zal ons ook twee andere getallen x en y,

183
00:10:37,000 --> 00:10:47,000
dat voldoet aan de vergelijking ax + by = de grootste gemene deler van a en b.

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

185
00:10:49,000 --> 00:10:52,000
Nou, het aansluiten van e = 5 voor een

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

187
00:10:56,000 --> 00:10:59,000
we weten al dat deze aantallen relatief priem zijn.

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

189
00:11:03,000 --> 00:11:09,000
Dit geeft 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 als we alleen de zorg over alles modulo 924

192
00:11:22,000 --> 00:11:25,000
dan kunnen we laten vallen - 924y.

193
00:11:25,000 --> 00:11:27,000
Denk terug aan de klok.

194
00:11:27,000 --> 00:11:31,000
Als de grote wijzer is op 1 en vervolgens precies 10 uur zijn verstreken,

195
00:11:31,000 --> 00:11:35,000
we weten dat de minutenwijzer nog steeds op 1.

196
00:11:35,000 --> 00:11:39,000
Hier zijn we beginnen bij 1 en daar dan omheen wikkelen precies y keer,

197
00:11:39,000 --> 00:11:41,000
dus we zullen nog steeds op 1.

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

199
00:11:49,000 --> 00:11:55,000
En hier deze x is hetzelfde als de d die we zochten voor,

200
00:11:55,000 --> 00:11:58,000
dus als we gebruik maken van de uitgebreide Euclidische algoritme

201
00:11:58,000 --> 00:12:04,000
om dit getal x, dat is het nummer dat we moeten gebruiken als onze d.

202
00:12:04,000 --> 00:12:07,000
Laten we nu lopen de uitgebreide Euclidische algoritme voor a = 5

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

204
00:12:11,000 --> 00:12:14,000
We zullen gebruik maken van een methode genaamd de tafel methode.

205
00:12:14,000 --> 00:12:21,000
De tabel zal 4 kolommen, x, y, d en k.

206
00:12:21,000 --> 00:12:23,000
Onze tafel begint met 2 rijen.

207
00:12:23,000 --> 00:12:28,000
In de eerste rij die we hebben 1, 0, dan is onze waarde van een, dat is 5,

208
00:12:28,000 --> 00:12:37,000
en de tweede rij 0, 1 en onze waarde b, wat 924.

209
00:12:37,000 --> 00:12:40,000
De waarde van de 4e kolom k, zal het resultaat

210
00:12:40,000 --> 00:12:45,000
verdelen de waarde van d in de rij erboven met de waarde van d

211
00:12:45,000 --> 00:12:49,000
op dezelfde rij.

212
00:12:49,000 --> 00:12:56,000
We hebben 5 gedeeld door 924 is 0 met wat rest.

213
00:12:56,000 --> 00:12:59,000
Dat betekent dat we k = 0.

214
00:12:59,000 --> 00:13:05,000
Nu de waarde van iedere andere cel wordt de waarde van de cel 2 rijen boven het

215
00:13:05,000 --> 00:13:09,000
minus de waarde van de rij erboven keer k.

216
00:13:09,000 --> 00:13:11,000
Laten we beginnen met d in de 3e rij.

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

218
00:13:19,000 --> 00:13:25,000
Vervolgens hebben we 0 - 1 * 0 die is 0

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

220
00:13:30,000 --> 00:13:33,000
Niet al te slecht, dus laten we verder gaan naar de volgende rij.

221
00:13:33,000 --> 00:13:36,000
Eerst moeten we onze waarde van k.

222
00:13:36,000 --> 00:13:43,000
924 gedeeld door 5 = 184 met enige overige

223
00:13:43,000 --> 00:13:46,000
zodat onze waarde voor k is 184.

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

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

226
00:14:05,000 --> 00:14:07,000
Oke, laten we het doen de volgende rij.

227
00:14:07,000 --> 00:14:10,000
De waarde van k is 1 omdat

228
00:14:10,000 --> 00:14:15,000
5 gedeeld door 4 = 1 met enkele rest.

229
00:14:15,000 --> 00:14:17,000
Laten we vullen in de andere kolommen.

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
Laten we eens kijken wat onze volgende waarde van k zou zijn.

234
00:14:35,000 --> 00:14:40,000
Nou, het lijkt erop dat we hebben 4 gedeeld door 1, dat is 4.

235
00:14:40,000 --> 00:14:43,000
In dit geval we delen door 1 zodanig dat k gelijk is aan

236
00:14:43,000 --> 00:14:50,000
de waarde van d in de bovenstaande rij betekent dat we klaar zijn met ons algoritme.

237
00:14:50,000 --> 00:14:58,000
We kunnen hier zien dat we x = 185 en y = -1 hebben in de laatste rij.

238
00:14:58,000 --> 00:15:00,000
Laten we nu terugkeren naar onze oorspronkelijke doel.

239
00:15:00,000 --> 00:15:04,000
We zeggen dat de waarde van x als gevolg van dit algoritme draait

240
00:15:04,000 --> 00:15:08,000
zou de multiplicatieve inverse van een (b mod) zijn.

241
00:15:08,000 --> 00:15:15,000
Dat betekent dat 185 is de multiplicatieve inverse van 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
Dit betekent dat we een waarde van 185 voor d hebben.

243
00:15:20,000 --> 00:15:23,000
Het feit dat d = 1 in de laatste rij

244
00:15:23,000 --> 00:15:26,000
controleert of e werd relatief priem aan m.

245
00:15:26,000 --> 00:15:30,000
Als het niet 1 dan zouden we een nieuwe e kiezen.

246
00:15:30,000 --> 00:15:33,000
Laten we nu eens kijken of Rob heeft ontvangen mijn boodschap.

247
00:15:33,000 --> 00:15:35,000
Wanneer iemand mij een gecodeerd bericht

248
00:15:35,000 --> 00:15:38,000
Zolang ik hield mijn persoonlijke sleutel een geheim

249
00:15:38,000 --> 00:15:41,000
Ik ben de enige die dat kan het bericht decoderen.

250
00:15:41,000 --> 00:15:46,000
Te decoderen een stuk c ik kan berekenen het originele bericht

251
00:15:46,000 --> 00:15:53,000
gelijk is aan het stuk om d vermogen (mod n).

252
00:15:53,000 --> 00:15:57,000
Vergeet niet dat d en n van mijn persoonlijke sleutel.

253
00:15:57,000 --> 00:16:01,000
Om een ​​volledige boodschap van haar brokken we decoderen elk blok

254
00:16:01,000 --> 00:16:04,000
en samenvoegen van de resultaten.

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

256
00:16:08,000 --> 00:16:10,000
De waarheid is, weten we niet.

257
00:16:10,000 --> 00:16:14,000
De beveiliging is gebaseerd op hoe lang het zou een aanvaller om een ​​bericht te kraken

258
00:16:14,000 --> 00:16:16,000
versleuteld met RSA.

259
00:16:16,000 --> 00:16:19,000
Vergeet niet dat een aanvaller toegang heeft tot uw publieke sleutel heeft,

260
00:16:19,000 --> 00:16:21,000
welke bevat zowel e en n.

261
00:16:21,000 --> 00:16:26,000
Als de aanvaller erin slaagt om n factor in de 2 priemgetallen, p en q,

262
00:16:26,000 --> 00:16:30,000
dan kon ze berekenen d met behulp van de uitgebreide Euclidische algoritme.

263
00:16:30,000 --> 00:16:35,000
Dit geeft haar private sleutel, die kunnen worden gebruikt voor het decoderen van een bericht.

264
00:16:35,000 --> 00:16:38,000
Maar hoe snel kunnen we factor gehele getallen?

265
00:16:38,000 --> 00:16:41,000
Nogmaals, weten we niet.

266
00:16:41,000 --> 00:16:43,000
Niemand heeft gevonden een snelle manier van doen,

267
00:16:43,000 --> 00:16:46,000
hetgeen betekent dat bij voldoende grote n

268
00:16:46,000 --> 00:16:49,000
het zou een aanvaller onrealistisch lange

269
00:16:49,000 --> 00:16:51,000
het aantal factor.

270
00:16:51,000 --> 00:16:54,000
Als iemand bleek een snelle manier van factoring gehele getallen

271
00:16:54,000 --> 00:16:57,000
RSA zou worden verbroken.

272
00:16:57,000 --> 00:17:01,000
Maar zelfs als integer factorisatie is inherent traag

273
00:17:01,000 --> 00:17:04,000
het RSA-algoritme wel wat fout nog steeds in het

274
00:17:04,000 --> 00:17:07,000
dat zorgt voor eenvoudige decodering van berichten.

275
00:17:07,000 --> 00:17:10,000
Niemand heeft gevonden en onthulde zulke fouten nog niet,

276
00:17:10,000 --> 00:17:12,000
maar dat betekent niet dat deze niet bestaat.

277
00:17:12,000 --> 00:17:17,000
In theorie zou iemand er uit het lezen van alle data versleuteld met RSA.

278
00:17:17,000 --> 00:17:19,000
Er is nog een beetje een privacy probleem.

279
00:17:19,000 --> 00:17:23,000
Als Tommy versleutelt een boodschap met behulp van mijn publieke sleutel

280
00:17:23,000 --> 00:17:26,000
en een aanvaller versleutelt dezelfde boodschap met behulp van mijn publieke sleutel

281
00:17:26,000 --> 00:17:29,000
de aanvaller zal zien dat de 2 berichten identiek zijn

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

283
00:17:32,000 --> 00:17:36,000
Om dit te voorkomen, worden berichten meestal gevuld met willekeurige bits

284
00:17:36,000 --> 00:17:39,000
alvorens te worden gecodeerd, zodat het dezelfde boodschap gecodeerd

285
00:17:39,000 --> 00:17:44,000
meerdere keren zal anders uitzien zolang de inleg van het bericht anders.

286
00:17:44,000 --> 00:17:47,000
Maar vergeet niet hoe we moeten boodschappen te splitsen in stukken

287
00:17:47,000 --> 00:17:50,000
zodat elk blok kleiner is dan n?

288
00:17:50,000 --> 00:17:52,000
Opvulling van de brokken betekent dat we zouden hebben om dingen te splitsen

289
00:17:52,000 --> 00:17:57,000
in nog meer stukken, omdat de gecapitonneerde stuk moet kleiner zijn dan n.

290
00:17:57,000 --> 00:18:01,000
Encryptie en decryptie zijn relatief duur met RSA,

291
00:18:01,000 --> 00:18:05,000
en dus om breken Bericht in vele stukjes kunnen zeer kostbaar zijn.

292
00:18:05,000 --> 00:18:09,000
Indien een grote hoeveelheid gegevens moet worden gecodeerd en gedecodeerd

293
00:18:09,000 --> 00:18:12,000
we kunnen de voordelen van symmetrische sleutelalgoritmen

294
00:18:12,000 --> 00:18:16,000
met die van RSA om zowel de veiligheid en efficiëntie te krijgen.

295
00:18:16,000 --> 00:18:18,000
Hoewel we hier niet op in,

296
00:18:18,000 --> 00:18:23,000
AES is een symmetrische sleutel algoritme, zoals de Vigenère en Caesar cijfers

297
00:18:23,000 --> 00:18:25,000
maar veel moeilijker te kraken.

298
00:18:25,000 --> 00:18:30,000
Natuurlijk kunnen we geen gebruik maken van AES zonder de oprichting van een gedeelde geheime sleutel

299
00:18:30,000 --> 00:18:34,000
tussen de 2 systemen, en we zagen het probleem met dat vóór.

300
00:18:34,000 --> 00:18:40,000
Maar nu kunnen we gebruik maken van RSA om de gedeelde geheime sleutel tussen de 2 systemen op te zetten.

301
00:18:40,000 --> 00:18:43,000
We bellen de computer het versturen van de gegevens van de afzender

302
00:18:43,000 --> 00:18:46,000
en de computer die de gegevens van de ontvanger.

303
00:18:46,000 --> 00:18:49,000
De receiver heeft een RSA-sleutelpaar en stuurt

304
00:18:49,000 --> 00:18:51,000
de publieke sleutel van de verzender.

305
00:18:51,000 --> 00:18:54,000
De zender genereert een AES toets

306
00:18:54,000 --> 00:18:57,000
versleutelt het met RSA de ontvanger de publieke sleutel,

307
00:18:57,000 --> 00:19:00,000
en stuurt de AES om de ontvanger.

308
00:19:00,000 --> 00:19:04,000
De ontvanger decodeert het bericht met zijn private sleutel RSA.

309
00:19:04,000 --> 00:19:09,000
Zowel de zender als de ontvanger hebben nu een gedeelde AES-sleutel tussen hen.

310
00:19:09,000 --> 00:19:14,000
AES, die veel sneller op dan encryptie en decryptie RSA,

311
00:19:14,000 --> 00:19:18,000
kan nu gebruikt worden om de grote hoeveelheden data te versleutelen en verzenden naar de ontvanger,

312
00:19:18,000 --> 00:19:21,000
wie kan decoderen met behulp van dezelfde toets.

313
00:19:21,000 --> 00:19:26,000
AES, die veel sneller op dan encryptie en decryptie RSA,

314
00:19:26,000 --> 00:19:30,000
kan nu gebruikt worden om de grote hoeveelheden data te versleutelen en verzenden naar de ontvanger,

315
00:19:30,000 --> 00:19:32,000
wie kan decoderen met behulp van dezelfde toets.

316
00:19:32,000 --> 00:19:36,000
We moesten RSA om de gedeelde sleutel over te dragen.

317
00:19:36,000 --> 00:19:40,000
We hoeven niet langer te RSA te gebruiken.

318
00:19:40,000 --> 00:19:46,000
Het lijkt erop dat ik heb een boodschap.

319
00:19:46,000 --> 00:19:49,000
Het maakt niet uit of iemand lezen wat er op het papier vliegtuig voordat ik ving hem

320
00:19:49,000 --> 00:19:55,000
want ik ben de enige met de private sleutel.

321
00:19:55,000 --> 00:19:57,000
Laten decoderen elk van de blokken in het bericht.

322
00:19:57,000 --> 00:20:07,000
De eerste stuk, 658, verhogen we de d macht, die is 185,

323
00:20:07,000 --> 00:20:18,000
mod n, die 989, gelijk aan 67,

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

325
00:20:24,000 --> 00:20:31,000
Nu, op de tweede brok.

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

327
00:20:35,000 --> 00:20:41,000
dat we te maken tegen de 185e macht

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

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

330
00:20:57,000 --> 00:21:06,000
Nu voor de derde stuk, welke waarde 799 heeft, we verhogen tot 185,

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

332
00:21:17,000 --> 00:21:24,000
Dit is de waarde van het teken 5 in ASCII.

333
00:21:24,000 --> 00:21:30,000
Nu voor de laatste brok, dat heeft waarde 975,

334
00:21:30,000 --> 00:21:41,000
we verhogen tot 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
en dit is gelijk aan 48, die van het teken 0 in ASCII.

336
00:21:51,000 --> 00:21:57,000
Mijn 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 helemaal.

339
00:22:08,000 --> 00:22:14,000
RSA helemaal. [Gelach]

340
00:22:14,000 --> 00:22:17,000
Helemaal.