Il problema della diffusione delle Chiavi

A partire dalla fine degli anni '70, con la nascita dei personal computer e la progressiva diffusione di Internet, non più destinata a un ristretto ambito militare-governativo, la crittografia subì un notevole impulso.  Divenne infatti indispensabile garantire la sicurezza delle informazioni e la tutela delle telecomunicazioni.  Tornò così a porsi, in modo sempre più pressante, la necessità di superare il limite intrinseco delle tradizionali tecniche crittografiche, il cosiddetto problema della diffusione delle chiave.

Per meglio comprendere il problema della diffusione delle chiavi, è utile riferirsi ad "Alice", "Bob" ed "Eva": tre personaggi simbolici comunemente usati nelle discussioni inerenti la crittografia commerciale:

Supponiamo che Alice voglia inviare un messaggio a Bob, ed Eva voglia conoscerne il contenuto. Per impedire che Eva possa comprendere il messaggio, Alice decide di criptarlo, usando un certo sistema di codifica e una chiave numerica (che permette di applicare lo stesso sistema di cifratura in modi diversi, generalmente un comune numero) prima di spedirlo a Bob.  Se ad esempio Alice decidesse di usare il cifrario di Cesare, la chiave servirebbe a indicare con quale rotazione tra i due dischi avviene la cifratura.

Una volta che Bob ha ricevuto il messaggio, se a conoscenza del sistema di cifratura e della chiave utilizzati da Alice, può facilmente ricostruire il messaggio originale.

Chiavi classiche

Ma come può Bob conoscere il metodo e la chiave con cui è stato cifrato il messaggio? Alice non può ovviamente spedire queste informazioni unitamente al messaggio cifrato, altrimenti un eventuale intercettatore potrebbe facilmente decodificare il contenuto.  Alice e Bob potrebbero semplicemente concordare in anticipo un sistema e una chiave da usare per tutti i loro messaggi. Ciò però darebbe inevitabilmente luogo ad alcune ricorrenze, ovvero alla sistematica trasformazione con stesso metodo di certe lettere in certe altre, ripetuta in tutti i messaggi con le stesse modalità.  Ciò faciliterebbe notevolmente la decrittazione da parte di Eva.

Ne deriva la necessità, quanto meno, di sostituire frequentemente le chiavi utilizzate, costringendo ogni volta Alice a dover comunicare a Bob la nuova chiave.  Potrebbero incontrarsi di persona settimanalmente e scambiarsi abbastanza chiavi per l'intera settimana.  E' però evidente che, a livello pratico, questo metodo è decisamente impegnativo, soprattutto in caso di grandi distanze o qualora un'azienda abbia la necessità di incontrare di persona una molteplicità di soggetti, come ad esempio i singoli clienti.

A tal proposito, proprio negli anni settanta, grazie a numerosi studi in cerca di una soluzione a questo problema, due crittografi americani, Diffie e Hellman, scoprirono un metodo che permetteva lo scambio di chiavi in assoluta sicurezza, applicabile anche senza necessità di incontro faccia a faccia fra Alice e Bob.

Si tratta di un sistema basato sul ricorso alle funzioni cosiddette unidirezionali.
Quando pensiamo a una funzione, abbiamo generalmente in mente un procedimento che permette di trasformare un numero in un altro, ad esempio "il doppio di...": il doppio di 1 è 2; il doppio di 2 è 4, e cosi via.  Si tratta quindi di funzioni bidirezionali, per le quali esiste la corrispondente funzione inversa, che permette di risalire al numero iniziale (conoscendo il valore finale ed il tipo di funzione iniziale utilizzata). Ad esempio la funzione inversa di "il doppio di..." è "la metà di...": la metà di 4 è 2 e quella di 2 è 1.

Per una funzione unidirezionale, invece, non esiste il corrispondente inverso.  Si tratta di una tipologia estremamente rara e particolare.

La funzione che interessa Alice e Bob e che permette loro di concordare le chiavi di cifratura è la funzione esponenziale associata ad un'altra funzione che deriva da una branca della matematica detta "aritmetica dei moduli", anche conosciuta come "aritmetica dell'orologio".  Come ben sappiamo 14:4=3,5 ma, più che il risultato della divisione, a noi interessa il valore del suo resto, trattando la divisione nell'ambito dei numeri interi. Dunque, per calcolare 14:4, troviamo quante volte il 4 sta nel 14 e ricaviamo il resto. Dato che 4x3=12 e 14-12=2, possiamo determinare che 2 è il resto della divisione. Diciamo infatti che 14=4x3+2.
In definitiva, qusto tipo di funzione permette di associare un numero (14) alla sua classe di resto (2) dato un certo modulo (4). In termini matematici [14]4=2

 

 

Sebbene questo tipo di calcolo appaia a prima vista inusuale, in realtà tutti noi vi facciamo ricorso comunemente quando guardiamo l'orologio. Se questo segna le ore 17, noi possiamo facilmente calcolare [17]12=x e troviamo che x=5, dunque se sono le 17, possiamo dire anche che sono le 5 del pomeriggio.

La funzione esponenziale, abbinata con una funzione di modulo, tende a comportarsi in maniera imprevedibile, non presentando una regolarità graficamente visibile.  Di contro, una funzione tradizionale, come ln(x)-cosx-2=0, nonostante non sia algebricamente risolubile una equazione del tipo f(x)=0, ha un andamento descrivibile e più prevedibile.  Tale prevedibilità la rende inutilizzabile ai fini della crittografia, poiché permette di determinare agevolmente gli intervalli delle possibili soluzioni.

Esempio di funzione tradizionale:

funzione tradizionale

Come abbiamo detto, le funzioni che operano con l'aritmetica dei moduli sono invece imprevedibili, non presentando continuità nei risultati.

Di seguito l'esempio della funzione [3x]7=y:

[3^x]7
Grafico di [3^x]7

In particolare l'equazione che fa al caso di Alice e Bob è l'elevazione a potenza: se ad esempio analizziamo la funzione [5x]6=y, scegliendo un valore di x, ad esempio 2, è estremamente facile calcolare 52 =25 e anche calcolare [25]6=1. E' invece estremamente complicato ricavare x se si conosce solo y [5x]6=1. L'unico modo è fare tentativi provando a sostituire a x i valori 1, 2, 3 e così via.  Nell'esempio precedente la soluzione (2) è facilmente determinabile, avendo utilizzato numeri piccoli, ma i tempi si allungano notevolmente aumentando il valore dei numeri utilizzati. Anche semplicemente in presenza di [453x]21997=5787, occorrerebbero molti tentativi prima di trovare un risultato che verifichi l'equazione.  Per dare un ordine di grandezza facilmente intuibile, ricorrendo a numeri dell'ordine di 1080, anche ipotizzando di poter usufruire delle capacità di calcolo di tutti i computer attualmente esistenti sulla terra, impiegheremmo circa 2000 anni per trovare una possibile x che verifichi l'equazione. Naturalmente l'operazione diretta, possibile solo conoscendo il valore di x, richiede soltanto pochi centesimi di secondo con un qualsiasi computer.

Come possono dunque Alice e Bob sfruttare questi calcoli per il loro problema? Innanzi tutto devono concordare il valore di due numeri, K e P, con l'unica limitazione che P sia un numero primo (divisibile solo per sé stesso o per 1) e che K sia minore di P.

Supponiamo che Alice e Bob abbiano concordato P=11 e K=7.  Visualizziamo ora i due procedimenti svolti da Alice e Bob in modo che possano concordare la chiave segretamente:

Alice

Sceglie un numero casuale A, poniamo 3, e lo sostituisce a x nella funzione concordata: [73]11=y

Calcola facilmente il risultato e trova che y=2

Chiamiamo il risultato M

Alice comunica M a Bob

Bob

Sceglie un numero casuale B, poniamo 6, e lo sostituisce a x nella funzione concordata: [76]11=y

Calcola facilmente il risultato e trova che y=4

Chiamiamo il risultato N

Bob comunica N ad Alice

Normalmente questo sarebbe un passaggio delicato, perche Alice e Bob dovrebbero riuscire a comunicare M e N senza che Eva venga a conoscenza dei due numeri, ma vedremo poi che il fatto che Eva possa venirne eventualmente a conosca è irrilevante.

Scoperto N, Alice calcola [NA]11=y

[43]11=y

y=9

Scoperto M, Bob calcola MB=y [11]

26=y [11]

y=9

Per quella che sembra una miracolosa coincidenza, Alice e Bob hanno ottenuto lo stesso risultato finale 9, usabile come chiave per cifrare i messaggi.

Perché invece Eva, anche qualora scoprisse i valori di K, P, M e N, non potrebbe scoprire la chiave?

Per il fatto che lei, anche se conosce la funzione [7x]11=y (avendo intercettato e scoperto K e P) e se conosce i valori M e N, non puo ricavare i valori A e B, essenziali per scoprire la chiave.  Ciò perché questi dovrebbero essere ricavati dalle funzioni [7A]11=M e [7B]11=N, che non sono invertibili, quindi per lei risolvere il calcolo comporterebbe tempi di fatto lunghissimi. Teoricamente potrebbe riuscirci per tentativi ma, come detto in precedenza, ricorrendo a numeri sufficentemente grandi, le reali possibilità sono praticamente azzerate.

Un ulteriore vantaggio è dato dal fatto che questo sistema impedisce anche agli stessi Alice e Bob di scoprire il numero iniziale A o B scelto dall'amico, garantendo una maggior sicurezza e permettendo ad Alice anche di scrivere a suo cugino Andrea usando sempre gli stessi numeri senza che Bob possa decifrare tali messaggi. Un soggetto non ha quindi bisogno di utilizzare una chiave diversa per ciascun interlocutore, né deve preoccuparsi di proteggere la propria chiave.

Se vogliamo rappresentare questo sistema in modo più semplice e intuitivo, pensiamo che come chiave vengano usati dei colori.

Immaginiamo che Alice e Bob abbiano ciascuno un recipiente da 3 litri contenente un litro della stessa vernice gialla, concordata in precedenza.

Alice sceglie di aggiungere un litro di azzurro cielo al suo recipiente, mentre Bob usa il rosso carminio. A questo punto, mescolate le vernici, Alice spedisce la sua vernice divenuta verde a Bob e Bob spedisce la sua arancione ad Alice.

Infine Alice aggiunge il suo azzurro alla vernice di Bob e lui aggiunge il suo rosso a quella di Alice.

In questo modo entrambi ottengono una vernice di colore uguale, che sarà la loro chiave.

Tuttavia Eva, anche se conosce il colore della vernice iniziale, non può conoscere l'esatta sfumatura dell'azzurro e del rosso usati da Alice e Bob, poiché può averle viste solo mescolate al giallo, e non riuscirà a ricreare alla perfezione il colore finale.

Sistema dello scabmio delle chiavi di Diffie e Hellman

Questa fu la grande intuizione che permise a Hellman e Diffie di confutare una certezza consolidata della crittografia, secondo cui non vi fosse altro modo che concordare preventivamente le chiavi, scambiandosele attraverso un sistema sicuro e segreto.

In realtà, seppure teoricamente ineccepibile, tale sistema non è stato adottato ai fini pratici per un limite intrinseco: oltre al tempo comunque necessario per i calcoli, permaneva comunque la necessità di scambiarsi la chiave segreta iniziale. Ciò nonostante, dobbiamo riconoscere che, grazie a questa fondamentale scoperta, fu compiuto un considerevole passo in avanti nel progresso degli studi crittografici, aprendo la strada ai moderni sistemi di crittografia.