Storia

Nell’ambito della crittografia, RSA è un algoritmo di cifratura a chiave pubblica; allo stato attuale delle cose, è ritenuto uno dei più sicuri ed infatti viene impiegato spesso in vari protocolli di commercio digitale.
L’algoritmo venne reso pubblico per la prima volta nel 1977 al Massachusetts Institute of Technolgy. Il nome deriva dalle inziali dei cognomi dei suoi creatori: Ronald Rivest, Adi Shamir e Leonard Adleman.
Sebbene ad un risultato simile fosse giunto alcuni anni prima anche Clifford Cocks, visto che la sua scoperta non venne mai dichiarata se non nel 2000, è noto che i tre ricercatori arrivarono alla stessa conclusione indipendetemente.

Procedimento di creazione delle chiavi

L’algoritmo richiede due chiavi, una pubblica e privata: quella pubblica può essere vista e conosciuta da tutti e sarà utilizzata per cifrare i messaggi. Tuttavia, il messaggio cifrato non risulterà leggibile a nessuno, poiché solo il destinatario possiede la chiave privata necessaria per  decifrare il messaggio. Possiamo riassumere brevemente il procedimento per generare le due chiavi:

1. Scegliete due numeri primi p e q diversi tra loro molto grandi (180~200 cifre);
2. Calcolate n = pq (n verrà utilizzato come modulo sia per la chiave privata che per la chiave pubblica);
3. Calcolate x = ( p - 1 )( q - 1 );
4. Calcolate un numero e tale che 1 < e < x  e (e, x) siano coprimi, ovvero il loro Massimo Comune Divisore sia uguale a 1;
5. Trovate un numero d che soddisfi l’equivalenza de % x = 1, a sua volta riscrivibile come d = ( 1 + nx ) / e.

La chiave pubblica è formata dal modulo n e dall’esponente pubblico e.
La chiave privata è formata dal modulo n e dall’esponente privato d, che deve essere tenuto nascosto.

Cifrare il messaggio

Alice trasmette le sue chiavi pubbliche ( n, e ) a Bob (Più in generale, le pubblica affinché chiunque possa mandarle un messaggio) e mantiene segreta la chiave privata. Bob vuole spedire un messaggio M ad Alice.

Per prima cosa, Bob trasforma il messaggio M in un numero m < n utilizzando uno schema precedentemente definito. A questo punto calcola il testo cifrato c in questo modo:

c = me % n

Bob adesso non deve far altro che trasmettere c ad Alice.

Decifrare il messaggio

Alice può ricavare m da c utilizzando la sua chiave privata d nel modo seguente:

m = cd % n

Una volta ottenuto m, riapplicando lo schema prestabilito, Alice potrà ricavare M.
Possiamo ricavare la validità di ciò in modo abbastanza semplice; innanzitutto, sappiamo che:

cd % n = med

Sapendo inoltre che ed % (( p - 1 )( q - 1 )) = 1, e di conseguenza:

ed % ( p - 1) = 1 and ed % ( q - 1 ) = 1

Possiamo riscrivere l’ultima formula come:

ed = k( p - 1) and ed = h ( q - 1 )

Ora, se m non è un multiplo di p i due numeri sono coprimi perché p è primo; e per il piccolo teorema di Fermat:

m( p – 1 )% p = 1

Quindi, usando la prima espressione per ed:

med % p = mk( p – 1 ) + 1 = (mp – 1)km = 1km = m  

Utilizzando la seconda espressione, possiamo concludere similmente:

med % q = m

Infine:

cd % n = m

Firma digitale

Ci si pone ora un problema: chiunque potrebbe inviare un messaggio sfruttando la chiave pubblica e spacciandosi per un’altra persona. Come ovviare ciò? Semplicemente, allegando in fondo al messaggio la propria “firma”, ottenuta utilizzando il procedimento normalmente utilizzato per decifrare. In questo modo, facendo notare al destinatario che è un allegato non facente parte del messaggio, egli potrà decifrarlo con la propria chiave privata.

Sicurezza

La sicurezza dell’algoritmo si basa essenzialmente su due problemi matematici: il problema della fattorizzazione dei numeri e il cosiddetto “problema RSA”.
E’ infatti risaputo che non è stato ancora trovato un algoritmo che riesca, in tempo polinomiale, a scomporre un numero nei suoi fattori primi. Inoltre, sufficiente sicurezza è data dal fatto che i numeri utilizzati sono molto probabilmente autentici primi: utilizzando un test probabilistico come quello di Miller-Rabin le possibilità che il numero probabilmente primo ottenuto non sia un vero primo sono una su qualche milione.
La sicurezza dell’RSA cresce quindi in modo direttamente proporzionale alla lunghezza di n.

Per risolvere invece il problema RSA sta nel non riuscire a fattorizzare il modulo n. Riuscendoci, un ipotetico attaccante sarebbe in grado di decifrare la chiave segreta utilizzata a partire da quella pubblica. Tuttavia, come suddetto, non è stato trovato nessun metodo per fattorizzare degli interi in tempo polinomiale su un classico computer, anche se non è stato dimostrato che un tale metodo non esista.

Considerazioni

Tra i principali problemi di questo algoritmo sono da annoverare:
• La velocità: RSA è molto più lenti degli altri sistemi di crittografia simmetrica; difatti, nella pratica,    Bob cifra il messaggio con un algoritmo di crittografia simmetrico e cifra la chiave simmetrica con RSA, trasmettendo il tutto ad Alice. Ella dovrà di conseguenza eseguire due processi inversi per ottenere il messaggio originale;
• La distribuzione delle chiavi: praticamente scontato, le chiavi vanno pubblicate e verificate con cura. Se colei che si spaccia per Alice diffonde delle finte chiavi a nome della vera Alice, Bob invierà chiaramente un messaggio illeggibile ad Alice ma che gradirà ricevere la finta Alice ad insaputa di Bob.