Algoritmo RSA
L’algoritmo che ha incontrato maggiore diffusione nelle comunicazioni e servizi Internet è l’algoritmo RSA, dal nome degli ideatori Ron Rivest, Adi Shamir, Leonard Adleman.
Pur non rappresentando uno standard ufficiale, l’algoritmo RSA ha conosciuto, fin da quando è stato pubblicato nel 1977, un enorme successo.
La robustezza dell’algoritmo RSA è intrinsecamente legata alla difficoltà computazionale di riuscire a fattorizzare numeri molto grandi.
Dato un numero n, preferibilmente molto grande, non esistono infatti metodi affidabili per trovare due numeri primi p e q tali che il loro prodotto abbia per risultato n.
L’eventuale scoperta di un metodo per ottenere, in un tempo computazionalmente limitato, i fattori p e q che danno origine a n renderebbe completamente inaffidabile l’intero algoritmo.
L’algoritmo RSA prevede infatti l’utilizzo di una chiave privata ricavata a partire dai numeri primi p e q mantenuti segreti.
La difficoltà di ricavare tale chiave a partire dalla chiave pubblica coincide con la difficoltà di fattorizzare il prodotto n nelle sue componenti.
Come tutti gli algoritmi già analizzati nei precedenti articoli, anche RSA è in grado di processare messaggi M di lunghezza limitata.
L’utilizzo di chiavi più lunghe rende possibile la codifica di messaggi M più lunghi.
Il numero di bit che possono essere processati è legato al valore di n, in quanto è necessario che la rappresentazione binaria di M sia un numero compreso tra 0 e n-1.
Anche per questo motivo è opportuno che n sia molto grande.
L’algoritmo RSA produce blocchi cifrati C a loro volta minori di n e quindi rappresentabili con lo stesso numero di coefficienti binari.
La codifica di messaggi maggiori di n può essere realizzata utilizzando uno degli schemi proposti per la frammentazione/codifica di messaggi lunghi.
La codifica RSA prevede l’uso di operatori esponenziali in aritmetica modulo n.
Il risultato del processo di codifica è C = Me.
La stessa funzione viene usata per la decodifica, ma con un esponente diverso (M’ = Cd mod n).
La scelta degli esponenti d ed e (e del modulo n) viene effettuata in modo che il messaggio ricostruito M’ coincida con il messaggio originale M.
Per poter operare correttamente entrambi i partecipanti devono conoscere preventivamente il valore del modulo n.
Per l’operazione di codifica è sufficiente conoscere l’esponente e, per l’operazione di decodifica è necessario invece conoscere l’esponente d.
L’utilizzo di due esponenti diversi per le due diverse fasi rappresenta la peculiarità di questo algoritmo asimmetrico.
Nello schema RSA la chiave privata è quindi rappresentata dalla coppia {d, n}, mentre la chiave pubblica è rappresentata dalla coppia {e, n}.
Negli anni in cui la cifratura asimmetrica era oggetto di studio da parte di numerosi studiosi, Rivest, Shamir e Aldeman sono riusciti a identificare una soluuzione elegante e robusta per:
-
trovare tre valori interi e, d, n tali che Med mod n = M per ogni possibile messaggio M < n;
-
calcolare in maniera computazionalmente semplice Me mod n e Cd mod n per ogni possibile messaggio M < n;
-
determinare l’esponente d in maniera che sia computazionalmente impossibile ricavarlo a partire dalla coppia {e, n }.
Il processo per la generazione delle chiavi utilizzate dall’algoritmo RSA è abbastanza complesso.
Stabilita la lunghezza delle chiavi pubbliche e private da determinare (per default oggi si consiglia di utilizzare chiavi lunghe almeno 2048 bit), la loro generazione si svolge secondo i seguenti passi:
-
si elegge una coppia di due numeri primi p e q molto grandi che non deve essere mai resa nota.
Se p e q finiscono nelle mani di un avversario, egli può facilmente ripetere il processo di generazione della chiave privata e ricavare l’esponente d. -
Si calcola il valore n = p*q.
-
Si calcola il valore Θ(n) = (p-1)(q-1) con p e q numeri primi, implica che Θ(n) coincide con il numero di possibili divisori del numero n.
Il valore Θ(n) viene utilizzato per la determinazione dei due esponenti d ed e. -
Si sceglie l’esponente e della chiave pubblica in modo che risulti minore di n e primo rispetto a Θ(n).
- si determina l’esponente d della chiave privata in modo che valga la relazione d= e-1 mod Θ(n).
L’esponente d è l’inverso moltiplicativo dell’esponente e modulo Θ(n).
La scelta di e, d e Θ(n) consente di sfruttare le seguenti equivalenze (in aritmetica mod(n)):
Cd = Med = Mk(p-1)(q-1)+1 = M * Mk(p-1)(q-1) = M* 1 = M.
Operando in aritmetica modulo n, l’algoritmo RSA permette inoltre di ridurre i risultati parziali delle operazioni di codifica e decodifica effettuando opportune divisioni modulo n, senza modificare il risultato finale.
Questa proprietà rende più pratico l’impiego dell’algoritmo, consentendo l’utilizzo di registri di dimensione limitata per svolgere i calcoli.
In condizioni generali la velocità dell’algoritmo RSA è fino a 1000 volte più bassa di quella raggiungibile con algoritmi simmetrici equivalenti in termini di robustezza.
Questa minore velocità è dovuta a due distinti fattori.
L’utilizzo di chiavi sensibilmente più lunghe di quelle utilizzate negli algoritmi simmetrici e l’utilizzo dell’operatore esponenziale, computazionalmente più oneroso delle operazioni matematiche previste negli algoritmi simmetrici.
Le chiavi usate dall’algoritmo RSA sono considerevolmente più lunghe di quelle usate con gli algoritmi simmetrici.
Questa sostanziale differenza, non deve indurre gli utenti a credere che un’applicazione che implementa l’algoritmo RSA sia più sicura rispetto ad un’applicazione che implementa algoritmi simmetrici con chiavi a 128 bit.
L’interpretazione più corretta è invece la seguente: occorre utilizzare chiavi sensibilmente più lunghe con l’algoritmo RSA per ottenere un livello di sicurezza paragonabile a quello degli algoritmi simmetrici, poichè molti valori dello spazio delle possibili chiavi non potranno mai essere utilizzati come chiavi RSA (in quanto non rispettano le proprietà richieste).
La conseguenza immediata di questo fatto è la necessità di un tempo computazionale maggiore per effettuare l’operazione di codifica e decodifica.
Per questo motivo è preferibile utilizzare l’algoritmo RSA per codificare messaggi brevi, generalmente rappresentanti le chiavi comuni utilizzate successivamente da algoritmi simmetrici più veloci, piuttosto che l’intero flusso di dati.
L’algoritmo RSA richiede inoltre un tempo sensibilmente maggiore degli altri algoritmi per la creazione delle chiavi pubbliche e delle chiavi private.
La differenza fondamentale con gli algoritmi simmetrici è che la chiave non può essere semplicemente un numero casuale, costituito da un prestabilito numero di bit.
In RSA le chiavi prescelte devono rispettare specifiche proprietà, il cui test richiede una serie di operazioni tutt’altro che banali.
Il primo problema pratico che si incontra nel generare le chiavi RSA consiste nel determinare due numeri primi p e q.
Purtroppo non esiste un metodo veloce per provare senza incertezze che un numero casuale è realmente un numero primo.
Per questo nella scelta di p e q si procede utilizzando alcuni metodi matematici che consentono di stabilire con buona probabilità se il numero prescelto è un numero primo.
La seconda difficoltà computazionale è generare l’esponente e primo rispetto a Θ(n).
Scelto l’esponente casualmente, occorre testare che sitratta di un numero primo rispetto a Θ(n).
per effettuare questo test si può utilizzare l’algoritmo di Euclide che permette di calcolare anche l’inverso moltiplicativo di e mod Θ(n).
Il livello di sicurezza dell’algoritmo RSA risiede fondamentalmente nella difficoltà computazionale di ricavare i due numeri primi p e q conoscendo il loro prodotto n.
Al momento non sono noti metodi per affrontare questo problema, al di là di quelli che prevedono di testare tutte le possibili combinazioni (brute-force attack).
È tutt’ora valito un challenge, promosso dalla stessa fondazione RSA, in cui si invitano i crittoanalisti a cimentarsi nella fattorizzazione di alcuni numeri n molto lunghi.
I risultati fin qui ottenuti dimostrano che con reti di calcolo distribuito è possibile arrivare a fattorizzare numeri di oltre 600 bit.
Scegliendo (come accade spesso) chiavi di 2048 bit un utente dovrebbe essere al riparo da attacchi ancora per molti anni.
