PROGRAMMIAMO
File - Un po' di storia
Diffie e Hellman: una rivoluzione nelle tecniche crittografiche

Whitfield Diffie e Martin Hellman sono i due crittografi statunitensi che per primi risolsero il problema dello scambio delle chiavi.

Diffie e Hellman

Il problema della distribuzione delle chiavi sembrava a Diffie particolarmente interessante: chi lo avesse risolto, sarebbe passato alla storia come uno dei massimi crittografi di ogni tempo.

Diffie, già agli albori della rete Internet, immaginò due estranei che si incontravano via Internet, e si chiese come avrebbero potuto scambiarsi messaggi crittati. Prese in considerazione il caso di una persona che volesse acquistare tramite Internet un prodotto. Come avrebbe potuto inviare un e-mail con i dati crittati della sua carta di credito, in modo che solo il destinatario Internet potesse decifrarli? Sembrava che le parti non potessero fare a meno di concordare una chiave, ma come riuscirci in condizioni di sicurezza? Il numero di scambi occasionali di comunicazioni e di e-mail tra gli utenti della rete sarebbe stato enorme, e altrettanto difficile sarebbe stata la distribuzione delle chiavi.

Nel 1974 egli fece visita al Laboratorio Watson dell’IBM, dov’era stato invitato a tenere una conferenza. Parlò di varie strategie di attacco relative al problema della distribuzione delle chiavi, ma tutte le sue idee erano in uno stadio iniziale di elaborazione, e l’uditorio le accolse con scetticismo. Alan Konheim, uno dei crittografi esperti dell’IBM accennò al fatto che recentemente un altro studioso aveva visitato il laboratorio e tenuto una conferenza e anch’egli aveva tentato di affrontare il problema della distribuzione delle chiavi. Il relatore era Martin Hellman, un professore dell’università californiana di Stanford. Quella sera Diffie prese la sua automobile e affrontò un viaggio di cinquemila chilometri fino alla costa occidentale per incontrare la sola persona che sembrava condividere la sua ossessione.

L’alleanza di Diffie e Hellman avrebbe generato una delle collaborazioni più dinamiche nella storia della crittografia.

Se si vuole arrivare da qualche parte compiendo ricerche originali, bisogna essere un po’ matti; solo i folli non si stancano di tentare. Ti viene l’idea numero 1, ci speri, e si rivela un fallimento. Allora provi l’idea numero 2, ci speri, e ti delude… Poi ti viene l’idea numero 99, ci speri, e anche quella ti delude. Solo un pazzo può lasciarsi tentare dalla centesima idea. Eppure, può accadere di doverne scartare novantanove per trovare quella che dà frutto. Se non si è abbastanza matti da continuare a entusiasmarsi, la motivazione vien meno, e non si può proseguire. Dio ripaga i folli.

L’intero problema della distribuzione delle chiavi sembra privo di via d’uscita. Se due persone vogliono usare il telefono per condividere un segreto, il mittente deve crittarlo. Per crittarlo deve ricorrere a una chiave, che è a sua volta un segreto. Sorge quindi il problema di trasmettere la chiave, per poter trasmettere il messaggio. In breve, per potere condividere un segreto (tramite un messaggio crittato), due persone dovrebbero già condividere un segreto (la chiave).

Per ragionare di distribuzione delle chiavi, è utile riferirsi ad Alice, Bob ed Eva, tre personaggi immaginari spesso utilizzati nelle discussioni sulla crittografia commerciale. Di solito Alice vuole mandare un messaggio a Bob, o viceversa, ed Eva vuole conoscerne il contenuto. Per impedire a Eva di scoprire cose che non la riguardano, Alice decide di crittare ogni messaggio con una chiave diversa prima di mandarlo a Bob. Ma ogni volta deve affrontare il problema del recapito della chiave. Una possibile soluzione sarebbe che Alice e Bob si incontrassero una volta alla settimana e si scambiassero abbastanza chiavi per i messaggi dei sette giorni successivi. Scambiarsi le chiavi brevi manu è un sistema sicuro ma esposto a contrattempi. Per incepparlo, basta una malattia che costringa a letto Alice o Bob per qualche tempo. Oppure, Alice e Bob potrebbero rivolgersi a un corriere; questo li solleverebbe da molti problemi, ma sarebbe più costoso e meno sicuro. Nell’un caso e nell’altro la distribuzione delle chiavi sembra inevitabile.

Da duemila anni, questo era considerato un assioma della crittografia; eppure, Diffie e Hellman conoscevano una storiella che lo faceva traballare. L’immaginaria vicenda, in cui ritroviamo Bob e Alice, è ambientata in un Paese dal servizio postale totalmente immorale. I suoi dipendenti si divertono a leggere tutta la corrispondenza non protetta, perciò un giorno Bob, dovendo inviare a Alice un messaggio personale, decide di collocarlo in una scatola di metallo chiusa da un lucchetto. Ovviamente, ella non ha intenzione di consegnare all’impiegato delle poste sia la scatola che la chiave. Consegnando solo la scatola, il messaggio giungerà a Alice in condizioni di sicurezza; ma come farà Alice ad aprire il lucchetto? Per un attimo, Bob pensa di collocare la chiave in un altra scatola con lucchetto e di spedirla a Alice. Ma poiché leii non ha nemmeno la chiave del secondo lucchetto, ciò non rappresenterebbe un passo avanti. Non sembrano esserci alternative: per uscire dall’impasse Bob deve fare una copia della chiave e consegnarla a Alice in anticipo, magari durante la pausa per il caffè. Siamo tornati al vecchio problema della distribuzione. Evitarlo sembra impossibile per ragioni logiche: se Bob chiude la scatola con un lucchetto, in modo che solo Alice possa prendere visione del contenuto, Alice deve possedere una copia della chiave. In termini crittografici: o Alice conosce la chiave usata da Bob per crittare il messaggio, o quest’ultimo gli sarà incomprensibile (a meno che si improvvisi crittoanalista).

Immaginate ora la seguente situazione. Come prima, Bob vuole mandare a Alice un messaggio molto personale. Di nuovo, lo colloca in una scatola metallica, chiude la scatola con un lucchetto, e la spedisce a Alice tenendo la chiave. Ricevuta la scatola, Alice le applica un secondo lucchetto e la rispedisce a Bob, tenendo con sé la chiave del secondo lucchetto. Quando Bob riceve la scatola è libera di rimuovere il primo lucchetto e di rispedirla a Alice; infatti il lucchetto di Alice è sufficiente ad assicurare l’inviolabilità del contenuto. Quando la scatola è finalmente recapitata a Alice, lei può aprire il secondo lucchetto con la relativa chiave, da cui non si è mai separata.

Le implicazioni di questo breve racconto sono profonde. Esso dimostra che un messaggio segreto può essere trasmesso da una persona a un’altra in modo sicuro, senza dover necessariamente recapitare la chiave. Per la prima volta, disponiamo di uno schema in cui la distribuzione delle chiavi non è parte integrante della crittografia. Il racconto può essere reinterpretato in termini di cifratura. Bob usa la propria chiave per crittare il messaggio destinato a Alice. Alice lo ricritta usando anch’egli la propria chiave, e lo rimanda a Bob. Bob rimuove dal messaggio bi-crittato la propria cifratura, e lo invia a Alice in forma mono-crittata. Infine, Alice rimuove la sua cifratura, e legge il messaggio.

Anche se il trucco dei due lucchetti non è immediatamente applicabile ai sistemi crittografici, esso rinforzò la determinazione di Diffie e Hellman a trovare il modo di aggirare la distribuzione delle chiavi. Mese dopo mese, continuarono a cercare una soluzione. Un’idea dopo l’altra si rivelò un fallimento, ma da autentici folli essi perseverarono. La loro attenzione era rivolta in particolare allo studio delle funzioni matematiche  «unidirezionali» (dette anche one-way trapdoor function). Come il loro nome suggerisce, il risultato delle funzioni unidirezionali è facile da ottenere, ma tornare indietro al numero di partenza è molto difficile. In altre parole, le funzioni bidirezionali possiedono una funzione inversa, quelle unidirezionali no. Ancora una volta, il miglior modo di illustrare una funzione unidirezionale è tramite la vita di tutti i giorni. Mescolare vernice gialla e vernice blu per ottenere vernice verde è l’equivalente di una funzione unidirezionale, perché il procedimento è semplice, ma non è possibile tornare alle condizioni di partenza.

Come esempio di funzione bidirezionale, consideriamo la funzione 3x. Essa ricava da x un altro numero (il valore della funzione) moltiplicando tra loro un numero di 3 uguale a x; così, se x = 2, la funzione assume il valore 3×3, cioè ricava 9 da 2. Nell’aritmetica ordinaria, al crescere di x cresce il valore della funzione; perciò è relativamente facile, conoscendo quest’ultimo, risalire al numero di partenza. Per esempio, se il valore della funzione è 81 è chiaro che x cioè il numero di partenza, è 4, perché 34 dà 81. Anche se per errore supponessimo che x sia 5, la scoperta e la correzione dell’errore non presenterebbero difficoltà. Un semplice calcolo rivela infatti che 35 dà 243; quindi è stato scelto un numero di partenza troppo alto. Attribuiremo quindi a x il valore 4, che è esatto. In breve, nell’aritmetica normale invertire una funzione non è difficile, perché qualche tentativo e un po’ di buon senso permettono, noto un numero ricavato tramite una funzione, di scoprire il numero di partenza.

L’aritmetica dei moduli, chiamata a volte aritmetica dell’orologio dagli studiosi (perché si applica alle somme di ore sul quadrante di un orologio), è un campo della matematica ricco di funzioni unidirezionali. In pratica la funzione modulo (indicata nel seguito con mod) calcola il resto della divisione fra due interi: così per esempio 13 mod 5 = 3, in quanto 12/5 fa 2 con il resto di 3. Supponiamo che qualcuno ci abbia detto che 3x mod 7 = 1 e ci abbia invitato a scoprire il valore di x. L’intuito non ci aiuta, perché l’aritmetica dei moduli non è di uso comune. Tirando a indovinare, potremmo partire dall’ipotesi che x sia 5, e calcolare 35 mod 7. Il risultato è 5 - troppo grande, visto che il numero cercato deve far sì che la funzione assuma il valore 1. Potremmo esser tentati di ridurre il valore di x e riprovare. In realtà, in tal modo andremmo nella direzione sbagliata, perché la risposta giusta è 6.

Dopo due anni di lavoro sull’aritmetica dei moduli e le funzioni unidirezionali, la follia di Diffie e Hellman cominciò a dar frutto. Nell’estate del 1976, Hellman intravide una strategia capace di risolvere il problema della distribuzione delle chiavi. In mezz’ora di frenetica scrittura, riuscì a dimostrare che Alice e Bob potevano stabilire una chiave senza comunicare l’una con l’altro, invalidando un assioma che aveva dominato la crittografia per secoli. L’idea di Hellman si basava su una funzione unidirezionale della forma Yx mod P. All’inizio, Alice e Bob devono accordarsi sui valori di Y e P. Quasi tutti i valori sono accettabili, fatta eccezione per un paio di limitazioni: P dev’essere numero primo, e Y dev’essere minore di P. Non è necessario che i valori in questione siano segreti; perciò Alice può telefonare a Bob e suggerire Y = 7 e P = 11. Come si vedrà, l’eventualità che la linea telefonica non sia sicura ed Eva abbia ascoltato la conversazione è irrilevante per la sicurezza del sistema crittografico. Dunque, Alice e Bob hanno concordato la funzione unidirezionale 7x (mod 11). A questo punto possono avviare il procedimento che permetterà loro di stabilire una chiave segreta senza incontrarsi. Ecco nel dettaglio come avviene lo scambio:

Passo Alice Bob
1 Sceglie un numero A (per esempio A = 3) e lo tiene segreto. Sceglie un numero B (per esempio B = 6) e lo tiene segreto
2 Inserisce il numero segreto A come x nella funzione unidirezionale e calcola:
Yx mod P = 73 mod 11 = 343 mod 11 =  2
Inserisce il numero segreto B come x nella funzione unidirezionale e calcola:
Yx mod P = 76 mod 11 = 117649 mod 11 =  4
3 Chiama α il risultato e lo comunica a Bob Chiama β il risultato e lo comunica a Alice
4 Si serve del risultato β di Bob e del suo numero segreto A per calcolare:
βA mod P = 43 mod 11 = 64 mod 11 =  9
Si serve del risultato α di Alice e del suo numero segreto B per calcolare:
αB mod P = 26 mod 11 = 64 mod 11 =  9

Ora che Alice e Bob hanno concordato la chiave (senza incontrarsi e usando linee telefoniche pubbliche), possono usarla per cifrare il messaggio. Per esempio, potrebbero usare il numero 9 per effettuare una cifratura DES (in realtà il DES usa come chiavi numeri molto più grandi, ma in realtà questo vale anche per il procedimento appena descritto).

Bob e Alice si erano scambiati solo le informazioni indispensabili a stabilire la chiave, ma le medesime informazioni erano insufficienti per Eva. Un paragone utile a chiarire lo schema di Hellman può basarsi su un’ipotetica cifratura che usi come chiavi i colori anziché i numeri. Immaginiamo che tutti, Alice, Bob ed Eva, abbiano un recipiente da tre litri, contenente un litro di vernice gialla. Se Alice e Bob vogliono concordare una chiave segreta, devono in primo luogo aggiungere un litro di un colore segreto nei rispettivi recipienti. Il colore di Alice potrebbe essere una particolare sfumatura di rosso, mentre Bob potrebbe aggiungere del verde.

Poi, ciascuno spedisce all’altro il suo recipiente. Infine, Alice aggiunge alla mistura di Bob un litro del suo colore segreto, e Bob aggiunge alla mistura di Alice un litro del proprio colore segreto. Ora il contenuto dei due recipienti dovrebbe avere lo stesso colore, perché è formato da un litro di giallo, un litro di rosso e un litro di verde. A fungere da chiave è il colore, preciso in ogni sfumatura, che si trova nei due recipienti due volte «contaminati». Alice ignora che colore, precisamente. Bob abbia aggiunto, e Bob ignora che colore, precisamente, abbia aggiunto Alice; ciò nonostante, il colore ottenuto alla fine da entrambi è identico.

Mettiamoci ora nei panni di Eva che intercetta il messaggio. Pur avendo intercettato i recipienti con la mistura intermedia, non è in grado di stabilire o fabbricare il colore della mistura finale, cioè la chiave. Ha prelevato un campione della mistura composta dal giallo e dal colore segreto di Alice durante il recapito a Bob, e della mistura composta dal giallo e dal colore segreto di Bob durante il recapito ad Alice. Ma per produrre la chiave le occorrono i colori segreti di Alice e Bob, dei quali le misture intermedie le danno solo un’idea imprecisa; e i colori della mistura non possono essere separati: una mescolanza di colori è irreversibile, proprio come una funzione unidirezionale.

Il metodo Diffie-Hellman-Merkle di scambio delle chiavi, come è chiamato, permette ad Alice e Bob di condividere un segreto per mezzo di un pubblico scambio di informazioni. In effetti, si tratta di una delle scoperte più controintuitive della storia della scienza; essa ha costretto la crittografia ufficiale a riscrivere le regole della messa in codice.

Rivest, Shamir e Adleman: l'invenzione della crittografia a chiave pubblica

Anche se sul piano teorico lo scambio di chiavi secondo Diffie, Hellman e Merkle era un enorme passo avanti, non era ancora perfetto. Infatti affinché Alice e Bob possano iniziare a comunicare, devono prima effettuare ripetuti scambi. Si tratta di un metodo abbastanza macchinoso, che chiaramente non va bene per esempio per effettuare un acquisito online su un sito pubblico. In questo caso infatti l'acquirente e il sito dovrebbero preventivamente scambiarsi una serie di mail per stabilire una chiave comune e quindi procedere alla transazione vera e propria.

Mentre Martin Hellman sviluppava il suo metodo, Whitfield Diffie lavorava a un approccio completamente diverso al problema della distribuzione delle chiavi. Spesso attraversava lunghi periodi di meditazione apparentemente improduttiva, e una volta, nel 1975, provò un tale senso di frustrazione che disse a sua moglie di essere solo uno scienziato fallito, destinato a non concludere mai niente. Le consigliò anche di cercare un partner migliore. Mary replicò di avere piena fiducia in lui, e dopo due sole settimane egli ebbe un’idea veramente brillante.

Diffie ricorda ancora che essa gli si presentò di colpo, e subito svanì:

«Scesi da basso con l’intenzione di bere una coca, e d’un tratto temetti di aver scordato tutto. Mi era venuto in mente qualcosa di interessante, ne ero certo, ma non ricordavo cosa fosse. Poi lo ritrovai, e subito tornai a emozionarmi; sentivo l’adrenalina scorrermi nelle vene. Per la prima volta da quando mi occupavo di crittografia capivo di aver fatto una scoperta veramente importante. In confronto, i contributi che avevo dato fino a quel momento mi sembrarono tecnicismi banali». Era metà pomeriggio, e Diffie dovette aspettare un paio d’ore prima che Mary rincasasse. «Whit mi aspettava sulla soglia», ricorda l’archeologa. «Affermò di avere qualcosa da comunicarmi, e aveva una buffa espressione. Entrai, e lui disse: “Siediti, per piacere, voglio parlarti. Credo di aver fatto una grande scoperta - qualcosa a cui nessun altro aveva ancora pensato’’. In quel momento, ebbi come l’impressione che il mondo si fosse fermato. Mi sentivo dentro la trama di un film hollywoodiano.»

Diffie aveva architettato un nuovo tipo di cifratura, basato su una chiave asimmetrica, in cui mittente e destinatario condividono solo la chiave pubblica del destinatario.

Nell’ipotesi che la cifratura asimmetrica sia una forma di crittografia computerizzata, la chiave per cifrare di Alice sarà un numero, quella per decifrare un altro numero. Ella terrà segreta la chiave per decifrare, che perciò è spesso chiamata chiave privata, e divulgherà la chiave per cifrare, in modo che chiunque possa adoperarla; questa chiave è spesso chiamata chiave pubblica. Se Bob vuole inviare ad Alice un messaggio, è sufficiente che impieghi la sua chiave pubblica, che potrebbe cercare in una sorta di guida telefonica. Il messaggio crittato è inviato ad Alice, che lo decifra con la chiave privata. In modo analogo Carlo, Davide ed Enrico possono inviare ad Alice messaggi crittati con la sua chiave pubblica, mentre solo Alice dispone della chiave privata necessaria a renderli intelligibili. Il grande pregio di questo sistema è che, diversamente dallo scambio delle chiavi secondo Diffie-Hellman, non ha niente di macchinoso. Bob non deve aspettare di ricevere informazioni da Alice per cifrare il messaggio a lei destinato: poiché la chiave per cifrare è pubblica, gli basta consultare un elenco. Nello stesso tempo, la cifratura asimmetrica risolve il problema della distribuzione delle chiavi altrettanto bene del sistema di Hellman. Alice non deve più preoccuparsi di comunicare la chiave a Bob in condizioni di sicurezza; al contrario, è suo interesse che la chiave per cifrare sia nota al maggior numero di persone.

Sebbene Diffie avesse avuto l'idea di un sistema a chiave pubblica, non sapeva ancora come realizzarlo. L'idea che permise di realizzare questo sistema crittografico fu sviluppata da nel 1977 da Ronald Rivest, Adi Shamir e Leonard Adleman. I tre studiosi elaborarono un algoritmo che da allora viene chiamato RSA (in base alle iniziali dei tre cognomi).

L'algoritmo RSA si basa sull'utilizzo di numeri primi molto grandi e sull'aritmetica dei moduli (la stessa usata da Diffie e Hellman) per la generazione di una coppia di chiavi, Pubblica e Privata. Maggiori dettagli sulla matematica del metodo sono spiegati più avanti.

 

precedente - successiva

Sito realizzato in base al emplate offerto da

http://www.graphixmania.it