[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[Questo è CS50.] [CS50.TV]
Diamo un'occhiata a RSA, un algoritmo ampiamente utilizzato per la crittografia dei dati.
Gli algoritmi di crittografia come Cesare e Vigenère cifre non sono molto sicuro.
Con il cifrario di Cesare, un attaccante ha solo bisogno di provare 25 tasti diversi
per ottenere testo normale del messaggio.
Mentre il cifrario Vigenère è più sicuro del cifrario di Cesare
a causa dello spazio di ricerca più grande per le chiavi, una volta che un utente malintenzionato
conosce la lunghezza della chiave in un cifrario Vigenère,
che può essere determinata mediante l'analisi del pattern nel testo cifrato,
il cifrario Vigenère non è molto più sicuro del cifrario di Cesare.
RSA, d'altra parte, non è vulnerabile agli attacchi come questo.
Il cifrario di Cesare e Vigenère cifratura utilizzare la stessa chiave
per crittografare e decrittografare un messaggio.
Questa proprietà rende questi algoritmi a chiave simmetrica cifrari.
Un problema fondamentale con algoritmi a chiave simmetrica
è che si basano su quello cifratura e l'invio del messaggio
e quella ricevente e decifrare il messaggio
di aver già concordato in anticipo sul tasto essi useranno i.
Ma noi abbiamo un po 'di un problema di avvio qui.
Come 2 computer che vogliono comunicare stabilire una chiave segreta tra di loro?
Se la chiave deve essere segreta, quindi abbiamo bisogno di un modo per crittografare e decrittografare la chiave.
Se tutto quello che abbiamo è crittografia a chiave simmetrica
allora abbiamo appena tornati allo stesso problema.
RSA, invece, utilizza una coppia di chiavi,
uno per la crittografia e la decrittografia per un'altra.
Una è chiamata la chiave pubblica, e l'altra è la chiave privata.
La chiave pubblica viene utilizzata per crittografare i messaggi.
Come si può intuire dal suo nome, possiamo condividere la nostra chiave pubblica con
chiunque vogliamo senza compromettere la sicurezza di un messaggio crittografato.
I messaggi crittografati utilizzando una chiave pubblica
possono essere decifrati solo con la sua chiave privata corrispondente.
Mentre è possibile condividere la vostra chiave pubblica, si dovrebbe sempre mantenere il vostro segreto della chiave privata.
e solo la chiave privata può essere usata per decifrare messaggi
se 2 utenti desidera inviare i messaggi crittografati con RSA
avanti e indietro entrambi gli utenti hanno bisogno di avere la propria coppia di chiavi pubblica e privata.
Messaggi da utente 1 a utente 2
utilizzare solo coppia di chiavi 2 utente, e messaggi da utente a utente 1 2
utilizzare solo coppia di chiavi dell'utente di 1.
Il fatto che ci sono 2 tasti separati per crittografare e decrittografare i messaggi
RSA fa un algoritmo a chiave asimmetrica.
Non abbiamo bisogno per crittografare la chiave pubblica, al fine di inviarlo a un altro computer
dato che la chiave pubblica è in ogni caso.
Ciò significa che RSA non ha lo stesso problema di avvio
come gli algoritmi della chiave simmetrica.
Quindi, se voglio inviare un messaggio utilizzando la crittografia RSA
a Rob, io per prima cosa bisogno di chiave pubblica di Rob.
Per generare una coppia di chiavi, Rob deve scegliere 2 numeri primi elevati.
Questi numeri saranno utilizzati in entrambe le chiavi pubbliche e private,
ma la chiave pubblica utilizza solo il prodotto di questi due numeri,
Non gli stessi numeri.
Una volta che ho criptato il messaggio usando la chiave pubblica di Rob
Posso inviare il messaggio a Rob.
Per un computer, i numeri di factoring è un problema difficile.
La chiave pubblica, lo ricordiamo, ha utilizzato il prodotto di 2 numeri primi.
Questo prodotto deve quindi avere solo 2 fattori,
che capita di essere i numeri che compongono la chiave privata.
Per decifrare il messaggio, RSA userà la chiave privata
oppure i numeri moltiplicati insieme nel processo di creazione della chiave pubblica.
Perché è computazionalmente difficile fattorizzare il numero
utilizzato in una chiave pubblica nelle due numeri usati per la chiave privata
è difficile per un utente malintenzionato di capire la chiave privata
che sarà necessario per decifrare il messaggio.
Ora andiamo in alcuni dettagli a basso livello della RSA.
Si deve prima vedere come possiamo generare una coppia di chiavi.
In primo luogo, abbiamo bisogno di due numeri primi.
Chiameremo questi 2 numeri p e q.
Al fine di scegliere p e q, in pratica ci pseudorandomly generare
grandi numeri e quindi utilizzare un test per determinare se
questi numeri sono probabilmente primo.
Possiamo mantenere la generazione di numeri casuali ripetutamente
fino a quando abbiamo 2 numeri primi che possiamo utilizzare.
Qui Riprendiamo p = 23 e q = 43.
Ricordare, in pratica, p e q devono essere numeri molto più grandi.
Per quanto ne sappiamo, più grandi i numeri, più difficile è
per rompere un messaggio cifrato.
Ma è anche più costoso per crittografare e decrittografare i messaggi.
Oggi è spesso raccomandato che p e q sono almeno 1024 bit,
che mette ogni numero a più di 300 cifre decimali.
Ma ci prendono questi piccoli numeri per questo esempio.
Ora si moltiplicano p e q insieme per ottenere un numero di 3 °,
che chiameremo n.
Nel nostro caso, n = 23 * 43, che = 989.
Abbiamo n = 989.
Avanti ci moltiplichiamo p - 1 con q - 1
per ottenere un 4 ° numero, che chiameremo m.
Nel nostro caso, m = 22 * ​​42 = 924 che.
Abbiamo m = 924.
Ora abbiamo bisogno di un numero e che è relativamente primo a m
e meno di m.
Due numeri sono primi fra loro o coprimi
se il solo numeri interi positivi che li divide entrambi in modo uniforme è 1.
In altre parole, il massimo comun divisore di e ed m
deve essere 1.
In pratica, è comune per l'e di essere il numero primo 65537
purché tale numero non capita di essere un fattore di m.
Per le nostre chiavi, ne sceglieremo e = 5
dal 5 è primo a 924.
Infine, abbiamo bisogno di un numero maggiore, che chiameremo d.
D deve essere un valore che soddisfa l'equazione de = 1 (mod m).
Questo m mod significa che useremo una cosa chiamata aritmetica modulare.
In aritmetica modulare, una volta ottiene un numero maggiore di qualche limite superiore
andrà a capo indietro intorno a 0.
Un orologio, per esempio, utilizza l'aritmetica modulare.
Un minuto dopo 1:59, per esempio, è 2:00,
non 1:60.
La lancetta dei minuti si è avvolto intorno a 0
al raggiungimento di un limite superiore di 60.
Quindi, possiamo dire che 60 è equivalente a 0 (mod 60)
e 125 è equivalente a 65 è equivalente a 5 (mod 60).
La nostra chiave pubblica sarà l'indirizzo e coppia e n
dove in questo caso e è 5 e n ​​è 989.
La nostra chiave privata sarà la coppia d ed n,
che nel nostro caso è di 185 e 989.
Si noti che il nostro originale numeri primi p e q non appaiono
in tutto le nostre chiavi pubbliche o private.
Ora che abbiamo la nostra coppia di chiavi, diamo un'occhiata a come siamo in grado di crittografare
e decifrare un messaggio.
Voglio mandare un messaggio a Rob,
così sarà quello di generare questa coppia di chiavi.
Poi mi chiedo Rob per la sua chiave pubblica, che userò
per cifrare un messaggio da inviare a lui.
Ricordate, è tutto a posto per Rob a condividere la sua chiave pubblica con me.
Ma non sarebbe giusto da condividere la sua chiave privata.
Non ho idea di quale sia la sua chiave privata è.
Siamo in grado di rompere il nostro messaggio m in parti diverse
tutto più piccolo di n e quindi crittografare ciascuno di questi pezzi.
Ci crittografare la CS50 stringa, che siamo in grado di spezzare in 4 pezzi,
uno per ogni lettera.
Per crittografare il mio messaggio, ho bisogno di convertirlo in
qualche tipo di rappresentazione numerica.
Facciamo concatenare i valori ASCII con i personaggi del mio messaggio.
Per cifrare un messaggio m dato
Ho bisogno di calcolare c = m all'indirizzo e (mod n).
M ma deve essere minore di n,
oppure il messaggio completo non può essere espresso modulo n.
Possiamo rompere m in parti diverse, che sono tutti minore di n,
e criptare ciascuno di questi pezzi.
Crittografia ognuno di questi blocchi, si ottiene c1 = 67 alla 5 (mod 989)
che = 658.
Per il nostro secondo blocco abbiamo 83 al 5 (mod 989)
che = 15.
Per il nostro terzo pezzo abbiamo 53 alla 5 (mod 989)
che = 799.
E, infine, per il nostro ultimo blocco abbiamo 48 al 5 (mod 989)
che = 975.
Ora siamo in grado di inviare più di questi valori crittografati a Rob.
Ecco a te, Rob.
Anche se il nostro messaggio è in volo, diamo un altro sguardo
il modo in cui abbiamo ottenuto che il valore per d.
Il nostro numero d necessaria per soddisfare 5d = 1 (mod 924).
Questo rende d l'inverso moltiplicativo di 5 modulo 924.
Dato 2 numeri interi, A e B, l'algoritmo euclideo esteso
può essere usato per trovare il massimo comun divisore di questi 2 numeri interi.
Essa ci darà anche due altri numeri, x e y,
che soddisfano l'equazione ax + by = il massimo comun divisore di a e b.
In che modo questo ci aiuta?
Be ', di collegare e = 5 per un
e m = 924 per b
sappiamo già che questi numeri sono coprimi.
Il loro massimo comun divisore è 1.
Questo ci dà 5x + 924y = 1
o 5x = 1 - 924y.
Ma se ci interessa solo tutto modulo 924
allora possiamo cadere il - 924y.
Ripensa al clock.
Se la lancetta dei minuti è il 1 ° e quindi esattamente 10 ore passano,
sappiamo che la lancetta dei minuti sarà ancora al 1.
Qui si parte da 1 e poi avvolgere esattamente y volte,
così saremo ancora a 1.
Abbiamo 5x = 1 (mod 924).
E qui questo x è lo stesso del d cercavamo prima,
quindi se si usa l'algoritmo di Euclide esteso
per ottenere questo numero x, che è il numero che dovremmo usare come il nostro d.
Ora eseguire l'algoritmo di Euclide esteso per a = 5
e b = 924.
Useremo un metodo chiamato il metodo della tabella.
Il nostro tavolo avrà 4 colonne, x, y, d, e k.
Il nostro tavolo inizia con 2 file.
Nella prima riga abbiamo 1, 0, allora il nostro valore di a, che è 5,
e la seconda riga è 0, 1, e il nostro valore di b, che è 924.
Il valore della colonna 4a, k, sarà il risultato
di dividere il valore di d nella riga sopra con il valore di d
sulla stessa riga.
Abbiamo 5 diviso 924 è 0 con qualche resto.
Ciò significa che abbiamo k = 0.
Ora il valore di ogni altra cellula sarà il valore della cella 2 righe sovrastanti
meno il valore della riga sopra k volte.
Cominciamo con d nella 3 ° fila.
Abbiamo 5-924 * 0 = 5.
Avanti abbiamo 0 - 1 * 0 che è 0
e 1 - 0 * 0 che è 1.
Non troppo male, quindi cerchiamo di passare alla riga successiva.
In primo luogo abbiamo bisogno del nostro valore di k.
924 diviso 5 = 184 con qualche resto,
così il nostro valore di k è 184.
Ora 924-5 * 184 = 4.
1-0 * 184 è di 1 e 0 - 1 * 184 è -184.
Va bene, facciamo la riga successiva.
Il valore di k sarà 1 perché
5 diviso 4 = 1 con qualche resto.
Riempiamo nelle altre colonne.
5-4 * 1 = 1.
0-1 * 1 = -1.
E 1 - 184 * 1 è 185.
Vediamo quello che il nostro prossimo valore di k sarebbe.
Beh, sembra che abbiamo 4 diviso per 1, che è 4.
In questo caso dove stiamo dividendo per 1 tale che k è uguale a
il valore di d nella riga sopra significa che abbiamo finito con il nostro algoritmo.
Possiamo vedere qui che si ha x = 185 e y = -1 in ultima fila.
Passiamo ora tornare al nostro obiettivo originario.
Abbiamo detto che il valore di x come risultato di funzionamento di questo algoritmo
sarebbe l'inverso moltiplicativo di a (mod b).
Ciò significa che 185 è l'inverso moltiplicativo di 5 (mod 924)
il che significa che abbiamo un valore di 185 per d.
Il fatto che d = 1 nella riga
verifica che è stato e primi con m.
Se non fosse 1, allora avremmo dovuto scegliere un nuovo indirizzo.
Ora vediamo se Rob ha ricevuto il mio messaggio.
Quando qualcuno mi invia un messaggio crittografato
fino a quando ho mantenuto la mia chiave privata segreta
Io sono l'unico che può decifrare il messaggio.
Per decrittografare un pezzo c posso calcolare il messaggio originale
è uguale al blocco di potenza d (mod n).
Ricordate che d ed n sono dalla mia chiave privata.
Per ottenere un messaggio pieno dai suoi pezzi ci decifrare ogni blocco
e concatenare i risultati.
Esattamente come è sicuro RSA?
La verità è che non lo sappiamo.
La sicurezza si basa su quanto tempo ci sarebbe voluto un utente malintenzionato di rompere un messaggio
cifrato con RSA.
Ricordate che un utente malintenzionato ha accesso alla chiave pubblica,
che contiene sia E n.
Se l'attaccante riesce a fattorizzare n nei suoi due numeri primi, p e q,
allora potrebbe calcolare d utilizzando l'algoritmo di Euclide esteso.
Questo le dà la chiave privata, che può essere utilizzata per decifrare qualsiasi messaggio.
Ma quanto velocemente possiamo fattorizzare numeri interi?
Ancora una volta, non lo sappiamo.
Nessuno ha trovato un modo veloce per farlo,
il che significa che, dato abbastanza grande n
ci vorrebbe un attaccante irrealisticamente lungo
per fattorizzare il numero.
Se qualcuno ha rivelato un modo veloce di interi factoring
RSA sarebbe rotto.
Ma anche se fattorizzazione di interi è di per sé lento
l'algoritmo RSA potrebbe avere ancora qualche difetto in esso
che consente un facile decifratura dei messaggi.
Nessuno ha trovato e ha rivelato un difetto ancora,
ma questo non significa che non esista.
In teoria, qualcuno potrebbe essere là fuori la lettura di tutti i dati crittografati con RSA.
C'è un altro po 'di un problema di privacy.
Se Tommy crittografa qualche messaggio con la mia chiave pubblica
e un attaccante crittografa il messaggio stesso con la mia chiave pubblica
l'attaccante vedrà che i 2 messaggi sono identici
e quindi sapere che cosa Tommy crittografati.
Per prevenire questo, i messaggi vengono generalmente riempiti con bit casuali
prima di essere criptati in modo che lo stesso messaggio cifrato
più volte sarà diversa purché l'imbottitura del messaggio è diverso.
Ma ricordate come dobbiamo dividere i messaggi in blocchi
in modo che ogni pezzo è più piccolo di n?
Imbottitura i pezzi significa che potremmo avere a dividere le cose
in blocchi ancora di più in quanto il pezzo imbottito deve essere inferiore a n.
Codifica e la decodifica sono relativamente costosi con RSA,
e quindi la necessità di suddividere un messaggio in blocchi molti può essere molto costoso.
Se un grande volume di dati devono essere codificati e decodificati
siamo in grado di combinare i vantaggi di algoritmi a chiave simmetrica
con quelli di RSA per ottenere sia la sicurezza e l'efficienza.
Anche se non sarà trattato in questa sede,
AES è un algoritmo a chiave simmetrica come il Vigenère e cifre Cesare
ma molto più difficile da decifrare.
Naturalmente, non è possibile utilizzare AES senza stabilire una chiave segreta condivisa
tra i 2 sistemi, e abbiamo visto il problema con che prima.
Ma ora possiamo usare RSA per stabilire la chiave segreta condivisa tra i 2 sistemi.
Chiameremo il computer che invia i dati del mittente
e il computer che riceve i dati del ricevitore.
Il ricevitore dispone di una coppia di chiavi RSA e invia
la chiave pubblica del mittente.
Il mittente genera una chiave AES,
crittografa mediante la chiave pubblica RSA del destinatario,
e invia la chiave AES al ricevitore.
Il destinatario decifra il messaggio con la sua chiave privata RSA.
Sia il mittente e il destinatario hanno ora una chiave condivisa AES tra loro.
AES, che è molto più veloce di crittografia e decrittografia di RSA,
può ora essere utilizzato per crittografare i grandi volumi di dati e li invia al ricevitore,
che può decifrare con la stessa chiave.
AES, che è molto più veloce di crittografia e decrittografia di RSA,
può ora essere utilizzato per crittografare i grandi volumi di dati e li invia al ricevitore,
che può decifrare con la stessa chiave.
Abbiamo solo bisogno di RSA per trasferire la chiave condivisa.
Non abbiamo più bisogno di usare RSA a tutti.
Sembra come se avessi ricevuto un messaggio.
Non importa se qualcuno leggere quello che c'è sul aeroplano di carta, prima ho preso
perché io sono l'unico con la chiave privata.
Facciamo decifrare ciascuno dei pezzi nel messaggio.
Il primo blocco, 658, eleviamo alla potenza d, che è 185,
mod n, che è 989, è pari a 67,
che è la lettera C in ASCII.
Ora, sul secondo blocco.
Il secondo blocco ha valore 15,
che eleviamo alla potenza 185,
mod 989, e questo è uguale a 83
che è la lettera S in ASCII.
Ora per il terzo pezzo, che ha valore 799, eleviamo a 185,
mod 989, e questo è uguale a 53,
che è il valore del carattere 5 in ASCII.
Ora per l'ultimo blocco, che ha valore 975,
eleviamo a 185, mod 989,
e questo è uguale a 48, che è il valore del carattere ASCII 0.
Il mio nome è Rob Bowden, e questo è CS50.
[CS50.TV]
RSA affatto.
RSA affatto. [Risate]
A tutti.