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
[Aquesta és CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Anem a fer una ullada a RSA, un algorisme utilitzat per xifrar dades.

5
00:00:11,000 --> 00:00:16,000
Els algorismes de xifrat com César i sistemes de xifrat Vigenère no són molt segures.

6
00:00:16,000 --> 00:00:20,000
Amb el xifrat César, un atacant només necessita tractar 25 diferents claus

7
00:00:20,000 --> 00:00:22,000
per obtenir text sense format del missatge.

8
00:00:22,000 --> 00:00:25,000
Mentre que el sistema de xifrat Vigenère és més segur que el xifrat César

9
00:00:25,000 --> 00:00:28,000
per l'espai de consulta ample per les claus, una vegada que un atacant

10
00:00:28,000 --> 00:00:30,000
coneix la longitud de la clau en un sistema de xifrat Vigenère,

11
00:00:30,000 --> 00:00:34,000
que es pot determinar a través d'una anàlisi dels patrons en el text xifrat,

12
00:00:34,000 --> 00:00:38,000
el xifrat Vigenère no és molt més segur que el xifrat César.

13
00:00:38,000 --> 00:00:42,000
RSA, d'altra banda, no és vulnerable als atacs d'aquest tipus.

14
00:00:42,000 --> 00:00:45,000
El xifrat César i xifrat Vigenère utilitzar la mateixa clau

15
00:00:45,000 --> 00:00:47,000
per xifrar i desxifrar un missatge.

16
00:00:47,000 --> 00:00:51,000
Aquesta propietat fa que aquests algorismes xifrats simètrics clau.

17
00:00:51,000 --> 00:00:54,000
Un problema fonamental amb algorismes de clau simètrica

18
00:00:54,000 --> 00:00:57,000
és que es basen en la codificació i l'enviament del missatge

19
00:00:57,000 --> 00:00:59,000
i el que rep i desxifra el missatge

20
00:00:59,000 --> 00:01:03,000
que ja han acordat per avançat en la clau que tots dos utilitzen.

21
00:01:03,000 --> 00:01:06,000
Però tenim una mica d'un problema d'inici aquí.

22
00:01:06,000 --> 00:01:10,000
Com dos equips que volen comunicar establir una clau secreta entre ells?

23
00:01:10,000 --> 00:01:16,000
Si la clau ha de ser secret, llavors necessitem una manera de xifrar i desxifrar la clau.

24
00:01:16,000 --> 00:01:18,000
Si tot el que tenim és la criptografia de clau simètrica

25
00:01:18,000 --> 00:01:21,000
llavors he tornat al mateix problema.

26
00:01:21,000 --> 00:01:25,000
RSA, d'altra banda, utilitza un parell de claus,

27
00:01:25,000 --> 00:01:28,000
una per encriptació i un altre per desencriptació.

28
00:01:28,000 --> 00:01:32,000
Un es diu la clau pública, i l'altre és la clau privada.

29
00:01:32,000 --> 00:01:34,000
La clau pública s'utilitza per xifrar missatges.

30
00:01:34,000 --> 00:01:38,000
Com es pot endevinar pel seu nom, podem compartir la nostra clau pública amb

31
00:01:38,000 --> 00:01:43,000
qualsevol persona que vulgui sense comprometre la seguretat d'un missatge xifrat.

32
00:01:43,000 --> 00:01:45,000
Els missatges xifrats amb una clau pública

33
00:01:45,000 --> 00:01:49,000
només es pot desxifrar amb la seva clau privada corresponent.

34
00:01:49,000 --> 00:01:53,000
Mentre que vostè pot compartir la seva clau pública, sempre s'ha de mantenir en secret la seva clau privada.

61
00:01:55,000 --> 00:01:58,000
i només la clau privada es pot utilitzar per desxifrar els missatges

62
00:01:58,000 --> 00:02:02,000
2 usuaris per enviar missatges de xifrat amb RSA

63
00:02:02,000 --> 00:02:07,000
d'anada i tornada els usuaris necessiten tenir el seu propi parell de claus pública i privada.

64
00:02:07,000 --> 00:02:10,000
Missatges d'usuari 1 a usuari 2

65
00:02:10,000 --> 00:02:15,000
només utilitzen parell de claus d'usuari 2, i els missatges d'usuari a usuari febrer 1

66
00:02:15,000 --> 00:02:17,000
només utilitzen un parell de claus d'usuari.

67
00:02:17,000 --> 00:02:21,000
El fet que hi ha 2 tecles separades per xifrar i desxifrar missatges

68
00:02:21,000 --> 00:02:24,000
RSA fa un algorisme de clau asimètrica.

69
00:02:24,000 --> 00:02:28,000
No necessitem per xifrar la clau pública amb la finalitat d'enviar a un altre ordinador

70
00:02:28,000 --> 00:02:31,000
ja que la clau pública és de totes maneres.

71
00:02:31,000 --> 00:02:33,000
Això vol dir que RSA no té el mateix problema d'inici

72
00:02:33,000 --> 00:02:36,000
com els algoritmes de clau simètrica.

73
00:02:36,000 --> 00:02:39,000
Així que si vull enviar un missatge utilitzant xifrat RSA

74
00:02:39,000 --> 00:02:42,000
a Rob, primer tindràs la clau pública de Rob.

75
00:02:42,000 --> 00:02:47,000
Per generar un parell de claus, Rob ha de triar dos nombres primers grans.

76
00:02:47,000 --> 00:02:50,000
Aquests números s'utilitzen tant en les claus públiques i privades,

77
00:02:50,000 --> 00:02:54,000
però la clau pública només s'utilitza el producte d'aquests números 2,

78
00:02:54,000 --> 00:02:56,000
no els números.

79
00:02:56,000 --> 00:02:59,000
Quan hagi xifrat el missatge amb la clau pública de Rob

80
00:02:59,000 --> 00:03:01,000
Puc enviar el missatge a Rob.

81
00:03:01,000 --> 00:03:05,000
Per a un equip, els números de factoring és un problema difícil.

82
00:03:05,000 --> 00:03:09,000
La clau pública, recorda, utilitza el producte de dos nombres primers.

83
00:03:09,000 --> 00:03:12,000
Aquest producte ha de tenir només 2 factors,

84
00:03:12,000 --> 00:03:16,000
que resulten ser els nombres que componen la clau privada.

85
00:03:16,000 --> 00:03:20,000
Per tal de desxifrar el missatge, RSA s'utilitza aquesta clau privada

86
00:03:20,000 --> 00:03:25,000
o els números multiplicats entre si en el procés de creació de la clau pública.

87
00:03:25,000 --> 00:03:28,000
Com que és computacionalment difícil factoritzar el nombre

88
00:03:28,000 --> 00:03:32,000
utilitzat en una clau pública en els 2 números utilitzats en la clau privada

89
00:03:32,000 --> 00:03:36,000
és difícil per a un atacant desxifrar la clau privada

90
00:03:36,000 --> 00:03:39,000
que serà necessari per desxifrar el missatge.

91
00:03:39,000 --> 00:03:43,000
Ara entrarem en alguns detalls de menor nivell de RSA.

92
00:03:43,000 --> 00:03:46,000
Primer veurem com podem generar un parell de claus.

93
00:03:46,000 --> 00:03:49,000
En primer lloc, anem a necessitar dos nombres primers.

94
00:03:49,000 --> 00:03:52,000
Anem a trucar a aquests números 2 p i q.

95
00:03:52,000 --> 00:03:56,000
Per tal de recollir p i q, en la pràctica seudoaleatoria generaria

96
00:03:56,000 --> 00:03:59,000
grans quantitats i aleshores utilitzar una prova per determinar si existeix o no

97
00:03:59,000 --> 00:04:02,000
aquests nombres són probablement millor moment.

98
00:04:02,000 --> 00:04:05,000
Podem mantenir la generació de nombres aleatoris i una altra

99
00:04:05,000 --> 00:04:08,000
fins que tinguem dos cosins que podem utilitzar.

100
00:04:08,000 --> 00:04:15,000
Aquí anem a escollir p = q = 23 i 43.

101
00:04:15,000 --> 00:04:19,000
Recordeu, a la pràctica, p i q ha de ser un nombre molt més gran.

102
00:04:19,000 --> 00:04:22,000
Pel que sabem, com més grans siguin els números, més difícil serà

103
00:04:22,000 --> 00:04:25,000
per trencar un missatge xifrat.

104
00:04:25,000 --> 00:04:29,000
Però també és més car per xifrar i desxifrar missatges.

105
00:04:29,000 --> 00:04:33,000
Avui dia és sovint es recomana que p i q són almenys 1024 bits,

106
00:04:33,000 --> 00:04:37,000
que posa a cada nombre en més de 300 dígits decimals.

107
00:04:37,000 --> 00:04:40,000
Però anem a recollir aquests petits nombres d'aquest exemple.

108
00:04:40,000 --> 00:04:43,000
Ara anem a multiplicar p i q en conjunt per obtenir un nombre de 3 º,

109
00:04:43,000 --> 00:04:45,000
que anomenarem n.

110
00:04:45,000 --> 00:04:55,000
En el nostre cas, n = 23 * 43, que = 989.

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

112
00:04:58,000 --> 00:05:02,000
A continuació multiplicar p - 1 amb q - 1

113
00:05:02,000 --> 00:05:05,000
per obtenir un nombre de quart, que anomenarem m.

114
00:05:05,000 --> 00:05:15,000
En el nostre cas, m = 22 * ​​42, que = 924.

115
00:05:15,000 --> 00:05:18,000
Comptem amb m = 924.

116
00:05:18,000 --> 00:05:22,000
Ara anem a necessitar un nombre i que és primer amb m

117
00:05:22,000 --> 00:05:25,000
i menys de m.

118
00:05:25,000 --> 00:05:28,000
Dos nombres són primers relatius o primers entre si,

119
00:05:28,000 --> 00:05:33,000
si el nombre enter únic positiu que els divideix de manera uniforme tant: 1.

120
00:05:33,000 --> 00:05:37,000
En altres paraules, el màxim comú divisor de i i m

121
00:05:37,000 --> 00:05:39,000
ha de ser 1.

122
00:05:39,000 --> 00:05:44,000
A la pràctica, és comú que i sigui el nombre primer 65537

123
00:05:44,000 --> 00:05:48,000
sempre que aquest nombre no passa de ser un factor de m.

124
00:05:48,000 --> 00:05:53,000
Per a les claus, anem a recollir i = 5

125
00:05:53,000 --> 00:05:57,000
ja que 5 és primer amb 924.

126
00:05:57,000 --> 00:06:01,000
Finalment, anem a necessitar un nombre més, que anomenarem d.

127
00:06:01,000 --> 00:06:11,000
D ha de ser un valor que satisfà l'equació de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Aquest mod m significa que farem servir una cosa anomenada aritmètica modular.

129
00:06:17,000 --> 00:06:21,000
En l'aritmètica modular, una vegada que rep un nombre més alt que algunes límit superior

130
00:06:21,000 --> 00:06:24,000
que baixés a 0.

131
00:06:24,000 --> 00:06:27,000
Un rellotge, per exemple, utilitza l'aritmètica modular.

132
00:06:27,000 --> 00:06:31,000
Un minut després de 1:59, per exemple, és 2:00,

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

134
00:06:33,000 --> 00:06:36,000
El minutera s'ha embolicat al voltant de 0

135
00:06:36,000 --> 00:06:39,000
en arribar a un límit superior de 60.

136
00:06:39,000 --> 00:06:46,000
Per tant, podem dir que 60 és equivalent a 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
i 125 és equivalent a 65 és equivalent a 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
La nostra clau pública serà el parell electrònic i núm

139
00:07:02,000 --> 00:07:09,000
on en aquest cas i és 5 i n a 989.

140
00:07:09,000 --> 00:07:15,000
La nostra clau privada serà el parell d i n,

141
00:07:15,000 --> 00:07:22,000
que en el nostre cas és de 185 i 989.

142
00:07:22,000 --> 00:07:25,000
Observi que el nostre original de nombres primers p i q no apareixen

143
00:07:25,000 --> 00:07:29,000
arreu de les nostres claus privades o públiques.

144
00:07:29,000 --> 00:07:33,000
Ara que tenim el nostre parell de claus, anem a fer una ullada a com podem xifrar

145
00:07:33,000 --> 00:07:36,000
i desxifrar un missatge.

146
00:07:36,000 --> 00:07:38,000
Vull enviar un missatge a Rob,

147
00:07:38,000 --> 00:07:42,000
pel que serà el de generar aquest parell de claus.

148
00:07:42,000 --> 00:07:46,000
Llavors vaig a demanar Rob la seva clau pública, que utilitzaré

149
00:07:46,000 --> 00:07:48,000
per xifrar un missatge per enviar a ell.

150
00:07:48,000 --> 00:07:53,000
Recorda, és totalment acceptable per Rob per compartir la seva clau pública amb mi.

151
00:07:53,000 --> 00:07:56,000
Però no estaria bé compartir la seva clau privada.

152
00:07:56,000 --> 00:08:00,000
No tinc ni idea del que la seva clau privada.

153
00:08:00,000 --> 00:08:03,000
Podem dividir el nostre missatge m cap amunt en diversos trossos

154
00:08:03,000 --> 00:08:07,000
tot menor que n i després encriptar cada un dels trossos.

155
00:08:07,000 --> 00:08:12,000
Anem a xifrar la cadena CS50, que podem dividir en 4 trossos,

156
00:08:12,000 --> 00:08:14,000
un per cada lletra.

157
00:08:14,000 --> 00:08:17,000
Per xifrar el missatge, vaig a haver de convertir-lo en

158
00:08:17,000 --> 00:08:20,000
algun tipus de representació numèrica.

159
00:08:20,000 --> 00:08:25,000
Anem a concatenar els valors ASCII amb els personatges del meu missatge.

160
00:08:25,000 --> 00:08:28,000
Per tal de xifrar un missatge donat m

161
00:08:28,000 --> 00:08:37,000
Vaig a haver de calcular c = ma l'E (mod n).

162
00:08:37,000 --> 00:08:40,000
Però m ha de ser menor que n,

163
00:08:40,000 --> 00:08:45,000
o bé el missatge complet no pot ser expressat mòdul núm.

164
00:08:45,000 --> 00:08:49,000
Podem trencar m fins a diversos trossos, tots els quals són més petites que n,

165
00:08:49,000 --> 00:08:52,000
i xifrar cada un dels trossos.

166
00:08:52,000 --> 00:09:03,000
Xifrat de cada un d'aquests trossos, obtenim c1 = 67 a la 5 (mod 989)

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

168
00:09:06,000 --> 00:09:15,000
Per al nostre segon fragment que tenim 83 a la 5 (mod 989)

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

170
00:09:18,000 --> 00:09:26,000
Per al nostre tros 3 tenim 53 a la 5 (mod 989)

171
00:09:26,000 --> 00:09:30,000
que és = 799.

172
00:09:30,000 --> 00:09:39,000
I finalment, per al nostre tros fi tenim 48 a la 5 (mod 989)

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

174
00:09:43,000 --> 00:09:48,000
Ara podem enviar a través d'aquests valors xifrats a Rob.

175
00:09:54,000 --> 00:09:58,000
Aquí tens, Rob.

176
00:09:58,000 --> 00:10:01,000
Mentre que el nostre missatge està en vol, anem a fer un altre cop d'ull

177
00:10:01,000 --> 00:10:07,000
en com hem arribat fins a aquest valor per d.

178
00:10:07,000 --> 00:10:17,000
El nostre número d necessària per satisfer 5d = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
Això fa que d l'invers multiplicatiu de 5 mòdul 924.

180
00:10:24,000 --> 00:10:28,000
Atès 2 sencers, A i B, l'algorisme d'Euclides estès

181
00:10:28,000 --> 00:10:33,000
es pot utilitzar per trobar el màxim comú divisor d'aquests 2 nombres enters.

182
00:10:33,000 --> 00:10:37,000
També ens donen 2 altres números, x i i,

183
00:10:37,000 --> 00:10:47,000
que satisfan l'equació ax + by = el màxim comú divisor de a i b.

184
00:10:47,000 --> 00:10:49,000
Com ens ajuda?

185
00:10:49,000 --> 00:10:52,000
Bé, connectar i = 5 per a una

186
00:10:52,000 --> 00:10:56,000
i m = 924 per b

187
00:10:56,000 --> 00:10:59,000
ja sabem que aquests nombres són primers entre si.

188
00:10:59,000 --> 00:11:03,000
El seu màxim comú divisor és 1.

189
00:11:03,000 --> 00:11:09,000
Això ens dóna 5x + 924y = 1

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

191
00:11:17,000 --> 00:11:22,000
Però si només es preocupen per tot mòdul 924

192
00:11:22,000 --> 00:11:25,000
llavors podem abandonar la - 924y.

193
00:11:25,000 --> 00:11:27,000
Penseu en el rellotge.

194
00:11:27,000 --> 00:11:31,000
Si el minuter està en 1 i després passar exactament 10 hores,

195
00:11:31,000 --> 00:11:35,000
sabem que la maneta dels minuts encara serà al 1.

196
00:11:35,000 --> 00:11:39,000
Aquí comencem a 1 i després embolicar vegades exactament de i,

197
00:11:39,000 --> 00:11:41,000
de manera que encara estarà en 1.

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

199
00:11:49,000 --> 00:11:55,000
I aquí aquesta x és el mateix que el d buscàvem abans,

200
00:11:55,000 --> 00:11:58,000
pel que si s'utilitza l'algorisme d'Euclides estès

201
00:11:58,000 --> 00:12:04,000
per obtenir aquest nombre x, que és el número que ha d'usar com el nostre d.

202
00:12:04,000 --> 00:12:07,000
Ara anem a executar l'algorisme estès d'Euclides per a = 5

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

204
00:12:11,000 --> 00:12:14,000
Utilitzarem un mètode anomenat mètode de la taula.

205
00:12:14,000 --> 00:12:21,000
La taula comptarà amb 4 columnes, x, i, d, k.

206
00:12:21,000 --> 00:12:23,000
La nostra taula comença amb 2 files.

207
00:12:23,000 --> 00:12:28,000
A la primera fila tenim 1, 0, llavors el nostre valor de a, que és 5,

208
00:12:28,000 --> 00:12:37,000
i la nostra segona fila és 0, 1, i el nostre valor de b, que és 924.

209
00:12:37,000 --> 00:12:40,000
El valor de la columna quarta, k, és el resultat

210
00:12:40,000 --> 00:12:45,000
de dividir el valor de d a la fila de dalt amb el valor de d

211
00:12:45,000 --> 00:12:49,000
en la mateixa fila.

212
00:12:49,000 --> 00:12:56,000
Tenim 5 dividit per 924 és 0 amb alguna resta.

213
00:12:56,000 --> 00:12:59,000
Això vol dir que tenim k = 0.

214
00:12:59,000 --> 00:13:05,000
Ara el valor de totes les altres cèl · lules és el valor de la cel · la 2 files per sobre del

215
00:13:05,000 --> 00:13:09,000
menys el valor de la fila per sobre d'ella k vegades.

216
00:13:09,000 --> 00:13:11,000
Anem a començar amb d en la 3 ª fila.

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

218
00:13:19,000 --> 00:13:25,000
Següent Tenim 0 - 1 * 0 que és 0

219
00:13:25,000 --> 00:13:30,000
i 1 - 0 * 0 que és 1.

220
00:13:30,000 --> 00:13:33,000
No està malament, així que passarem a la següent fila.

221
00:13:33,000 --> 00:13:36,000
En primer lloc tenim el nostre valor de k.

222
00:13:36,000 --> 00:13:43,000
924 dividit per 5 = 184 amb alguna resta,

223
00:13:43,000 --> 00:13:46,000
pel que el nostre valor de k és 184.

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

225
00:13:54,000 --> 00:14:05,000
1-0 * 184 és 1 i 0 - 1 * 184 és -184.

226
00:14:05,000 --> 00:14:07,000
Molt bé, farem la següent fila.

227
00:14:07,000 --> 00:14:10,000
El nostre valor de k serà 1 perquè

228
00:14:10,000 --> 00:14:15,000
5 dividit per 4 = 1 amb alguna resta.

229
00:14:15,000 --> 00:14:17,000
Anem a omplir les altres columnes.

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
I 1-184 * 1 és de 185.

233
00:14:33,000 --> 00:14:35,000
Anem a veure el que el nostre següent valor de k seria.

234
00:14:35,000 --> 00:14:40,000
Bé, sembla que tenim 4 dividit per 1, que és 4.

235
00:14:40,000 --> 00:14:43,000
En aquest cas en el qual estem dividint per 1 tal que k és igual a

236
00:14:43,000 --> 00:14:50,000
el valor de d a la fila de dalt vol dir que hem acabat amb el nostre algorisme.

237
00:14:50,000 --> 00:14:58,000
Podem veure aquí que tenim x = 185 iy = -1 en l'última fila.

238
00:14:58,000 --> 00:15:00,000
Ara anem a tornar a la nostra meta original.

239
00:15:00,000 --> 00:15:04,000
Hem dit que el valor de x, com a resultat de l'execució d'aquest algorisme

240
00:15:04,000 --> 00:15:08,000
seria l'invers multiplicatiu d'un (b mod).

241
00:15:08,000 --> 00:15:15,000
Això vol dir que 185 és l'invers multiplicatiu de 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
el que significa que tenen un valor de 185 per d.

243
00:15:20,000 --> 00:15:23,000
El fet que d = 1 en l'última fila

244
00:15:23,000 --> 00:15:26,000
verifica que el correu va ser primers entre si a m.

245
00:15:26,000 --> 00:15:30,000
Si no fos 1, llavors hauríem de triar un correu nou.

246
00:15:30,000 --> 00:15:33,000
Ara veurem si Rob ha rebut el meu missatge.

247
00:15:33,000 --> 00:15:35,000
Quan algú m'envia un missatge xifrat

248
00:15:35,000 --> 00:15:38,000
sempre que he mantingut la meva clau privada en secret

249
00:15:38,000 --> 00:15:41,000
Jo sóc l'única persona que pot desxifrar el missatge.

250
00:15:41,000 --> 00:15:46,000
Per desxifrar un tros c puc calcular el missatge original

251
00:15:46,000 --> 00:15:53,000
és igual a la quantitat de potència d (mod n).

252
00:15:53,000 --> 00:15:57,000
Recordeu que d i n són de la meva clau privada.

253
00:15:57,000 --> 00:16:01,000
Per obtenir un missatge ple dels seus fragments de desxifrar cada bloc

254
00:16:01,000 --> 00:16:04,000
i concatenar els resultats.

255
00:16:04,000 --> 00:16:08,000
Exactament què tan segur és RSA?

256
00:16:08,000 --> 00:16:10,000
La veritat és que no ho sé.

257
00:16:10,000 --> 00:16:14,000
La seguretat es basa en el temps que li prendria a un atacant desxifrar un missatge

258
00:16:14,000 --> 00:16:16,000
encriptada amb RSA.

259
00:16:16,000 --> 00:16:19,000
Recordeu que un atacant té accés a la seva clau pública,

260
00:16:19,000 --> 00:16:21,000
que conté tant i i n.

261
00:16:21,000 --> 00:16:26,000
Si l'atacant aconsegueix factoritzar n en els seus 2 cosins, p i q,

262
00:16:26,000 --> 00:16:30,000
llavors podria calcular d usant el algorisme d'Euclides estès.

263
00:16:30,000 --> 00:16:35,000
Això li dóna la clau privada, que es pot utilitzar per desxifrar qualsevol missatge.

264
00:16:35,000 --> 00:16:38,000
Però la rapidesa podem factoritzar sencers?

265
00:16:38,000 --> 00:16:41,000
Un cop més, no ho sé.

266
00:16:41,000 --> 00:16:43,000
Ningú ha trobat una manera ràpida de fer-ho,

267
00:16:43,000 --> 00:16:46,000
el que significa que donat n prou gran

268
00:16:46,000 --> 00:16:49,000
que portaria a un atacant irrealment llarg

269
00:16:49,000 --> 00:16:51,000
factoritzar el nombre.

270
00:16:51,000 --> 00:16:54,000
Si algú revela una forma ràpida de factoritzar sencers

271
00:16:54,000 --> 00:16:57,000
RSA es trencaria.

272
00:16:57,000 --> 00:17:01,000
Però fins i tot si factorització d'enters és inherentment lent

273
00:17:01,000 --> 00:17:04,000
l'algoritme RSA encara podria tenir algun defecte-hi

274
00:17:04,000 --> 00:17:07,000
que permet la fàcil desxifrat de missatges.

275
00:17:07,000 --> 00:17:10,000
Ningú ha trobat i revela una falla, però,

276
00:17:10,000 --> 00:17:12,000
però això no vol dir que no n'hi ha un.

277
00:17:12,000 --> 00:17:17,000
En teoria, algú podria estar per aquí llegint totes les dades xifrades amb RSA.

278
00:17:17,000 --> 00:17:19,000
Hi ha una mica d'un problema de privacitat.

279
00:17:19,000 --> 00:17:23,000
Si Tommy encripta algun missatge amb el meu clau pública

280
00:17:23,000 --> 00:17:26,000
i un atacant xifra el missatge mateix amb la meva clau pública

281
00:17:26,000 --> 00:17:29,000
l'atacant es veurà que els dos missatges són idèntics

282
00:17:29,000 --> 00:17:32,000
i així saber el que Tommy xifrat.

283
00:17:32,000 --> 00:17:36,000
Per tal d'evitar això, els missatges són típicament emplenat amb bits aleatoris

284
00:17:36,000 --> 00:17:39,000
abans de ser xifrats perquè el mateix missatge xifrat

285
00:17:39,000 --> 00:17:44,000
múltiples vegades serà diferent, sempre que el farciment en el missatge és diferent.

286
00:17:44,000 --> 00:17:47,000
Però recorda com hem de dividir els missatges en trossos

287
00:17:47,000 --> 00:17:50,000
de manera que cada fragment és menor que n?

288
00:17:50,000 --> 00:17:52,000
Farciment els trossos vol dir que haguem de dividir les coses

289
00:17:52,000 --> 00:17:57,000
en trossos encara més des del tros encoixinat ha de ser menor que n.

290
00:17:57,000 --> 00:18:01,000
El xifrat i desxifrat són relativament cars amb RSA,

291
00:18:01,000 --> 00:18:05,000
i per tant necessitat de trencar un missatge en trossos molts pot ser molt costós.

292
00:18:05,000 --> 00:18:09,000
Si un gran volum de dades ha de ser xifrats i desxifrats

293
00:18:09,000 --> 00:18:12,000
podem combinar els beneficis d'algorismes de clau simètrica

294
00:18:12,000 --> 00:18:16,000
amb els de RSA per obtenir la seguretat i l'eficiència.

295
00:18:16,000 --> 00:18:18,000
Encara que no vaig a entrar-hi aquí,

296
00:18:18,000 --> 00:18:23,000
AES és un algorisme de clau simètrica com el xifrat Vigenère i César

297
00:18:23,000 --> 00:18:25,000
però molt més difícil de rosegar.

298
00:18:25,000 --> 00:18:30,000
Per descomptat, no podem usar AES sense establir una clau secreta compartida

299
00:18:30,000 --> 00:18:34,000
entre els 2 sistemes i vam veure el problema amb això abans.

300
00:18:34,000 --> 00:18:40,000
Però ara podem utilitzar RSA per establir la clau secreta compartida entre els 2 sistemes.

301
00:18:40,000 --> 00:18:43,000
Anomenarem a l'ordinador que envia les dades del remitent

302
00:18:43,000 --> 00:18:46,000
i l'equip que rep les dades del receptor.

303
00:18:46,000 --> 00:18:49,000
El receptor té un parell de claus RSA i envia

304
00:18:49,000 --> 00:18:51,000
la clau pública al remitent.

305
00:18:51,000 --> 00:18:54,000
L'emissor genera una clau d'AES,

306
00:18:54,000 --> 00:18:57,000
xifra amb la clau pública RSA del receptor,

307
00:18:57,000 --> 00:19:00,000
i envia la clau AES per al receptor.

308
00:19:00,000 --> 00:19:04,000
El receptor desxifra el missatge amb la seva clau privada RSA.

309
00:19:04,000 --> 00:19:09,000
Tant l'emissor com el receptor tenen ara una clau compartida AES entre ells.

310
00:19:09,000 --> 00:19:14,000
AES, que és molt més ràpid en el xifrat i desxifrat de RSA,

311
00:19:14,000 --> 00:19:18,000
Ara es pot utilitzar per a xifrar les grans volums de dades i enviar-los al receptor,

312
00:19:18,000 --> 00:19:21,000
que pot desxifrar utilitzant la mateixa clau.

313
00:19:21,000 --> 00:19:26,000
AES, que és molt més ràpid en el xifrat i desxifrat de RSA,

314
00:19:26,000 --> 00:19:30,000
Ara es pot utilitzar per a xifrar les grans volums de dades i enviar-los al receptor,

315
00:19:30,000 --> 00:19:32,000
que pot desxifrar utilitzant la mateixa clau.

316
00:19:32,000 --> 00:19:36,000
Només necessitàvem RSA per transferir la clau compartida.

317
00:19:36,000 --> 00:19:40,000
Ja no necessita utilitzar RSA en absolut.

318
00:19:40,000 --> 00:19:46,000
Sembla que tinc un missatge.

319
00:19:46,000 --> 00:19:49,000
Tant se val si algú llegeix el que hi ha a l'avió de paper abans que em va cridar

320
00:19:49,000 --> 00:19:55,000
perquè jo sóc l'únic que té la clau privada.

321
00:19:55,000 --> 00:19:57,000
Anem a desxifrar cada un dels trossos en el missatge.

322
00:19:57,000 --> 00:20:07,000
El primer tros, 658, elevem a la potència d, que és de 185,

323
00:20:07,000 --> 00:20:18,000
mod n, que a 989, és igual a 67,

324
00:20:18,000 --> 00:20:24,000
que és la lletra C en ASCII.

325
00:20:24,000 --> 00:20:31,000
Ara, en el segon fragment.

326
00:20:31,000 --> 00:20:35,000
El segon fragment té un valor 15,

327
00:20:35,000 --> 00:20:41,000
que elevem a la potència 185,

328
00:20:41,000 --> 00:20:51,000
mod 989, i això és igual a 83

329
00:20:51,000 --> 00:20:57,000
que és la lletra S en ASCII.

330
00:20:57,000 --> 00:21:06,000
Ja pel tros tercer, que té un valor 799, elevem a 185,

331
00:21:06,000 --> 00:21:17,000
mod 989, i això és igual a 53,

332
00:21:17,000 --> 00:21:24,000
que és el valor del caràcter ASCII en 5.

333
00:21:24,000 --> 00:21:30,000
Ara, per a l'últim fragment, que té un valor 975,

334
00:21:30,000 --> 00:21:41,000
elevem a 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
i això és igual a 48, que és el valor de 0 en el caràcter ASCII.

336
00:21:51,000 --> 00:21:57,000
El meu nom és Rob Bowden, i això és CS50.

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

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

339
00:22:08,000 --> 00:22:14,000
RSA en absolut. [Rialles]

340
00:22:14,000 --> 00:22:17,000
En totes.