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
La oss ta en titt på RSA, en mye brukt algoritme for å kryptere data.

5
00:00:11,000 --> 00:00:16,000
Krypteringsalgoritmer som Caesar og Vigenère ciphers er ikke veldig sikker.

6
00:00:16,000 --> 00:00:20,000
Med Caesar cipher, må en angriper bare å prøve 25 forskjellige nøkler

7
00:00:20,000 --> 00:00:22,000
å få budskapet er ren tekst.

8
00:00:22,000 --> 00:00:25,000
Mens Vigenère chiffer er mer sikker enn Caesar cipher

9
00:00:25,000 --> 00:00:28,000
på grunn av den større søket plass for nøkler, en gang en angriper

10
00:00:28,000 --> 00:00:30,000
kjenner lengden på nøkkelen i en Vigenère siffer,

11
00:00:30,000 --> 00:00:34,000
som kan bestemmes via en analyse av mønstre i den krypterte teksten,

12
00:00:34,000 --> 00:00:38,000
den Vigenère chiffer er ikke så mye sikrere enn Caesar cipher.

13
00:00:38,000 --> 00:00:42,000
RSA, derimot, er ikke utsatt for angrep som dette.

14
00:00:42,000 --> 00:00:45,000
Caesar cipher og Vigenère cipher bruke samme nøkkel

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

16
00:00:47,000 --> 00:00:51,000
Denne egenskapen gjør disse ciphers symmetriske nøkkel algoritmer.

17
00:00:51,000 --> 00:00:54,000
Et grunnleggende problem med symmetriske nøkkel algoritmer

18
00:00:54,000 --> 00:00:57,000
er at de er avhengige av en kryptering og sende meldingen

19
00:00:57,000 --> 00:00:59,000
og den som mottar og dekryptere meldingen

20
00:00:59,000 --> 00:01:03,000
å ha blitt enige på forhånd om nøkkelen de vil ta i bruk.

21
00:01:03,000 --> 00:01:06,000
Men vi har litt av en oppstart problem her.

22
00:01:06,000 --> 00:01:10,000
Hvordan etablere to datamaskiner som ønsker å kommunisere gjør en hemmelig nøkkel mellom dem?

23
00:01:10,000 --> 00:01:16,000
Hvis nøkkelen må være hemmelig, så vi trenger en måte å kryptere og dekryptere nøkkelen.

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

25
00:01:18,000 --> 00:01:21,000
så vi har nettopp kommet tilbake til det samme problemet.

26
00:01:21,000 --> 00:01:25,000
RSA, derimot, bruker et par nøkler,

27
00:01:25,000 --> 00:01:28,000
ett for kryptering og en annen for dekryptering.

28
00:01:28,000 --> 00:01:32,000
En kalles den offentlige nøkkel, og den andre er den private nøkkelen.

29
00:01:32,000 --> 00:01:34,000
Den offentlige nøkkelen brukes til å kryptere meldinger.

30
00:01:34,000 --> 00:01:38,000
Som du kanskje skjønner av navnet, kan vi dele vår offentlige nøkkel med

31
00:01:38,000 --> 00:01:43,000
noen vi ønsker uten at sikkerheten av en kryptert melding.

32
00:01:43,000 --> 00:01:45,000
Meldinger kryptert ved hjelp av en offentlig nøkkel

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

34
00:01:49,000 --> 00:01:53,000
Selv om du kan dele din offentlige nøkkel, bør du alltid holde din private nøkkel hemmelig.

61
00:01:55,000 --> 00:01:58,000
og bare den private nøkkelen kan brukes for å dekryptere meldinger

62
00:01:58,000 --> 00:02:02,000
hvis 2 brukere ønsker å sende meldinger kryptert med RSA

63
00:02:02,000 --> 00:02:07,000
frem og tilbake både brukere må ha sin egen offentlig og privat nøkkelpar.

64
00:02:07,000 --> 00:02:10,000
Meldinger fra brukeren en til bruker 2

65
00:02:10,000 --> 00:02:15,000
bare bruke bruker 2s nøkkelpar, og meldinger fra bruker 2 til bruker 1

66
00:02:15,000 --> 00:02:17,000
bare bruke bruker 1-nøkkelpar.

67
00:02:17,000 --> 00:02:21,000
Det faktum at det er 2 separate taster for å kryptere og dekryptere meldinger

68
00:02:21,000 --> 00:02:24,000
gjør RSA en asymmetrisk nøkkel algoritme.

69
00:02:24,000 --> 00:02:28,000
Vi trenger ikke å kryptere den offentlige nøkkelen for å sende den til en annen datamaskin

70
00:02:28,000 --> 00:02:31,000
siden nøkkelen er offentlig allikevel.

71
00:02:31,000 --> 00:02:33,000
Dette betyr at RSA ikke har samme oppstartsproblemet

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

73
00:02:36,000 --> 00:02:39,000
Så hvis jeg ønsker å sende en melding ved hjelp av RSA kryptering

74
00:02:39,000 --> 00:02:42,000
til Rob, jeg må først Rob offentlige nøkkel.

75
00:02:42,000 --> 00:02:47,000
For å generere et par nøkler, må Rob å plukke to store primtall.

76
00:02:47,000 --> 00:02:50,000
Disse tallene vil bli brukt i både offentlige og private nøkler,

77
00:02:50,000 --> 00:02:54,000
men den offentlige nøkkelen vil bare bruke produktet av disse to tallene,

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 kryptert melding ved hjelp av Rob offentlige nøkkel

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

81
00:03:01,000 --> 00:03:05,000
For en datamaskin, er factoring tall et vanskelig problem.

82
00:03:05,000 --> 00:03:09,000
Den offentlige nøkkelen, må du huske, brukte produktet av to primtall.

83
00:03:09,000 --> 00:03:12,000
Dette produktet må da ha bare 2 faktorer,

84
00:03:12,000 --> 00:03:16,000
som tilfeldigvis er tallene som utgjør den private nøkkelen.

85
00:03:16,000 --> 00:03:20,000
For å dekryptere meldingen, vil RSA bruke denne private nøkkelen

86
00:03:20,000 --> 00:03:25,000
eller tallene multiplisert sammen i prosessen med å lage den offentlige nøkkelen.

87
00:03:25,000 --> 00:03:28,000
Fordi det er beregningsmessig vanskelig å faktor tallet

88
00:03:28,000 --> 00:03:32,000
brukes i en offentlig nøkkel inn i to tallene som brukes i den private nøkkelen

89
00:03:32,000 --> 00:03:36,000
det er vanskelig for en angriper å finne ut den private nøkkelen

90
00:03:36,000 --> 00:03:39,000
som vil være nødvendig for å dekryptere meldingen.

91
00:03:39,000 --> 00:03:43,000
Nå la oss gå inn i noen lavere nivå detaljer om RSA.

92
00:03:43,000 --> 00:03:46,000
La oss først se hvordan vi kan generere et par nøkler.

93
00:03:46,000 --> 00:03:49,000
Først må vi to primtall.

94
00:03:49,000 --> 00:03:52,000
Vi vil kalle disse to tallene p og q.

95
00:03:52,000 --> 00:03:56,000
For å plukke p og q, i praksis vi ville pseudorandomly generere

96
00:03:56,000 --> 00:03:59,000
store tall og deretter bruke en test for å avgjøre hvorvidt

97
00:03:59,000 --> 00:04:02,000
disse tallene er sannsynligvis primtall.

98
00:04:02,000 --> 00:04:05,000
Vi kan holde generere tilfeldige tall over og over igjen

99
00:04:05,000 --> 00:04:08,000
før vi har to primtall som vi kan bruke.

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

101
00:04:15,000 --> 00:04:19,000
Husk at i praksis bør p og q være mye større antall.

102
00:04:19,000 --> 00:04:22,000
Så vidt vi vet, jo større tall, jo vanskeligere er det

103
00:04:22,000 --> 00:04:25,000
å knekke en kryptert melding.

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

105
00:04:29,000 --> 00:04:33,000
I dag er det ofte anbefalt at p og q er minst 1024 biter,

106
00:04:33,000 --> 00:04:37,000
som setter hvert nummer på over 300 desimaler.

107
00:04:37,000 --> 00:04:40,000
Men vi vil plukke disse små tall for dette eksemplet.

108
00:04:40,000 --> 00:04:43,000
Nå skal vi multiplisere p og q sammen for å få en tredje nummer,

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

110
00:04:45,000 --> 00:04:55,000
I vårt tilfelle, n = 23 * 43, som = 989.

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

112
00:04:58,000 --> 00:05:02,000
Neste vi vil formere p - 1 med q - 1

113
00:05:02,000 --> 00:05:05,000
for å få et fjerde nummer, som vi kaller m.

114
00:05:05,000 --> 00:05:15,000
I vårt tilfelle, m = 22 * ​​42, som = 924.

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

116
00:05:18,000 --> 00:05:22,000
Nå trenger vi en rekke e som er relativt prime til m

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

118
00:05:25,000 --> 00:05:28,000
To tall er relativt prime eller coprime

119
00:05:28,000 --> 00:05:33,000
hvis den eneste positive heltall som deler dem begge jevnt er en.

120
00:05:33,000 --> 00:05:37,000
Med andre ord, den største felles divisor av e og m

121
00:05:37,000 --> 00:05:39,000
må være en.

122
00:05:39,000 --> 00:05:44,000
I praksis er det vanlig for e å være primtall 65537

123
00:05:44,000 --> 00:05:48,000
så lenge dette nummeret ikke tilfeldigvis være en faktor av m.

124
00:05:48,000 --> 00:05:53,000
For våre keys, vil vi plukke 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
Til slutt vil vi trenger en mer tall, som vi kaller d.

127
00:06:01,000 --> 00:06:11,000
D må være noen verdi som tilfredsstiller likningen de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Denne mod m betyr vi vil bruke noe som kalles modulær aritmetikk.

129
00:06:17,000 --> 00:06:21,000
I modulær aritmetikk, får en gang et nummer høyere enn noen øvre grense

130
00:06:21,000 --> 00:06:24,000
det vil bryte tilbake rundt til 0.

131
00:06:24,000 --> 00:06:27,000
En klokke, for eksempel, bruker modulær aritmetikk.

132
00:06:27,000 --> 00:06:31,000
Ett minutt etter 01:59, for eksempel, er 2:00,

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

134
00:06:33,000 --> 00:06:36,000
Minuttviseren har pakket rundt til 0

135
00:06:36,000 --> 00:06:39,000
ved å nå en øvre grense på 60 år.

136
00:06:39,000 --> 00:06:46,000
Så kan vi si 60 tilsvarer 0 (mod 60)

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

138
00:06:57,000 --> 00:07:02,000
Vår offentlige nøkkel blir paret e og n

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

140
00:07:09,000 --> 00:07:15,000
Våre private nøkkel vil være paret d og n,

141
00:07:15,000 --> 00:07:22,000
som i vårt tilfelle er 185 og 989.

142
00:07:22,000 --> 00:07:25,000
Legg merke til at vår opprinnelige primtall p og q ikke vises

143
00:07:25,000 --> 00:07:29,000
hvor som helst i våre private eller offentlige nøkler.

144
00:07:29,000 --> 00:07:33,000
Nå som vi har vår nøkkelpar, la oss ta en titt på hvordan vi kan kryptere

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

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

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

148
00:07:42,000 --> 00:07:46,000
Da vil jeg spørre Rob for hans offentlige nøkkel, som jeg skal bruke

149
00:07:46,000 --> 00:07:48,000
å kryptere en melding for å sende ham.

150
00:07:48,000 --> 00:07:53,000
Husk, det er helt greit for Rob å dele sin offentlige nøkkel med meg.

151
00:07:53,000 --> 00:07:56,000
Men det ville ikke være greit å dele sin private nøkkel.

152
00:07:56,000 --> 00:08:00,000
Jeg har ikke noen anelse om hva hans private nøkkelen er.

153
00:08:00,000 --> 00:08:03,000
Vi kan bryte vårt budskap m opp i flere biter

154
00:08:03,000 --> 00:08:07,000
alle mindre enn n og deretter kryptere hver av disse biter.

155
00:08:07,000 --> 00:08:12,000
Vi vil kryptere strengen CS50, som vi kan bryte opp i fire biter,

156
00:08:12,000 --> 00:08:14,000
én per bokstav.

157
00:08:14,000 --> 00:08:17,000
For å kryptere meldingen min, jeg trenger å konvertere den til

158
00:08:17,000 --> 00:08:20,000
en slags numerisk representasjon.

159
00:08:20,000 --> 00:08:25,000
La oss sette sammen de ASCII-verdier med karakterene i mitt budskap.

160
00:08:25,000 --> 00:08:28,000
For å kryptere en gitt melding m

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

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

163
00:08:40,000 --> 00:08:45,000
ellers hele meldingen ikke kan uttrykkes modulo n.

164
00:08:45,000 --> 00:08:49,000
Vi kan bryte m opp i flere biter, som alle er mindre enn n,

165
00:08:49,000 --> 00:08:52,000
og kryptere hver av disse biter.

166
00:08:52,000 --> 00:09:03,000
Kryptering hver av disse biter, får vi c1 = 67 til 5 (mod 989)

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

168
00:09:06,000 --> 00:09:15,000
For våre andre del har vi 83 til 5 (mod 989)

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

170
00:09:18,000 --> 00:09:26,000
For vår tredje del har vi 53 til 5 (mod 989)

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

172
00:09:30,000 --> 00:09:39,000
Og til slutt, for vår siste del har vi 48 til 5 (mod 989)

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

174
00:09:43,000 --> 00:09:48,000
Nå kan vi sende over disse krypterte verdier til Rob.

175
00:09:54,000 --> 00:09:58,000
Her du går, Rob.

176
00:09:58,000 --> 00:10:01,000
Mens vårt budskap er i flukt, la oss ta en titt

177
00:10:01,000 --> 00:10:07,000
på hvordan vi fikk denne verdien for d.

178
00:10:07,000 --> 00:10:17,000
Vårt nummer d trengs for å oppfylle 5d = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
Dette gjør d multiplikativ inverse av 5 modulo 924.

180
00:10:24,000 --> 00:10:28,000
Gitt to heltall, A og B, den utvidede Euklids algoritme

181
00:10:28,000 --> 00:10:33,000
kan brukes til å finne den største felles divisor av disse to heltall.

182
00:10:33,000 --> 00:10:37,000
Det vil også gi oss 2 andre tall, x og y,

183
00:10:37,000 --> 00:10:47,000
som tilfredsstiller ligningen ax + by = største felles divisor av a og b.

184
00:10:47,000 --> 00:10:49,000
Hvordan hjelper dette oss?

185
00:10:49,000 --> 00:10:52,000
Vel, koble 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 vet allerede at disse tallene er coprime.

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

189
00:11:03,000 --> 00:11:09,000
Dette gir oss 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 bare bryr seg om alt modulo 924

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

193
00:11:25,000 --> 00:11:27,000
Tenk tilbake til klokken.

194
00:11:27,000 --> 00:11:31,000
Hvis minutt hånd er på 1 og deretter nøyaktig 10 timer passere,

195
00:11:31,000 --> 00:11:35,000
vi vet minuttviseren vil fortsatt være på en.

196
00:11:35,000 --> 00:11:39,000
Her starter vi på en og deretter vikle rundt akkurat y ganger,

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

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 denne x er det samme som D vi leter etter før,

200
00:11:55,000 --> 00:11:58,000
så hvis vi bruker den utvidede Euklids algoritme

201
00:11:58,000 --> 00:12:04,000
å få dette nummeret x, er at antallet vi bør bruke som d vår.

202
00:12:04,000 --> 00:12:07,000
Nå la oss kjøre den utvidede Euklids algoritme for a = 5

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

204
00:12:11,000 --> 00:12:14,000
Vi vil bruke en metode som kalles tabellen metoden.

205
00:12:14,000 --> 00:12:21,000
Vårt bord vil ha 4 kolonner, x, y, d, og k..

206
00:12:21,000 --> 00:12:23,000
Vårt bord starter med to rader.

207
00:12:23,000 --> 00:12:28,000
I den første raden har vi 1, 0, så vår verdien av en, som er 5,

208
00:12:28,000 --> 00:12:37,000
og våre andre rad er 0, 1, og vår verdi for b, som er 924.

209
00:12:37,000 --> 00:12:40,000
Verdien av fjerde kolonnen, k, vil være et resultat

210
00:12:40,000 --> 00:12:45,000
av å dele verdien av d i raden over den med verdien av d

211
00:12:45,000 --> 00:12:49,000
på samme rad.

212
00:12:49,000 --> 00:12:56,000
Vi har 5 delt på 924 er 0 med noen rest.

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

214
00:12:59,000 --> 00:13:05,000
Nå verdien av annenhver celle vil være verdien av cellen 2 rader over det

215
00:13:05,000 --> 00:13:09,000
minus verdien av raden over det ganger K.

216
00:13:09,000 --> 00:13:11,000
La oss starte med d i 3. rad.

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

218
00:13:19,000 --> 00:13:25,000
Neste vi har 0-1 * 0 som er 0

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

220
00:13:30,000 --> 00:13:33,000
Ikke så ille, så la oss gå videre til neste rad.

221
00:13:33,000 --> 00:13:36,000
Først må vi vår verdi av k.

222
00:13:36,000 --> 00:13:43,000
924 delt på 5 = 184 med noen resten,

223
00:13:43,000 --> 00:13:46,000
så vår verdi for k er 184.

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

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

226
00:14:05,000 --> 00:14:07,000
Greit, la oss gjøre den neste raden.

227
00:14:07,000 --> 00:14:10,000
Vår verdi av k vil være en grunn

228
00:14:10,000 --> 00:14:15,000
5 delt på 4 = 1 med noen rest.

229
00:14:15,000 --> 00:14:17,000
La oss fylle de andre kolonnene.

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

233
00:14:33,000 --> 00:14:35,000
La oss se hva vår neste verdien av k ville være.

234
00:14:35,000 --> 00:14:40,000
Vel, det ser ut som vi har 4 delt på 1, som er 4.

235
00:14:40,000 --> 00:14:43,000
I dette tilfellet hvor vi dividere med 1 slik at k er lik

236
00:14:43,000 --> 00:14:50,000
verdien av d i ovennevnte rad betyr at vi er ferdig med algoritmen vår.

237
00:14:50,000 --> 00:14:58,000
Vi ser her at vi har x = 185 og y = -1 i den siste raden.

238
00:14:58,000 --> 00:15:00,000
La oss nå komme tilbake til vårt opprinnelige mål.

239
00:15:00,000 --> 00:15:04,000
Vi sa at verdien av x som følge av kjøre denne algoritmen

240
00:15:04,000 --> 00:15:08,000
ville være multiplikativ inverse av en (mod b).

241
00:15:08,000 --> 00:15:15,000
Det betyr at 185 er multiplikativ inverse av 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
noe som betyr at vi har en verdi på 185 for d.

243
00:15:20,000 --> 00:15:23,000
Det faktum at d 1 = i siste rad

244
00:15:23,000 --> 00:15:26,000
bekrefter at e ble coprime til minnekort.

245
00:15:26,000 --> 00:15:30,000
Hvis det ikke var en så vi måtte plukke en ny e.

246
00:15:30,000 --> 00:15:33,000
Nå la oss se om Rob har mottatt budskapet mitt.

247
00:15:33,000 --> 00:15:35,000
Når noen sender meg en kryptert melding

248
00:15:35,000 --> 00:15:38,000
så lenge jeg har holdt min private nøkkel hemmelig

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

250
00:15:41,000 --> 00:15:46,000
Til dekryptere en del c kan jeg beregne den opprinnelige meldingen

251
00:15:46,000 --> 00:15:53,000
er lik den del til d strøm (mod n).

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

253
00:15:57,000 --> 00:16:01,000
Å få en full melding fra sine biter vi dekryptere hver del

254
00:16:01,000 --> 00:16:04,000
og sette sammen resultatene.

255
00:16:04,000 --> 00:16:08,000
Nøyaktig hvor sikker er RSA?

256
00:16:08,000 --> 00:16:10,000
Sannheten er, vet vi ikke.

257
00:16:10,000 --> 00:16:14,000
Sikkerhet er basert på hvor lang tid det ville ta en angriper å knekke en melding

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

259
00:16:16,000 --> 00:16:19,000
Husk at en angriper får tilgang til den offentlige nøkkelen,

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

261
00:16:21,000 --> 00:16:26,000
Hvis angriperen klarer å faktor n i sine to primtall, p og q,

262
00:16:26,000 --> 00:16:30,000
så hun kunne beregne d med utvidede Euklids algoritme.

263
00:16:30,000 --> 00:16:35,000
Dette gir henne den private nøkkelen, som kan brukes for å dekryptere en melding.

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

265
00:16:38,000 --> 00:16:41,000
Igjen, vi vet ikke.

266
00:16:41,000 --> 00:16:43,000
Ingen har funnet en rask måte å gjøre det,

267
00:16:43,000 --> 00:16:46,000
som betyr at gitt stort nok n

268
00:16:46,000 --> 00:16:49,000
det ville ta en angriper urealistisk lang

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

270
00:16:51,000 --> 00:16:54,000
Hvis noen avslørte en rask måte å factoring heltall

271
00:16:54,000 --> 00:16:57,000
RSA ville bli brutt.

272
00:16:57,000 --> 00:17:01,000
Men selv om heltall faktorisering er iboende treg

273
00:17:01,000 --> 00:17:04,000
RSA algoritmen kan fortsatt ha noen feil i det

274
00:17:04,000 --> 00:17:07,000
som gjør det enkelt dekryptering av meldinger.

275
00:17:07,000 --> 00:17:10,000
Ingen har funnet og avdekket en slik feil ennå,

276
00:17:10,000 --> 00:17:12,000
men det betyr ikke at man ikke eksisterer.

277
00:17:12,000 --> 00:17:17,000
I teorien kan noen være der ute å lese alle data kryptert med RSA.

278
00:17:17,000 --> 00:17:19,000
Det er en annen bit av en personvern problemet.

279
00:17:19,000 --> 00:17:23,000
Hvis Tommy krypterer noen melding med min offentlige nøkkel

280
00:17:23,000 --> 00:17:26,000
og en angriper krypterer den samme meldingen med min offentlige nøkkel

281
00:17:26,000 --> 00:17:29,000
angriperen vil se at de to meldingene er identiske

282
00:17:29,000 --> 00:17:32,000
og dermed vet hva Tommy kryptert.

283
00:17:32,000 --> 00:17:36,000
For å unngå dette, er meldinger typisk polstret med tilfeldige biter

284
00:17:36,000 --> 00:17:39,000
før blir kryptert slik at den samme meldingen krypteres

285
00:17:39,000 --> 00:17:44,000
flere ganger vil se annerledes så lenge polstring på meldingen er forskjellig.

286
00:17:44,000 --> 00:17:47,000
Men husk hvor vi må dele meldinger i biter

287
00:17:47,000 --> 00:17:50,000
slik at hver del er mindre enn n?

288
00:17:50,000 --> 00:17:52,000
Padding biter betyr at vi kanskje må dele ting opp

289
00:17:52,000 --> 00:17:57,000
inn enda flere biter siden den polstrede del må være mindre enn n.

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

291
00:18:01,000 --> 00:18:05,000
og så ønsker å bryte opp en melding i mange biter kan være svært kostbare.

292
00:18:05,000 --> 00:18:09,000
Hvis store mengder data må krypteres og dekrypteres

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

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

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

296
00:18:18,000 --> 00:18:23,000
AES er en symmetrisk nøkkel algoritme som Vigenère og Caesar chifre

297
00:18:23,000 --> 00:18:25,000
men mye vanskeligere å knekke.

298
00:18:25,000 --> 00:18:30,000
Selvfølgelig kan vi ikke bruke AES uten å etablere en felles hemmelig nøkkel

299
00:18:30,000 --> 00:18:34,000
mellom de to systemene, og vi så problemet med det før.

300
00:18:34,000 --> 00:18:40,000
Men nå kan vi bruke RSA å etablere felles hemmelig nøkkel mellom de 2 systemene.

301
00:18:40,000 --> 00:18:43,000
Vi kaller datamaskinen som sender data avsenderen

302
00:18:43,000 --> 00:18:46,000
og datamaskinen som mottar dataene mottakeren.

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

304
00:18:49,000 --> 00:18:51,000
den offentlige nøkkelen til avsenderen.

305
00:18:51,000 --> 00:18:54,000
Avsenderen genererer en AES nøkkel,

306
00:18:54,000 --> 00:18:57,000
krypterer den med mottakerens RSA offentlig nøkkel,

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

308
00:19:00,000 --> 00:19:04,000
Mottakeren dekrypterer meldingen med sin RSA private nøkkelen.

309
00:19:04,000 --> 00:19:09,000
Både avsender og mottaker har nå en felles AES nøkkel mellom dem.

310
00:19:09,000 --> 00:19:14,000
AES, som er mye raskere på kryptering og dekryptering enn RSA,

311
00:19:14,000 --> 00:19:18,000
kan nå brukes til å kryptere store mengder data og sende dem til mottakeren,

312
00:19:18,000 --> 00:19:21,000
som kan dekryptere med samme nøkkel.

313
00:19:21,000 --> 00:19:26,000
AES, som er mye raskere på kryptering og dekryptering enn RSA,

314
00:19:26,000 --> 00:19:30,000
kan nå brukes til å kryptere store mengder data og sende dem til mottakeren,

315
00:19:30,000 --> 00:19:32,000
som kan dekryptere med samme nøkkel.

316
00:19:32,000 --> 00:19:36,000
Vi trengte RSA å overføre delt nøkkel.

317
00:19:36,000 --> 00:19:40,000
Vi trenger ikke lenger å bruke RSA i det hele tatt.

318
00:19:40,000 --> 00:19:46,000
Det ser ut som jeg har fått en melding.

319
00:19:46,000 --> 00:19:49,000
Det spiller ingen rolle om noen leser hva som står på papiret flyet før jeg fanget den

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

321
00:19:55,000 --> 00:19:57,000
La oss dekryptere hver av biter i meldingen.

322
00:19:57,000 --> 00:20:07,000
Den første del, 658, øker vi til d makt, som er 185,

323
00:20:07,000 --> 00:20:18,000
mod n, som er 989, er lik 67,

324
00:20:18,000 --> 00:20:24,000
som er bokstaven C i ASCII.

325
00:20:24,000 --> 00:20:31,000
Nå, på den andre del.

326
00:20:31,000 --> 00:20:35,000
Den andre del har verdi 15,

327
00:20:35,000 --> 00:20:41,000
som vi heve til ett hundre og åttifemte makt,

328
00:20:41,000 --> 00:20:51,000
989 mod, og dette er lik 83

329
00:20:51,000 --> 00:20:57,000
som er bokstaven S i ASCII.

330
00:20:57,000 --> 00:21:06,000
Nå for tredje del, som har verdi 799, øker vi til 185,

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

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

333
00:21:24,000 --> 00:21:30,000
Nå for siste blings, har hvilke verdi 975,

334
00:21:30,000 --> 00:21:41,000
Vi høyner til 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
og dette er lik 48, som er verdien for tegnet 0 i ASCII.

336
00:21:51,000 --> 00:21:57,000
Mitt 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 hele tatt.

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

340
00:22:14,000 --> 00:22:17,000
I det hele tatt.