Quanto è davvero sicuro un algoritmo crittografico. Il caso di RSA

La crittografia RSA (prende il nome dai suoi inventori Rivest-Shamir-Adleman che presentarono l’algoritmo nel 1977) è un sistema che risolve quello che una volta era uno dei più grandi problemi della crittografia. Come si può inviare a qualcuno un messaggio codificato senza avere la possibilità di condividere precedentemente con lui la corrispondente chiave di decodifica?
L’idea è stata brevettata nel 1983 dal MIT ma soltanto dopo l’algoritmo RSA ha iniziato a diffondersi ed essere universalmente apprezzato come un importante strumento di sicurezza.

La risposta arriva dagli algoritmi crittografici a chiave pubblica (crittografia asimmetrica) come abbiamo visto nell’articolo incentrato sulle principali differenze tra cifratura simmetrica e asimmetrica.

Abbiamo visto che RSA non è l’unico algoritmo a cifratura asimmetrica che viene oggi utilizzato ma resta uno dei più diffusi in assoluto e a distanza di 45 anni dalla sua invenzione resta attualissimo.

La crittografia RSA è spesso usata in combinazione con altri schemi di codifica o per l’apposizione di firme digitali utili per provare l’autenticità e l’integrità di un messaggio. Generalmente l’algoritmo RSA non viene usato per crittografare interi messaggi o file, perché è meno efficiente e più pesante in termini di risorse della crittografia a chiave simmetrica.
Di solito ciò che si fa è crittografare un file con un algoritmo a chiave simmetrica con la chiave di codifica e decodifica successivamente protetta con la crittografia RSA: solo un’entità che ha accesso alla chiave privata RSA sarà in grado di decifrare la chiave simmetrica.

La crittografia RSA è utilizzata per proteggere i certificati digitali che attestano l’identità di un sito web e permettono uno scambio di dati sicuro attraverso il protocollo HTTPS (l’alternativa sempre più diffusa è ECC, Elliptical Curve Cryptography) ed è utilizzata in molteplici sistemi a tutti i livelli: la utilizzano ad esempio OpenSSL e altre librerie crittografiche di vasto impiego come cryptlib e wolfCrypt.
RSA è stata usata in TLS ed è stato anche l’algoritmo originale usato nella crittografia PGP. Si usa ancora oggi per proteggere le comunicazioni con i browser web, i client email, VPN, sistemi di messaggistica e così via.

Sapere cosa c’è dietro RSA aiuta a capire come molte parti della nostra vita online sono tenute al sicuro.

Nella crittografia RSA i messaggi sono protetti con un codice chiamato chiave pubblica che può essere condiviso liberamente.
In forza delle proprietà matematiche dell’algoritmo RSA che legano messaggio, chiave pubblica e chiave privata (“il segreto” che deve essere gelosamente conservato da ciascun utente coinvolto nella comunicazione), una volta che un messaggio è stato crittografato con la chiave pubblica esso potrà essere decifrato solo usando un’altra chiave, conosciuta appunto come chiave privata. Ogni utente ha una coppia di chiavi pubblica e privata: quella privata deve essere sempre tenuta segreta.

Come abbiamo visto, gli schemi di crittografia a chiave pubblica differiscono dalla crittografia a chiave simmetrica in cui sia il processo di codifica che quello di decodifica usano la stessa chiave privata.

Come funziona RSA in breve

Illustrare il funzionamento di un algoritmo crittografico non è semplicissimo perché sono molteplici i passaggi sui quali sarebbe importante soffermarsi. Le relazioni matematiche che regolano il funzionamento dell’algoritmo devono essere comprese per avere un quadro preciso delle dinamiche che rendono sicuro un algoritmo come RSA.

La crittografia RSA funziona basandosi su un aspetto fondamentale: l’algoritmo è facile da gestire in una direzione mentre è quasi impossibile nel senso inverso.
La sicurezza di RSA deriva dal fatto che mentre la moltiplicazione è un’operazione molto semplice da effettuare, la fattorizzazione di numeri molto grandi è un’operazione computazionalmente impegnativa.

Dato un numero naturale N molto grande non esiste un metodo veloce per risalire ai due numeri primi P e Q che moltiplicati diano per risultato proprio N.
Prendiamo come esempio un semplice numero a quattro cifre, 2993, risultato della moltiplicazione dei numeri primi (sono divisibili soltanto per 1 e per se stessi) 41 e 73.

Conoscendo solo il numero 2993 risalire ai numeri primi che moltiplicati danno quel numero non è banale. Si possono usare i metodi di Eulero, Fermat, Dixon e Shor oppure usare la “forza bruta” (brute force) quindi dividere iterativamente 2993 per tutti i numeri primi P conosciuti, uno dopo l’altro. Se si otterrà un intero il risultato sarà l’altro numero primo Q che si stava cercando.
Il metodo brute force è efficace ma è ovviamente lentissimo mettendo in crisi qualunque sistema informatico nel tentativo di fattorizzare numeri composti da tante cifre.

Il problema della difficoltà nel fattorizzare un numero composto da poche cifre lascia intendere quanto possa essere complessa la procedura nel caso di numeri composti da 270 cifre o più.

Fino al 2007 RSA Laboratories ha avviato una sorta di concorso su scala planetaria sfidando matematici, informatici e ricercatori a fattorizzare 54 semiprimi con numero di cifre decimali compreso tra 100 e 617.
I numeri da RSA-100 a RSA-250 sono stati tutti fattorizzati da vari studiosi mentre già RSA-260 (composto da 260 cifre decimali) ad oggi non lo è stato.

In precedenza abbiamo detto che le funzioni utilizzate nell’algoritmo RSA sono quasi impossibili da invertire proprio per l’oggettiva complessità dell’operazione di fattorizzazione. Ecco il perché del “quasi”.

La dimensione dei numeri primi usati in una reale implementazione di RSA varia ma in RSA-2048 (2048 bit) ampiamente utilizzato al giorno d’oggi si usano chiavi lunghe 617 cifre.

Quindi è certamente vero che le chiavi pubbliche e private sono strettamente legate e che in linea teorica la chiave pubblica potrebbe essere utilizzata per risalire al messaggio in chiaro ma la complessità dell’operazione di fattorizzazione, anche se effettuata con una batteria di computer ad alte prestazioni o combinando una serie di GPU che lavorano in parallelo, rende l’impresa impraticabile quindi virtualmente impossibile.
Con un algoritmo crittografico “forte” di tipo asimmetrico le chiavi pubbliche possono perciò essere condivise senza mettere in pericolo il messaggio o rivelare la chiave privata.

I numeri primi usati in RSA devono comunque essere molto grandi e anche relativamente distanti. I numeri che sono piccoli o più vicini tra loro sono molto più facili da decifrare quindi vengono automaticamente scartati.

Le relazioni matematiche alla base del funzionamento del cifrario RSA sono splendidamente illustrate in questo articolo di approfondimento.

Da cosa dipende la sicurezza della crittografia RSA

La sicurezza di RSA dipende in larga misura da come l’algoritmo viene implementato e utilizzato. Esattamente come accade nel caso degli altri algoritmi crittografici.

Un fattore importante è la dimensione della chiave: più grande è il numero di bit che formano una chiave più difficile essa sarà da trovare usando attacchi basati su bruce forcing e fattorizzazione.

Poiché gli algoritmi a chiave asimmetrica come RSA possono essere violati usando la fattorizzazione dei numeri interi mentre gli algoritmi a chiave simmetrica come AES non sono soggetti a questo tipo di problematica, le chiavi RSA devono essere molto più lunghe per raggiungere lo stesso livello di sicurezza offerto dagli algoritmi a chiave simmetrica.

Il National Institute of Standards and Technology (NIST) raccomanda una dimensione minima della chiave di 2048 bit ma è utile usare chiavi a 4096 bit in quelle situazioni in cui i dati devono essere protetti da aggressori che possono potenzialmente disporre di risorse computazionali di primissimo livello.

L’utilizzo della fattorizzazione è soltanto uno dei modi con cui i dati protetti con RSA possono essere eventualmente violati. Altre tipologie di attacco hanno infatti il potenziale per per rompere la crittografia con una minore quantità di risorse impegnate ma il loro successo dipende dall’implementazione e da altri fattori, non necessariamente da RSA stesso. Citiamone alcuni:

– Generazione pseudo casuale dei numeri. Alcune implementazioni di RSA usano generatori di numeri primi pseudocasuali che risultano “deboli”. Se i numeri primi non sono sufficientemente casuali è molto più facile per gli attaccanti fattorizzarli e rompere la crittografia. Il generatore di numeri pseudocasuali deve essere quindi crittograficamente sicuro.

– Generazione imperfetta delle chiavi. Le chiavi RSA devono rientrare in certi parametri per essere considerabili come sicure. Se i primi P e Q sono troppo vicini tra loro la chiave può essere facilmente scoperta.
Allo stesso modo il numero D che costituisce parte della chiave privata non può essere troppo piccolo. Un valore basso lo rende facilmente individuabile.
Di un caso simile avevamo parlato a suo tempo indicando come addirittura una chiave RSA-1024 potesse essere trovata con una configurazione AWS (Amazon Web Services) in appena 45 minuti di tempo e con 75 dollari di investimento a causa della generazione superficiale dei numeri primi.

– Attacchi side channel. Gli attacchi side channel non rompono direttamente la cifratura RSA ma invece usano informazioni relative all’implementazione per dare agli attaccanti suggerimenti sul processo seguito.
Interagendo con i meccanismi di branch prediction a livello di CPU o misurando il tempo di esecuzione delle istruzioni in alcuni casi è possibile risalire alla chiave privata.
Utilizzando un timing attack un aggressore può misurare il tempo di decodifica per un certo numero di messaggi crittografati e anche in questo caso esporre la chiave privata (l’attacco si può contrastare usando alcune accortezze ad esempio la tecnica RSA blinding).

La buona notizia è che RSA può essere considerato sicuro nonostante tutti i possibili attacchi dei quali abbiamo parlato. Soprattutto se ci si orienta almeno sull’utilizzo dell’algoritmo RSA-2048 consigliato da tutte le realtà industriali.
L’importante è che l’algoritmo RSA sia implementato correttamente con una chiave che soddisfa i requisiti.

Ciò che ci si aspetta è che i computer quantistici possano in futuro porre sfide importanti contribuendo a rendere obsoleti algoritmi che oggi rappresentano standard universalmente approvati.

I computer quantistici potrebbero essere in grado di risolvere facilmente alcuni problemi che attualmente sono considerati ingestibili con i sistemi tradizionali.
Nel caso di algoritmi a chiave simmetrica come AES potenti computer quantistici che sfruttano l’algoritmo di ricerca di Grover sarebbero in grado di accelerare notevolmente gli attacchi. Tutto quello che dovremo fare per difenderci, però, consisterà nel raddoppiare la dimensione della chiave.

Quando si tratta di crittografia a chiave pubblica come RSA il problema diventa indubbiamente più imponente: una volta che i computer quantistici diventeranno abbastanza potenti da poter eseguire l’algoritmo di fattorizzazione di Shor in modo efficace sarà possibile risolvere i seguenti tre problemi matematici:

• Fattorizzazione dei numeri interi
• Logaritmo discreto
• Logaritmo discreto a curva ellittica

L’ultimo è utilizzato nella crittografia ECC, alternativa a RSA che usa chiavi di dimensioni più piccole e curve matematiche ellittiche per eseguire l’operazione di cifratura dei dati.
ECC è spesso usata per firmare digitalmente le transazioni effettuate con le criptovalute (Bitcoin usa ECC o meglio ECDSA per firmare digitalmente le transazioni e garantire che i fondi siano spesi solo da utenti autorizzati) ed è frequentemente adoperata anche per i certificati digitali: Google ad esempio utilizza proprio una chiave pubblica ECC.
Si tratta di un algoritmo che viene considerato come il nuovo punto di riferimento per il Web oltre che per un’infinità di altre applicazioni (è tra l’altro molto più veloce di RSA nella generazione di chiavi e firme).

Allo stato attuale è difficile sapere quando un computer quantistico sarà effettivamente in grado di rompere RSA anche se ricerche e sviluppi significativi sono già in corso.
Le minacce alla crittografia figlie del calcolo quantistico sono però ancora lontane: oggi possiamo contare al massimo su enormi computer quantistici basati al massimo su 70 qubit quando come recentemente dimostrato nello studio di Craig Gidney e Martin Ekerå ci vorrebbero 20 milioni di qubit per completare con successo la fattorizzazione di una chiave RSA-2048 in sole 8 ore.