GUIDA ALLA CRITTOGRAFIA 
INTRODUZIONE

 A cura di: Francesco Groccia www.fginf.com   

I messaggi di posta elettronica, per chi non lo sapesse, possono essere letti da tutti, e non solo nei molti paesi in cui vige un controllo repressivo delle informazioni. 

È di poco tempo fa il caso ECHELON, il sistema che intercettava e controllava severamente il contenuto delle e-mail di mezzo mondo alla ricerca di parole chiave che potessero interessare al governo. Phil Zimmermann, autore del celebre software di crittografia PGP e che si è dato molto da fare per consentire a tutti di comunicare in modo sicuro, nel manuale d'uso del suo programma spiega a modo suo perché è importante usare la crittografia: «Che accadrebbe se tutti pensassero che i cittadini onesti usano solo cartoline per la loro posta? 

Se qualche persona per bene volesse usare una busta chiusa per proteggere la sua privacy, desterebbe dei grossi sospetti. 

Forse le autorità aprirebbero la sua posta per controllare cosa nasconde. Fortunatamente non viviamo in un mondo fatto così, perché tutti proteggono la maggior parte della loro posta chiudendola in una busta. Sarebbe bello se tutti usassero abitualmente la crittografia per la loro posta elettronica, indipendentemente dal contenuto più o meno riservato, e in tal modo nessuno desterebbe sospetti».

La crittografia dunque è l'arte di progettare algoritmi (o cifrari) per crittografare un messaggio rendendolo incomprensibile a tutti tranne al suo destinatario che con un algoritmo simile deve essere in grado di codificarlo, attraverso un parametro segreto detto chiave, usato in precedenza anche dal mittente per la cifratura. 

La sicurezza di un sistema di crittografia risiede solo ed esclusivamente nella segretezza della chiave e non dell'algoritmo che è opportuno far conoscere alla pubblica analisi, in modo che se ne possano scoprire eventuali punti deboli in tempo. Un algoritmo di crittografia riceve un testo da codificare (detto testo in chiaro) e lo trasforma, attraverso la chiave, in un testo cifrato apparentemente incomprensibile. I passaggi di cifratura e decifratura del testo vengono solitamente indicati in questo modo: 

cifratura: M = Ck(Mc)
decifratura: Dk(Ck(M)) = M

dove M è il messaggio da cifrare, C è l'algoritmo di codifica, D quello di decodifica e k il parametro per i due algoritmi (chiave).

I metodi di crittografia di questo tipo, cioè che utilizzano la stessa chiave per la codifica e la decodifica sono detti metodi a chiave segreta. Altri metodi che utilizzano due chiavi diverse per la codifica e la decodifica vengono detti a chiave pubblica. La lunghezza della chiave utilizzata è uno dei fattori più importanti per la segretezza del testo, evita infatti che possa essere decifrato per tentativi, dato che provare tutte le possibili combinazioni di caratteri che potrebbero formare una chiave è un problema che gli analisti definiscono a complessità computazionale esponenziale (basta infatti aggiungere una sola lettera alla chiave per aumentare in modo vertiginoso il numero di possibili combinazioni che possono essere ottenute). Tradizionalmente si usavano algoritmi semplici e chiavi lunghe. Gli algoritmi moderni si basano invece su un'alta complessità in modo da rendere difficile il lavoro del crittoanalista anche se questo possiede una grossa quantità di testo cifrato. Il crittoanalista è colui che, come avrete già capito, ha il compito di violare i cifrari, o almeno di scoprire i punti deboli degli algoritmi. La potenza dei computer moderni può aiutare moltissimo il crittoanalista, ma molti sistemi che possono sembrare estremamente sicuri possono essere infranti semplicemente con carta e penna.

La crittografia ha origini antichissime. Più di 6000 anni fa si scrivevano geroglifici egizi e ancora oggi si lavora per la loro interpretazione. Da sempre l'uomo ha cercato di proteggere i propri segreti e il campo in cui l'uomo ha l'assoluta necessità di farlo da sempre è quello militare. Nell'epoca dell'impero romano e di Giulio Cesare, quando ancora pochi sapevano leggere e scrivere, troviamo il primo esempio di cifrato.

Per comunicare con i sui generali, Giulio Cesare sostituiva ad ogni lettera del messaggio un'altra lettera con un certo numero di posizioni più avanti nell'alfabeto. Per l'esattezza utilizzava la chiave "3", tutte le lettere venivano scalate di tre cifre: la A diventava D, la B diventava E, la C diventava F e così via. Un metodo semplicissimo ma per quell'epoca più che rivoluzionario.
La debolezza di questo codice sta nel fatto che si possono utilizzare solo 25 chiavi, cioè tante quanto le lettere dell'alfabeto. Comunque è da questo cifrato che iniziano i miglioramenti e l'evoluzione della crittografia.
Il primo miglioramento che fu concepito all'epoca, fu quello di avere ogni lettera sostituita con un'altra in modo casuale, senza una regola fissa. Per esempio questa può essere una chiave:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
TREWQYUIOPLKJHGFDSAZXCVBNM 

Nel corso del tempo sono stati sviluppati diverse tecnice per la cifratura: il codice di Vigenère, che si basa su una sostituzione polialfabetica; cifratura a trasposione di colonna; macchina Enigma. Quest'ultimo codice fu l'ultimo passo prima della crittografia moderna, e fu inventato dai tedeschi durante la Seconda Guerra Mondiale. Era una macchina elettromeccanica composta da ruote con i caratteri incisi sul bordo, e con contatti elettrici in corrispondenza delle lettere in entrambi i lati. Il testo in chiaro, digitato su una tastiera, veniva riprodotto utilizzando i caratteri della prima ruota, la quale a sua volta costruiva un nuovo alfabeto utilizzando i caratteri della seconda, e poi della terza, e così via. Tutte le ruote, e potevano essere parecchie, venivano "scalate", in modo che la sostituzione delle lettere fosse ogni volta diversa. La chiave consisteva nel settaggio iniziale delle ruote, che potevano essere posizionate in una quantità di posizioni diverse tanto alte quante più erano le ruote utilizzate. Questo meccanismo è facile da costruire via software e abbastanza sicuro, può tuttavia essere infranto. Fu brillantemente attaccato dal matematico polacco Marin Rejewsky che con il suo lavoro permise di decifrare numerosi messaggi militari tedeschi, uno dei passi che contribuì alla vittoria degli Alleati.

La crittografia moderna utilizza ancora operazioni di sostituzioni e trasposizioni combinate tra loro in algoritmi molto complessi. Il primo è il DES (Data Encryption Standard).

Il DES è un cifrario composto sviluppato dall'IBM, modificato dalla National Security Agency (NSA) e adottato dal governo statunitense nel 1977 ufficialmente per la protezione di dati riservati ma non classificati come "segreti militari" o di "stato" e che tuttora è usato da tutte le agenzie federali (fatta eccezione per quegli atti che richiedevano un livello più alto di sicurezza).
Il 17 luglio 1998 la Electronic Frontier Foundation diffonde un comunicato stampa con il quale annuncia la definitiva sconfitta del DES. Per dimostrare i gravi rischi di sicurezza a cui si sottopone chi utilizza il DES, la EFF costruisce il primo apparecchio hardware non coperto dal segreto di stato per decodificare i messaggi crittografati utilizzando il Data Encryption Standard. In meno di un anno viene costruito un calcolatore costato 250.000 dollari che in meno di sessanta ore era capace di forzare un messaggio cifrato con DES. Tutte le specifiche utilizzate sono documentate in un libro realizzato dalla EFF dal titolo "Cracking DES: Secrets of Encryption Research, Wiretap Politics, and Chip Design". Con le informazioni contenute nel libro è possibile realizzabile, a partire da un normale personal computer domestico, il così detto DES cracker. Il testo è disponibile unicamente in versione cartacea perché secondo le leggi USA in materia di esportazioni è reato pubblicare e quindi esportare questo tipo di informazioni su Internet.

IDEA (International Data Encryption Algorithm) è nato nel 1991 sotto il nome di IPES (Improved Proposed Encryption Standard), ed è stato progettato da due famosi ricercatori in Svizzera: Xuejja Lai e James L. Massey. Come il DES è un codice cifrato a blocchi di 64 bit, la differenza sta nel fatto che questa volta però la chiave è di 128 bit, che dovrebbe eliminare qualsiasi possibilità di riuscita di ricerca della chiave procedendo per tentativi: le chiavi possibili sono infatti 2^128.
IDEA è al momento il cifrario a chiave segreta più utilizzato per quanto riguarda i software commerciali di crittografia vista la sua velocità di codifica e decodifica nonché la sua elevata sicurezza.
Come detto in precedenza, questi sistemi di cifratura sono detti a chiave segreta, quindi utilizzano la stessa chiave sia per cifrare che per decifrare. Nell'utilizzo della comunicazione a distanza, questo è un problema, perché due comunicanti devono riuscire a scambiarsi la chiave in sicurezza. La soluzione a questo tipo di problema fu proposta nel 1975 da Whitfield Diffie e Martin Hellman, che ebbero un'intuizione che rivoluzionò il mondo della crittografia: nacque così la crittografia a chiave pubblica.

Diffie ed Hellman pensarono ad un sistema asimmetrico, basato su l'uso di due chiavi generate in modo che sia impossibile ricavarne una dall'altra. Le due chiavi vengono chiamate pubblica e privata: la prima serve per cifrare e la seconda per decifrare. Una persona che deve comunicare con un'altra persona non deve far altro che cifrare il messaggio con la chiave pubblica del destinatario, il quale a sua volta, ricevuto il messaggio non dovrà fare altro che decifrarlo con la chiave segreta personale. Ogni persona con questo sistema possiede quindi una coppia di chiavi: quella pubblica può essere tranquillamente distribuita e resa di pubblico dominio perché consente solo di cifrare il messaggio, mentre quella privata deve essere conosciuta solo da una persona. In questo modo lo scambio di chiavi è assolutamente sicuro. Fino a questo punto sembrava andare tutto bene, ma bisognava trovare il modo di implementare matematicamente questo sistema, riuscire cioè a creare due chiavi per cui non fosse possibile dedurre quella privata conoscendo quella pubblica.

Il primo modello di chiave pubblica e privata, fu sviluppato nel 1978 da tre professori: Ronald Rivest, Adi Shamir e Leonard Adleman, che realizzarono una procedura di calcoli matematici che prenderà il nome di "algoritmo RSA", dalle iniziali dei suoi inventori. 

Quando ci si rese conto dell'efficacia di questo algoritmo, ritenuto ancora oggi inattaccabile, il governo americano decise che i programmi basati su questo algoritmo potevano essere utilizzati liberamente negli Stati Uniti, ma la loro esportazione costituiva reato. 

Un altro ostacolo all'immediato sviluppo di questo algoritmo è dovuto al fatto che i tre inventori del sistema RSA decisero nel 1982 di brevettare il loro algoritmo e fondare la RSA Data Security Inc, una compagnia nata per lo sfruttamento commerciale del loro sistema di crittografia. Nonostante le restrizioni statunitensi all'utilizzo dell'RSA, al di fuori degli USA, dove il governo americano non ha potere e gli algoritmi non sono coperti da brevetto, iniziano a diffondersi numerosi programmi ispirati molto da vicino alla tecnica di Rivest, Shamir e Adleman.

Vediamo un po' come funziona: 

il codice RSA si basa su un procedimento che utilizza i numeri primi e funzioni matematiche che è quasi impossibile invertire. Dati due numeri primi, è molto facile stabilire il loro prodotto, mentre è molto più difficile determinare, a partire da un determinato numero, quali numeri primi hanno prodotto quel risultato dopo essere stati moltiplicati tra loro. In questo modo si garantisce quel principio di sicurezza alla base della crittografia a chiave pubblica. Infatti l'operazione di derivare la chiave segreta da quella pubblica è troppo complessa per venire eseguita in pratica. Vediamo in pratica l'algoritmo e le varie funzioni matematiche: 
calcolare il valore di n, prodotto di p e q, due numeri primi molto elevati (sono consigliati valori maggiori di 10^100). Negli esempi in seguito utilizzeremo numeri più piccoli per facilitare la lettura. 

Esempio: n = p*q = 7*5= 35
Calcolare il valore di z =(p-1)*(q-1). 
z = (p-1)*(q-1) = 24 

Scegliere un intero D tale che D sia primo rispetto a z, il che significa che i due numeri non devono avere fattori primi in comune. 

Esempio: 
z = 24 
d=7 
Trovare un numero E tale che E*D mod z = 1, cioè che il resto della divisione tra E*D e z sia 1. 
E = 7 --> 49 mod 24 = 1 

Dopo aver calcolato questi parametri inizia la cifratura. Il testo in chiaro viene visto come una stringa di bit e viene diviso in blocchi costituiti da kbit, dove k è il più grande intero che soddisfa la disequazione 2^k < n. 

A questo punto per ogni blocco M si procede con la cifratura calcolando Mc = M^E mod n.

In ricezione, invece, per decifrare Mc si calcola Mc^D mod n.
Come si può capire da quanto appena detto per la cifratura si devono conoscere E ed n che quindi costituiranno in qualche modo la chiave pubblica, mentre per decifrare è necessario conoscere D ed n che quindi faranno parte della chiave segreta. 

Il codice RSA viene considerato sicuro perché non è ancora stato trovato il modo per fattorizzare numeri primi molto grandi, che nel nostro caso significa riuscire a trovare p e q conoscendo n.
Nel corso degli anni l'algoritmo RSA ha più volte dimostrato la sua robustezza: in un esperimento del 1994, coordinato da Arjen Lenstra dei laboratori Bellcore, per "rompere" una chiave RSA di 129 cifre, svelando il meccanismo con cui quella chiave generava messaggi crittografati, sono stati necessari 8 mesi di lavoro coordinato effettuato da 600 gruppi di ricerca sparsi in 25 paesi, che hanno messo a disposizione 1600 macchine da calcolo, facendole lavorare in parallelo collegate tra loro attraverso Internet. 
Data la mole delle risorse necessarie per rompere la barriera di sicurezza dell'algoritmo RSA, è chiaro come un attacco alla privacy di un sistema a doppia chiave non sia praticamente realizzabile. Inoltre, nell'esperimento era stata utilizzata una chiave di 129 cifre mentre i programmi di crittografia attualmente a disposizione prevedono chiavi private con una "robustezza" che raggiunge e supera i 2048 bit, risultando quindi praticamente inattaccabili, visto anche che l'ordine di grandezza dei tempi necessari alla rottura di chiavi di questo tipo è esponenziale e passa in fretta da qualche giorno a qualche centinaia di anni.

L'introduzione dei metodi a chiave pubblica come RSA hanno risolto brillantemente il grosso problema dello scambio della chiave.

La crittografia a doppia chiave è stata una brillante intuizione ma le funzioni matematiche che generano il codice cifrato e quelle inverse per decifrarlo fanno si che questo tipo di crittografia sia uno dei più lenti in assoluto, si dice che sia da 100 a 1000 volte più lento dei sistemi a chiave segreta. 
Per questo sono nati sistemi di crittografia misti, che combinano le due tecniche in modo da fonderne i vantaggi.

In pratica quindi si utilizza la chiave pubblica soltanto per comunicare la chiave segreta (che in questi casi viene chiamata chiave di sessione) che poi verrà usata per una normale comunicazione basata su cifrati a chiave segreta. In questo modo quindi è ampiamente risolto il problema della sicurezza nello scambio della chiave e la velocità di cifratura/decifratura rimane molto alta e non penalizza la comunicazione. 
In pratica avviene questo: se due entità A e B devono comunicare in modo sicuro e veloce: 
A utilizza la chiave pubblica di B per inviare la chiave di sessione 
B decifra la chiave di sessione con la propria chiave segreta 
A e B possono comunicare utilizzando la chiave di sessione.

La crittografia a chiave pubblica è ritenuta una delle più importanti intuizioni nel campo delle comunicazioni anche per il fatto che può essere utilizzata per risolvere il problema della firma digitale.
La firma digitale di un documento (per documento intendiamo qualsiasi cosa sia memorizzata con tecnologie informatiche e quindi trasmissibile tramite sistemi di comunicazione quali Internet) si pone di risolvere tre problemi (definiti come autenticazione e integrità dei dati):

1) che il destinatario possa verificare l'identità del mittente
2) che il mittente non possa disconoscere un documento da lui firmato
3) che il destinatario non possa inventarsi o modificare un documento firmato da qualcun altro.

Per firmare un documento si utilizza come detto la crittografia a chiave pubblica, in una modalità che può essere definita inversa. Se un individuo cifra un messaggio con la sua chiave privata, quel messaggio cifrato potrà essere letto da tutte le persone che possiedono la sua chiave pubblica. Se queste riusciranno a decifrare il messaggio avranno la certezza che è stato inviato dal proprietario della chiave pubblica usata per la decifratura. Tutto è garantito dal principio base della crittografia asimmetrica, dal fatto cioè che la chiave segreta decifra solo ciò che è stato cifrato con la rispettiva chiave pubblica e viceversa.

 
Come si può notare la firma digitale non garantisce la segretezza del contenuto del documento, infatti tutti i possessori della chiave pubblica del mittente possono averne accesso. Il problema però è facilmente risolvibile in modo intuibile: è sufficiente crittografare il messaggio firmato con una delle tecniche viste fino a questo punto. Il ricevente non dovrà fare altro che decifrare il messaggio (in questo caso solo lui potrà farlo) e successivamente controllarne la firma. 
I più attenti di voi avranno però notato un piccolo inconveniente in quanto detto fino a questo momento. Parlando di crittografia a chiave pubblica avevamo sottolineato l'eccessiva lentezza del sistema, che ne rendeva sconsigliato l'utilizzo "esclusivo" per la quantità di dati generata e il tempo impiegato, e visto che le funzioni utilizzate sono le stesse, anche se in senso inverso, il problema continua a persistere. La soluzione consiste nel cifrare solo una piccola parte dell'intero messaggio. Ovviamente la parte di messaggio da cifrare non può essere scelta in modo qualsiasi, si utilizzano in pratica delle funzioni di Hash.
Funzioni di HASH
Una funzione di hash, detta anche one way hash, trasforma un testo normale di lunghezza arbitraria in una stringa di lunghezza relativamente limitata. Questa stringa rappresenta una sintesi del messaggio (message digest) che non è altro che una vera e propria impronta digitale unica che viene definita valore di hash e che gode di tre importanti proprietà: 

1) dato un messaggio si può facilmente calcolare il suo valore di hash 
2) dato il valore di hash è impossibile risalire al messaggio (per questo one way hash) 
3) non si possono generare due messaggi che abbiano la stessa sintesi.

Sappiamo che questo non è praticabile ma in genere si intende che la probabilità di collisione (due messaggi con la stessa sintesi) deve essere molto bassa. 

Solitamente per le impronte vengono utilizzati 128 bit, ma il valore può essere qualsiasi, tenendo conto che più basso è e più alta è la probabilità di collisione. 
Continuiamo il nostro studio sulla crittografia, analizzando il programma che viene più usato al mondo per crittografare documenti a chiave doppia, PGP.