RSA (crittografia)

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.

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.

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.
La fattorizzazione di interi grandi, infatti, è progredita rapidamente mediante l'utilizzo di hardware sofisticati, al punto che potrebbe essere possibile fattorizzare un intero di 1024 bit in un solo anno di tempo, al costo di un milione di dollari (un costo sostenibile per qualunque grande organizzazione, agenzia o intelligence).

Nel 2022 un gruppo di ricercatori cinesi ha dichiarato di aver violato la chiave a 48 bit dell'algoritmo RSA con un computer quantistico a 10 qubit.

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 ad 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 (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.

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,  e  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)
 si calcola il loro prodotto , chiamato modulo (dato che tutta l'aritmetica seguente è modulo n), e il prodotto , dove  è 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  (chiamato esponente pubblico), coprimo con  e più piccolo di  
 si calcola il numero  (chiamato esponente privato) tale che il suo prodotto con   sia congruo a  modulo  ovvero che ; per calcolare  si utilizza l'Algoritmo esteso di Euclide

La chiave pubblica è , mentre la chiave privata è .

La forza dell'algoritmo sta nel fatto che per calcolare  da  (o viceversa) non basta la conoscenza di  ma serve il numero , 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  viene cifrato attraverso l'operazione  trasformandolo nel messaggio cifrato . Una volta trasmesso,  viene decifrato con .
Il procedimento funziona solo se  e la chiave  utilizzata per cifrare e la chiave  utilizzata per decifrare sono legate tra loro dalla relazione , 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 , con  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:

Ma sappiamo che , di conseguenza abbiamo che  e che .

Quindi, per il piccolo teorema di Fermat:

 e 

Siccome  e  sono numeri diversi e primi, possiamo applicare il teorema cinese del resto, ottenendo che

e quindi che

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 .

Generazione delle chiavi
  e 
  e 
 prendo , dato che  ed  è coprimo con  (non è necessario che  sia primo)
 ; infatti  poiché  con resto 

Quindi abbiamo la chiave privata  e la chiave pubblica  (il fatto che  sia uguale a  è puramente casuale).

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

E ora decifriamo  per ottenere ; qui utilizzeremo 3, componente essenziale della chiave privata.

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

Voci correlate
 Algoritmo Blum-Goldwasser
 Crittografia asimmetrica
 PKCS
 Optimal Asymmetric Encryption Padding

Altri progetti

Collegamenti esterni 
 
 
 

Crittosistemi asimmetrici
Crittosistemi di firma digitale