La pubblicazione di un documento in cui un gruppo di ricercatori cinesi afferma di poter violare l’algoritmo crittografico RSA a 2048 bit (sebbene non lo abbia ancora fatto) non ha colto di sorpresa gli addetti ai lavori.
Non è una novità, infatti, che il quantum computing possa diventare un problema di sicurezza: già da tempo gli esperti si interrogano sulle sfide che ci attendono nei prossimi anni per far sì che lo sviluppo di questa tecnologia non avvantaggi in qualche modo il cyber crimine nel mettere fuori gioco gli attuali algoritmi crittografici usati per garantire la sicurezza delle informazioni.
In questo contesto, ad esempio, il NIST (il National Institute of Standards and Technology degli Stati Uniti) lo scorso 5 luglio 2022 ha comunicato di aver selezionato i primi quattro algoritmi crittografici in grado di resistere alla computazione quantistica.
Facciamo, dunque, chiarezza sull’argomento perché, come ha affermato il noto crittografo Bruce Schneier, l’annuncio dei ricercatori cinesi è da “prendere sul serio: potrebbe non essere corretto, ma non è ovviamente sbagliato”.
Il quantum computing diventerà un problema di sicurezza? Le sfide che ci attendono
Indice degli argomenti
Cos’è l’algoritmo crittografico RSA
L’algoritmo RSA deve il suo nome a tre matematici americani, R. Rivest, L. Adleman e A. Shamir, che per primi inventarono una funzione matematica per realizzare nella pratica un sistema di crittografia asimmetrica, ovvero basato sui concetti di chiave pubblica e privata.
Il lavoro dei tre matematici prese spunto dall’articolo originale sulla crittografia asimmetrica di Diffie e Hellman del 1976 che servì da un lato alla scoperta di questa nuova forma di crittografia e in secondo luogo alla nascita dell’algoritmo RSA per la distribuzione sicura delle chiavi, risolvendo un annoso problema della crittografia simmetrica che aveva grandi difficoltà proprio nel distribuire chiavi sicure ad un gran numero di utenti.
Ma l’articolo di Diffie e Hellman che poneva queste basi lasciò spazio per la successiva ricerca di un algoritmo vero e proprio di crittografia. Rivest, Adleman e Shamir riuscirono nel 1978 in questa impresa, cioè identificare quale funzione matematica occorresse per trovare questa soluzione.
Come funziona l’algoritmo crittografico RSA
L’algoritmo RSA viene descritto in uno dei documenti della famiglia PKCS e funziona secondo lo schema logico riportato nella figura sottostante.
Due utenti (A e B) vogliono scambiarsi in modo sicuro un messaggio attraverso un canale non sicuro, non avendo la possibilità di incontrarsi di persona o in altro modo per scambiarsi (sempre in modo sicuro) una chiave di crittografia simmetrica.
I due utenti, allora, creano una coppia di chiavi (pubblica e privata). L’utente B utilizza la chiave pubblica di A per crittografare il messaggio e lo invia ad A. L’utente A utilizzerà la propria chiave privata che solo lui conosce e possiede per de-crittografare il messaggio di B. Anche se un utente terzo, malevolo, viene in possesso del messaggio inviato da B , non potrà decifrarlo perché non possiede la corrispondente chiave privata di A.
L’algoritmo, in termini matematici, è più complesso e si affida a una sequenza di operazioni basate sull’impiego di numeri primi:
- Si scelgono due numeri primi p e q diversi tra di loro.
- Si calcola il modulo N=p*q e il numero di Eulero phi(N)=(p-1)*(q-1).
- Si sceglie il numero “e” co-primo a phi(N), nel range da 1 a phi(N) in modo che GCD(e, phi(N))=1, essendo GCD=massimo comune divisore.
- Si calcola la chiave privata come d=e^(-1)(mod phi(N)), i.e d*e=1 mod phi(N).
- La chiave pubblica sarà la coppia formata da (e,N).
- La chiave privata sarà la coppia formata da (d,N).
A questo punto, segue la sequenza di cifratura/decifratura:
- Dato un testo da cifrare, si trasforma il testo in una sequenza di numeri.
- Si procede a cifrare il testo originale usando la formula c[i]=(m[i]^e) mod(N).
- Per decifrare il messaggio si userà invece la formula inversa I[i]= c[i]^d mod (N).
Tipicamente N=1024 bits oppure 2048 oppure 3072 o ancora 4096.
Una nuova crittografia, contro i computer quantistici: ecco qualche possibile soluzione
Attacchi agli algoritmi crittografici
I principali metodi di attacco all’algoritmo RSA si basano sulla fattorizzazione dei numeri primi. Il segreto di RSA (chiave privata) risiede infatti nella moltiplicazione di due numeri primi molto grandi. L’operazione inversa sarebbe infatti computazionalmente impossibile (tempi oggi considerati proibitivi) con metodi di calcolo classici.
Ad esempio un numero RSA a 2048 bit consiste in 309 cifre decimali. Un numero primo così grande è appunto (quasi) impossibile da fattorizzare nei suoi due componenti.
Algoritmo RSA e quantum computing
In questo contesto entra dunque in gioco il documento dei ricercatori cinesi (“Factoring integers with sublinear resources on a superconducting quantum processor”) che, per l’appunto, avrebbero inventato un nuovo algoritmo per fattorizzare i numeri di RSA.
In realtà, alcuni lavori di ricerca erano stati già pubblicati per dimostrare che RSA non è più un algoritmo inviolabile. In particolare, nel paper “Fast Factoring Integers by SVP Algorithms”, Claus Peter Schnorr afferma che “it destroys the RSA Cryptosystem” e il lavoro di ricerca cinese si basa proprio su una modifica di questo algoritmo.
In precedenza, ancora un altro articolo degli Anni 90 di Schnorr descriveva un metodo per fattorizzare numeri primi, ma richiedeva l’uso di quantum computers molto grandi (milioni di qubits).
Consci di questa limitazione, i ricercatori cinesi affermano che hanno utilizzato un algoritmo quantico universale per fattorizzare alcuni interi fino a 2048 bit e stimano di poter sfidare RSA 2048 (che richiede “solo” 372 qubits e 205 qubits per RSA 1024) nel prossimo futuro.
Giustamente concludono che per ora possono solo pensare di sfidare RSA 581, mentre per avere una soluzione valida anche per RSA a chiavi più grandi la strada è ancora lunga. Anche per questo, l’esperto di cyber security Bruce Schneier afferma una certa cautela sulla notizia, ma si dice pronto a prendere con attenzione la cosa.
Sempre di recente, l’amministrazione USA ha trasformato in legge una direttiva sull’adozione del “Quantum Computing Cybersecurity Preparedness Act”, che impone l’obbligo di accelerare la migrazione alla crittografia post-quantum a partire dal momento in cui il NIST definirà gli algoritmi appropriati. Come cita la legge, “i computer quantistici potrebbero un giorno avere la capacità di spingere i limiti computazionali, permettendoci di risolvere problemi finora intrattabili, come la fattorizzazione di numeri interi, che è importante per la crittografia”.
Suona come un importante monito per il futuro. L’avvento dei computer quantistici rivoluzionerà lo scenario degli algoritmi di crittografia in tempi molto rapidi.
Quantum Key Distribution: cos’è e perché è utile a rendere inattaccabili i sistemi di cifratura
Conclusioni
Al di là del clamore suscitato su Internet dalla notizia sulla nuova ricerca, occorre ricordare che l’algoritmo crittografico RSA esiste con diverse lunghezze di chiave ed esistono raccomandazioni sulla lunghezza da utilizzare con un certo orizzonte temporale.
Ad oggi, ad esempio, il report CNSA (Commercial National Security Suite 2.0) della National Security Agency di settembre 2022 raccomanda RSA con minimo 3072 bit. Il NIST (National Institute for Standards and Technology) raccomanda RSA 2048 fino al 2030 e RSA 3072 per tempi ancora più lunghi.
Anche ENISA, Agenzia Europea per la Cybersicurezza in uno dei suoi ultimi report sull’argomento crittografico, raccomanda l’adozione di RSA 3072.
Introducendo il concetto di “Security Strength”, ad esempio, RSA 1024 ha una valore di 80 bit, RSA 2048 ha una valore di 112 bit mentre RSA 3072 ha un valore di 128, da cui nasce la raccomandazione vista prima. Questi valori sono destinati ad essere rivisti nei prossimi tempi, quando le ricerche con quantum computer produrranno effetti pratici concreti.
Intanto, si procede con la standardizzazione dei futuri algoritmi di crittografia che siano resistenti ai quantum computer. Per ora sono stati selezionati CRYSTALS-Kyber per la crittografia e CRYSTALS-Dilithium per la firma digitale. Entrambi richiamati nella lista CNSA.
Una volta approvati, i vari vendor di apparati/prodotti di sicurezza potranno adottare i nuovi algoritmi e relativi requisiti.
