Crittografia/RSA

In crittografia l'acronimo RSA indica un algoritmo di crittografia asimmetrica, utilizzabile per cifrare o firmare informazioni.

Storia

L'algoritmo RSA è stato descritto nel 1977 da Ronald Rivest, Adi Shamir e Len Adleman al Massachusetts Institute of Technology; le lettere RSA vengono proprio dalle iniziali dei cognomi.

Clifford Cocks, un matematico britannico che lavorava per un dipartimento di spionaggio, il GCHQ, descrisse un sistema equivalente in un documento interno nel 1973. I documenti furono posti sotto segreto e, visto il costo relativamente alto delle macchine necessario a quel tempo per implementarlo, non ci furono ulteriori indagini né prove pratiche e la cosa fu considerata come una curiosità, per quanto se ne sa. La scoperta di Cocks fu resa pubblica solo nel 1997.

Nel 1983 l'algoritmo fu brevettato negli Stati Uniti dal MIT (brevetto 4.405.829). Il brevetto è scaduto il 21 settembre 2000.

Nel 2005 un gruppo di ricerca riuscí a scomporre un numero di 640 bit (193 decimali) in due numeri primi da 320 bit, impiegando per cinque mesi un cluster Opteron con 80 processori da 2,2 GHz, potenzialmente decifrando un messaggio codificato con RSA-640.

Fatto abbastanza rilevante è che RSA è computazionalmente impegnativo, soprattutto per quanto riguarda una eventuale realizzazione hardware. Di conseguenza un attuale buon utilizzo è quello di sfruttare RSA per codificare un unico messaggio contentene una chiave segreta, tale chiave verrà poi utilizzata per scambiarsi messaggi tramite un algoritmo a chiave segreta (ad esempio AES).

Oggi, insieme a DSS, RSA e' uno degli algoritmi piu' usati per la cifratura di firme digitali.

Operazioni

RSA è basato sul problema complesso della fattorizzazione in numeri primi. Il suo funzionamento base è il seguente:

1. si scelgono a caso due numeri primi, $p\,$ e $q\,$, l'uno indipendentemente dall'altro, abbastanza grandi da garantire la sicurezza dell'algoritmo
2. si calcola il loro prodotto $n=pq\,$, chiamato modulo (dato che tutta l'aritmetica seguente è modulo n)
3. si sceglie poi un numero $e\,$ (chiamato esponente pubblico), più piccolo e coprimo con $(p-1)(q-1)\,$
4. si calcola il numero $d\,$ (chiamato esponente privato) tale che $e*d\equiv 1{\pmod {(p-1)(q-1)}}\,$

La chiave pubblica è $(n,e)\,$, mentre la chiave privata è $(n,d)\,$. I fattori $p\,$ e $q\,$ possono essere distrutti, anche se spesso vengono mantenuti all'interno della chiave privata.

La forza dell'algoritmo è che per calcolare $d\,$ da $e\,$ (così come il contrario) non basta la conoscenza di $n\,$, ma serve il numero $(p-1)(q-1)\,$, infatti fattorizzare (cioè scomporre un numero nei suoi divisori) è un'operazione molto lenta, soprattutto se $n\,$ è un numero grande a sufficienza, poiché non si conoscono algoritmi efficienti.

Un messaggio $m\,$ viene cifrato attraverso l'operazione $m^{e}{\pmod {n}}\,$, mentre il messaggio $c\,$ viene decifrato con $c^{d}=m^{ed}=m^{1}{\pmod {n}}\,$. Il procedimento funziona solo se la chiave $e\,$ utilizzata per cifrare e la chiave $d\,$ utilizzata per decifrare sono legate tra loro dalla relazione $ed\equiv 1{\pmod {n}}\,$, e quindi quando un messaggio viene cifrato con una delle due chiavi può essere decifrato solo utilizzando l'altra. Tuttavia proprio qui si vede la debolezza dell'algoritmo: si basa sull'assunzione mai dimostrata (nota come assunzione RSA, o RSA assumption in inglese) che il problema di calcolare ${\sqrt[{e}]{c}}\mod n$ con $n\,$ numero composto di cui non si conoscono i fattori sia computazionalmente non trattabile.

La firma digitale non è altro che l'inverso: il messaggio viene crittato con la chiave privata, in modo che chiunque possa, utilizzando la chiave pubblica conosciuta da tutti, decifrarlo e, oltre a poterlo leggere in chiaro, essere certo che il messaggio è stato mandato dal possessore della chiave privata corrispondente a quella pubblica utilizzata per leggerlo.

Per motivi di efficienza e comodità normalmente viene inviato il messaggio in chiaro con allegata la firma digitale di un hash del messaggio stesso; in questo modo il ricevente può direttamente leggere il messaggio (che è in chiaro) e può comunque utilizzare la chiave pubblica per verificare che l'hash ricevuto sia uguale a quello calcolato localmente sul messaggio ricevuto. Se i due hash corrispondono anche il messaggio completo corrisponde (questo, ovviamente, solo se l'hash utilizzato è crittograficamente sicuro).

Fondamenti matematici

La decrittazione del messaggio è assicurata grazie ad alcuni teoremi matematici, infatti dal calcolo noi otteniamo

$c^{d}=(m^{e})^{d}=m^{ed}{\pmod {n}}\,$

Ma sappiamo che $ed\equiv 1{\pmod {p-1}}$ e che $ed\equiv 1{\pmod {q-1}}$ quindi, per il piccolo teorema di Fermat

$m^{ed}\equiv m{\pmod {p}}\,$ e $m^{ed}\equiv m{\pmod {q}}\,$

Siccome $p\,$ e $q\,$ sono numeri diversi e primi, possiamo applicare il Teorema cinese del resto, ottenendo che

$m^{ed}\equiv m{\pmod {p*q}}\,$

e quindi che

$c^{d}\equiv m{\pmod {n}}\,$

Esempio

Ecco un esempio di criptazione e decriptazione RSA. I numeri scelti sono volutamente primi piccoli, ma nella realtà sono usati numeri dell'ordine di $10^{100}$.

Generazione delle chiavi

1. $p=61\,$ e $q=53\,$, $(p-1)(q-1)=3120\,$
2. $n=p*q=61*53=3233\,$
3. $e=17\,$, $e<n\,$ ed è coprimo per 3120 (in questo caso è primo, ma in generale non è necessario)
4. $d=2753\,$ infatti $e*d=2753*17=46801\equiv 1{\pmod {(p-1)(q-1)}}\equiv 1{\pmod {3120}}\,$ poiché $46801/3120=15\,$ con resto $1\,$

Quindi abbiamo la chiave pubblica $(3233,17)\,$ e la chiave privata $(3233,2753)\,$.

Cifratura e decifratura

Prendiamo ora in considerazione il messaggio $m=123\,$ e cifriamolo per ottenere il messaggio cifrato $c\,$, ovviamente possiamo usare i 3233 e 17, ma non 2753 che fa parte della chiave privata.

$c=m^{e}{\pmod {n}}=123^{17}{\pmod {3233}}=855\,$

E ora decifriamo $c=855\,$ per ottenere $m\,$; qui utilizzeremo 2753, componente essenziale della chiave privata.

$m=c^{d}{\pmod {n}}=855^{2753}{\pmod {3233}}=123\,$