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
[Questo è CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Diamo un'occhiata a RSA, un algoritmo ampiamente utilizzato per la crittografia dei dati.

5
00:00:11,000 --> 00:00:16,000
Gli algoritmi di crittografia come Cesare e Vigenère cifre non sono molto sicuro.

6
00:00:16,000 --> 00:00:20,000
Con il cifrario di Cesare, un attaccante ha solo bisogno di provare 25 tasti diversi

7
00:00:20,000 --> 00:00:22,000
per ottenere testo normale del messaggio.

8
00:00:22,000 --> 00:00:25,000
Mentre il cifrario Vigenère è più sicuro del cifrario di Cesare

9
00:00:25,000 --> 00:00:28,000
a causa dello spazio di ricerca più grande per le chiavi, una volta che un utente malintenzionato

10
00:00:28,000 --> 00:00:30,000
conosce la lunghezza della chiave in un cifrario Vigenère,

11
00:00:30,000 --> 00:00:34,000
che può essere determinata mediante l'analisi del pattern nel testo cifrato,

12
00:00:34,000 --> 00:00:38,000
il cifrario Vigenère non è molto più sicuro del cifrario di Cesare.

13
00:00:38,000 --> 00:00:42,000
RSA, d'altra parte, non è vulnerabile agli attacchi come questo.

14
00:00:42,000 --> 00:00:45,000
Il cifrario di Cesare e Vigenère cifratura utilizzare la stessa chiave

15
00:00:45,000 --> 00:00:47,000
per crittografare e decrittografare un messaggio.

16
00:00:47,000 --> 00:00:51,000
Questa proprietà rende questi algoritmi a chiave simmetrica cifrari.

17
00:00:51,000 --> 00:00:54,000
Un problema fondamentale con algoritmi a chiave simmetrica

18
00:00:54,000 --> 00:00:57,000
è che si basano su quello cifratura e l'invio del messaggio

19
00:00:57,000 --> 00:00:59,000
e quella ricevente e decifrare il messaggio

20
00:00:59,000 --> 00:01:03,000
di aver già concordato in anticipo sul tasto essi useranno i.

21
00:01:03,000 --> 00:01:06,000
Ma noi abbiamo un po 'di un problema di avvio qui.

22
00:01:06,000 --> 00:01:10,000
Come 2 computer che vogliono comunicare stabilire una chiave segreta tra di loro?

23
00:01:10,000 --> 00:01:16,000
Se la chiave deve essere segreta, quindi abbiamo bisogno di un modo per crittografare e decrittografare la chiave.

24
00:01:16,000 --> 00:01:18,000
Se tutto quello che abbiamo è crittografia a chiave simmetrica

25
00:01:18,000 --> 00:01:21,000
allora abbiamo appena tornati allo stesso problema.

26
00:01:21,000 --> 00:01:25,000
RSA, invece, utilizza una coppia di chiavi,

27
00:01:25,000 --> 00:01:28,000
uno per la crittografia e la decrittografia per un'altra.

28
00:01:28,000 --> 00:01:32,000
Una è chiamata la chiave pubblica, e l'altra è la chiave privata.

29
00:01:32,000 --> 00:01:34,000
La chiave pubblica viene utilizzata per crittografare i messaggi.

30
00:01:34,000 --> 00:01:38,000
Come si può intuire dal suo nome, possiamo condividere la nostra chiave pubblica con

31
00:01:38,000 --> 00:01:43,000
chiunque vogliamo senza compromettere la sicurezza di un messaggio crittografato.

32
00:01:43,000 --> 00:01:45,000
I messaggi crittografati utilizzando una chiave pubblica

33
00:01:45,000 --> 00:01:49,000
possono essere decifrati solo con la sua chiave privata corrispondente.

34
00:01:49,000 --> 00:01:53,000
Mentre è possibile condividere la vostra chiave pubblica, si dovrebbe sempre mantenere il vostro segreto della chiave privata.

61
00:01:55,000 --> 00:01:58,000
e solo la chiave privata può essere usata per decifrare messaggi

62
00:01:58,000 --> 00:02:02,000
se 2 utenti desidera inviare i messaggi crittografati con RSA

63
00:02:02,000 --> 00:02:07,000
avanti e indietro entrambi gli utenti hanno bisogno di avere la propria coppia di chiavi pubblica e privata.

64
00:02:07,000 --> 00:02:10,000
Messaggi da utente 1 a utente 2

65
00:02:10,000 --> 00:02:15,000
utilizzare solo coppia di chiavi 2 utente, e messaggi da utente a utente 1 2

66
00:02:15,000 --> 00:02:17,000
utilizzare solo coppia di chiavi dell'utente di 1.

67
00:02:17,000 --> 00:02:21,000
Il fatto che ci sono 2 tasti separati per crittografare e decrittografare i messaggi

68
00:02:21,000 --> 00:02:24,000
RSA fa un algoritmo a chiave asimmetrica.

69
00:02:24,000 --> 00:02:28,000
Non abbiamo bisogno per crittografare la chiave pubblica, al fine di inviarlo a un altro computer

70
00:02:28,000 --> 00:02:31,000
dato che la chiave pubblica è in ogni caso.

71
00:02:31,000 --> 00:02:33,000
Ciò significa che RSA non ha lo stesso problema di avvio

72
00:02:33,000 --> 00:02:36,000
come gli algoritmi della chiave simmetrica.

73
00:02:36,000 --> 00:02:39,000
Quindi, se voglio inviare un messaggio utilizzando la crittografia RSA

74
00:02:39,000 --> 00:02:42,000
a Rob, io per prima cosa bisogno di chiave pubblica di Rob.

75
00:02:42,000 --> 00:02:47,000
Per generare una coppia di chiavi, Rob deve scegliere 2 numeri primi elevati.

76
00:02:47,000 --> 00:02:50,000
Questi numeri saranno utilizzati in entrambe le chiavi pubbliche e private,

77
00:02:50,000 --> 00:02:54,000
ma la chiave pubblica utilizza solo il prodotto di questi due numeri,

78
00:02:54,000 --> 00:02:56,000
Non gli stessi numeri.

79
00:02:56,000 --> 00:02:59,000
Una volta che ho criptato il messaggio usando la chiave pubblica di Rob

80
00:02:59,000 --> 00:03:01,000
Posso inviare il messaggio a Rob.

81
00:03:01,000 --> 00:03:05,000
Per un computer, i numeri di factoring è un problema difficile.

82
00:03:05,000 --> 00:03:09,000
La chiave pubblica, lo ricordiamo, ha utilizzato il prodotto di 2 numeri primi.

83
00:03:09,000 --> 00:03:12,000
Questo prodotto deve quindi avere solo 2 fattori,

84
00:03:12,000 --> 00:03:16,000
che capita di essere i numeri che compongono la chiave privata.

85
00:03:16,000 --> 00:03:20,000
Per decifrare il messaggio, RSA userà la chiave privata

86
00:03:20,000 --> 00:03:25,000
oppure i numeri moltiplicati insieme nel processo di creazione della chiave pubblica.

87
00:03:25,000 --> 00:03:28,000
Perché è computazionalmente difficile fattorizzare il numero

88
00:03:28,000 --> 00:03:32,000
utilizzato in una chiave pubblica nelle due numeri usati per la chiave privata

89
00:03:32,000 --> 00:03:36,000
è difficile per un utente malintenzionato di capire la chiave privata

90
00:03:36,000 --> 00:03:39,000
che sarà necessario per decifrare il messaggio.

91
00:03:39,000 --> 00:03:43,000
Ora andiamo in alcuni dettagli a basso livello della RSA.

92
00:03:43,000 --> 00:03:46,000
Si deve prima vedere come possiamo generare una coppia di chiavi.

93
00:03:46,000 --> 00:03:49,000
In primo luogo, abbiamo bisogno di due numeri primi.

94
00:03:49,000 --> 00:03:52,000
Chiameremo questi 2 numeri p e q.

95
00:03:52,000 --> 00:03:56,000
Al fine di scegliere p e q, in pratica ci pseudorandomly generare

96
00:03:56,000 --> 00:03:59,000
grandi numeri e quindi utilizzare un test per determinare se

97
00:03:59,000 --> 00:04:02,000
questi numeri sono probabilmente primo.

98
00:04:02,000 --> 00:04:05,000
Possiamo mantenere la generazione di numeri casuali ripetutamente

99
00:04:05,000 --> 00:04:08,000
fino a quando abbiamo 2 numeri primi che possiamo utilizzare.

100
00:04:08,000 --> 00:04:15,000
Qui Riprendiamo p = 23 e q = 43.

101
00:04:15,000 --> 00:04:19,000
Ricordare, in pratica, p e q devono essere numeri molto più grandi.

102
00:04:19,000 --> 00:04:22,000
Per quanto ne sappiamo, più grandi i numeri, più difficile è

103
00:04:22,000 --> 00:04:25,000
per rompere un messaggio cifrato.

104
00:04:25,000 --> 00:04:29,000
Ma è anche più costoso per crittografare e decrittografare i messaggi.

105
00:04:29,000 --> 00:04:33,000
Oggi è spesso raccomandato che p e q sono almeno 1024 bit,

106
00:04:33,000 --> 00:04:37,000
che mette ogni numero a più di 300 cifre decimali.

107
00:04:37,000 --> 00:04:40,000
Ma ci prendono questi piccoli numeri per questo esempio.

108
00:04:40,000 --> 00:04:43,000
Ora si moltiplicano p e q insieme per ottenere un numero di 3 °,

109
00:04:43,000 --> 00:04:45,000
che chiameremo n.

110
00:04:45,000 --> 00:04:55,000
Nel nostro caso, n = 23 * 43, che = 989.

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

112
00:04:58,000 --> 00:05:02,000
Avanti ci moltiplichiamo p - 1 con q - 1

113
00:05:02,000 --> 00:05:05,000
per ottenere un 4 ° numero, che chiameremo m.

114
00:05:05,000 --> 00:05:15,000
Nel nostro caso, m = 22 * ​​42 = 924 che.

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

116
00:05:18,000 --> 00:05:22,000
Ora abbiamo bisogno di un numero e che è relativamente primo a m

117
00:05:22,000 --> 00:05:25,000
e meno di m.

118
00:05:25,000 --> 00:05:28,000
Due numeri sono primi fra loro o coprimi

119
00:05:28,000 --> 00:05:33,000
se il solo numeri interi positivi che li divide entrambi in modo uniforme è 1.

120
00:05:33,000 --> 00:05:37,000
In altre parole, il massimo comun divisore di e ed m

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

122
00:05:39,000 --> 00:05:44,000
In pratica, è comune per l'e di essere il numero primo 65537

123
00:05:44,000 --> 00:05:48,000
purché tale numero non capita di essere un fattore di m.

124
00:05:48,000 --> 00:05:53,000
Per le nostre chiavi, ne sceglieremo e = 5

125
00:05:53,000 --> 00:05:57,000
dal 5 è primo a 924.

126
00:05:57,000 --> 00:06:01,000
Infine, abbiamo bisogno di un numero maggiore, che chiameremo d.

127
00:06:01,000 --> 00:06:11,000
D deve essere un valore che soddisfa l'equazione de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Questo m mod significa che useremo una cosa chiamata aritmetica modulare.

129
00:06:17,000 --> 00:06:21,000
In aritmetica modulare, una volta ottiene un numero maggiore di qualche limite superiore

130
00:06:21,000 --> 00:06:24,000
andrà a capo indietro intorno a 0.

131
00:06:24,000 --> 00:06:27,000
Un orologio, per esempio, utilizza l'aritmetica modulare.

132
00:06:27,000 --> 00:06:31,000
Un minuto dopo 1:59, per esempio, è 2:00,

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

134
00:06:33,000 --> 00:06:36,000
La lancetta dei minuti si è avvolto intorno a 0

135
00:06:36,000 --> 00:06:39,000
al raggiungimento di un limite superiore di 60.

136
00:06:39,000 --> 00:06:46,000
Quindi, possiamo dire che 60 è equivalente a 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
e 125 è equivalente a 65 è equivalente a 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
La nostra chiave pubblica sarà l'indirizzo e coppia e n

139
00:07:02,000 --> 00:07:09,000
dove in questo caso e è 5 e n ​​è 989.

140
00:07:09,000 --> 00:07:15,000
La nostra chiave privata sarà la coppia d ed n,

141
00:07:15,000 --> 00:07:22,000
che nel nostro caso è di 185 e 989.

142
00:07:22,000 --> 00:07:25,000
Si noti che il nostro originale numeri primi p e q non appaiono

143
00:07:25,000 --> 00:07:29,000
in tutto le nostre chiavi pubbliche o private.

144
00:07:29,000 --> 00:07:33,000
Ora che abbiamo la nostra coppia di chiavi, diamo un'occhiata a come siamo in grado di crittografare

145
00:07:33,000 --> 00:07:36,000
e decifrare un messaggio.

146
00:07:36,000 --> 00:07:38,000
Voglio mandare un messaggio a Rob,

147
00:07:38,000 --> 00:07:42,000
così sarà quello di generare questa coppia di chiavi.

148
00:07:42,000 --> 00:07:46,000
Poi mi chiedo Rob per la sua chiave pubblica, che userò

149
00:07:46,000 --> 00:07:48,000
per cifrare un messaggio da inviare a lui.

150
00:07:48,000 --> 00:07:53,000
Ricordate, è tutto a posto per Rob a condividere la sua chiave pubblica con me.

151
00:07:53,000 --> 00:07:56,000
Ma non sarebbe giusto da condividere la sua chiave privata.

152
00:07:56,000 --> 00:08:00,000
Non ho idea di quale sia la sua chiave privata è.

153
00:08:00,000 --> 00:08:03,000
Siamo in grado di rompere il nostro messaggio m in parti diverse

154
00:08:03,000 --> 00:08:07,000
tutto più piccolo di n e quindi crittografare ciascuno di questi pezzi.

155
00:08:07,000 --> 00:08:12,000
Ci crittografare la CS50 stringa, che siamo in grado di spezzare in 4 pezzi,

156
00:08:12,000 --> 00:08:14,000
uno per ogni lettera.

157
00:08:14,000 --> 00:08:17,000
Per crittografare il mio messaggio, ho bisogno di convertirlo in

158
00:08:17,000 --> 00:08:20,000
qualche tipo di rappresentazione numerica.

159
00:08:20,000 --> 00:08:25,000
Facciamo concatenare i valori ASCII con i personaggi del mio messaggio.

160
00:08:25,000 --> 00:08:28,000
Per cifrare un messaggio m dato

161
00:08:28,000 --> 00:08:37,000
Ho bisogno di calcolare c = m all'indirizzo e (mod n).

162
00:08:37,000 --> 00:08:40,000
M ma deve essere minore di n,

163
00:08:40,000 --> 00:08:45,000
oppure il messaggio completo non può essere espresso modulo n.

164
00:08:45,000 --> 00:08:49,000
Possiamo rompere m in parti diverse, che sono tutti minore di n,

165
00:08:49,000 --> 00:08:52,000
e criptare ciascuno di questi pezzi.

166
00:08:52,000 --> 00:09:03,000
Crittografia ognuno di questi blocchi, si ottiene c1 = 67 alla 5 (mod 989)

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

168
00:09:06,000 --> 00:09:15,000
Per il nostro secondo blocco abbiamo 83 al 5 (mod 989)

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

170
00:09:18,000 --> 00:09:26,000
Per il nostro terzo pezzo abbiamo 53 alla 5 (mod 989)

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

172
00:09:30,000 --> 00:09:39,000
E, infine, per il nostro ultimo blocco abbiamo 48 al 5 (mod 989)

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

174
00:09:43,000 --> 00:09:48,000
Ora siamo in grado di inviare più di questi valori crittografati a Rob.

175
00:09:54,000 --> 00:09:58,000
Ecco a te, Rob.

176
00:09:58,000 --> 00:10:01,000
Anche se il nostro messaggio è in volo, diamo un altro sguardo

177
00:10:01,000 --> 00:10:07,000
il modo in cui abbiamo ottenuto che il valore per d.

178
00:10:07,000 --> 00:10:17,000
Il nostro numero d necessaria per soddisfare 5d = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
Questo rende d l'inverso moltiplicativo di 5 modulo 924.

180
00:10:24,000 --> 00:10:28,000
Dato 2 numeri interi, A e B, l'algoritmo euclideo esteso

181
00:10:28,000 --> 00:10:33,000
può essere usato per trovare il massimo comun divisore di questi 2 numeri interi.

182
00:10:33,000 --> 00:10:37,000
Essa ci darà anche due altri numeri, x e y,

183
00:10:37,000 --> 00:10:47,000
che soddisfano l'equazione ax + by = il massimo comun divisore di a e b.

184
00:10:47,000 --> 00:10:49,000
In che modo questo ci aiuta?

185
00:10:49,000 --> 00:10:52,000
Be ', di collegare e = 5 per un

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

187
00:10:56,000 --> 00:10:59,000
sappiamo già che questi numeri sono coprimi.

188
00:10:59,000 --> 00:11:03,000
Il loro massimo comun divisore è 1.

189
00:11:03,000 --> 00:11:09,000
Questo ci dà 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
Ma se ci interessa solo tutto modulo 924

192
00:11:22,000 --> 00:11:25,000
allora possiamo cadere il - 924y.

193
00:11:25,000 --> 00:11:27,000
Ripensa al clock.

194
00:11:27,000 --> 00:11:31,000
Se la lancetta dei minuti è il 1 ° e quindi esattamente 10 ore passano,

195
00:11:31,000 --> 00:11:35,000
sappiamo che la lancetta dei minuti sarà ancora al 1.

196
00:11:35,000 --> 00:11:39,000
Qui si parte da 1 e poi avvolgere esattamente y volte,

197
00:11:39,000 --> 00:11:41,000
così saremo ancora a 1.

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

199
00:11:49,000 --> 00:11:55,000
E qui questo x è lo stesso del d cercavamo prima,

200
00:11:55,000 --> 00:11:58,000
quindi se si usa l'algoritmo di Euclide esteso

201
00:11:58,000 --> 00:12:04,000
per ottenere questo numero x, che è il numero che dovremmo usare come il nostro d.

202
00:12:04,000 --> 00:12:07,000
Ora eseguire l'algoritmo di Euclide esteso per a = 5

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

204
00:12:11,000 --> 00:12:14,000
Useremo un metodo chiamato il metodo della tabella.

205
00:12:14,000 --> 00:12:21,000
Il nostro tavolo avrà 4 colonne, x, y, d, e k.

206
00:12:21,000 --> 00:12:23,000
Il nostro tavolo inizia con 2 file.

207
00:12:23,000 --> 00:12:28,000
Nella prima riga abbiamo 1, 0, allora il nostro valore di a, che è 5,

208
00:12:28,000 --> 00:12:37,000
e la seconda riga è 0, 1, e il nostro valore di b, che è 924.

209
00:12:37,000 --> 00:12:40,000
Il valore della colonna 4a, k, sarà il risultato

210
00:12:40,000 --> 00:12:45,000
di dividere il valore di d nella riga sopra con il valore di d

211
00:12:45,000 --> 00:12:49,000
sulla stessa riga.

212
00:12:49,000 --> 00:12:56,000
Abbiamo 5 diviso 924 è 0 con qualche resto.

213
00:12:56,000 --> 00:12:59,000
Ciò significa che abbiamo k = 0.

214
00:12:59,000 --> 00:13:05,000
Ora il valore di ogni altra cellula sarà il valore della cella 2 righe sovrastanti

215
00:13:05,000 --> 00:13:09,000
meno il valore della riga sopra k volte.

216
00:13:09,000 --> 00:13:11,000
Cominciamo con d nella 3 ° fila.

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

218
00:13:19,000 --> 00:13:25,000
Avanti abbiamo 0 - 1 * 0 che è 0

219
00:13:25,000 --> 00:13:30,000
e 1 - 0 * 0 che è 1.

220
00:13:30,000 --> 00:13:33,000
Non troppo male, quindi cerchiamo di passare alla riga successiva.

221
00:13:33,000 --> 00:13:36,000
In primo luogo abbiamo bisogno del nostro valore di k.

222
00:13:36,000 --> 00:13:43,000
924 diviso 5 = 184 con qualche resto,

223
00:13:43,000 --> 00:13:46,000
così il nostro valore di k è 184.

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

225
00:13:54,000 --> 00:14:05,000
1-0 * 184 è di 1 e 0 - 1 * 184 è -184.

226
00:14:05,000 --> 00:14:07,000
Va bene, facciamo la riga successiva.

227
00:14:07,000 --> 00:14:10,000
Il valore di k sarà 1 perché

228
00:14:10,000 --> 00:14:15,000
5 diviso 4 = 1 con qualche resto.

229
00:14:15,000 --> 00:14:17,000
Riempiamo nelle altre colonne.

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

233
00:14:33,000 --> 00:14:35,000
Vediamo quello che il nostro prossimo valore di k sarebbe.

234
00:14:35,000 --> 00:14:40,000
Beh, sembra che abbiamo 4 diviso per 1, che è 4.

235
00:14:40,000 --> 00:14:43,000
In questo caso dove stiamo dividendo per 1 tale che k è uguale a

236
00:14:43,000 --> 00:14:50,000
il valore di d nella riga sopra significa che abbiamo finito con il nostro algoritmo.

237
00:14:50,000 --> 00:14:58,000
Possiamo vedere qui che si ha x = 185 e y = -1 in ultima fila.

238
00:14:58,000 --> 00:15:00,000
Passiamo ora tornare al nostro obiettivo originario.

239
00:15:00,000 --> 00:15:04,000
Abbiamo detto che il valore di x come risultato di funzionamento di questo algoritmo

240
00:15:04,000 --> 00:15:08,000
sarebbe l'inverso moltiplicativo di a (mod b).

241
00:15:08,000 --> 00:15:15,000
Ciò significa che 185 è l'inverso moltiplicativo di 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
il che significa che abbiamo un valore di 185 per d.

243
00:15:20,000 --> 00:15:23,000
Il fatto che d = 1 nella riga

244
00:15:23,000 --> 00:15:26,000
verifica che è stato e primi con m.

245
00:15:26,000 --> 00:15:30,000
Se non fosse 1, allora avremmo dovuto scegliere un nuovo indirizzo.

246
00:15:30,000 --> 00:15:33,000
Ora vediamo se Rob ha ricevuto il mio messaggio.

247
00:15:33,000 --> 00:15:35,000
Quando qualcuno mi invia un messaggio crittografato

248
00:15:35,000 --> 00:15:38,000
fino a quando ho mantenuto la mia chiave privata segreta

249
00:15:38,000 --> 00:15:41,000
Io sono l'unico che può decifrare il messaggio.

250
00:15:41,000 --> 00:15:46,000
Per decrittografare un pezzo c posso calcolare il messaggio originale

251
00:15:46,000 --> 00:15:53,000
è uguale al blocco di potenza d (mod n).

252
00:15:53,000 --> 00:15:57,000
Ricordate che d ed n sono dalla mia chiave privata.

253
00:15:57,000 --> 00:16:01,000
Per ottenere un messaggio pieno dai suoi pezzi ci decifrare ogni blocco

254
00:16:01,000 --> 00:16:04,000
e concatenare i risultati.

255
00:16:04,000 --> 00:16:08,000
Esattamente come è sicuro RSA?

256
00:16:08,000 --> 00:16:10,000
La verità è che non lo sappiamo.

257
00:16:10,000 --> 00:16:14,000
La sicurezza si basa su quanto tempo ci sarebbe voluto un utente malintenzionato di rompere un messaggio

258
00:16:14,000 --> 00:16:16,000
cifrato con RSA.

259
00:16:16,000 --> 00:16:19,000
Ricordate che un utente malintenzionato ha accesso alla chiave pubblica,

260
00:16:19,000 --> 00:16:21,000
che contiene sia E n.

261
00:16:21,000 --> 00:16:26,000
Se l'attaccante riesce a fattorizzare n nei suoi due numeri primi, p e q,

262
00:16:26,000 --> 00:16:30,000
allora potrebbe calcolare d utilizzando l'algoritmo di Euclide esteso.

263
00:16:30,000 --> 00:16:35,000
Questo le dà la chiave privata, che può essere utilizzata per decifrare qualsiasi messaggio.

264
00:16:35,000 --> 00:16:38,000
Ma quanto velocemente possiamo fattorizzare numeri interi?

265
00:16:38,000 --> 00:16:41,000
Ancora una volta, non lo sappiamo.

266
00:16:41,000 --> 00:16:43,000
Nessuno ha trovato un modo veloce per farlo,

267
00:16:43,000 --> 00:16:46,000
il che significa che, dato abbastanza grande n

268
00:16:46,000 --> 00:16:49,000
ci vorrebbe un attaccante irrealisticamente lungo

269
00:16:49,000 --> 00:16:51,000
per fattorizzare il numero.

270
00:16:51,000 --> 00:16:54,000
Se qualcuno ha rivelato un modo veloce di interi factoring

271
00:16:54,000 --> 00:16:57,000
RSA sarebbe rotto.

272
00:16:57,000 --> 00:17:01,000
Ma anche se fattorizzazione di interi è di per sé lento

273
00:17:01,000 --> 00:17:04,000
l'algoritmo RSA potrebbe avere ancora qualche difetto in esso

274
00:17:04,000 --> 00:17:07,000
che consente un facile decifratura dei messaggi.

275
00:17:07,000 --> 00:17:10,000
Nessuno ha trovato e ha rivelato un difetto ancora,

276
00:17:10,000 --> 00:17:12,000
ma questo non significa che non esista.

277
00:17:12,000 --> 00:17:17,000
In teoria, qualcuno potrebbe essere là fuori la lettura di tutti i dati crittografati con RSA.

278
00:17:17,000 --> 00:17:19,000
C'è un altro po 'di un problema di privacy.

279
00:17:19,000 --> 00:17:23,000
Se Tommy crittografa qualche messaggio con la mia chiave pubblica

280
00:17:23,000 --> 00:17:26,000
e un attaccante crittografa il messaggio stesso con la mia chiave pubblica

281
00:17:26,000 --> 00:17:29,000
l'attaccante vedrà che i 2 messaggi sono identici

282
00:17:29,000 --> 00:17:32,000
e quindi sapere che cosa Tommy crittografati.

283
00:17:32,000 --> 00:17:36,000
Per prevenire questo, i messaggi vengono generalmente riempiti con bit casuali

284
00:17:36,000 --> 00:17:39,000
prima di essere criptati in modo che lo stesso messaggio cifrato

285
00:17:39,000 --> 00:17:44,000
più volte sarà diversa purché l'imbottitura del messaggio è diverso.

286
00:17:44,000 --> 00:17:47,000
Ma ricordate come dobbiamo dividere i messaggi in blocchi

287
00:17:47,000 --> 00:17:50,000
in modo che ogni pezzo è più piccolo di n?

288
00:17:50,000 --> 00:17:52,000
Imbottitura i pezzi significa che potremmo avere a dividere le cose

289
00:17:52,000 --> 00:17:57,000
in blocchi ancora di più in quanto il pezzo imbottito deve essere inferiore a n.

290
00:17:57,000 --> 00:18:01,000
Codifica e la decodifica sono relativamente costosi con RSA,

291
00:18:01,000 --> 00:18:05,000
e quindi la necessità di suddividere un messaggio in blocchi molti può essere molto costoso.

292
00:18:05,000 --> 00:18:09,000
Se un grande volume di dati devono essere codificati e decodificati

293
00:18:09,000 --> 00:18:12,000
siamo in grado di combinare i vantaggi di algoritmi a chiave simmetrica

294
00:18:12,000 --> 00:18:16,000
con quelli di RSA per ottenere sia la sicurezza e l'efficienza.

295
00:18:16,000 --> 00:18:18,000
Anche se non sarà trattato in questa sede,

296
00:18:18,000 --> 00:18:23,000
AES è un algoritmo a chiave simmetrica come il Vigenère e cifre Cesare

297
00:18:23,000 --> 00:18:25,000
ma molto più difficile da decifrare.

298
00:18:25,000 --> 00:18:30,000
Naturalmente, non è possibile utilizzare AES senza stabilire una chiave segreta condivisa

299
00:18:30,000 --> 00:18:34,000
tra i 2 sistemi, e abbiamo visto il problema con che prima.

300
00:18:34,000 --> 00:18:40,000
Ma ora possiamo usare RSA per stabilire la chiave segreta condivisa tra i 2 sistemi.

301
00:18:40,000 --> 00:18:43,000
Chiameremo il computer che invia i dati del mittente

302
00:18:43,000 --> 00:18:46,000
e il computer che riceve i dati del ricevitore.

303
00:18:46,000 --> 00:18:49,000
Il ricevitore dispone di una coppia di chiavi RSA e invia

304
00:18:49,000 --> 00:18:51,000
la chiave pubblica del mittente.

305
00:18:51,000 --> 00:18:54,000
Il mittente genera una chiave AES,

306
00:18:54,000 --> 00:18:57,000
crittografa mediante la chiave pubblica RSA del destinatario,

307
00:18:57,000 --> 00:19:00,000
e invia la chiave AES al ricevitore.

308
00:19:00,000 --> 00:19:04,000
Il destinatario decifra il messaggio con la sua chiave privata RSA.

309
00:19:04,000 --> 00:19:09,000
Sia il mittente e il destinatario hanno ora una chiave condivisa AES tra loro.

310
00:19:09,000 --> 00:19:14,000
AES, che è molto più veloce di crittografia e decrittografia di RSA,

311
00:19:14,000 --> 00:19:18,000
può ora essere utilizzato per crittografare i grandi volumi di dati e li invia al ricevitore,

312
00:19:18,000 --> 00:19:21,000
che può decifrare con la stessa chiave.

313
00:19:21,000 --> 00:19:26,000
AES, che è molto più veloce di crittografia e decrittografia di RSA,

314
00:19:26,000 --> 00:19:30,000
può ora essere utilizzato per crittografare i grandi volumi di dati e li invia al ricevitore,

315
00:19:30,000 --> 00:19:32,000
che può decifrare con la stessa chiave.

316
00:19:32,000 --> 00:19:36,000
Abbiamo solo bisogno di RSA per trasferire la chiave condivisa.

317
00:19:36,000 --> 00:19:40,000
Non abbiamo più bisogno di usare RSA a tutti.

318
00:19:40,000 --> 00:19:46,000
Sembra come se avessi ricevuto un messaggio.

319
00:19:46,000 --> 00:19:49,000
Non importa se qualcuno leggere quello che c'è sul aeroplano di carta, prima ho preso

320
00:19:49,000 --> 00:19:55,000
perché io sono l'unico con la chiave privata.

321
00:19:55,000 --> 00:19:57,000
Facciamo decifrare ciascuno dei pezzi nel messaggio.

322
00:19:57,000 --> 00:20:07,000
Il primo blocco, 658, eleviamo alla potenza d, che è 185,

323
00:20:07,000 --> 00:20:18,000
mod n, che è 989, è pari a 67,

324
00:20:18,000 --> 00:20:24,000
che è la lettera C in ASCII.

325
00:20:24,000 --> 00:20:31,000
Ora, sul secondo blocco.

326
00:20:31,000 --> 00:20:35,000
Il secondo blocco ha valore 15,

327
00:20:35,000 --> 00:20:41,000
che eleviamo alla potenza 185,

328
00:20:41,000 --> 00:20:51,000
mod 989, e questo è uguale a 83

329
00:20:51,000 --> 00:20:57,000
che è la lettera S in ASCII.

330
00:20:57,000 --> 00:21:06,000
Ora per il terzo pezzo, che ha valore 799, eleviamo a 185,

331
00:21:06,000 --> 00:21:17,000
mod 989, e questo è uguale a 53,

332
00:21:17,000 --> 00:21:24,000
che è il valore del carattere 5 in ASCII.

333
00:21:24,000 --> 00:21:30,000
Ora per l'ultimo blocco, che ha valore 975,

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

335
00:21:41,000 --> 00:21:51,000
e questo è uguale a 48, che è il valore del carattere ASCII 0.

336
00:21:51,000 --> 00:21:57,000
Il mio nome è Rob Bowden, e questo è CS50.

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

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

339
00:22:08,000 --> 00:22:14,000
RSA affatto. [Risate]

340
00:22:14,000 --> 00:22:17,000
A tutti.