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
[Dette er CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Lad os tage et kig på RSA, et udbredt algoritme til at kryptere data.

5
00:00:11,000 --> 00:00:16,000
Krypteringsalgoritmer som Cæsar og Vigenère ciphers er ikke meget sikker.

6
00:00:16,000 --> 00:00:20,000
Med Caesar cipher, kun en angriber skal prøve 25 forskellige nøgler

7
00:00:20,000 --> 00:00:22,000
at få budskabet er almindelig tekst.

8
00:00:22,000 --> 00:00:25,000
Mens Vigenère cipher er mere sikker end den Caesar cipher

9
00:00:25,000 --> 00:00:28,000
på grund af den større søgerummet til nøgler, når en hacker

10
00:00:28,000 --> 00:00:30,000
kender længden af ​​nøglen i en Vigenère cipher,

11
00:00:30,000 --> 00:00:34,000
som kan bestemmes via en analyse af mønstrene i den krypterede tekst,

12
00:00:34,000 --> 00:00:38,000
Den Vigenère cifferliste er ikke så meget mere sikker end Cæsar ciffer.

13
00:00:38,000 --> 00:00:42,000
RSA, på den anden side, er ikke sårbare over for angreb lignende.

14
00:00:42,000 --> 00:00:45,000
The Caesar cipher og Vigenère cipher bruge den samme nøgle

15
00:00:45,000 --> 00:00:47,000
både kryptere og dekryptere en meddelelse.

16
00:00:47,000 --> 00:00:51,000
Denne egenskab gør disse ciphers symmetriske nøgle algoritmer.

17
00:00:51,000 --> 00:00:54,000
Et grundlæggende problem med symmetriske nøgle algoritmer

18
00:00:54,000 --> 00:00:57,000
er, at de er afhængige af en kryptering og sender meddelelsen

19
00:00:57,000 --> 00:00:59,000
og den ene modtager og dekryptering af meddelelsen

20
00:00:59,000 --> 00:01:03,000
allerede at have aftalt på forhånd på tasten de begge vil bruge.

21
00:01:03,000 --> 00:01:06,000
Men vi har lidt af et startproblemet her.

22
00:01:06,000 --> 00:01:10,000
Hvordan 2 computere, der ønsker at kommunikere etablere en hemmelig nøgle mellem dem?

23
00:01:10,000 --> 00:01:16,000
Hvis nøglen skal være hemmelig, så har vi brug for en måde at kryptere og dekryptere nøglen.

24
00:01:16,000 --> 00:01:18,000
Hvis alt vi har, er symmetriske nøgle kryptografi

25
00:01:18,000 --> 00:01:21,000
så vi er lige kommet tilbage til det samme problem.

26
00:01:21,000 --> 00:01:25,000
RSA, på den anden side bruger et sæt nøgler,

27
00:01:25,000 --> 00:01:28,000
en for krypteringen og en anden for dekrypteringen.

28
00:01:28,000 --> 00:01:32,000
En kaldes den offentlige nøgle, og den anden er den private nøgle.

29
00:01:32,000 --> 00:01:34,000
Den offentlige nøgle bruges til at kryptere meddelelser.

30
00:01:34,000 --> 00:01:38,000
Som du kan gætte med sit navn, kan vi dele vores offentlige nøgle med

31
00:01:38,000 --> 00:01:43,000
nogen, vi ønsker, uden at kompromittere sikkerheden i en krypteret meddelelse.

32
00:01:43,000 --> 00:01:45,000
Meddelelser krypteret med en offentlig nøgle

33
00:01:45,000 --> 00:01:49,000
kan kun dekrypteres med den tilhørende private nøgle.

34
00:01:49,000 --> 00:01:53,000
Mens du kan dele din offentlige nøgle, bør du altid holde din private nøgle hemmelighed.

61
00:01:55,000 --> 00:01:58,000
og kun den private nøgle kan bruges til at dekryptere beskeder

62
00:01:58,000 --> 00:02:02,000
hvis 2 brugere ønsker at sende meddelelser krypteret med RSA

63
00:02:02,000 --> 00:02:07,000
frem og tilbage begge brugere er nødt til at have deres egne offentlige og private nøglepar.

64
00:02:07,000 --> 00:02:10,000
Meddelelser fra bruger 1 til bruger 2

65
00:02:10,000 --> 00:02:15,000
kun bruge bruger 2 s nøglepar, og beskeder fra bruger 2 til bruger 1

66
00:02:15,000 --> 00:02:17,000
kun bruge bruger 1 s nøglepar.

67
00:02:17,000 --> 00:02:21,000
Det faktum, at der er 2 separate taster til at kryptere og dekryptere beskeder

68
00:02:21,000 --> 00:02:24,000
gør RSA asymmetrisk nøglealgoritme.

69
00:02:24,000 --> 00:02:28,000
Vi behøver ikke at kryptere den offentlige nøgle for at sende den til en anden computer

70
00:02:28,000 --> 00:02:31,000
da nøglen er offentlig alligevel.

71
00:02:31,000 --> 00:02:33,000
Dette betyder, at RSA ikke har den samme startproblemet

72
00:02:33,000 --> 00:02:36,000
som de symmetriske nøgle algoritmer.

73
00:02:36,000 --> 00:02:39,000
Så hvis jeg ønsker at sende en besked ved hjælp af RSA-kryptering

74
00:02:39,000 --> 00:02:42,000
til Rob, jeg først nødt Rob offentlige nøgle.

75
00:02:42,000 --> 00:02:47,000
For at generere et sæt nøgler, Rob nødt til at vælge 2 store primtal.

76
00:02:47,000 --> 00:02:50,000
Disse tal vil blive anvendt i både den offentlige og private nøgler,

77
00:02:50,000 --> 00:02:54,000
men den offentlige nøgle vil kun bruge produktet af disse 2 numre,

78
00:02:54,000 --> 00:02:56,000
ikke tallene selv.

79
00:02:56,000 --> 00:02:59,000
Når jeg har krypteret beskeden ved hjælp af Rob offentlige nøgle

80
00:02:59,000 --> 00:03:01,000
Jeg kan sende beskeden til Rob.

81
00:03:01,000 --> 00:03:05,000
For en computer, er factoring numre en hård problem.

82
00:03:05,000 --> 00:03:09,000
Den offentlige nøgle, husk, der anvendes produktet af to primtal.

83
00:03:09,000 --> 00:03:12,000
Dette produkt skal derefter have kun 2 faktorer,

84
00:03:12,000 --> 00:03:16,000
som tilfældigvis er de numre, der udgør den private nøgle.

85
00:03:16,000 --> 00:03:20,000
For at dekryptere meddelelsen, vil RSA bruge denne private nøgle

86
00:03:20,000 --> 00:03:25,000
eller antallet multipliceres og i processen med at skabe den offentlige nøgle.

87
00:03:25,000 --> 00:03:28,000
Fordi det er beregningsmæssigt vanskeligt at faktor det antal

88
00:03:28,000 --> 00:03:32,000
bruges i en offentlig nøgle i 2 numre anvendes i private nøgle

89
00:03:32,000 --> 00:03:36,000
Det er svært for en hacker at finde ud af den private nøgle

90
00:03:36,000 --> 00:03:39,000
der vil være nødvendigt til at dekryptere meddelelsen.

91
00:03:39,000 --> 00:03:43,000
Lad os nu gå ind i nogle lavere niveau detaljer om RSA.

92
00:03:43,000 --> 00:03:46,000
Lad os først se, hvordan vi kan skabe et sæt nøgler.

93
00:03:46,000 --> 00:03:49,000
Først vil vi brug for 2 primtal.

94
00:03:49,000 --> 00:03:52,000
Vi kalder disse 2 numre p og q.

95
00:03:52,000 --> 00:03:56,000
For at samle p og q i praksis ville vi pseudorandomly genererer

96
00:03:56,000 --> 00:03:59,000
store tal og derefter bruge en test til bestemmelse af, om eller ej

97
00:03:59,000 --> 00:04:02,000
disse numre er sandsynligvis prime.

98
00:04:02,000 --> 00:04:05,000
Vi kan holde generere tilfældige tal igen og igen

99
00:04:05,000 --> 00:04:08,000
indtil vi har 2 primtal, som vi kan bruge.

100
00:04:08,000 --> 00:04:15,000
Her lad os plukke p = 23 og q = 43.

101
00:04:15,000 --> 00:04:19,000
Husk, i praksis, bør p og q er meget større tal.

102
00:04:19,000 --> 00:04:22,000
Så vidt vi ved, jo større tal, jo sværere er det

103
00:04:22,000 --> 00:04:25,000
at knække en krypteret meddelelse.

104
00:04:25,000 --> 00:04:29,000
Men det er også dyrere at kryptere og dekryptere beskeder.

105
00:04:29,000 --> 00:04:33,000
Dag er det ofte anbefales, at p og q er mindst 1024 bit,

106
00:04:33,000 --> 00:04:37,000
der sætter hvert nummer på over 300 decimaler.

107
00:04:37,000 --> 00:04:40,000
Men vi henter disse små tal for dette eksempel.

108
00:04:40,000 --> 00:04:43,000
Nu vil vi formere p og q sammen for at få en 3. nummer,

109
00:04:43,000 --> 00:04:45,000
som vi kalder n..

110
00:04:45,000 --> 00:04:55,000
I vores tilfælde, n = 23 * 43, hvilket = 989.

111
00:04:55,000 --> 00:04:58,000
Vi har n = 989.

112
00:04:58,000 --> 00:05:02,000
Næste vi vil mangedoble p - 1 med q - 1

113
00:05:02,000 --> 00:05:05,000
at opnå en 4. tal, som vi vil kalde m.

114
00:05:05,000 --> 00:05:15,000
I vores tilfælde, m = 22 * ​​42, hvilket = 924.

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

116
00:05:18,000 --> 00:05:22,000
Nu vil vi have en række e, der er relativt prime til m

117
00:05:22,000 --> 00:05:25,000
og mindre end m.

118
00:05:25,000 --> 00:05:28,000
To numre er relativt prime eller primiske

119
00:05:28,000 --> 00:05:33,000
hvis det eneste positive heltal, der skiller dem begge jævnt er 1.

120
00:05:33,000 --> 00:05:37,000
Med andre ord, den største fælles divisor af e og m

121
00:05:37,000 --> 00:05:39,000
skal være 1.

122
00:05:39,000 --> 00:05:44,000
I praksis er det fælles for e at være primtal 65.537

123
00:05:44,000 --> 00:05:48,000
så længe et sådant ikke tilfældigvis er en faktor m.

124
00:05:48,000 --> 00:05:53,000
For vores nøgler, vil vi vælge e = 5

125
00:05:53,000 --> 00:05:57,000
siden 5 er relativt prime til 924.

126
00:05:57,000 --> 00:06:01,000
Endelig får vi brug for en mere antal, som vi vil kalde d.

127
00:06:01,000 --> 00:06:11,000
D skal være en værdi, der tilfredsstiller ligningen de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Denne mod m betyder vi vil bruge noget, der hedder modulær aritmetik.

129
00:06:17,000 --> 00:06:21,000
I modulær aritmetik, får en gang et tal højere end nogle øvre grænse

130
00:06:21,000 --> 00:06:24,000
Det vil automatisk gå tilbage rundt til 0.

131
00:06:24,000 --> 00:06:27,000
Et ur, for eksempel anvender modulær aritmetik.

132
00:06:27,000 --> 00:06:31,000
Et minut efter 1:59, for eksempel er 02:00,

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

134
00:06:33,000 --> 00:06:36,000
Minutviseren har svøbt omkring til 0

135
00:06:36,000 --> 00:06:39,000
efter at have nået en øvre grænse på 60.

136
00:06:39,000 --> 00:06:46,000
Så kan vi sige 60 svarer til 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
og 125 svarer til 65 svarer til 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Vores offentlige nøgle bliver parret e og n

139
00:07:02,000 --> 00:07:09,000
hvor i dette tilfælde e er 5, og n er 989.

140
00:07:09,000 --> 00:07:15,000
Vores private nøgle bliver parret d og n,

141
00:07:15,000 --> 00:07:22,000
hvilket i vores tilfælde er 185 og 989.

142
00:07:22,000 --> 00:07:25,000
Bemærk, at vores oprindelige primtal p og q ikke vises

143
00:07:25,000 --> 00:07:29,000
overalt i vores private eller offentlige nøgler.

144
00:07:29,000 --> 00:07:33,000
Nu hvor vi har vores sæt nøgler, så lad os tage et kig på, hvordan vi kan kryptere

145
00:07:33,000 --> 00:07:36,000
og dekryptere en meddelelse.

146
00:07:36,000 --> 00:07:38,000
Jeg ønsker at sende en besked til Rob,

147
00:07:38,000 --> 00:07:42,000
så han vil være en til at generere denne nøglepar.

148
00:07:42,000 --> 00:07:46,000
Så vil jeg bede Rob for hans offentlige nøgle, som jeg vil bruge

149
00:07:46,000 --> 00:07:48,000
til at kryptere en besked at sende til ham.

150
00:07:48,000 --> 00:07:53,000
Husk, det er helt okay for Rob at dele sin offentlige nøgle med mig.

151
00:07:53,000 --> 00:07:56,000
Men det ville ikke være okay at dele sin private nøgle.

152
00:07:56,000 --> 00:08:00,000
Jeg har ikke nogen idé om, hvad hans private nøgle er.

153
00:08:00,000 --> 00:08:03,000
Vi kan bryde vores budskab m op i flere bidder

154
00:08:03,000 --> 00:08:07,000
alle mindre end n og derefter kryptere hver af disse stykker.

155
00:08:07,000 --> 00:08:12,000
Vi vil kryptere strengen CS50, som vi kan bryde op i 4 stykker,

156
00:08:12,000 --> 00:08:14,000
en per bogstav.

157
00:08:14,000 --> 00:08:17,000
For at kryptere mit budskab, vil jeg nødt til at konvertere det til

158
00:08:17,000 --> 00:08:20,000
en slags numerisk repræsentation.

159
00:08:20,000 --> 00:08:25,000
Lad os sammenkæde ASCII værdier med personerne i mit budskab.

160
00:08:25,000 --> 00:08:28,000
For at kryptere en given meddelelse m

161
00:08:28,000 --> 00:08:37,000
Jeg bliver nødt til at beregne c = m til e (mod n).

162
00:08:37,000 --> 00:08:40,000
Men m skal være mindre end n,

163
00:08:40,000 --> 00:08:45,000
eller også hele meddelelsen ikke kan udtrykkes modulo n.

164
00:08:45,000 --> 00:08:49,000
Vi kan bryde m op i flere stykker, som alle er mindre end n,

165
00:08:49,000 --> 00:08:52,000
og kryptere hver af disse stykker.

166
00:08:52,000 --> 00:09:03,000
Kryptering af hver af disse stykker, fås c1 = 67 til 5 (mod 989)

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

168
00:09:06,000 --> 00:09:15,000
For vores anden luns har vi 83 til 5 (mod 989)

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

170
00:09:18,000 --> 00:09:26,000
For vores tredje luns har vi 53 til 5 (mod 989)

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

172
00:09:30,000 --> 00:09:39,000
Og endelig, for vores sidste luns har vi 48 til 5 (mod 989)

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

174
00:09:43,000 --> 00:09:48,000
Nu kan vi sende over disse krypterede værdier til Rob.

175
00:09:54,000 --> 00:09:58,000
Værsgo, Rob.

176
00:09:58,000 --> 00:10:01,000
Mens vores budskab er på flugt, lad os tage endnu et kig

177
00:10:01,000 --> 00:10:07,000
på, hvordan vi fik denne værdi for d.

178
00:10:07,000 --> 00:10:17,000
Vores nummer d nødvendige for at dække 5d = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
Dette gør d det multiplikative inverse af 5. modulo 924.

180
00:10:24,000 --> 00:10:28,000
Da 2 heltal, a og b, den udvidede Euklidiske algoritme

181
00:10:28,000 --> 00:10:33,000
kan anvendes til at finde den største fælles divisor af disse 2 heltal.

182
00:10:33,000 --> 00:10:37,000
Det vil også give os 2 andre numre, x og y,

183
00:10:37,000 --> 00:10:47,000
der opfylder ligningen ax + by = den største fælles divisor af a og b.

184
00:10:47,000 --> 00:10:49,000
Hvordan kan dette hjælpe os?

185
00:10:49,000 --> 00:10:52,000
Nå, tilslutte e = 5 for en

186
00:10:52,000 --> 00:10:56,000
og m = 924 for b

187
00:10:56,000 --> 00:10:59,000
Vi ved allerede, at disse tal er indbyrdes primiske.

188
00:10:59,000 --> 00:11:03,000
Deres største fælles divisor er 1.

189
00:11:03,000 --> 00:11:09,000
Dette giver os 5x + 924y = 1

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

191
00:11:17,000 --> 00:11:22,000
Men hvis vi kun interesserer os for alt modulo 924

192
00:11:22,000 --> 00:11:25,000
så kan vi droppe - 924y.

193
00:11:25,000 --> 00:11:27,000
Tænk tilbage på uret.

194
00:11:27,000 --> 00:11:31,000
Hvis minutviseren er på 1 og derefter præcis 10 timer, skal

195
00:11:31,000 --> 00:11:35,000
vi ved minutviseren vil stadig være på 1.

196
00:11:35,000 --> 00:11:39,000
Her starter vi på 1 og derefter indhyllingsafstand præcis y gange,

197
00:11:39,000 --> 00:11:41,000
så vi vil stadig være på 1.

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

199
00:11:49,000 --> 00:11:55,000
Og her i x er det samme som d vi søgte før,

200
00:11:55,000 --> 00:11:58,000
så hvis vi bruger den udvidede Euklidiske algoritme

201
00:11:58,000 --> 00:12:04,000
at få dette nummer x, det er det antal, vi skal bruge som vores d..

202
00:12:04,000 --> 00:12:07,000
Nu lad os køre den udvidede Euklidiske algoritme til a = 5

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

204
00:12:11,000 --> 00:12:14,000
Vi bruger en metode kaldet tabellen metoden.

205
00:12:14,000 --> 00:12:21,000
Vores tabel har 4 søjler, x, y, d og k.

206
00:12:21,000 --> 00:12:23,000
Vores tabel starter med 2 rækker.

207
00:12:23,000 --> 00:12:28,000
I den første række har vi 1, 0, så vores værdi af en, der er 5,

208
00:12:28,000 --> 00:12:37,000
og vores anden række er 0, 1, og vores værdi for b, der er 924.

209
00:12:37,000 --> 00:12:40,000
Værdien af ​​den 4. kolonne, k, bliver resultatet

210
00:12:40,000 --> 00:12:45,000
for at dividere værdien af ​​d i rækken over den med værdien af ​​d

211
00:12:45,000 --> 00:12:49,000
på samme række.

212
00:12:49,000 --> 00:12:56,000
Vi har 5 divideret med 924 er 0 med nogle resten.

213
00:12:56,000 --> 00:12:59,000
Det betyder, at vi har k = 0.

214
00:12:59,000 --> 00:13:05,000
Nu værdien af ​​hver celle bliver værdien af ​​cellen 2 p ovenover

215
00:13:05,000 --> 00:13:09,000
minus værdien af ​​rækken ovenover gange k.

216
00:13:09,000 --> 00:13:11,000
Lad os starte med d i 3. række.

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

218
00:13:19,000 --> 00:13:25,000
Næste vi har 0 - 1 * 0, hvilket er 0

219
00:13:25,000 --> 00:13:30,000
og 1 - 0 * 0 der er 1.

220
00:13:30,000 --> 00:13:33,000
Ikke alt for dårlig, så lad os gå videre til den næste række.

221
00:13:33,000 --> 00:13:36,000
Først har vi brug for vores værdi af k.

222
00:13:36,000 --> 00:13:43,000
924 divideret med 5 = 184 med en vis resterende,

223
00:13:43,000 --> 00:13:46,000
så vores værdi for k er 184.

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

225
00:13:54,000 --> 00:14:05,000
1 til 0 * 184 er 1 og 0 - 1 * 184 er -184.

226
00:14:05,000 --> 00:14:07,000
Okay, lad os gøre den næste række.

227
00:14:07,000 --> 00:14:10,000
Vores værdi af k vil være 1, fordi

228
00:14:10,000 --> 00:14:15,000
5 divideret med 4 = 1 med nogle resten.

229
00:14:15,000 --> 00:14:17,000
Lad os udfylde de andre kolonner.

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
Og fra 1 til 184 * 1 185.

233
00:14:33,000 --> 00:14:35,000
Lad os se, hvad vores næste værdi af k ville være.

234
00:14:35,000 --> 00:14:40,000
Tja, det ser ud som om vi har 4 divideres med 1, hvilket er 4.

235
00:14:40,000 --> 00:14:43,000
I dette tilfælde, hvor vi dividere med 1, således at k er lig med

236
00:14:43,000 --> 00:14:50,000
værdien af ​​d i ovenstående række, betyder, at vi er færdige med vores algoritme.

237
00:14:50,000 --> 00:14:58,000
Vi kan se her, at vi har x = 185 og y = -1 i den sidste række.

238
00:14:58,000 --> 00:15:00,000
Lad os nu vende tilbage til vores oprindelige mål.

239
00:15:00,000 --> 00:15:04,000
Vi sagde, at værdien af ​​x som et resultat af at køre denne algoritme

240
00:15:04,000 --> 00:15:08,000
vil være det multiplikative inverse af en (mod b).

241
00:15:08,000 --> 00:15:15,000
Det betyder, at 185 er det multiplikative inverse af 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
hvilket betyder, at vi har en værdi på 185 for d.

243
00:15:20,000 --> 00:15:23,000
Den kendsgerning, at d = 1 i den sidste række

244
00:15:23,000 --> 00:15:26,000
bekræfter, at e var indbyrdes primiske til m.

245
00:15:26,000 --> 00:15:30,000
Hvis det ikke var 1 så ville vi nødt til at vælge en ny e.

246
00:15:30,000 --> 00:15:33,000
Lad os nu se, om Rob har modtaget min besked.

247
00:15:33,000 --> 00:15:35,000
Når en person sender mig en krypteret meddelelse

248
00:15:35,000 --> 00:15:38,000
så længe jeg har holdt min private nøgle en hemmelighed

249
00:15:38,000 --> 00:15:41,000
Jeg er den eneste, der kan dekryptere meddelelsen.

250
00:15:41,000 --> 00:15:46,000
For at dekryptere en luns c jeg kan beregne den oprindelige meddelelse

251
00:15:46,000 --> 00:15:53,000
er lig med bid til d effekt (mod n).

252
00:15:53,000 --> 00:15:57,000
Husk, at d og n er fra min private nøgle.

253
00:15:57,000 --> 00:16:01,000
For at få en fuld besked fra sine bidder vi dekryptere hver luns

254
00:16:01,000 --> 00:16:04,000
og sammenkæde resultaterne.

255
00:16:04,000 --> 00:16:08,000
Præcis hvordan sikker er RSA?

256
00:16:08,000 --> 00:16:10,000
Sandheden er, ved vi ikke.

257
00:16:10,000 --> 00:16:14,000
Sikkerhed er baseret på hvor lang tid det ville tage en hacker at knække en besked

258
00:16:14,000 --> 00:16:16,000
krypteret med RSA.

259
00:16:16,000 --> 00:16:19,000
Husk, at en hacker har adgang til din offentlige nøgle,

260
00:16:19,000 --> 00:16:21,000
der indeholder både e og n.

261
00:16:21,000 --> 00:16:26,000
Hvis hackeren formår at faktor n i sine 2 primtal, p og q,

262
00:16:26,000 --> 00:16:30,000
så hun kunne beregne d med den udvidede Euklidiske algoritme.

263
00:16:30,000 --> 00:16:35,000
Dette giver hende den private nøgle, som kan anvendes til at dekryptere en meddelelse.

264
00:16:35,000 --> 00:16:38,000
Men hvor hurtigt kan vi faktor heltal?

265
00:16:38,000 --> 00:16:41,000
Igen, ved vi ikke.

266
00:16:41,000 --> 00:16:43,000
Ingen har fundet en hurtig måde at gøre det,

267
00:16:43,000 --> 00:16:46,000
hvilket betyder, at given stor nok n

268
00:16:46,000 --> 00:16:49,000
det ville tage en hacker urealistisk lang

269
00:16:49,000 --> 00:16:51,000
til faktor nummeret.

270
00:16:51,000 --> 00:16:54,000
Hvis nogen afslørede en hurtig måde at factoring heltal

271
00:16:54,000 --> 00:16:57,000
RSA ville blive brudt.

272
00:16:57,000 --> 00:17:01,000
Men selv hvis heltal faktorisering er i sagens natur langsom

273
00:17:01,000 --> 00:17:04,000
RSA algoritmen kunne stadig have nogle fejl i det

274
00:17:04,000 --> 00:17:07,000
der tillader let dekryptering af meddelelser.

275
00:17:07,000 --> 00:17:10,000
Ingen har fundet og afsløret en sådan fejl endnu,

276
00:17:10,000 --> 00:17:12,000
men det betyder ikke en ikke eksisterer.

277
00:17:12,000 --> 00:17:17,000
I teorien kunne nogen være derude læse alle data krypteret med RSA.

278
00:17:17,000 --> 00:17:19,000
Der er en anden lidt af et privat anliggende.

279
00:17:19,000 --> 00:17:23,000
Hvis Tommy krypterer nogle besked ved hjælp af min offentlige nøgle

280
00:17:23,000 --> 00:17:26,000
og en angriber krypterer det samme budskab ved hjælp af min offentlige nøgle

281
00:17:26,000 --> 00:17:29,000
angriberen vil se, at de 2 budskaber er identiske

282
00:17:29,000 --> 00:17:32,000
og dermed ved, hvad Tommy krypteret.

283
00:17:32,000 --> 00:17:36,000
For at forhindre dette, er meddelelser typisk foret med tilfældige bits

284
00:17:36,000 --> 00:17:39,000
før de krypteres, så den samme meddelelse krypteres

285
00:17:39,000 --> 00:17:44,000
flere gange ser anderledes ud, så længe polstring på meddelelsen er forskellig.

286
00:17:44,000 --> 00:17:47,000
Men huske, hvordan vi er nødt til at opdele beskeder i stykker

287
00:17:47,000 --> 00:17:50,000
således at hvert stykke er mindre end n?

288
00:17:50,000 --> 00:17:52,000
Polstring de klumper betyder, at vi måske nødt til at splitte tingene op

289
00:17:52,000 --> 00:17:57,000
ind i endnu flere bidder, da det polstrede luns skal være mindre end n..

290
00:17:57,000 --> 00:18:01,000
Kryptering og dekryptering er relativt dyre med RSA,

291
00:18:01,000 --> 00:18:05,000
og så behøver at bryde op en besked i mange stykker kan være meget dyrt.

292
00:18:05,000 --> 00:18:09,000
Hvis en stor mængde data skal være krypteret og dekrypteret

293
00:18:09,000 --> 00:18:12,000
vi kan kombinere fordelene ved symmetriske nøgle algoritmer

294
00:18:12,000 --> 00:18:16,000
med de RSA at få både sikkerhed og effektivitet.

295
00:18:16,000 --> 00:18:18,000
Selv om vi ikke vil gå ind i det her,

296
00:18:18,000 --> 00:18:23,000
AES er en symmetrisk nøglealgoritme som Vigenère og Cæsar ciphers

297
00:18:23,000 --> 00:18:25,000
men meget sværere at knække.

298
00:18:25,000 --> 00:18:30,000
Selvfølgelig kan vi ikke bruge AES uden at etablere en fælles hemmelig nøgle

299
00:18:30,000 --> 00:18:34,000
mellem de 2 systemer, og vi oplevede det problem med det før.

300
00:18:34,000 --> 00:18:40,000
Men nu kan vi bruge RSA til at etablere den delte hemmelige nøgle mellem de 2 systemer.

301
00:18:40,000 --> 00:18:43,000
Vi ringer til computer, der sender data afsenderen

302
00:18:43,000 --> 00:18:46,000
og computeren modtager dataene modtageren.

303
00:18:46,000 --> 00:18:49,000
Modtageren har en RSA-nøglepar og sender

304
00:18:49,000 --> 00:18:51,000
den offentlige nøgle for afsenderen.

305
00:18:51,000 --> 00:18:54,000
Afsenderen genererer en AES nøgle,

306
00:18:54,000 --> 00:18:57,000
krypterer den med modtagerens RSA offentlige nøgle,

307
00:18:57,000 --> 00:19:00,000
og sender AES nøglen til modtageren.

308
00:19:00,000 --> 00:19:04,000
Modtageren dekrypterer meddelelsen med sin RSA private nøgle.

309
00:19:04,000 --> 00:19:09,000
Både afsender og modtager har nu en delt AES nøgle mellem dem.

310
00:19:09,000 --> 00:19:14,000
AES, som er meget hurtigere ved kryptering og dekryptering end RSA,

311
00:19:14,000 --> 00:19:18,000
kan nu bruges til at kryptere de store mængder af data og sende dem til modtageren,

312
00:19:18,000 --> 00:19:21,000
der kan dekryptere med den samme nøgle.

313
00:19:21,000 --> 00:19:26,000
AES, som er meget hurtigere ved kryptering og dekryptering end RSA,

314
00:19:26,000 --> 00:19:30,000
kan nu bruges til at kryptere de store mængder af data og sende dem til modtageren,

315
00:19:30,000 --> 00:19:32,000
der kan dekryptere med den samme nøgle.

316
00:19:32,000 --> 00:19:36,000
Vi har bare brug for RSA at overføre den delte nøgle.

317
00:19:36,000 --> 00:19:40,000
Vi vil ikke længere nødt til at bruge RSA overhovedet.

318
00:19:40,000 --> 00:19:46,000
Det ser ud som jeg har fået en besked.

319
00:19:46,000 --> 00:19:49,000
Det betyder ikke noget, om nogen læse hvad der er på papirflyver før jeg fangede det

320
00:19:49,000 --> 00:19:55,000
fordi jeg er den eneste med den private nøgle.

321
00:19:55,000 --> 00:19:57,000
Lad os dekryptere hver af klumper i meddelelsen.

322
00:19:57,000 --> 00:20:07,000
Den første bid, 658, hæver vi til d magt, hvilket er 185,

323
00:20:07,000 --> 00:20:18,000
mod n, hvilket er 989, er lig med 67,

324
00:20:18,000 --> 00:20:24,000
der er bogstavet C i ASCII.

325
00:20:24,000 --> 00:20:31,000
Nu, på det andet stykke.

326
00:20:31,000 --> 00:20:35,000
Det andet stykke har værdien 15,

327
00:20:35,000 --> 00:20:41,000
som vi hæve til 185. strøm,

328
00:20:41,000 --> 00:20:51,000
mod 989, hvilket svarer til 83

329
00:20:51,000 --> 00:20:57,000
der er bogstavet S i ASCII.

330
00:20:57,000 --> 00:21:06,000
Nu til den tredje bid, der har værdi 799, rejser vi til 185,

331
00:21:06,000 --> 00:21:17,000
mod 989, og dette er lig med 53,

332
00:21:17,000 --> 00:21:24,000
som er værdien for tegnet 5 i ASCII.

333
00:21:24,000 --> 00:21:30,000
Nu til den sidste bid, har hvilken værdi 975,

334
00:21:30,000 --> 00:21:41,000
vi rejser til 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
og dette er lig med 48, som er værdien af ​​den karakter 0 i ASCII.

336
00:21:51,000 --> 00:21:57,000
Mit navn er Rob Bowden, og dette er CS50.

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

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

339
00:22:08,000 --> 00:22:14,000
RSA overhovedet. [Latter]

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