Comments
Description
Transcript
Crittografia - My-Lab
“I matematici, hanno vinto la guerra” da A Beautiful Mind << Dall'Enigma alla Crittografia Quantistica, indice Enigma 1918 d.C. Decrittare Enigma Sostituzione Monoalfabetica 1970 d.C. Crittografia Moderna Varcare la Soglia Crittografia Quantistica ? d.C. << Enigma Le Origini Enigma per uso commerciale 1918 Arthur Scherbius (brevetto) Enigma per uso militare 1926 Funkschlüssel C 1928-30 Wehrmacht (Enigma I) il brevetto di Scherbius << Vista da vicino Sono visibili le parti che richiedono interazione con l'operatore Dischi Schermo Tastiera Plugboard << Tastiera e Schermo L'operatore digita il testo e legge carattere per carattere la versione criptata Il marconista trasmette in codice morse il messaggio a destinazione << Plugboard La Plugboard permette di scambiare fra di loro una lettera con un'altra lettera Le 26 lettere dell'alfabeto permettono 26! combinazioni, cioé 4x10^26 combinazioni << Dischi Rotanti I dischi rotanti alternano ad ogni lettera un diverso alfabeto cifrante All'inizio del messaggio i tre dischi rotanti vengono impostati su una delle 26^3 (17576) combinazioni iniziali << Dischi Rotanti I dischi rotanti alternano ad ogni lettera un diverso alfabeto cifrante All'inizio del messaggio i tre dischi rotanti vengono impostati su una delle 26^3 (17576) combinazioni iniziali << Decrittare Enigma GCHQ Fu il GCHQ a decrittare i crittogrammi Enigma della II guerra mondiale Nel 1994 i servizi segreti britannici hanno finalmente svelato al pubblico l'esistenza di questa struttura Si è venuti a sapere, così, che al GCHQ avevano costruito Colossus (probabilmente, il primo computer al mondo) e che il metodo DiffieHellman era già stato scoperto con circa 30 anni di anticipo << Alan Turing E' stato Alan Turing, il padre dei programmi informatici, a capire come si poteva far breccia in Enigma Egli aveva individuato infatti alcune combinazioni di lettere che permettevano di ignorare lo stato della plugboard << Le concatenazioni Si tratta delle concatenazioni, in cui ogni lettera del testo originale manda ad una successiva lettera uguale nel testo cifrato << Automatizzazione Isolati i pannlli rimangono solo 17576 assetti da controllare Anche se è inconcepibile controllare manualmente una per una le possibili combinazioni... << La Bomba ...si tratta di un compito che può essere facilmente eseguito da una macchina automatica Il grande lavoro teorico svolto da Turing in precedenza, gli permise di costruire una bomba in grado di decrittare Enigma << La cifratura monoalfabetica Per quanto riguarda invece la plugboard, la soluzione era già nota da molto tempo Nel secolo IX, Abu Yusuf Yaqub ibn Ishaq alSabbah Al-Kindi, aveva scoperto un'interessante proprietà linguisticomatematica... << Crittografia Moderna Crittografia Moderna La crittografia moderna usa tecniche profondamente diverse da quelle conosciute al tempo di Enigma Con la scoperta del metodo Diffie-Hellman, e in seguito con l'RSA è oggi possibile risolvere il problema più grande di Enigma: lo scambio di una chiave crittografica attraverso un mezzo non sicuro come ad esempio attraverso le onde radio << Alice Alice vuole spedire una lettera a Bob, ma sa che nel suo Paese i postini si divertono a curiosare tra le missive altrui. Alice chiude il suo messaggio con un lucchetto di cui lei sola possiede la chiave e lo spedisce a Bob << Bob Bob riceve il messaggio di Alice, ma non è in grado di aprirlo Bob chiude il messaggio di Alice con un ulteriore lucchetto, di cui lui solo possiede la chiave, e rispedisce il tutto ad Alice << Alice Alice riceve il messaggio che aveva precedentemente spedito a Bob Alice toglie il suo lucchetto e rispedisce la missiva a Bob << Bob Bob riceve il messaggio di Alice Bob toglie il suo lucchetto, e finalmente può leggere la chiave che Alice ha voluto mandargli, e che in seguito userà per cifrare tutta la corrispondenza << In sintesi In questo modo Alice ha inviato a Bob un messaggio senza la necessità di concordare con lui un qualche codice segreto. Eva non è riuscita ad aprire il plico, perché ogni volta che veniva scambiato da Alice a Bob e viceversa, ad esso era applicato un lucchetto. Esiste un equivalente matematico di questa situazione reale? << Funzioni Unidirezionali Nell'aritmetica dei moduli esistono alcune funzioni cosiddette unidirezionali. Mentre calcolare il risultato di queste funzioni è semplice, altrettanto non si può dire della loro funzione inversa. infatti k = B a mod N è facilmente calcolabile anche per grandi numeri se consideriamo che Z xN vale mod N ... all'interno di un gruppo moltiplicativo k = B 2 mod N ∗ B a − 2 mentre al contrario a = logB k mod N ha una complessità paragonabile alla scomposizione in fattori primi << Esempi numerici Vediamo alcuni esempi di calcoli con le operazioni modulo esp.= 2base modulo 7= esp. mod 7 base esp. 1 2 3 4 5 6 7 modulo 7 2 2 4 4 8 1 16 2 32 4 64 1 128 2 funzione diretta (facilmente calcolabile) funzione inversa (difficilmente calcolabile) << Diffie-Hellmann Alice e Bob possono sfruttare questa asimmetria (usando queste funzioni come un lucchetto) per concordare una chiave su un canale non sicuro Alice concorda g con Bob su un canale pubblico, poi genera un numero casuale a < N e calcola A= g a mod N Il numero A viene comunicato pubblicamente a Bob. In modo del tutto analogo Bob genera b < N e ottiene B= g b mod N Bob comunica pubblicamente B ad Alice. Alice calcola il numero k = B a mod N Bob ottiene lo stesso numero calcolando b k = A mod N a a poiché A= g e g = Ba b << Un esempio numerico E' possibile, per meglio comprendere l'esempio prima proposto, ignorare l'operazione modulo e verificare il tutto con un esempio numerico Alice e Bob hanno calcolato g = 2, Alice ha scelto a = 3 A= g a = 23= 8 Il numero A viene comunicato pubblicamente a Bob. Bob sceglie b = 4 e ottiene B= g b = 24 = 16 Bob comunica pubblicamente B ad Alice. Alice calcola il numero a 3 43 k = B = 16 = 2 = 4096 Bob ottiene lo stesso numero calcolando b 4 3 4 k = A = 8 = 2 = 4096 a a poiché A= g e g = Ba b << RSA l'rsa è stata brevettata nel 1977 Questa tecnica sta alla base della moderna crittografia La sua evoluzione, l'RSA permette inoltre di evitare gli attacchi del tipo man-in-the-middle è quindi possibile scambiare una chiave anche su un canale non sicuro << Applicazioni Comunicazioni militari Bancomat, Carte di credito Certificazione di identità Telefono sicuro Web sicuro Posta elettronica << Varcare la Soglia Qual'è il punto debole? Abbiamo analizzato alcune tra le più potenti tecniche crittografiche esistenti Com'è possibile, nonostante queste tecniche funzionino perfettamente, che esistano hacker in grado di penetrare nei nostri sistemi? /default.ida?NNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNN%u9090%u6 858%ucbd3%u7801%u9090%u6858%ucbd3% u7801%u9090%u6858%ucbd3%u7801%u9090% u9090%u8190%u00c3%u0003%u8b00%u531 b%u53ff%u0078%u0000%u00=a la tristemente nota sequenza di code red << Il fattore umano In realtà la maggior parte degli attacchi non partono da debolezze del sistema informatico, ma dalla nostra stessa disponibilità a collaborare con questi hacker un avviso di sicurezza di Windows XP Gli hacker sono infatti molto bravi a mascherarsi << Cavallo di Troia La storia è simile a quella di Ulisse e del cavallo di Troia Un hacker può invitarci a cliccare su una finestrella “innocente” che dovrebbe scaricare quel tale programma che cerchiando, mentre in realtà... << << << << E Virus D'altra parte via email si possono inviare anche programmi Anche se stiamo molto attenti a non aprire allegati sospetti è bene tenere presente che questi virus possono assomigliare ad un comunissimo file word, che sarebbe innocuo per la macchina L'icona è la stessa, anche l'estensione sembrerebbe confermare l'ipotesi di un file doc ma... << << Crittografia Quantistica Il futuro della Crittografia Crittoanalisi Lo scambio di chiavi effettuato tramite RSA o simili potrebbe essere istantaneamente decriptato da un calcolatore quantistico Crittografia E' effettivamente possibile scambiare una chiave indecifrabile ed inviolabile sfruttando il principio di indeterminazione di Heisenberg << Il Calcolatore Quantistico Mentre in un calcolatore tradizionale il valore di un bit può essere 1 oppure 0, in un computer quantistico un qbit può valere contemporaneamente 1 e 0. Eseguendo una certa funzione f su quel qbit, che ad esempio controlli se n è divisibile per x, si calcolerebbe quindi istantaneamente sia il risultato di f(1) che di f(0). << Un esempio concreto Se, ad esempio, volessi scoprire l'utente a cui corrisponde un certo numero telefonico, con un computer tradizionale dovrei scorrere tutto l'elenco fino al numero in esame Un computer quantistico non scorrerebbe l'elenco. Controllerebbe contemporaneamente a chi corrispondono tutti i numeri dell'elenco, per poi restituire il numero in questione << Realtà o Fantascienza? Costruire un calcolatore quantistico comporta ancora notevoli inconvenienti tecnici Tuttavia presso l'IBM nel 2001 ne è stato realizzato un prototipo con un registro di 7qbit che ben fa sperare per il futuro << La base Per il principio di indeterminazione di Heisenberg, sappiamo che di un elettrone è possibile conoscere solo o la traiettoria o la posizione, ma mai tutte e due insieme Tutte le asimmetrie sono di grande interesse nel campo della crittografia Quando eseguiamo una misura dobbiamo scegliere quale delle due misurare << Campi Magnetici Anche per un campo magnetico orientato nello spazio vale questo discorso Non è possibile conoscerne a priori l'orientazione di un campo magnetico e la sua intensità L'unica maniera per misurare l'orientazione di un campo è quella di usare un filtro polarizzante << Filtri Polarizzatori Ecco un esempio di filtro polarizzatore (che possiamo trovare anche nei nostri occhiali da sole) Solo le frecce rosse verticali riescono ad attraversare la fenditura << Misurare l'Orientazione In un caso normale, è possibile eseguire due misure: la prima usando il filtro 1 e la seconda usando il filtro 2 e determinare così qual è l'orientazione del campo Se però usiamo un solo fotone, questo non è più possibile << In conclusione Si può ricevere il singolo fotone solo usando il filtro corretto Se si usa il filtro sbagliato infatti non è più possibile eseguire ulteriori misure poiché ormai il fotone, scontrandosi col filtro, ha perso l'informazione originaria Se invece non si usa il filtro, non si ha alcuna informazione sull'orientazione del campo << Alice e Bob Alice sceglie un'orientazione casuale e trasmette a Bob Bob sceglie un filtro a caso e riceve Alice e Bob scartano l'informazione data dai fotoni dove hanno usato filtri diversi Alice 1filtro 1 7filtro 2 9filtro 2 5filtro 1 5filtro 2 3filtro 2 2filtro 1 1filtro 2 5filtro 1 6filtro 2 8filtro 1 Bob filtro filtro filtro filtro filtro filtro filtro filtro filtro filtro filtro 2 2 1 1 2 1 2 2 2 1 1 Check Dati x v 7 x v 5 v 5 x x v 1 x x v 8 chiave trasmessa: 75518 << Eva Anche Eva ha scelto un'orientazione casuale, come hanno fatto Bob ed Alice, per rilevare i fotoni Tuttavia non sempre ha scelto l'orientazione corretta, e di conseguenza non è in grado di ricostruire la chiave originale Alice 1filtro 1 7filtro 2 9filtro 2 5filtro 1 5filtro 2 3filtro 2 2filtro 1 1filtro 2 5filtro 1 6filtro 2 8filtro 1 Bob filtro filtro filtro filtro filtro filtro filtro filtro filtro filtro filtro 2 2 1 1 2 1 2 2 2 1 1 Check Eva x filtro v filtro x filtro v filtro v filtro x filtro x filtro v filtro x filtro x filtro v filtro Dati 2 1 ? 1 2 ? 1 ? 2 1 2 1 1 1 1 8 chiave trasmessa: ???18 << Applicazioni La crittografia Quantistica è già disponibile per applicazioni commerciali Attualmente è possibile usare questa tecnica con cavi in fibra ottica lunghi fino a 100km <<