RSA è un algoritmo di crittografia a chiave simmetrica che nasce nel 1977 dagli inventori Ron Rivest, Adi Shamir e Leonard Adleman (dalle cui iniziali deriva il nome “RSA”).
Indice degli argomenti
Cos’è l’algoritmo RSA: una spiegazione dettagliata
Come tutti gli algoritmi di crittografia a chiave asimmetrica, esso impiega due chiavi, una pubblica e una privata, che sono matematicamente correlate tra di loro per effettuare le operazioni di cifratura e decifratura dei dati. In particolare, chiunque voglia utilizzare questo algoritmo sarà in possesso della propia coppia di chiavi e condividerà la propira chiave pubblica con le altre persone con cui vorrà comunicare, mentre terrà segreta e non condivisa la propria chiave privata.
Chiunque venga in possesso della suddetta chiave pubblica potrà utilizzarla per cifrare i dati da inviare al relativo proprietario. Esso infatti, data la relazione matematica tra la chiave pubblica con cui sono cifrati i dati e la relativa chiave privata, sarà l’unico in grado di decrifrare il messaggio.
Per capire meglio il modo in cui questo meccanismo funziona, dobbiamo descrivere i prinicipi matematici su cui l’algoritmo RSA si basa.
I principi matematici alla base dell’RSA
L’algoritmo RSA si basa sul principio dell’esponenziazione modulare. Le chiavi pubblica e privata di RSA non sono altro che due numeri interi tali che la seguente equazione è soddisfatta:
In questa equazione n rappresenta il modulo dell’algoritmo RSA. La sua lunghezza è conosciuta e va solitamente dai 1024 ai 4096 bit di lunghezza (ma può arrivare anche fino a 16384 bit). Il suo valore viene calcolato (nel metodo classico) sulla base della fattorizzazione di due numeri interi p e q che vengono generati randomicamente durante l’algoritmo di generazione della coppia di chiavi RSA. Una voltà generati randomicamente, vengono sottoposti a dei test di primalità e vengono presi come fattori del modulo n solo in caso questi test siano positivi. Infine, m rappresenta il messaggio.
La chiave pubblica di RSA che è conosciuta a chiunque (potenzialmente) è composta dalla coppia (n, e). Mentre la chiave privata è rappresentata dall’esponente d.
L’operazione di cifratura è rappresentata dall’esponenziazione del messaggio m tramite l’esponente e della chiave pubblica:
Questa operazione può essere effettuata da chiunque conosca l’esponente e ed il valore del modulo n, che sono infatti le due informazioni rese pubbliche da chi ha generato la coppia di chiavi.
L’operazione di decrifratura, invece, avviene tramite l’esponenziazione del crittotesto c tramite l’esponente d della chiave privata:
Essendo la chiave privata (e quindi l’esponente d) conosciuta solo al proprietario della coppia di chiavi RSA, questa operazione può essere effettuata solo da quest’ultimo, rendendo sicuro il contenuto m.
I metodi di generazione del modulo n e degli esponenti d ed e sono ora standardizzati e descritti nello standard FIPS 186-5. Lo stesso standard descrive anche i test di primalità da effettuare sui due fattori q e p del modulo n.
La sicurezza dell’algoritmo RSA si basa principalmente su:
- La difficoltà di fattorizzazione del modulo n.
- La difficoltà di computazione dell’esponente d partendo dalla conoscenza di n ed e (conosciuto anche com RSA Problem).
La formulazione dell’RSA problem è: date le informazioni conosciute ad un potenziale attaccante (il crittotesto c, l’esponente e ed il modulo n), recuperare il valore m (quindi il messaggio in chiaro) tale che l’equazione di cifratura sia soddisfatta è un problema computazionalmente impossibile da risolvere in un tempo utile.
Il metodo più efficace per risolvere questo problema risulta essere proprio quello di fattorizzare il modulo n, che permetterebbe di risalire a p e q e, di conseguenza al valore dell’esponenente d che permetterebbe di decrifrare il messaggio m.
Da qui capiamo quindi perché i fattori p e q vengano scelti per essere numeri primi. Come tali infatti non posso essere a loro volta fattorizzati in numeri più piccoli, il che rende la fattorizzazione del modulo n ancora più complessa da parte di un eventuale attaccante.
È chiaro anche come la siucurezza di questo sistema sia strettamente legata alle capacità computazionali di chi prova ad attaccarlo ed anche alla lunghezza dei numeri che vengono utilizzati (che dipende direttamente dalla lunghezza in bit del modulo n).
Applicazioni dell’RSA nella crittografia a chiave pubblica
Si sa come, in generale, gli algoritmmi a chiave asimmetrica siano computazionalmente menno efficienti da utilizzare di quelli a chiave simmetrica per la cifratura di grandi quantità di informazioni. Nel caso dell’algoritmo RSA, questa affermazione è ancora più fondata a causa della consistente lunghezza dei numeri che questo utilizza (solitamente interi >=1024 bit in lunghezza), il che rende molto inefficienti le operazioni di cifratura e decrifratura dei dati.
Di conseguenza, l’algoritmo RSA viene nella pratica utilizzato come algoritmo di firma digitale e di generazione di certificati digitali.
In questo caso, l’utilizzo delle chiavi segreta e pubblica di RSA viene in un certo modo invertito. Per firmare infatti un messaggio ne viene prima di tutto calcolato un valore di digest tramite una funzione di hash (come per esempio SHA). Il mittente può poi usare la sua chiave privata per firmare questo digest nel seguente modo:
Dove h è il digest calcolato a partire dal messaggio originario, d è l’esponente della chiave privata del mittente e s è la firma digitale risultante.
Da questo momento, chiunque riceve un messaggio da questo mittente può verificarne l’integrità e l’autenticità tramite l’utilizzo dell’esponente e della chiave pubblica del mittente:
Il destinatario potrà quindi verificare che il valore h che riceve da questo calcolo corrisponde al valore h’ dell’hash che può calcolare dal messaggio che riceve. Se questa comparazione va a buon fine, il destinatario può avere la certezza che il messaggio sia stato effettivamente firmato dal mittente atteso, in quanto questo è l’unico in possesso della chiave di firma.
Questo stesso meccanismo viene utilizzato per la generazione dei certificati di identità digitale che attestano l’autenticità di un ente nelle comunicazioni in rete. Questi certificati contengono la chiave pubblica dell’entità di cui si vuole attestare l’identità e vengono firmati dalla CA (Certificate Authority) che li rilascia. Tramite la chiave pubblica della CA si potrà quindi verificare l’autenticità e l’integrità del certificato stesso.
L’RSA è ancora sicuro? Le minacce emergenti
Alcune accortezze sono necessarie affinché l’utilizzo di RSA per crittografia o firma digitale sia considerabile sicuro. Primo fra tutti, la lunghezza del modulo utilizzato (e, di conseguenza, delle chiavi) deve essere adeguata affinché un attacco a forza bruta risulti infattibile anche con le capacità computazionali a disposizione ai giorni odierni.
Attacchi all’RSA e contromisure
Nel 1993 è stato dimostrato come analizzando i tempi di esecuzione del processo di decifratura di RSA per un numero sufficiente di crittotesti conosiuti si potesse risalire al valore dell’esponente segreto d.
Timing attacks
Tale osservazione ha ottenuto ancora più rilevanza quando nel 2003 è stato dimostrato come questa vulnerabilità potesse essere sfruttata anche non avendo accesso fisico all’hardware che sta effettuando l’operazione di decifratura.
Una contromisura per evitare questo attacco è cercare di rendere i tempi di esecuzione dell’algoritmo di decifratura sempre costanti. Cosa che però non è facilmente realizzabile ed efficiente nella pratica.
Quello che si fa è quindi utilizzare una tecnica chiamata RSA blinding. Praticamente, al momento di effettuare la decifratura di un crittotesto c, viene generato un numero randomico addizionale r chiamato blinding factor. Il calcolo che viene quindi effettuato, al posto della classica decifratura di c, è il seguente:
Chi decifra è poi in grado di ottenere il valore valore originario di m semplicemente moltiplicando per l’inverso di r in modulo n.
Questo addizionale fattore di randomicità nel processo rende infattibile qualsiasi tipo di attacco basato sui tempi di esecuzione dell’algoritmo di decifratura in quanto rimuove la relazione diretta tra il crittotesto c ed il tempo di esecuzione dell’algoritmo.
La maggior parte delle librerie utilizzate al giorno d’oggi che implementano l’algoritmo RSA per qualsiasi utilizzo fanno utilizzo di questo tipo di contromisura.
Adaptive Chosen-ciphertext Attacks
La versione classica di RSA che non fa utilizzo di nessun padding è di base vulnerabile ad attacchi di tipo chosed plaintext. La causa di questa vulnerabilità sta nel fatto che l’algoritmo (al di fuori della generazione delle chiavi) non ha una componente randomica nel calcolare il crittotesto di un messaggio. Per tale motivo, un attaccante può correlare dei messaggi conosciuti ai relativi crittotesti ed utilizzare questa informazione per lanciare una serie di possibili attacchi.
Per evitare questo tipo di vulnerabilità, i messaggi non vengono mai cifrati direttamente ma prima ad essi viene aggiunto un padding che spesso è di natura randomica e non ha una struttura predefinita. Lo standard PKCS#1 è stato il primo a descrivere una tecnica di padding da utilizzare per l’algoritmo RSA che è stata considerata sicura fino al 1998.
In quest anno, Daniel Bleichenbacher ha dimostrato come lo schema di padding descrittto nel PKCS#1 v1 fosse vulnerabile. Sfruttando la struttura di questo schema era infatti possibile risalire alle session key scambiate nel protocollo SSL.
Questo portò negli anni a seguire all’adozione di nuovi schemi di padding più sicuri come il PKCS#1 v1.5 e il PSS.
L’avvento della crittografia post-quantum
Anche ammettendo che un implementazione di RSA sia fatta “a regola d’arte”, tenendo in conto tutti i possibili attacchi conosciuti all’algoritmo ed adottando tutte le possibili contromisure e best practices, la sicurezza dell’algoritmo sarà sempre e comunque dipendente dalle capacità computazionali a disposizione degli attaccanti.
Tuttavia, il problema della fattorizzazione del modulo RSA rimane comunque uno degli argomenti più discussi e dei problemi più difficili da risolvere in termini computazionali. Nel 1991 fu creata una challenge su scala mondiale dove venivano rilasciati dei premi ai contendenti che fossero in grado di fattorizzare dei moduli RSA di lunghezza sempre crescente. Al giorno d’oggi, il più alto numero di bit che è stato fattorizzato è di 829 bits. Questo renderebbe l’utilizzo dei moduli di RSA >=1024 bit ancora sicuro a livello computazionale. Nella pratica, si consiglia sempre di usare un modulo di lunghezza 2048 bit o superiore.
La prospettiva potrebbe però drasticamente cambiare con l’avvento possibile dei quantum computer sul mercato.
È stato infatti dimostrato, per via teoretica tramite la pubblicazione dell’algoritmo di Shor, che se qualcuno fosse in grado di costruire un computer quantistico, quest’ultimo sarebbe in grado di fattorizzare qualsiasi modulo di RSA in un tempo polinomiale.
L’avvento di una tale tecnologia metterebbe completamente a repentaglio la sicurezza di RSA così come della maggior parte degli algoritmi crittografici in quanto le teorie computazionali di compessità sulle quali questi si basano verrebbero totalmente meno.
Alternative all’RSA: una panoramica
L’avvento del quantum computing e la poca efficienza (al giorno d’oggi) dell’esecuzione di RSA sono due dei motivi cardine per i quali il mondo della crittografia fornisce delle alternative a questo algoritmo.
Il problema del logaritmo discreto
Un altro problema matematico di nota difficile risoluzione è quello del logaritmo discreto. Tale problema si base sull’esponenziazione modulare di numeri interi. In particolare, dati due numeri interi non nulli a e b ed un numero primo p tali che:
Trovare, dati a, b e p, il numero x che soddisfi questa relazione risulta essere un problema di difficile risoluzione. Mentre il problema inverso, ovvero l’esponenziazione modulare di un numero, può essere risolto in maniera efficiente.
Data questa asimmetria (analoga a quella vista per il problema della fattorizzazione di numeri primi in RSA), sono stati ideati diversi algoritmi crittografici basati su quest tipo concetto. Tra i più noti abbiamo sicuramente Diffie-Hellman e il Digital Signature Algorithm (anche conosciuti come DH e DSA). Il primo viene impiegato nella derivazione di uno shared secret tra due comunicanti, mentre il secondo è un vero e proprio algoritmo di firma digitale.
Data però la somiglianza computazionale del problema del logaritmo discreto nel campo dei numeri interi e quello della fattorizzazione di numeri primi, l’efficienza e la sicurezza di questi algoritmi è paragonabile a quella di RSA. Infatti, questi utilizzano numeri la cui lunghezza in bit si aggira di solito intorno ai 1024 bit al minimo.
Algoritmi a curva ellittica
Gli algoritmi crittografici che si basano sul problema del logaritmo discreto ma che risultano molto più efficiente di quelli mostrati fin’ora sono quelli basati sulle curve ellittiche. Esse non sono altro che gruppi matematici definiti dalla relazione:
All’interno di questi gruppi, la complessità di risoluzione del problema del logaritmo discreto risulta essere molto maggiore di quelle affrontata per RSA o simili. Ciò permette agli algoritmi basati su curve ellittiche di fare uso di numeri primi molto più piccoli (intorno ai 200-500 bit) a parità di sicurezza garantita.
Alcuni esempi di algoritmi a curva ellittica che vengono utilizzati al giorno d’oggi sono ECDH e ECDSA. Il primo, anche detto Elliptic Curve Diffie-Hellman, è un sostituto dell’algoritmo DH, utilizzato per la derivazione di uno shared secret tra due parti che intendono comunicare.
Il secondo invece, anche detto Elliptic Curve Digital Signature Algorithm, è un vero e proprio sostituto dell’algoritmo ECDSA utilizzato per la generazione e la verifica di firme digitali.
I vantaggi
Il principale motivo per cui ECDSA viene spesso utilizzato al posto dell’algoritmo RSA è principalmente quello del guadagno computazionale. Abbiamo detto che, data la maggiore complessità computazionale introdotta dalle curve ellittiche, ECDSA permette a chi ne fa uso di utilizzare chiavi molto più brevi di quelle di RSA ottenendo lo stesso risultato in termini di sicurezza. Ma di quanta differenza stiamo parlando nello specifico?
Se analizziamo i relativi standard riusciamo bene a comprendere l’impatto di questa differenza. In particolare, se guardiamo allo standard NIST SP 800-57, vedremo come questo mette a confronto le security strength garantite da diversi tipi di algoritmi crittografici all’interno dei loro rispettivi utilizzi. Per security strength si intende il numero di operazioni necessarie ad un attaccante per “bypassare” uno specifico algoritmi crittografico (e.g., se si tratta di cifratura, allora si parla di decifrare il messaggio oppure ottenere la chiave segreta). Facendo un esempio, una security strength di 80 bits, si traduce in un numero di operazioni pari a 280 per rompere l’algoritmo.
In questo standard sono messi a confronto anche ECDSA e RSA nell’utilizzo come algoritmi di firma digitale. Se prendiamo la security strength minima (112 bits) che viene considerata accettabile, data la capacità computazionale a disposizione di un potenziale attaccante, vediamo come per ottenere tale risultato con RSA abbiamo bisogno di utilizzare moduli che vanno al di sopra dei 2048 bit. Per ottenere lo stesso risultato utilizzando ECDSA, possiamo limitarci all’utilizzo di chiavi nell’ordine di 224 bit.
Si nota quindi subito, come il rapporto efficienza/sicurezza sia totalmente diverso per i due algoritmi. Questo è ancora più evidente quando i requisiti di sicurezza diventano ancora più stringenti. Infatti, se vogliamo puntare ad una sicurezza di 256 bit, con RSA dobbiamo utilizzare moduli di almeno 15360 bits, mentre con ECDSA possiamo limitarci a l’utilizzo di numeri e chiavi nell’ordine di 512 bits.
Il futuro della crittografia: verso una nuova era
Nonostante il vantaggio a livello di efficienza introdotto dagli algoritmi basati sulle curve ellittiche, essi stessi rimangono comunque vulnerabili all’avvento dei computer quantistici.
Lo stesso algoritmo di Shor, menzionato nel caso di RSA, può essere infatti utilizzato per risolvere il problema del logaritmo discreto, anche nel campo delle curve ellittiche, in maniera efficiente (ovvero, con un tempo di esecuzione polinomiale e non esponenziale).
È per questo motivo che nuovi algoritmi alternativi stanno emergendo negli ultimi anni. Lo scopo adesso è quello ideare un algoritmo che sia in grado di sopperire all’ingente aumento di capacità computazionale che verrà introdotto dal possibile utilizzo di computer quantistici.
Crittografia basata su reticoli
Se vogliamo fare alcuni esempi di algoritmi che potranno essere in grado si svolgere questi compiti, il NIST ha recentemente rilasciato tre nuovi standard per la definizione di algoritmi post-quantum:
- FIPS 203: questo standard descrive un algoritmo di key encapsulation chiamato ML-KEM, li cui scopo è quello di stabilire uno shared secret tra due comunicanti tramite un canale pubblico.
- FIPS 204: questo standard descrive un algoritmo di digital signature chiamato ML-DSA, il cui scopo è quello di creare e verificare firme digitali.
- FIPS 205: questo standard descrive un altro algoritmo di digital signature chiamato SLH-DSA, il cui scopo è quello di creare e verificare firme digitali.
I primi due algoritmi sono basati sulle costruzioni matematiche chiamate reticoli, mentre il terzo si base sulla difficoltà di calcolare la pre-image delle hash function.
Tutti questi algoritmi sono considerati sicuri anche quando un avversario avrà a disposizione un computer quantistico.
Con la pubblicazione di questi standard, il NIST sta cercando di modellare il futuro della crittografia. Nessuno sa quando la costruzione di un computer quantistico sarà possibile e distribuita su larga scala, ma certamente avere già della alternative per quando questo avverrà non può che aiutare.
