La crittografia a chiave pubblica

di Fabrizio Sinopoli

scritto il

La crittografia a chiave pubblica rappresenta una rivoluzione rispetto alla crittografia tradizionale.

Proprio con queste parole (“Siamo all’inizio di una rivoluzione nella crittografia”) infatti, nel Maggio 1976, Whitfield Diffie e Martin Hellman, due ricercatori della Stanford University, annunciano la nascita della crittografia a chiave pubblica nell’articolo “New Direction in Cryptography“, pubblicato su “IEEE Transactions on Information Theory” del Novembre 1976.

Contrariamente alla crittografia a chiave segreta, la crittografia a chiave pubblica prevede l’utilizzo di due chiavi distinte: una detta chiave pubblica e l’altra detta chiave privata.

La chiave pubblica viene utilizzata nel processo di codifica e può essere tranquillamente resa disponibile a chiunque, anche utilizzando canali di comunicazione non sicuri. La chiave privata viene invece utilizzata per la decodifica del messaggio cifrato e deve quindi necessariamente essere custodita nel modo più sicuro possibile.

Ecco come avviene il processo di cifratura e di decifratura utilizzando un sistema di crittografia a chiave pubblica, supponendo che Alice debba spedire un messaggio a Bob:

  • Alice e Bob si accordano sull’algoritmo a chiave pubblica da adottare;
  • Bob spedisce la propria chiave pubblica ad Alice. (In alternativa: Alice recupera la chiave pubblica di Alice da un database);
  • Alice cifra il proprio messaggio M utilizzando la chiave pubblica di Bob, ottenendo il testo cifrato C;
  • Alice invia a Bob il testo cifrato ;
  • Bob decifra il testo cifrafo C con la propria chiave privata;

Da un punto di vista matematico, la crittografia a chiave pubblica si basa sul concetto di trapdoor one-way function.

Una funzione a una via (one-way function) è una funzione f() tale che:

  • dato x, è “facile” calcolare f(x);
  • dato f(x), è “difficile” ricavare x;

Come si può notare, i termini “facile” e “difficile” sono utilizzati tra virgolette, in quanto essi vanno intesi in senso computazionale: il calcolo della funzione inversa è teoricamente possibile, ma in pratica non si conosce nessun sistema efficiente per farlo. Quindi, queste funzioni sono “percorribili” in un solo senso (one-way), in quanto sembra essere un problema intrattabile quello di “tornare indietro”.

La funzione one-way con trapdoor (ossia con una via d’uscita) costituisce un particolare tipo di funzione one-way con un’ulteriore proprietà rispetto a queste ultime: dato y (un’informazione segreta) e f(x), è facile ricavare x.

La crittografia a chiave pubblica utilizza proprio questo tipo di funzione: si utilizza una trapdoor one-way function per codificare cosicché solo chi possiede l’informazione segreta è in grado di decodificare.

L’esempio più classico è costituito dall’algoritmo RSA sviluppato da Rivest, Shamir e Adleman (che vedremo in un prossimo articolo): l’idea è quella di utilizzare come funzione one-way la fattorizzazione di due numeri primi. Infatti, mentre è facile calcolarne il prodotto, risulta difficile, dato il prodotto, recuperare i fattori.