RSA (crittografia)

Questa voce o sezione sull'argomento crittografia non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

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.

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.

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.

È 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.

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, ${\displaystyle p}$ e ${\displaystyle 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)
2. si calcola il loro prodotto ${\displaystyle n=pq}$, chiamato modulo (dato che tutta l'aritmetica seguente è modulo n), e il prodotto ${\displaystyle \varphi (n)=(p-1)(q-1)}$, dove ${\displaystyle \varphi (n)}$ è la funzione toziente
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 ${\displaystyle e}$ (chiamato esponente pubblico), coprimo con ${\displaystyle \varphi (n)}$ e più piccolo di ${\displaystyle \varphi (n)}$
5. si calcola il numero ${\displaystyle d}$ (chiamato esponente privato) tale che il suo prodotto con ${\displaystyle e}$ sia congruo a ${\displaystyle 1}$ modulo ${\displaystyle \varphi (n)}$ ovvero che ${\displaystyle ed\equiv 1{\pmod {\varphi (n)}}}$; per calcolare ${\displaystyle d}$ si utilizza l'algoritmo esteso di Euclide

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

La forza dell'algoritmo sta nel fatto che per calcolare ${\displaystyle d}$ da ${\displaystyle e}$ (o viceversa) non basta la conoscenza di ${\displaystyle n}$ ma serve il numero ${\displaystyle \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 ${\displaystyle m}$ viene cifrato attraverso l'operazione ${\displaystyle m^{e}{\pmod {n}}}$ trasformandolo nel messaggio cifrato ${\displaystyle c}$. Una volta trasmesso, ${\displaystyle c}$ viene decifrato con ${\displaystyle c^{d}{\pmod {n}}=m}$. Il procedimento funziona solo se ${\displaystyle m<n}$ e la chiave ${\displaystyle e}$ utilizzata per cifrare e la chiave ${\displaystyle d}$ utilizzata per decifrare sono legate tra loro dalla relazione ${\displaystyle 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 ${\displaystyle {\sqrt[{e}]{c}}\mod n}$, con ${\displaystyle 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.

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

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

Ma sappiamo che ${\displaystyle ed\equiv 1{\pmod {(p-1)(q-1)}}}$, di conseguenza abbiamo che ${\displaystyle ed\equiv 1{\pmod {p-1}}}$ e che ${\displaystyle ed\equiv 1{\pmod {q-1}}}$.

Quindi, per il piccolo teorema di Fermat:

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

Siccome ${\displaystyle p}$ e ${\displaystyle q}$ sono numeri diversi e primi, possiamo applicare il teorema cinese del resto, ottenendo che

${\displaystyle m^{ed}\equiv m{\pmod {pq}}}$

e quindi che

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

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

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

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

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

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

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

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

Quindi alla fine abbiamo decifrato il messaggio.

Lo stesso argomento in dettaglio: 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.

Annotazioni

Fonti

• Algoritmo Blum-Goldwasser
• Crittografia asimmetrica
• Optimal Asymmetric Encryption Padding
• PKCS
• RSA Security

• Wikibooks contiene testi o manuali sull'RSA

• RSA, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Gustavus J. Simmons, RSA encryption, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Opere riguardanti RSA, su Open Library, Internet Archive.
• (EN) Eric W. Weisstein, RSA Encryption, su MathWorld, Wolfram Research.
• (EN) Denis Howe, RSA, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL

Portale Crittografia

Portale Sicurezza informatica