Algoritmo crittografico RSA a rischio attacco: Bruce Schneier invita a non sottovalutare il problema

Gli algoritmi crittografici a chiave pubblica, altrimenti detti a crittografia asimmetrica, si basano su meccanismi che a loro volta poggiano su problemi matematici che attualmente non ammettono soluzioni efficienti. In altre parole, l’algoritmo è facile da gestire in una direzione mentre è quasi impossibile nel senso inverso.

Abbiamo parlato della sicurezza di RSA, algoritmo nato nel 1977 dal lavoro degli inventori Ronald Rivest, Adi Shamir e Leonard Adleman (le iniziali dei cognomi corrispondono alla sigla RSA).
RSA è utilizzatissimo, oggi, a tutti i livelli e, a patto che la chiave sia sufficientemente lunga e generata in modo corretto, le informazioni protette mediante RSA sono al sicuro.

Alcuni algoritmi a chiave pubblica usano la fattorizzazione di un numero intero, il logaritmo discreto o le relazioni delle curve ellittiche come operazioni difficilmente invertibili, se non a fronte di un costo computazionale troppo elevato e quindi non affrontabile.

Nello specifico RSA poggia il suo funzionamento proprio sulla fattorizzazione: dato un numero naturale N molto grande non esiste un metodo veloce per risalire ai due numeri primi P e Q che moltiplicati tra loro diano per risultato proprio N. Se quindi la moltiplicazione di due numeri è un’operazione molto semplice da effettuarsi, la fattorizzazione non lo è affatto ed è storicamente rimasto come uno dei problemi più complessi da gestire.

Si possono usare i metodi di Eulero, Fermat, Dixon e Shor oppure la “forza bruta” (brute force) per provare a fattorizzare un numero. Come abbiamo visto, nel caso di RSA, qualora fossero state usate chiavi molto deboli è possibile decodificare un messaggio cifrato: di recente un gruppo di ricercatori c’è riuscito usando addirittura il vecchio algoritmo di Pierre de Fermat per decifrare informazioni protette con RSA.

A cambiare le regole in ambito supercomputing ci penseranno i computer quantistici. I problemi risolvibili con un computer quantistico sono infatti buona parte di quelli che non sono gestibili con l’informatica tradizionale, proprio a causa del già citato costo computazionale.
La fattorizzazione di una chiave crittografica diventa quindi una cosa più che fattibile con il quantum computing: questo lo si sapeva, tanto che il NIST ha deciso di iniziare a studiare algoritmi crittografici progettati per resistere agli attacchi sferrati usando computer quantistici.
Il NIST (National Institute of Standards and Technology) statunitense ha infatti più volte ricordato che è bene agire per tempo per non trovarsi all’improvviso in una situazione emergenziale con gli algoritmi crittografici ritenuti sicuri che diventano di colpo inaffidabili.
C’è ancora tanto lavoro da fare perché è capitato che alcuni algoritmi resistenti agli attacchi con computer quantistici sono stati violati con normali attacchi “vecchia scuola” usando macchine convenzionali.

Uno studio di Craig Gidney e Martin Ekerå dimostrava comunque che ci vorrebbero computer quantistici da 20 milioni di qubit per completare con successo la fattorizzazione di una chiave RSA-2048 in appena 8 ore.
Sulla carta si tratta di uno sforzo immane se si pensa che il quantum computer IBM Osprey ha 433 qubit e solo nel 2025 l’azienda conta di arrivare a 4.000 qubit.
Sebbene l’intenzione di IBM sia quella di sviluppare computer quantistici che utilizzati in batteria possano aumentare significativamente il numero di qubit in gioco, il traguardo di 20 milioni di qubit appare lontanissimo.

Il noto crittografo statunitense Bruce Schneier sta richiamando l’attenzione su una ricerca appena pubblicata da un gruppo di ricercatori cinesi.
Il team di studiosi afferma di essere in grado di violare RSA-2048 anche se all’atto pratico questo non è stato ancora fatto. Secondo le conclusioni della ricerca, basterebbe soltanto un computer quantistico a 372 qubit per decifrare i messaggi protetti con l’algoritmo RSA-2048 ma il gruppo cinese afferma di non disporre di un computer quantistico così potente con cui lavorare.

Gli autori dell’indagine hanno dimostrato di riuscire a fattorizzare numeri a 48 bit utilizzando un computer quantistico a 10 qbit. Avere a disposizione un computer quantistico a 372 qubit non è impossibile visto che il migliore quantum computer di IBM può appunto contare su 433 qubit.

Ciò che i ricercatori hanno fatto è combinare le classiche tecniche di fattorizzazione volte alla riduzione del reticolo con un algoritmo di ottimizzazione approssimata di tipo quantistico: così si è potuto ridurre quei 20 milioni di qubit ad appena 372.

Secondo Schneier il lavoro del team cinese si basa sull’approccio al problema della fattorizzazione di Peter Schnorr: si tratta di un documento controverso perché descrive un algoritmo che funziona bene con moduli più piccoli, all’incirca dello stesso ordine di quelli testati dal gruppo cinese ma fallisce al crescere delle dimensioni delle chiavi. Nel documento cinese si afferma che le tecniche quantistiche adottate permettono di aggirare le limitazioni dell’algoritmo di Schnorr ma mancano diversi elementi del puzzle.

Schneier, pur invitando a non sottovalutare il problema, scrive che dopo un’analisi più approfondita del lavoro svolto dal team cinese, vi sono meno fonti di preoccupazione. Invita comunque i tecnici di IBM ad effettuare una serie di test servendosi dei computer quantistici sin qui realizzati.