Tutti i sistemi di cifratura visti fino a questo punto sono detti a chiave segreta ed utilizzano la stessa chiave sia per cifrare che per decifrare. Questo costituisce un problema non indifferente se pensiamo all'utilizzo della crittografia per la comunicazione a distanza, infatti le due parti devono riuscire in qualche modo a scambiarsi la chiave con la certezza che nessuno ne venga a conoscenza. 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.
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, che una 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.
RSA
La prima applicazione pratica basata sulle tecniche di crittografia a doppia chiave fu sviluppata 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.
Il codice RSA si basa su un procedimento che utilizza i numeri primi e funzioni matematiche che è quasi impossibile invertire. Dati due numeri primi, e' 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 che 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 centinai di anni.
