[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. Dal momento che la chiave privata deve essere tenuta segreta e solo la chiave privata può essere usato per decifrare messaggi, se due utenti desiderano inviare messaggi criptato con RSA 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 due coppia di chiavi dell'utente, e messaggi da utente 2 a utente 1 utilizzare solo utente 1 coppia di chiavi. 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 un algoritmo a chiave simmetrica. 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 tornare lo 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, siamo in grado di condividere la nostra chiave pubblica con chiunque vogliamo senza compromettere la sicurezza di un messaggio crittografato. I messaggi crittografati utilizzando una chiave pubblica può essere decifrato con la sua chiave privata corrispondente. Mentre è possibile condividere la vostra chiave pubblica, si dovrebbe sempre mantenere il vostro segreto della chiave privata. Dal momento che la chiave privata deve essere tenuta segreta 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.