RSA

Da Wikipedia, l'enciclopedia libera.
bussola Disambiguazione – Se stai cercando altri significati, vedi RSA (disambigua).

In crittografia la sigla RSA indica un algoritmo di crittografia asimmetrica, utilizzabile per cifrare o firmare informazioni.

Nel 1976 Whitfield Diffie e Martin Hellman, crittologi americani, hanno ipotizzato la creazione di un cifrario "asimmetrico" composto da "chiavi pubbliche". 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 sia 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 poter realizzare con il cifrario asimmetrico un sistema crittografico pubblico è importante che un utente si crei autonomamente entrambe le chiavi, denominate "diretta" ed "inversa", e ne renda pubblica una soltanto. Così facendo si viene a creare una sorta di "elenco telefonico" a disposizione di tutti gli utenti, che raggruppa tutte le chiavi dirette, mentre quelle inverse saranno tenute segrete dagli utenti che le hanno create e da questi utilizzate solo quando ricevono un messaggio cifrato con la rispettiva chiave pubblica dell'"elenco" da parte di un certo mittente, ottenendo in questo modo i presupposti necessari alla sicurezza del sistema.

Esempi pratici[modifica | modifica sorgente]

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 inversa, sarà anche l'unico a poter decifrare il messaggio, che rimarrà così segreto per tutti gli altri, compresa Alice, che non disponendo della chiave inversa 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 ad essere in possesso della chiave inversa. 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 inversa 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 solo e soltanto da Alice, unica a possedere la chiave inversa 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 crittografando il messaggio con la propria chiave inversa, chiunque sarà in grado di leggere il messaggio, decrittandolo con la sua chiave pubblica, assicurandosi in tal modo che il mittente sia proprio Alice.

L'implementazione tramite algoritmo RSA[modifica | modifica sorgente]

È nel 1978 che questo sistema trova la sua applicazione reale. Infatti sono 3 ricercatori del MIT (Ronald Rivest, Adi Shamir e Leonard Adleman) che hanno saputo implementare tale logica utilizzando particolari proprietà formali dei numeri primi con alcune centinaia di cifre. L'algoritmo da loro inventato, denominato RSA per via delle 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 decrittare un messaggio, ma l'enorme mole di calcoli e l'enorme dispendio in termini di tempo necessario per trovare la soluzione, fa di questo algoritmo un sistema di affidabilità pressoché assoluta.

Ronald Rivest, Adi Shamir e Leonard Adleman nel 1983 hanno brevettato l'algoritmo negli Stati Uniti dal MIT (brevetto 4.405.829, scaduto il 21 settembre 2000); inoltre hanno dato 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 ed altri. Una variante del sistema RSA è utilizzato 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 autentificare gli utenti.

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 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 contenente una chiave segreta, tale chiave verrà poi utilizzata per scambiarsi messaggi tramite un algoritmo a chiave simmetrica (ad esempio AES).

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

Funzionamento[modifica | modifica sorgente]

Per semplificare il funzionamento immaginiamo che A debba spedire un messaggio segreto a B. Occorrono i seguenti passaggi:

  1. B sceglie due numeri primi molto grandi (per esempio di 300 cifre) e li moltiplica con il suo computer (impiegando meno di un secondo).
  2. B invia il numero che ha ottenuto ad A. Chiunque può vedere questo numero.
  3. A usa questo numero per cifrare il messaggio.
  4. A manda il messaggio cifrato a B, chiunque può vederlo, ma non decifrarlo.
  5. B riceve il messaggio e utilizzando i due fattori primi che solo lui conosceva lo decifra.

A e B hanno impiegato pochi secondi a cifrare e decifrare, ma chiunque avesse intercettato le loro comunicazioni impiegherebbe troppo tempo per scoprire i due fattori primi, con cui si può decifrare il messaggio.

In realtà questo sistema non è così semplice, come si può notare dai calcoli descritti nel paragrafo successivo, e per trasmettere grandi quantità di dati occorre tanto tempo per la decifratura, quindi A e B si scambieranno con questo sistema una chiave segreta (che non occupa molto spazio), che poi useranno per comunicare tra loro usando un sistema a crittografia simmetrica, più semplice e veloce.

Operazioni[modifica | modifica sorgente]

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

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

La chiave pubblica è (n, e) , mentre la chiave privata è (n, d) . I due numeri primi p e q possono essere distrutti, anche se spesso vengono mantenuti insieme alla chiave privata.

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 f(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 molto lenta.

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 la chiave e utilizzata per cifrare e la chiave d utilizzata per decifrare sono legate tra loro dalla relazione ed \equiv 1 \pmod{f(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 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) 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[modifica | modifica sorgente]

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

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

  1. p=3 e q=11
  2. n=p*q=3*11=33 e f(n)=(p-1)(q-1)=2*10=20
  3. prendo e=7 , dato che e<20 ed e è coprimo di 20 (non è necessario che e sia primo)
  4. d=3 , infatti ed=7*3=21 \equiv 1 \pmod{20} poiché 21/20=1 con resto 1

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[modifica | modifica sorgente]

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 decrittato il messaggio.

Blind signature[modifica | modifica sorgente]

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

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]