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
[Detta är CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Låt oss ta en titt på RSA, en allmänt använd algoritm för kryptering av data.

5
00:00:11,000 --> 00:00:16,000
Krypteringsalgoritmer som Caesar och Vigenère chiffer är inte mycket säker.

6
00:00:16,000 --> 00:00:20,000
Med Caesar chiffer, behöver en angripare bara för att prova 25 olika nycklar

7
00:00:20,000 --> 00:00:22,000
att få ut budskapet är oformaterad text.

8
00:00:22,000 --> 00:00:25,000
Medan Vigenère chiffer är säkrare än Caesar chiffer

9
00:00:25,000 --> 00:00:28,000
på grund av den större sökrymden för nycklar, när en angripare

10
00:00:28,000 --> 00:00:30,000
vet längden på nyckeln i en Vigenère chiffer,

11
00:00:30,000 --> 00:00:34,000
vilket kan avgöras genom en analys av mönster i den krypterade texten,

12
00:00:34,000 --> 00:00:38,000
den Vigenère chiffer är inte så mycket säkrare än Caesar chiffer.

13
00:00:38,000 --> 00:00:42,000
RSA, å andra sidan, är inte sårbar för attacker som denna.

14
00:00:42,000 --> 00:00:45,000
Caesar chiffer och Vigenère chiffer använda samma nyckel

15
00:00:45,000 --> 00:00:47,000
både kryptera och dekryptera ett meddelande.

16
00:00:47,000 --> 00:00:51,000
Denna egenskap gör dessa chiffer symmetriska nyckel algoritmer.

17
00:00:51,000 --> 00:00:54,000
Ett grundläggande problem med symmetrisk nyckel algoritmer

18
00:00:54,000 --> 00:00:57,000
är att de förlitar sig på en kryptering och skicka meddelandet

19
00:00:57,000 --> 00:00:59,000
och en mottagande och dekryptering av meddelandet

20
00:00:59,000 --> 00:01:03,000
att redan överenskomna förskott på nyckeln kommer de båda använder.

21
00:01:03,000 --> 00:01:06,000
Men vi har en bit av en start problem här.

22
00:01:06,000 --> 00:01:10,000
Hur skapa 2 datorer som vill kommunicera en hemlig nyckel mellan dem?

23
00:01:10,000 --> 00:01:16,000
Om nyckeln måste vara hemliga, så vi behöver ett sätt att kryptera och dekryptera nyckeln.

24
00:01:16,000 --> 00:01:18,000
Om allt vi har är symmetrisk nyckel kryptografi

25
00:01:18,000 --> 00:01:21,000
då vi har precis kommit tillbaka till samma problem.

26
00:01:21,000 --> 00:01:25,000
RSA, å andra sidan, använder ett nyckelpar,

27
00:01:25,000 --> 00:01:28,000
en för kryptering och en annan för dekryptering.

28
00:01:28,000 --> 00:01:32,000
Den ena kallas den publika nyckeln, och den andra är den privata nyckeln.

29
00:01:32,000 --> 00:01:34,000
Den offentliga nyckeln används för att kryptera meddelanden.

30
00:01:34,000 --> 00:01:38,000
Som du kan gissa av namnet, kan vi dela med oss ​​av publika nyckel med

31
00:01:38,000 --> 00:01:43,000
vem vi vill utan att äventyra säkerheten för ett krypterat meddelande.

32
00:01:43,000 --> 00:01:45,000
Meddelanden som krypteras med en publik nyckel

33
00:01:45,000 --> 00:01:49,000
kan endast dekrypteras med motsvarande privata nyckel.

34
00:01:49,000 --> 00:01:53,000
Även om du kan dela din publika nyckel, bör du alltid hålla din privata nyckel hemlig.

61
00:01:55,000 --> 00:01:58,000
och endast den privata nyckeln kan användas för att dekryptera meddelanden

62
00:01:58,000 --> 00:02:02,000
Om 2 användare vill skicka meddelanden krypterade med RSA

63
00:02:02,000 --> 00:02:07,000
fram och tillbaka både användare måste ha sin egen offentliga och privata nyckelpar.

64
00:02:07,000 --> 00:02:10,000
Meddelanden från användare 1 till användare 2

65
00:02:10,000 --> 00:02:15,000
endast använda användarens 2 är nyckelpar och meddelanden från användare 2 till användare 1

66
00:02:15,000 --> 00:02:17,000
Använd endast användare 1: s nyckelpar.

67
00:02:17,000 --> 00:02:21,000
Det faktum att det finns 2 separata nycklar för att kryptera och dekryptera meddelanden

68
00:02:21,000 --> 00:02:24,000
gör RSA en asymmetrisk nyckel algoritm.

69
00:02:24,000 --> 00:02:28,000
Vi behöver inte kryptera den publika nyckeln för att skicka den till en annan dator

70
00:02:28,000 --> 00:02:31,000
eftersom nyckeln är öppen ändå.

71
00:02:31,000 --> 00:02:33,000
Detta innebär att RSA inte har samma startproblemet

72
00:02:33,000 --> 00:02:36,000
som de symmetriska nyckel algoritmer.

73
00:02:36,000 --> 00:02:39,000
Så om jag vill skicka ett meddelande med RSA-kryptering

74
00:02:39,000 --> 00:02:42,000
att Rob, jag måste först Robs publika nyckel.

75
00:02:42,000 --> 00:02:47,000
För att generera ett nyckelpar behöver Rob att plocka 2 stora primtal.

76
00:02:47,000 --> 00:02:50,000
Dessa siffror kommer att användas i både den offentliga och privata nycklar,

77
00:02:50,000 --> 00:02:54,000
men den publika nyckeln kommer endast att använda produkten av dessa 2 siffror,

78
00:02:54,000 --> 00:02:56,000
inte själva siffran.

79
00:02:56,000 --> 00:02:59,000
När jag har krypterat meddelandet med Rob publika nyckel

80
00:02:59,000 --> 00:03:01,000
Jag kan skicka meddelandet till Rob.

81
00:03:01,000 --> 00:03:05,000
För en dator är factoring nummer ett svårt problem.

82
00:03:05,000 --> 00:03:09,000
Den publika nyckeln, kom ihåg, använde produkten av 2 primtal.

83
00:03:09,000 --> 00:03:12,000
Denna produkt måste sedan ha bara 2 faktorer,

84
00:03:12,000 --> 00:03:16,000
som råkar vara de nummer som utgör den privata nyckeln.

85
00:03:16,000 --> 00:03:20,000
För att dekryptera meddelandet kommer RSA att använda denna privata nyckel

86
00:03:20,000 --> 00:03:25,000
eller siffrorna multipliceras tillsammans i processen för att skapa den publika nyckeln.

87
00:03:25,000 --> 00:03:28,000
Eftersom det är beräkningsmässigt svårt att räkna antalet

88
00:03:28,000 --> 00:03:32,000
används i en publik nyckel till de 2 numren som används i den privata nyckeln

89
00:03:32,000 --> 00:03:36,000
det är svårt för en angripare att räkna ut den privata nyckeln

90
00:03:36,000 --> 00:03:39,000
som kommer att vara nödvändig för att dekryptera meddelandet.

91
00:03:39,000 --> 00:03:43,000
Nu går i vissa lägre nivå detaljer i RSA.

92
00:03:43,000 --> 00:03:46,000
Låt oss först se hur vi kan skapa ett nyckelpar.

93
00:03:46,000 --> 00:03:49,000
Först behöver vi 2 primtal.

94
00:03:49,000 --> 00:03:52,000
Vi ringer dessa 2 nummer p och q.

95
00:03:52,000 --> 00:03:56,000
För att plocka p och q, i praktiken skulle vi pseudoslumpmässigt generera

96
00:03:56,000 --> 00:03:59,000
stort antal och sedan använda ett test för att bestämma huruvida eller ej

97
00:03:59,000 --> 00:04:02,000
dessa siffror är förmodligen Prime.

98
00:04:02,000 --> 00:04:05,000
Vi kan fortsätta generera slumptal om och om igen

99
00:04:05,000 --> 00:04:08,000
tills vi har 2 primtal som vi kan använda.

100
00:04:08,000 --> 00:04:15,000
Här ska vi plocka p = 23 och q = 43.

101
00:04:15,000 --> 00:04:19,000
Kom ihåg att, i praktiken, bör p och q vara mycket större antal.

102
00:04:19,000 --> 00:04:22,000
Så vitt vi vet, desto större siffrorna, desto svårare är det

103
00:04:22,000 --> 00:04:25,000
att knäcka ett krypterat meddelande.

104
00:04:25,000 --> 00:04:29,000
Men det är också dyrare att kryptera och dekryptera meddelanden.

105
00:04:29,000 --> 00:04:33,000
Idag är det ofta rekommenderas att p och q är minst 1024 bitar,

106
00:04:33,000 --> 00:04:37,000
som sätter varje nummer på över 300 decimaler.

107
00:04:37,000 --> 00:04:40,000
Men vi hämtar dessa små siffror för detta exempel.

108
00:04:40,000 --> 00:04:43,000
Nu ska vi multiplicera p och q tillsammans för att få en 3: e nummer,

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

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

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

112
00:04:58,000 --> 00:05:02,000
Nästa vi multiplicera p - 1 med q - 1

113
00:05:02,000 --> 00:05:05,000
att få en 4: e nummer, som vi kallar m..

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

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

116
00:05:18,000 --> 00:05:22,000
Nu ska vi behöva ett antal e som är relativt prima till m

117
00:05:22,000 --> 00:05:25,000
och mindre än m..

118
00:05:25,000 --> 00:05:28,000
Två nummer är relativt prima eller coprime

119
00:05:28,000 --> 00:05:33,000
om det enda positiva heltal som delar dem båda jämnt är 1.

120
00:05:33,000 --> 00:05:37,000
Med andra ord, den största gemensamma delaren av e och m

121
00:05:37,000 --> 00:05:39,000
måste vara 1.

122
00:05:39,000 --> 00:05:44,000
I praktiken är det vanligt att e att vara primtal 65.537

123
00:05:44,000 --> 00:05:48,000
så länge detta nummer inte råkar vara en faktor av m.

124
00:05:48,000 --> 00:05:53,000
För våra nycklar, vi plockar e = 5

125
00:05:53,000 --> 00:05:57,000
sedan 5 är relativt primtal till 924.

126
00:05:57,000 --> 00:06:01,000
Slutligen behöver vi en mer nummer, som vi kallar d..

127
00:06:01,000 --> 00:06:11,000
D måste vara ett värde som uppfyller ekvationen de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Denna mod m innebär att vi kommer att använda något som kallas modulär aritmetik.

129
00:06:17,000 --> 00:06:21,000
I modulär aritmetik, får gång ett nummer högre än vissa övre gräns

130
00:06:21,000 --> 00:06:24,000
det kommer att svepa tillbaka runt till 0.

131
00:06:24,000 --> 00:06:27,000
En klocka, till exempel, använder modulär aritmetik.

132
00:06:27,000 --> 00:06:31,000
En minut efter 1:59, till exempel, är 2:00,

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

134
00:06:33,000 --> 00:06:36,000
Minutvisaren har fastnat runt till 0

135
00:06:36,000 --> 00:06:39,000
på att nå en övre gräns på 60.

136
00:06:39,000 --> 00:06:46,000
Så kan vi säga 60 motsvarar 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
och 125 är ekvivalent med 65 motsvarar 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Vår offentliga nyckel blir paret e och n

139
00:07:02,000 --> 00:07:09,000
där i detta fall e är 5 och n är 989.

140
00:07:09,000 --> 00:07:15,000
Vår privata nyckel blir paret d och n,

141
00:07:15,000 --> 00:07:22,000
som i vårt fall är 185 och 989.

142
00:07:22,000 --> 00:07:25,000
Observera att vår ursprungliga primtal p och q visas inte

143
00:07:25,000 --> 00:07:29,000
någonstans i våra privata eller offentliga nycklar.

144
00:07:29,000 --> 00:07:33,000
Nu när vi har vår nyckelpar, låt oss ta en titt på hur vi kan kryptera

145
00:07:33,000 --> 00:07:36,000
och dekryptera ett meddelande.

146
00:07:36,000 --> 00:07:38,000
Jag vill skicka ett meddelande till Rob,

147
00:07:38,000 --> 00:07:42,000
så han kommer att vara en att skapa detta nyckelpar.

148
00:07:42,000 --> 00:07:46,000
Då ska jag be Rob för hans publika nyckel, som jag kommer att använda

149
00:07:46,000 --> 00:07:48,000
att kryptera ett meddelande att skicka till honom.

150
00:07:48,000 --> 00:07:53,000
Kom ihåg, det är helt okej för Rob att dela sin publika nyckel med mig.

151
00:07:53,000 --> 00:07:56,000
Men det skulle inte vara okej att dela hans privata nyckel.

152
00:07:56,000 --> 00:08:00,000
Jag har ingen aning om vad hans privata nyckel är.

153
00:08:00,000 --> 00:08:03,000
Vi kan bryta vårt budskap m upp i flera bitar

154
00:08:03,000 --> 00:08:07,000
alla mindre än n och sedan kryptera varje av dessa bitar.

155
00:08:07,000 --> 00:08:12,000
Vi ska kryptera strängen CS50, som vi kan bryta upp i 4 bitar,

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

157
00:08:14,000 --> 00:08:17,000
För att kryptera mitt budskap, jag behöver konvertera den till

158
00:08:17,000 --> 00:08:20,000
någon form av numerisk representation.

159
00:08:20,000 --> 00:08:25,000
Låt oss slå samman de ASCII-värden med karaktärerna i mitt budskap.

160
00:08:25,000 --> 00:08:28,000
För att kryptera ett givet meddelande m

161
00:08:28,000 --> 00:08:37,000
Jag behöver att beräkna c = m till e (mod n).

162
00:08:37,000 --> 00:08:40,000
Men m måste vara mindre än n,

163
00:08:40,000 --> 00:08:45,000
annars hela meddelandet inte kan uttryckas modulo n.

164
00:08:45,000 --> 00:08:49,000
Vi kan bryta m upp i flera bitar, som alla är mindre än n,

165
00:08:49,000 --> 00:08:52,000
och kryptera varje av dessa bitar.

166
00:08:52,000 --> 00:09:03,000
Kryptera alla dessa bitar får vi c1 = 67 till 5 (mod 989)

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

168
00:09:06,000 --> 00:09:15,000
För vår andra bit har vi 83 till 5 (mod 989)

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

170
00:09:18,000 --> 00:09:26,000
För vår tredje bit har vi 53 till 5 (mod 989)

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

172
00:09:30,000 --> 00:09:39,000
Och slutligen, för vår sista bit har vi 48 till 5 (mod 989)

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

174
00:09:43,000 --> 00:09:48,000
Nu kan vi skicka över dessa krypterade värden till Rob.

175
00:09:54,000 --> 00:09:58,000
Här har du, Rob.

176
00:09:58,000 --> 00:10:01,000
Medan vårt budskap är i luften, låt oss ta en titt

177
00:10:01,000 --> 00:10:07,000
hur vi fick det värdet för d.

178
00:10:07,000 --> 00:10:17,000
Vår nummer d behövs för att uppfylla 5d = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
Detta gör d. den multiplikativa inversen av 5 modulo 924.

180
00:10:24,000 --> 00:10:28,000
Med tanke på 2 heltal, A och B, den förlängda Euklides algoritm

181
00:10:28,000 --> 00:10:33,000
kan användas för att hitta den största gemensamma nämnaren för dessa 2 heltal.

182
00:10:33,000 --> 00:10:37,000
Det kommer också att ge oss 2 andra tal, x och y,

183
00:10:37,000 --> 00:10:47,000
som uppfyller ekvationen ax + by = den största gemensamma delaren av a och b.

184
00:10:47,000 --> 00:10:49,000
Hur hjälper det oss?

185
00:10:49,000 --> 00:10:52,000
Tja, koppla in e = 5 för en

186
00:10:52,000 --> 00:10:56,000
och m = 924 för b

187
00:10:56,000 --> 00:10:59,000
Vi vet redan att dessa siffror är coprime.

188
00:10:59,000 --> 00:11:03,000
Deras största gemensamma delare är 1.

189
00:11:03,000 --> 00:11:09,000
Detta ger 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 om vi bryr bara om allt modulo 924

192
00:11:22,000 --> 00:11:25,000
då kan vi släppa - 924y.

193
00:11:25,000 --> 00:11:27,000
Tänk tillbaka till klockan.

194
00:11:27,000 --> 00:11:31,000
Om minutvisaren är på 1 och sedan exakt 10 timmar ska

195
00:11:31,000 --> 00:11:35,000
vi vet minutvisaren fortfarande kommer att vara på 1.

196
00:11:35,000 --> 00:11:39,000
Här börjar vi på 1 och sedan linda runt exakt y gånger,

197
00:11:39,000 --> 00:11:41,000
så vi kommer fortfarande vara 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
Och här i x är samma som d vi letade efter innan,

200
00:11:55,000 --> 00:11:58,000
så om vi använder den förlängda Euklides algoritm

201
00:11:58,000 --> 00:12:04,000
att få det här numret X, det är det antal vi ska använda som vår d..

202
00:12:04,000 --> 00:12:07,000
Nu ska vi köra den utökade Euklides algoritm för a = 5

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

204
00:12:11,000 --> 00:12:14,000
Vi kommer att använda en metod som kallas tabell metoden.

205
00:12:14,000 --> 00:12:21,000
Vårt bord har 4 kolumner, x, y, d och k..

206
00:12:21,000 --> 00:12:23,000
Vårt bord börjar med 2 rader.

207
00:12:23,000 --> 00:12:28,000
I den första raden har vi 1, 0, då vår värdet av en, vilket är 5,

208
00:12:28,000 --> 00:12:37,000
och våra andra raden är 0, 1 och vårt värde för b, vilket är 924.

209
00:12:37,000 --> 00:12:40,000
Värdet på den 4: e kolumnen, k, blir resultatet

210
00:12:40,000 --> 00:12:45,000
att dela upp värdet på d i raden ovanför det med värdet av d

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

212
00:12:49,000 --> 00:12:56,000
Vi har 5 delat med 924 är 0 med viss resten.

213
00:12:56,000 --> 00:12:59,000
Det innebär att vi har k = 0.

214
00:12:59,000 --> 00:13:05,000
Nu värdet på varje annan cell blir värdet på cellen 2 rader ovanför det

215
00:13:05,000 --> 00:13:09,000
minus värdet på raden ovanför den tid k..

216
00:13:09,000 --> 00:13:11,000
Låt oss börja med d i 3: e raden.

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

218
00:13:19,000 --> 00:13:25,000
Sedan har vi från 0 till 1 * 0, som är 0

219
00:13:25,000 --> 00:13:30,000
och 1 - 0 * 0, som är 1.

220
00:13:30,000 --> 00:13:33,000
Inte alltför illa, så låt oss gå vidare till nästa rad.

221
00:13:33,000 --> 00:13:36,000
Först behöver vi vårt värde på K.

222
00:13:36,000 --> 00:13:43,000
924 dividerat med 5 = 184 med viss resten,

223
00:13:43,000 --> 00:13:46,000
så vårt värde för k är 184.

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

225
00:13:54,000 --> 00:14:05,000
1 till 0 * 184 är 1 och 0 till 1 * 184 är -184.

226
00:14:05,000 --> 00:14:07,000
Okej, låt oss göra nästa rad.

227
00:14:07,000 --> 00:14:10,000
Vår värdet av k blir 1 eftersom

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

229
00:14:15,000 --> 00:14:17,000
Låt oss fylla i de andra kolumnerna.

230
00:14:17,000 --> 00:14:21,000
5 till 4 * 1 = 1.

231
00:14:21,000 --> 00:14:25,000
0 till 1 * 1 = -1.

232
00:14:25,000 --> 00:14:33,000
Och 1 - 184 * 1 är 185.

233
00:14:33,000 --> 00:14:35,000
Låt oss se vad vår nästa värde på k skulle vara.

234
00:14:35,000 --> 00:14:40,000
Det ser ut som om vi har 4 delat med 1, vilket är 4.

235
00:14:40,000 --> 00:14:43,000
I det här fallet där vi dividera med 1 så att k är lika med

236
00:14:43,000 --> 00:14:50,000
Värdet på d i ovanstående raden betyder att vi är klara med vår algoritm.

237
00:14:50,000 --> 00:14:58,000
Vi kan här se att vi har x = 185 och y = -1 i den sista raden.

238
00:14:58,000 --> 00:15:00,000
Låt oss nu komma tillbaka till vår ursprungliga målsättning.

239
00:15:00,000 --> 00:15:04,000
Vi sa att värdet på x som en följd av att köra denna algoritm

240
00:15:04,000 --> 00:15:08,000
skulle vara den multiplikativa inversen av en (mod B).

241
00:15:08,000 --> 00:15:15,000
Det innebär att 185 är den multiplikativa inversen av 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
vilket innebär att vi har ett värde på 185 för d.

243
00:15:20,000 --> 00:15:23,000
Det faktum att d = 1 i den sista raden

244
00:15:23,000 --> 00:15:26,000
verifierar att e var coprime till m.

245
00:15:26,000 --> 00:15:30,000
Om det inte vore 1 då vi skulle behöva välja en ny e.

246
00:15:30,000 --> 00:15:33,000
Nu ska vi se om Rob har fått mitt budskap.

247
00:15:33,000 --> 00:15:35,000
När någon skickar mig ett krypterat meddelande

248
00:15:35,000 --> 00:15:38,000
så länge jag har hållit min privata nyckel hemlig

249
00:15:38,000 --> 00:15:41,000
Jag är den enda som kan dekryptera meddelandet.

250
00:15:41,000 --> 00:15:46,000
För att dekryptera en bit c jag kan räkna det ursprungliga meddelandet

251
00:15:46,000 --> 00:15:53,000
är lika med den bit till d effekt (mod n).

252
00:15:53,000 --> 00:15:57,000
Kom ihåg att d och n är från min privata nyckel.

253
00:15:57,000 --> 00:16:01,000
För att få en fullständig budskap från sina bitar vi dekryptera varje bit

254
00:16:01,000 --> 00:16:04,000
och konkatenera resultaten.

255
00:16:04,000 --> 00:16:08,000
Exakt hur säker är RSA?

256
00:16:08,000 --> 00:16:10,000
Sanningen är, vet vi inte.

257
00:16:10,000 --> 00:16:14,000
Säkerhet bygger på hur lång tid det skulle ta en angripare att knäcka ett meddelande

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

259
00:16:16,000 --> 00:16:19,000
Kom ihåg att en angripare har tillgång till din publika nyckel,

260
00:16:19,000 --> 00:16:21,000
vilken innehåller både e och n.

261
00:16:21,000 --> 00:16:26,000
Om angriparen lyckas faktor N i sina 2 primtal, p och q,

262
00:16:26,000 --> 00:16:30,000
då kunde hon räkna d med den utökade Euklides algoritm.

263
00:16:30,000 --> 00:16:35,000
Detta ger henne den privata nyckeln, som kan användas för att dekryptera ett meddelande.

264
00:16:35,000 --> 00:16:38,000
Men hur snabbt kan vi räkna heltal?

265
00:16:38,000 --> 00:16:41,000
Återigen vet vi inte.

266
00:16:41,000 --> 00:16:43,000
Ingen har hittat ett snabbt sätt att göra det,

267
00:16:43,000 --> 00:16:46,000
vilket innebär att givet tillräckligt stora n

268
00:16:46,000 --> 00:16:49,000
det skulle ta en angripare orealistiskt lång

269
00:16:49,000 --> 00:16:51,000
att räkna antalet.

270
00:16:51,000 --> 00:16:54,000
Om någon visade ett snabbt sätt för factoring heltal

271
00:16:54,000 --> 00:16:57,000
RSA skulle brytas.

272
00:16:57,000 --> 00:17:01,000
Men även om heltal faktorisering sig är långsam

273
00:17:01,000 --> 00:17:04,000
RSA-algoritmen kan fortfarande ha några fel i den

274
00:17:04,000 --> 00:17:07,000
som möjliggör enkel dekryptering av meddelanden.

275
00:17:07,000 --> 00:17:10,000
Ingen har hittat och avslöjade en sådan brist ännu,

276
00:17:10,000 --> 00:17:12,000
men det betyder inte att man inte existerar.

277
00:17:12,000 --> 00:17:17,000
I teorin kan någon vara där ute läser alla data krypteras med RSA.

278
00:17:17,000 --> 00:17:19,000
Det finns en annan lite privatliv fråga.

279
00:17:19,000 --> 00:17:23,000
Om Tommy krypterar några budskap med min publika nyckel

280
00:17:23,000 --> 00:17:26,000
och en angripare krypterar samma meddelande med min publika nyckel

281
00:17:26,000 --> 00:17:29,000
angriparen kommer att se till att de 2 meddelanden är identiska

282
00:17:29,000 --> 00:17:32,000
och därmed vet vad Tommy krypterad.

283
00:17:32,000 --> 00:17:36,000
För att förhindra detta är meddelanden oftast vadderade med slumpmässiga bitar

284
00:17:36,000 --> 00:17:39,000
innan de krypteras så att samma meddelande krypteras

285
00:17:39,000 --> 00:17:44,000
flera gånger kommer att se annorlunda så länge stoppning på meddelandet är annorlunda.

286
00:17:44,000 --> 00:17:47,000
Men kom ihåg att vi måste dela upp meddelanden i bitar

287
00:17:47,000 --> 00:17:50,000
så att varje bit är mindre än n?

288
00:17:50,000 --> 00:17:52,000
Utfyllnad bitarna innebär att vi kanske måste dela upp saker

289
00:17:52,000 --> 00:17:57,000
till ännu fler bitar sedan stoppade bit måste vara mindre än n.

290
00:17:57,000 --> 00:18:01,000
Kryptering och dekryptering är relativt dyra med RSA,

291
00:18:01,000 --> 00:18:05,000
och så behöva bryta upp ett budskap i många bitar kan bli mycket kostsamt.

292
00:18:05,000 --> 00:18:09,000
Om en stor mängd data måste krypteras och dekrypteras

293
00:18:09,000 --> 00:18:12,000
Vi kan kombinera fördelarna med symmetrisk nyckel algoritmer

294
00:18:12,000 --> 00:18:16,000
med de RSA för att få både säkerhet och effektivitet.

295
00:18:16,000 --> 00:18:18,000
Även om vi inte kommer att gå in i det här,

296
00:18:18,000 --> 00:18:23,000
AES är en symmetrisk nyckel algoritm som Vigenère och Caesar chiffer

297
00:18:23,000 --> 00:18:25,000
men mycket svårare att knäcka.

298
00:18:25,000 --> 00:18:30,000
Naturligtvis kan vi inte använda AES utan att etablera en gemensam hemlig nyckel

299
00:18:30,000 --> 00:18:34,000
mellan de 2 systemen, och vi såg problem med det förut.

300
00:18:34,000 --> 00:18:40,000
Men nu kan vi använda RSA för att upprätta den delade hemliga nyckeln mellan de 2 systemen.

301
00:18:40,000 --> 00:18:43,000
Vi ringer den dator som skickar uppgifterna avsändaren

302
00:18:43,000 --> 00:18:46,000
och datorn som mottar data mottagaren.

303
00:18:46,000 --> 00:18:49,000
Mottagaren har en RSA-nyckelpar och skickar

304
00:18:49,000 --> 00:18:51,000
den publika nyckeln till avsändaren.

305
00:18:51,000 --> 00:18:54,000
Avsändaren genererar en AES-nyckel,

306
00:18:54,000 --> 00:18:57,000
krypterar det med mottagarens RSA publik nyckel,

307
00:18:57,000 --> 00:19:00,000
och sänder AES-nyckel till mottagaren.

308
00:19:00,000 --> 00:19:04,000
Mottagaren dekrypterar meddelandet med sin privata RSA-nyckel.

309
00:19:04,000 --> 00:19:09,000
Både avsändaren och mottagaren har nu en gemensam AES-nyckel mellan dem.

310
00:19:09,000 --> 00:19:14,000
AES, vilket är mycket snabbare på kryptering och dekryptering än RSA,

311
00:19:14,000 --> 00:19:18,000
kan nu användas för att kryptera de stora datamängder och skicka dem till mottagaren,

312
00:19:18,000 --> 00:19:21,000
som kan dekryptera med samma nyckel.

313
00:19:21,000 --> 00:19:26,000
AES, vilket är mycket snabbare på kryptering och dekryptering än RSA,

314
00:19:26,000 --> 00:19:30,000
kan nu användas för att kryptera de stora datamängder och skicka dem till mottagaren,

315
00:19:30,000 --> 00:19:32,000
som kan dekryptera med samma nyckel.

316
00:19:32,000 --> 00:19:36,000
Vi behövde bara RSA för att överföra den delade nyckeln.

317
00:19:36,000 --> 00:19:40,000
Vi behöver inte längre använda RSA alls.

318
00:19:40,000 --> 00:19:46,000
Det ser ut som jag har ett meddelande.

319
00:19:46,000 --> 00:19:49,000
Det spelar ingen roll om någon läser vad som finns på papper flygplan innan jag fick det

320
00:19:49,000 --> 00:19:55,000
eftersom jag är den enda med den privata nyckeln.

321
00:19:55,000 --> 00:19:57,000
Låt oss dekryptera varje bitar i meddelandet.

322
00:19:57,000 --> 00:20:07,000
Den första bit, 658, höjer vi till d makten, vilket är 185,

323
00:20:07,000 --> 00:20:18,000
mod n, vilket är 989, är lika med 67,

324
00:20:18,000 --> 00:20:24,000
vilket är bokstaven C i ASCII.

325
00:20:24,000 --> 00:20:31,000
Nu, på den andra bit.

326
00:20:31,000 --> 00:20:35,000
Den andra bit har värdet 15,

327
00:20:35,000 --> 00:20:41,000
som vi höjer till 185. effekt,

328
00:20:41,000 --> 00:20:51,000
mod 989, och detta är lika med 83

329
00:20:51,000 --> 00:20:57,000
vilket är bokstaven S i ASCII.

330
00:20:57,000 --> 00:21:06,000
Nu för tredje bit, som har värdet 799, höjer vi till 185,

331
00:21:06,000 --> 00:21:17,000
mod 989, och detta är lika med 53,

332
00:21:17,000 --> 00:21:24,000
vilket är värdet av tecknet 5 i ASCII.

333
00:21:24,000 --> 00:21:30,000
Nu till den sista bit, som har värdet 975,

334
00:21:30,000 --> 00:21:41,000
Vi höjer till 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
och detta är lika med 48, vilket är värdet av tecknet 0 i ASCII.

336
00:21:51,000 --> 00:21:57,000
Mitt namn är Rob Bowden, och detta är CS50.

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

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

339
00:22:08,000 --> 00:22:14,000
RSA alls. [Skratt]

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