Renato Betti


LO SCAMBIO DELLA CHIAVE

Riprendiamo Alice e Bob alle prese con il problema di scambiarsi una chiave da usare per le loro comunicazioni personali, al riparo dalla curiosità di Charlie. Non hanno la possibilità di incontrarsi ma dispongono di macchine con una buona capacità di calcolo e di comunicazione, pur sapendo che le loro e-mail sono regolarmente intercettate. Procederanno in questo modo: per telefono -anch'esso intercettato dall'invidioso Charlie- fissano un numero intero positivo n; poi ciascuno di loro ne sceglie per proprio conto un altro, senza rivelarlo a nessuno: Alice fissa a e Bob fissa b, Alice comunica a Bob il valore di na e Bob le comunica il valore di nb (e Charlie ascolta tutto). Ora Alice calcola nab semplicemente elevando al suo esponente segreto a il valore che Bob le ha comunicato e analogamente Bob calcola lo stesso valore elevando na all'esponente b che solo lui conosce. Tutto qui (nella proprietà commutativa del prodotto):

(na)b = (nb)a = nab

ed entrambi conoscono questo numero, che servirà loro da chiave crittografica. Il deluso Charlie conosce separatamente na ed nb ma non a e b, per i quali dovrebbe calcolare due logaritmi in base n. Questo è il suo problema, perché Alice e Bob hanno scelto dei numeri (n, a e b) abbastanza alti per mettere i sistemi di calcolo di Charlie al di fuori da questa possibilità, semplice in linea di principio ma disperatamente lungo nella pratica.
Si capisce dove sta il punto: il calcolo degli esponenziali, con un sistema anche poco o potente, si può fare facilmente mentre il suo inverso, il logaritmo, può richiedere risorse di calcolo intollerabili in termini di tempo.



Diffie e Hellman
Questa è l'idea che è sorta negli anni `70 ed è stata poi pubblicata in Diffie e Hellman [7]: dotarsi di una funzione - invertibile sì, altrimenti non è possibile decifrare, ma facile da calcolare in un senso e molto difficile, lunga o praticamente impossibile da calcolare in senso inverso - una funzione che con la terminologia anglosassone ormai in voga viene detta trapdoor, a trabocchetto.

È facile cadere, mentre risalire risulta praticamente impossibile (a meno che non si conosca una via segreta).

Una di queste funzioni, di fatto quella che viene usata nelle più diffuse implementazioni dei sistemi crittografici, è data dal prodotto di numeri interi: mentre questa è un'operazione facile da eseguire anche fra numeri con molte cifre (pur di disporre di strumenti di calcolo abbastanza potenti), l'operazione inversa che è quella di scomposizione in fattori può risultare intollerabilmente lunga. Le stime relative alla fattorizzazione di un numero di qualche centinaio di cifre decimali, pur avendo a disposizione i più moderni sistemi di calcolo veloce, si misurano ancora in termini di milioni di anni. Si tratta di un problema di Teoria dei numeri che sembra computazionalmente intrattabile.