I sistemi che criptano con chiave pubblica e chiave privata garantiscono che i messaggi ricevuti possono essere solo aperti da chi possiede la chiave privata. Quello che non riesco a capire è perché la chiave pubblica usata per criptare non può essere usata per decrittare.

Un algoritmo di crittografia a chiave pubblica (detto anche
asimmetrico) è caratterizzato dal fatto che utilizza due chiavi:
una per cifrare e l’altra per riportare in chiaro il testo cifrato.

La chiave di cifratura può essere resa pubblica, perché
è inutilizzabile per decifrare il testo cifrato ed inoltre da
essa non è possibile1
ricavare la
chiave di decifrazione. Chiunque può usare la chiave pubblica del
corrispondente per cifrare un testo, ma solo il possessore della chiave privata sarà in grado di decifrarlo.

Gli algoritmi di tipo simmetrico, invece, utilizzano la stessa chiave sia per
la cifratura che per la decifratura2,
e sono quindi molto più vulnerabili
perché richiedono che i due corrispondenti comunichino tramite un mezzo
intrinsecamente sicuro la chiave.

Per comprendere il funzionamento degli algoritmi di questo tipo
partiamo da un semplice esempio di algoritmo simmetrico, la sostituzione:
numeriamo le lettere dell’alfabeto da 0 a 23 e definiamo una funzione di
cifratura come segue:

C = (x + K) mod 23   

dove x è il numero corrispondente ad un qualunque carattere del messaggio
in chiaro, K la chiave e
C il numero del carattere cifrato. mod indica la funzione modulo,
ovvero il resto della divisione per 233.

Come si comprende facilmente l’algoritmo consiste nel sostituire ad
ogni carattere un altro carattere ottenuto avanzando di K
passi nell’alfabeto. Ad esempio per K=5, il carattere A viene sostituito da
F, il carattere W da B, ecc.

La chiave di decifratura è però facilmente derivabile
da quella di cifratura, infatti vale -K (o equivalentemente 23-K).

Il più noto algoritmo a chiave pubblica (RSA4) è molto simile
a quello mostrato:

C = (T^E) mod N    Per la cifratura

T = (C^D) mod N    Per la decifratura

dove T
rappresenta il testo in chiaro, e C il testo cifrato; la coppia
(E, N) è la chiave pubblica ed il numero D la chiave privata. Il
simbolo ^ indica l’elevamento a potenza. Anche qui supponiamo di aver
trasformato il testo in una forma numerica equivalente, ad esempio,
come abbiamo fatto
sopra, assegnando un numero ad ogni lettera dell’alfabeto, e
raggruppando più lettere insieme per avere numeri di grandezza
opportuna.
Le due operazioni si basano su una proprietà dell’aritmetica modulo N
per
cui l’operazione inversa di un elevamento a potenza con esponente E è
ancora un elevamento a potenza con esponente D.

Tutto si basa sulla scelta opportuna di E, D, N. È facile
dimostrare5 che
esiste un semplice procedimento per generare moltissime terne E, D, N, mentre
per ricavare il numero D conoscendo solo E ed N è necessario fattorizzare
N, ovvero trovarne i divisori primi. Dato che per N viene scelto un numero
molto grande (dell’ordine di 200 cifre decimali),
questa operazione richiederebbe un tempo enormemente
grande anche sul più veloce dei computer.

Forse è interessante notare che la “robustezza” dell’algoritmo
si basa su “congetture” e non su teoremi, ovvero non è provato
in senso matematico che per derivare la chiave privata sia necessario
fattorizzare il numero N e non è nemmeno provato che non esista
un algoritmo che consenta di fattorizzare in modo semplice (ovvero con un
minor numero di operazioni) un qualunque numero. Allo stato attuale
delle conoscenze quindi non è assolutamente certo che sia impossibile
trovare un metodo in grado di “rompere” l’algoritmo RSA, anche se
il fatto che sia ormai universalmente usato per applicazioni “sensibili”
ci fa capire che gli esperti ritengano assai improbabile che questo metodo
esista.


  1. Più precisamente dovremmo dire che il procedimento
    per ricavare la chiave privata di decifrazione da quella pubblica richiede un
    numero molto alto di operazioni, tanto da renderlo di fatto impossibile.

  2. Oppure le due chiavi sono diverse ma, data una delle due,
    l’altra può essere facilmente calcolata.

  3. Molti algoritmi crittografici si basano sull’aritmetica modulo N.
    Tutti noi siamo abituati ad usare l’artmetica modulo 12 nelle
    operazioni con le ore. In generale si ha aritmetica modulo N quando si
    applicano le operazioni
    ad un insieme finito di numeri [0,N-1] e tutti i risultati vengono
    riportati nello stesso insieme calcolando per ogni risultato il
    resto della divisione per N. Ad esempio in aritmetica modulo 12 si ha:
    9+7=4.

  4. L’algoritmo
    RSA è stato inventato nel 1978 da
    Ron Rivest, Adi Shamir e Leonard Adleman e prende nome dalle
    iniziali dei cognomi degli inventori.

  5. Per una descrizione dettagliata dell’algortimo RSA, si veda:

    http://www.amagri.it/Crittologia/Crittografia/Algoritmi_crittografici/RSA/algoritmo_rsa.htm