Datemi una chiave e… anzi due!

Il passo decisivo veso l’asimmetria

Diffie, Hellman e Merkle avevano ormai imboccato la strada giusta e avevano dimostrato al mondo dei crittografi professionisti che trasmettere delle chiavi crittografiche in maniera sicura era, ancorché macchinoso, per lo meno possibile.
Uno degli aspetti negativi del procedimento da loro individuato era dovuto al fatto che Alice e Bob devono fare un certo lavoro preparatorio prima di poter effettivamente trasmettersi i messaggi opportunamente cifrati.
Inoltre il metodo descritto permetteva di generare in modo asimmetrico una chiave segreta, ma la chiave in sé era ancora una chiave simmetrica. Era la stessa chiave che sarebbe stata usata sia da Alice che da Bob sia per crittografare che per decrittare i loro messaggi.
Ciò che Diffie continuò a cercare, come descrisse in una conferenza nel 1975, era un sistema in cui le chiavi stesse fossero asimmetriche.
Ciò che serviva era un sistema in cui ci fossero due chiavi, di cui una fosse utilizzabile solo per crittografare ed una solo per decrittare.
In questo modo Alice avrebbe potuto diffondere liberamente la sua chiave per crittografare, che quindi sarebbe divenuta la sua chiave pubblica, per dare la possibilità a chiunque di spedirle dei messaggi crittografati, che nessuno sarebbe stato in grado di decodificare. Lei stessa avrebbe poi utilizzato la sua chiave, che ora chiameremo chiave privata, per decodificare tali messaggi.
Per mantenere l’analogia con cofanetti e lucchetti, è come se Alice mettesse a disposizione dei lucchetti aperti che chiunque potesse utilizzare per sigillare il proprio cofanetto ma solo lei detenesse la chiave per riaprirli.

La ricerca di una funzione che permettesse di individuare delle chiavi con le caratteristiche descritte era aperta e i protagonisti della scoperta questa volta sono tre ricercatori del Laboratorio di Scienza dei Calcolatori del MIT: Ronald Rivest, Adi Shamir e Leonard Adleman.

Partendo da un’idea originale di Rivest, i tre pubblicarono i loro risultati nel 1978 e rivoluzionarono per sempre il mondo dell’informatica moderna sfruttando un’altra funzione unidirezionale, la scomposizione in fattori primi, creando quella che oggi si chiama crittografia RSA dalle iniziali dei loro cognomi.

La matematica ci dice che qualunque numero intero ha una e una sola scomposizione in fattori primi. Se supponiamo di scegliere due numeri primi, chiamiamoli p e q e li moltiplichiamo fra loro per ottenere un numero N, abbiamo la garanzia che non esiste nessun’altra combinazione di numeri che moltiplicati fra loro diano per risultato N.
La particolarità in questo caso è che, avendo il numero N, il processo per risalire a p e q è lungo e laborioso. Se il nostro numero è composto, come avviene nei moderni algoritmi, da centinaia (sic!) di cifre, il tempo per individuare i due fattori di partenza, anche avendo a disposizione capacità di calcolo enormi, è confrontabile con tempi letteralmente galattici!
Questa è l’asimmetria che è stata sfruttata per creare l’algoritmo RSA. Vediamolo nel dettaglio con un esempio semplificato tratto dal volume di Simon Singh riportato in bibliografia.

Alice deve scegliere i due numeri primi che faranno parte della sua chiave privata. Nella realtà questi numeri saranno estremamente grossi, ma in questo caso supporremo che siano scelti p=17 e q=11.
Il numero che risulta dal loro prodotto, detto non a caso modulo, sarà quindi N=187.
Poi Alice dovrà scegliere un altro numero, detto esponente pubblico, che sarà reso noto insieme alla sua chiave pubblica che nel nostro caso sarà e=7.
Siccome tutti i messaggi che sono gestiti attraverso dispositivi informatici sono, in ultima analisi, dei numeri, attraverso dei sistemi di codifica come per esempio ASCII o Unicode, anche il messaggio che andremo a codificare sarà un numero. In questo esempio supponiamo che il messaggio sia M=88
L’operazione di codifica consiste nell’applicare la seguente formula (ci ricorda qualcosa?):

C=M ^e(mod N)

Quindi Bob, che vuole spedirle il messaggio M, dovrà usare la chiave pubblica di Alice e calcolare:

C=88⁷(mod 187) → C=11

Come abbiamo visto nel precedente paragrafo, l’esponenziale modulare non è invertibile e la fattorizzazione di N è virtualmente non praticabile (a parte in questo esempio semplificato), quindi Eva che venisse a conoscenza del valore di C non se ne farebbe assolutamente nulla.
In quanto ad Alice, lei è l’unica che ha la possibilità di rendere invertibile l’esponenziale avendo un’informazione speciale: la fattorizzazione di N.

La decrittazione del messaggio si basa sulla seguente formula:

e x d = 1 [mod (p-1)(q-1)]

e nel nostro caso:

7 x d = 1 (mod 160) → d=23

con d che viene denominato esponente privato.

Quindi Alice per decrittare il messaggio dovrà semplicemente effettuare il calcolo:

M=C^d(mod N) → 11²³(mod 187)=88

In sintesi nel 1978 Rivest, Shamir e Adleman avevano inventato un sistema di lucchetti asimmetrici che si basava sull’uso di una chiave privata, costituita dalla coppia (N,d) e dalla chiave pubblica, costituita dalla coppia (N,e).
Ora si trattava solo di renderlo fruibile a tutto il mondo.