RSA (crittografia)

RSA
Generale
Progettisti	Ronald Rivest, Adi Shamir, Leonard Adleman
Prima pubblicazione	1977
Dettagli
Dimensione chiave	Tipicamente da 1024 bit a 4096 bit (consigliato almeno 2048 bit)
Migliore crittanalisi
	Crivello dei campi di numeri generale per computer classico.; Algoritmo di fattorizzazione di Shor per computer quantistico.

In crittografia la sigla RSA indica un algoritmo di crittografia asimmetrica, inventato nel 1977 da Ronald Rivest, Adi Shamir e Leonard Adleman utilizzabile per cifrare o firmare informazioni.

L'algoritmo RSA si basa sulla difficoltà di fattorizzare un numero molto grande in due numeri primi. Quindi, anche se qualcuno ha accesso all'informazione cifrata e alla chiave pubblica, è molto difficile per loro scoprire la chiave privata che è necessaria per decodificare il messaggio. Questa caratteristica rende l'algoritmo RSA molto sicuro e per questo viene utilizzato per proteggere molte comunicazioni online, come per esempio i pagamenti online o le comunicazioni via e-mail.

Storia

I creatori dell'algoritmo

Ron Rivest

Adi Shamir

Leonard Adleman

Nel 1976 Whitfield Diffie e Martin Hellman, crittologi americani, furono i primi a pubblicare un sistema che si basasse sulla creazione di un cifrario asimmetrico composto da chiavi pubbliche; anche se pochi anni prima ci avevano già pensato James H. Ellis, Clifford Cocks, e Malcolm J. Williamson dei servizi segreti inglesi, la notizia era coperta dal segreto militare e fu rivelata soltanto nel 1997.^[1]

Il sistema di crittografia si basa sull'esistenza di due chiavi distinte, che vengono usate per cifrare e decifrare. Se la prima chiave viene usata per la cifratura, la seconda deve necessariamente essere utilizzata per la decifratura e viceversa. La questione fondamentale è che, nonostante le due chiavi siano fra loro dipendenti, non è possibile risalire dall'una all'altra, in modo che se anche si è a conoscenza di una delle due chiavi, non si possa risalire all'altra, garantendo in questo modo l'integrità della crittografia.

Per ottenere una discreta sicurezza è necessario utilizzare chiavi binarie di almeno 2048 bit. Quelle a 512 bit sono ricavabili in poche ore. Le chiavi a 1024 bit, ancora oggi ampiamente utilizzate, non sono più consigliabili.

Descrizione

Facendo un esempio pratico, se Alice vuole spedire un messaggio a Bob e non vuole che altri all'infuori di Bob possano leggerlo, Alice cercherà sull'elenco la chiave pubblica di Bob e con quella potrà cifrare il messaggio. Essendo Bob l'unico a possedere la chiave privata (in grado quindi di poter decifrare il messaggio cifrato con la chiave pubblica), sarà anche l'unico a poter decifrare il messaggio, che rimarrà così segreto per tutti gli altri, compresa Alice, che non disponendo della chiave privata di Bob, non sarà in grado di decifrare il messaggio da lei stessa creato. Ovviamente il successo di questo sistema si basa sull'assoluta necessità che Bob sia l'unico a essere in possesso della propria chiave privata. In caso contrario, avendo entrambe le chiavi, chiunque potrebbe decifrare agevolmente il messaggio.

Con questo metodo di cifratura è possibile anche garantire la provenienza di un messaggio. Riprendiamo l'esempio precedente: Alice questa volta, prima di cifrare il messaggio usando la chiave pubblica di Bob, lo cifrerà usando la propria chiave privata e solo in un secondo momento lo ri-crittograferà utilizzando la chiave pubblica di Bob. Quando Bob riceverà il messaggio e lo decifrerà usando la propria chiave inversa, otterrà ancora un messaggio crittografato. Quel dato messaggio necessiterà poi della chiave pubblica di Alice per essere decifrato, garantendo in questo modo che il messaggio è stato spedito soltanto da Alice, unica a possedere la chiave privata con la quale era stato crittografato il messaggio.

Più semplicemente, utilizzando questo metodo di cifratura, Alice può mandare messaggi a tutti, garantendo la provenienza. Infatti, cifrando il messaggio con la propria chiave privata, chiunque sarà in grado di leggere il messaggio, decifrandolo con la sua chiave pubblica, assicurandosi in tal modo che il mittente sia proprio Alice.

Implementazione tramite algoritmo RSA

È nel 1978 che questo sistema trova la sua applicazione reale, quando i tre ricercatori del MIT Ronald Rivest, Adi Shamir e Leonard Adleman seppero implementare tale logica utilizzando particolari proprietà formali dei numeri primi con alcune centinaia di cifre. L'algoritmo da loro inventato, denominato RSA dalle iniziali dei loro cognomi, non è sicuro da un punto di vista matematico teorico, in quanto esiste la possibilità che tramite la conoscenza della chiave pubblica si possa decifrare un messaggio; ma l'enorme mole di calcoli e l'enorme dispendio in termini di tempo necessario per trovare la soluzione fanno di questo algoritmo un sistema di affidabilità pressoché assoluta.

Ronald Rivest, Adi Shamir e Leonard Adleman nel 1983 brevettarono l'algoritmo negli Stati Uniti dal MIT (brevetto 4.405.829, scaduto il 21 settembre 2000); hanno dato inoltre vita alla società RSA Data Security, tutelando così i propri interessi commerciali. In seguito la Security Dynamics acquisì la società e vendette l'utilizzo degli algoritmi a società come Netscape, Microsoft e altri. Una variante del sistema RSA è utilizzata nel pacchetto di crittografia Pretty Good Privacy (PGP). L'algoritmo RSA costituisce la base dei sistemi crittografici su cui si fondano i sistemi di sicurezza informatici utilizzati sulla rete Internet per autenticare gli utenti.

Clifford Cocks, matematico britannico che lavorava per un dipartimento di spionaggio, il GCHQ, aveva descritto 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 2005 un gruppo di ricerca riuscì a scomporre un numero di 640 bit (centonovantatrè decimali) in due numeri primi da 320 bit, impiegando per cinque mesi un cluster Opteron con ottanta processori da 2,2 GHz, potenzialmente decifrando un messaggio codificato con RSA-640.

RSA è computazionalmente impegnativo, soprattutto per quanto riguarda una eventuale realizzazione hardware. Di conseguenza, un uso efficiente è quello di sfruttare RSA per codificare un unico messaggio contenente una chiave segreta; tale chiave verrà poi utilizzata per scambiarsi messaggi tramite un algoritmo a chiave simmetrica, come AES.

Oggi, insieme a DSA, RSA è uno degli algoritmi più usati per la cifratura di firme digitali.

Operazioni

RSA è basato sull'elevata complessità computazionale della fattorizzazione in numeri primi. Il suo funzionamento base è il seguente:

si scelgono a caso due numeri primi, $p$ e $q$ abbastanza grandi da garantire la sicurezza dell'algoritmo (per esempio, il più grande numero RSA, RSA-2048, utilizza due numeri primi lunghi più di 300 cifre)
si calcola il loro prodotto $n=pq$ , chiamato modulo (dato che tutta l'aritmetica seguente è modulo n), e il prodotto $\varphi (n)=(p-1)(q-1)$ , dove $\varphi (n)$ è la funzione toziente
si considera che la fattorizzazione di n è segreta e solo chi sceglie i due numeri primi, p e q, la conosce
si sceglie poi un numero $e$ (chiamato esponente pubblico), coprimo con $\varphi (n)$ e più piccolo di $\varphi (n)$
si calcola il numero $d$ (chiamato esponente privato) tale che il suo prodotto con $e$ sia congruo a $1$ modulo $\varphi (n)$ ovvero che $ed\equiv 1{\pmod {\varphi (n)}}$ ; per calcolare $d$ si utilizza l'algoritmo esteso di Euclide

La chiave pubblica è $(n,e)$ , mentre la chiave privata è $(n,d)$ .^{[N 1]}

La forza dell'algoritmo sta nel fatto che per calcolare $d$ da $e$ (o viceversa) non basta la conoscenza di $n$ ma serve il numero $\varphi (n)=(p-1)(q-1)$ , e che il suo calcolo richiede tempi molto elevati; infatti fattorizzare in numeri primi (cioè scomporre un numero nei suoi divisori primi) è un'operazione computazionalmente costosa.

Un messaggio $m$ viene cifrato attraverso l'operazione $m^{e}{\pmod {n}}$ trasformandolo nel messaggio cifrato $c$ . Una volta trasmesso, $c$ viene decifrato con $c^{d}{\pmod {n}}=m$ . Il procedimento funziona solo se $m<n$ e la chiave $e$ utilizzata per cifrare e la chiave $d$ utilizzata per decifrare sono legate tra loro dalla relazione $ed\equiv 1{\pmod {\varphi (n)}}$ , quindi quando un messaggio viene cifrato con una delle due chiavi può essere decifrato solo utilizzando l'altra. L'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 crittografato 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), utilizzare la chiave pubblica per estrarre l'hash dalla firma e verificare che questo sia uguale a quello calcolato localmente sul messaggio ricevuto. Se l'hash utilizzato è crittograficamente sicuro, la corrispondenza dei due valori conferma che il messaggio ricevuto è identico a quello originalmente firmato e trasmesso.

Fondamenti matematici

La decifratura del messaggio è assicurata grazie ad alcuni teoremi matematici; infatti dal calcolo si ottiene:

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

Ma sappiamo che $ed\equiv 1{\pmod {(p-1)(q-1)}}$ , di conseguenza abbiamo 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 {pq}}$

e quindi che

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

Esempio

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

Generazione delle chiavi

$p=3$ e $q=11$
$n=p\cdot q=3\cdot 11=33$
$\varphi (n)=(p-1)(q-1)=2\cdot 10=20$
prendo $e=7$ , dato che $e<20$ ed $e$ è coprimo con $20$ (non è necessario che $e$ sia primo)
$d=3$ ; infatti $ed=7\cdot 3=21\equiv 1{\pmod {20}}$ poiché $21/20=1$ con resto $1$ ^{[N 2]}

Quindi abbiamo la chiave privata $(33,3)$ e la chiave pubblica $(33,7)$ (il fatto che $d$ sia uguale a $p$ è puramente casuale).

Cifratura e decifratura

Prendiamo ora in considerazione il messaggio $m=15$ e cifriamolo per ottenere il messaggio cifrato $c$ ; ovviamente possiamo usare i 33 e 7, ma non 3 che fa parte della chiave privata.

$c=m^{e}{\pmod {n}}=15^{7}{\pmod {33}}=27$

E ora decifriamo $c=27$ per ottenere $m$ ; qui utilizzeremo 3, componente essenziale della chiave privata.

$m=c^{d}{\pmod {n}}=27^{3}{\pmod {33}}=15$

Quindi alla fine abbiamo decifrato il messaggio.

Blind signature

Esiste un formato di firma digitale basato anche su RSA, in cui il contenuto di un messaggio viene nascosto prima di essere firmato, detto blind signature.

Note

Annotazioni

^ Benché da un punto di vista matematico la sola conoscenza di $(n,d)$ sia sufficiente, per motivi di efficienza è possibile conservare esplicitamente i due fattori $p$ e $q$ , la cui conoscenza rende possibile l'utilizzo di un metodo di calcolo più rapido per la cifratura/decifratura.
^ d si può calcolare usando l'Algoritmo esteso di Euclide.