La crittografia è diventata uno strumento indispensabile per proteggere le informazioni nei sistemi informatici. In questo e altri articoli cercheremo di introdurre alcuni concetti base della crittografia e approfondire tecnicamente alcuni casi di utilizzo nel mondo reale.
Il riferimento è il corso Cryptography I del prof. Dan Boneh della Stanford University disponibile nella piattaforma Coursera. Il corso è in lingua inglese ma sono disponibili i sottotitoli anche in lingua italiana.
Il concetto alla base della crittografia
Il primo e fondamentale obiettivo della crittografia è quello di permettere una comunicazione sicura tra due parti. Il processo necessario ad assicurare una comunicazione sicura consiste essenzialmente di due parti. La prima comporta lo stabilire una chiave sicura K condivisa tra le due parti. La seconda è come procedere, una volta stabilita la chiave condivisa, a scambiare i messaggi tra le due parti.
Nella prima fase le nostre due parti, che chiameremo confidenzialmente – come tradizione nello studio della crittografia, Alice e Bob, si scambiano dei messaggi il cui intento è quello di condividere la chiave segreta K e di assicurare i due interlocutori sull’identità reciproca. Questo deve essere fatto in modo che una eventuale terza persona che dovesse intercettare la conversazione non sia in grado di venire a conoscenza della chiave K.
Successivamente, Alice e Bob potranno portare avanti la loro conversazione utilizzando la chiave segreta K. Per fare questo essi utilizzeranno uno schema di codifica (encryption schema) tale che un eventuale soggetto attaccante non sia in grado di comprendere i loro messaggi. Inoltre, ogni tentativo da parte di un attaccante di manomettere i messaggi, verrebbe scoperto. Tecnicamente diremo che questo schema di codifica (encryption schema) permette di ottemperare a due fondamentali requisiti della sicurezza informativa: la confidenzialità (le informazioni vengono protette da accessi non autorizzati) e l’integrità (le informazioni sono complete e sicure e non possono essere alterate o modificate da utenti non autorizzati).
Altre aree di utilizzo: la firma digitale
La firma digitale, come sappiamo, è il tentativo di trasportare nel mondo digitale il concetto di firma che utilizziamo tutti i giorni nel mondo reale. Firmiamo dei documenti per assicurare che ne abbiamo preso visione o che li approviamo, garantendo così la nostra identità. E, con la stessa firma, possiamo firmare tutti i documenti che vogliamo, per ottenere il medesimo scopo di garanzia.
E’ subito evidente che non è possibile portare nel mondo digitale questo concetto: se la nostra firma digitale fosse sempre la stessa, nulla impedirebbe a un attaccante di procurarsi un documento da me firmato, copiare la mia firma e incollarla su altri documenti a sua discrezione. La firma digitale dunque non può essere la stessa in tutti i documenti, anzi, dovrà sempre essere diversa.
Come si procede dunque? Anche in questo caso viene utilizzata una funzione di codifica: essa codifica la mia firma in modo dipendente dal contenuto del documento che andrò a firmare. In questo modo la firma generata mi identifica ma contemporaneamente essa è unica poichè generata in funzione del contenuto del documento che sto firmando in quel momento.
In questo modo, anche se un attaccante dovesse appropriarsi di una mia firma, non potrebbe applicarla a un altro documento e sarebbe facile verificarne la falsità.
Altre aree di utilizzo: la comunicazione anonima
Possiamo immaginare molti casi in cui si desidera scambiare messaggi con un interlocutore restando però anonimi. Ad esempio Alice vuole parlare in una chat con Bob e desidera che nè Bob nè gli stessi server usati nella comunicazione possano risalire alla sua identità. Il metodo standard in questo caso è l’utilizzo di una rete mixnet: i messaggi vengono inoltrati attraverso una sequenza di proxy che, oltre a nascondere la provenienza del messaggio, lo cifrano in modo che nè Bob nè i server stessi siano in grado di sapere chi ha inviato il messaggio. Bob tuttavia, anche se non sa chi sia il suo interlocutore, può rispondere ai messaggi e la sua risposta giungerà ad Alice. In altre parole si tratta di una tecnica bidirezionale.
Il denaro digitale
Una applicazione derivata dalla comunicazione anonima è il denaro digitale. Analogamente al caso della firma digitale, si vorrebbe riprodurre quanto avviene nel mondo reale: posso entrare in un negozio e spendere la mia banconota da 10 euro senza che il negoziante sappia nulla della mia identità, quindi il mio acquisto resta sostanzialmente anonimo.
Nel mondo digitale, Alice vorrebbe poter spendere la sua banconota “virtuale” da 10 euro in un negozio online senza rivelare nulla della propria identità al commerciante. Ma, come nel caso della firma, anche qui sorge un problema: la banconota digitale potrebbe essere facilmente clonata da Alice stessa che, dunque, dopo averla spesa in qualche e-commerce, potrebbe spenderla nuovamente in altro negozio online senza che sia possibile accorgersi della frode.
Anche in questo caso la crittografia ci viene in aiuto. Senza addentrarci, per il momento, nei dettagli tecnici, è possibile implementare la banconota digitale in modo tale che quando essa viene spesa la prima volta nulla sia rivelato della identità di Alice; mentre, se ella tentasse di usarla nuovamente per altri acquisti, la sua identità diventerebbe palese e sarebbe possibile scoprire la sua frode e perseguirla legalmente.
Private outsourced computation
Questa applicazione, oggetto di molti studi recenti, trova ampio uso nel cloud computing. Tecnicamente si parla di POC quando un client desidera delegare la valutazione di una funzione f applicata a un input privato x, a un soggetto terzo “non affidabile” senza che quest’ultimo possa acquisire alcuna informazione su x e f(x).
In modo meno tecnico, nella POC, una parte possiede i dati e vuole essere in grado di ottenere il risultato del calcolo su tali dati. La seconda parte riceve e archivia i dati in formato crittografato, esegue il calcolo sui dati crittografati e fornisce i risultati crittografati al proprietario dei dati, senza apprendere nulla sui dati di input, sui valori intermedi o sul risultato finale. Il proprietario dei dati può quindi decrittografare i risultati restituiti per ottenere l’output.
Un esempio semplice è quello della ricerca su Google. Alice vuole eseguire una ricerca su Google ma non vuole rendere noto l’oggetto della sua query. Esistono modelli di crittografia, inventati piuttosto recentemente, che permettono ad Alice di crittare la sua query e inviarla (outsource) a Goggle. Quest’ultimo sarà in grado di applicare i suoi algoritmi di ricerca senza conoscere nè la query di ricerca (x, nella precedente definizione) nè lo schema di crittazione (f, nella precedente deinizione). Google restituirà ad Alice il risultato crittato della sua ricerca che, decrittato da Alice, le fornirà i risultati desiderati.
Sembra un risultato magico, no? Google può calcolare (computation) il risultato della query di Alice senza conoscere il testo della query ma solo il suo valore crittato. Tuttavia questo straordinario risultato è ancora teorico, in quanto, con la tecnologia attuale, Google impiegherebbe migliaia di anni per soddisfare a una query di tal genere. Tuttavia resta un risultato clamoroso che lascia presagire futuri sviluppi.
Ultimo esempio: zero-knowledge proof
Premessa: i numeri primi. Un numero primo è un intero, maggiore a uno, che è divisibile soltanto per uno e per se stesso. Eccone alcuni: 2, 3, 5, 7, 11, 13, … Ogni intero positivo si può scomporre, in modo unico (a meno dell’ordine dei fattori), nel prodotto di numeri primi. Per esempio: 60 = 22 · 3 · 5; 10001 = 73 · 137.
Con l’avvento dei calcolatori elettronici, la ricerca si è concentrata sul trovare metodi efficienti per calcolare la scomposizione in fattori primi di un dato intero n. Come vedremo, questo problema è di interesse sia pratico che teorico, poichè da esso sono nati alcuni potenti algoritmi di crittografia.
Il problema, in realtà, può essere scomposto in due fasi:
- decidere se un dato numero è primo oppure no. Questo è il cosiddetto test di primalità.
- determinare esplicitamente una qualche scomposizione in fattori (non banali) di un numero composto. Questo è il problema della fattorizzazione.
Anche se chiaramente legati l’uno all’altro, questi due problemi sono di natura differente. Allo stato presente della conoscenza, il primo risulta relativamente facile, mentre il secondo risulta essere piuttosto difficile. Per dare un’idea di quello che è possibile fare su un grosso calcolatore, diciamo che si possono fattorizzare numeri che raggiungono le 90 cifre decimali. Naturalmente, fra essi ci sono anche numeri facili da fattorizzare; ad ogni modo, si tratta di casi piuttosto rari. In generale, la fattorizzazione di un numero con più di 60 cifre decimali è difficile e anche
su di un grosso calcolatore essa richiede diverse ore. Il record mondiale è costituito da un intero di 93 cifre, fattorizzato 1988. Ci sono volute 95 ore di calcoli su un super computer per trovare la scomposizione del numero seguente:
25590419435661766569669195465155692745666184377627375121409756912567458209805153386642764777=1284827442574221936870974393373403·19917397922626842334449833677404096613537638684348856178059
Da notare che se volessimo, con lo stesso calcolatore, fattorizzare un intero con il doppio delle cifre, sarebbe necessario un tempo pari a circa 200.000 anni.
Detto questo, torniamo alla zero-knoledge proof. Supponiamo che Alice abbia un certo numero N del quale conosce la fattorizzazione in due grandi numeri primi P e Q, ovvero N=P•Q. Ora Alice vorrebbe comunicare a Bob non solo il numero N ma anche il fatto che ne conosce una fattorizzazione: senza però rivelare i fattori P e Q. Ebbene esiste un particolare protocollo “magico” attraverso il quale Bob può accertare in modo inequivocabile che Alice conosce una fattorizzazione di N ma senza che egli venga a conoscenza dei fattori P e Q.
Questo esempio è del tutto generale: in crittografia una zero-knowledge proof è un metodo mediante il quale una parte (Alice) può dimostrare a un’altra parte (Bob) che una determinata affermazione è vera evitando di trasmettere qualsiasi informazione aggiuntiva oltre al fatto che l’affermazione è effettivamente vera.
Ci occuperemo ancora di crittografia nei prossimi articoli.
