Un gruppo di ricercatori cinesi ha appena pubblicato un documento in cui afferma di poter violare l’algoritmo di cifratura RSA a 2048 bit, ma al contempo ha dichiarato di non averlo fatto, perché non ha a disposizione l’hardware quantistico necessario. L’articolo in questione, il cui titolo è “Factoring integers with sublinear resources on a superconducting quantum processor”, è quindi solo un esercizio di stile, al momento molto criticato in rete per la mancanza di dettagli importanti. Un ottimo punto di vista, anche grazie ai commenti, è disponibile sul blog di Bruce Schneier, esperto internazionale di sicurezza.

In estrema sintesi, i ricercatori cinesi hanno combinato le classiche tecniche di fattorizzazione della riduzione del reticolo con un algoritmo di ottimizzazione approssimata quantistica (QAOA). La formula che collega la profondità P dell’algoritmo al numero Q di qbits necessari a decifrare il codice è Q =  2∗P/log2P. Per RSA 2048 P è ovviamente 2.048, il cui logaritmo in base 2 è 11. Q è quindi 4.096/11=372,36, quindi servono almeno 373 qubits.

“L’articolo è interessante. Non è detto che sia sbagliato e forse è anche corretto, sebbene alcuni colleghi siano chiaramente negativi”, ci ha detto Nicolas Gisin, Group of Applied Physics & Constructor dell’Università di Ginevra. “Il semplice fatto che questo articolo possa essere modificato ci ricorda che il factoring potrebbe essere molto più semplice del previsto, sia con piccoli processori quantistici, sia classicamente”.

Ed ecco che arriva un elemento importante: il marketing. Poiché IBM ha da tempo dichiarato di aver disponibile Ospray, un hardware quantistico da 433 qubit, il gioco sembra fatto: l’attuale hardware da 433 qubit può infrangere le sicurezze che tengono insieme la rete, il mondo finanziario e i segreti di aziende e governi con un software che opera su 373 qubit? Nel quantum computing, però, non sempre 1 vale 1.

L’algoritmo non scala, indipendentemente dai quanti

Secondo le informazioni raccolte da Schneier, la storia è molto diversa e si compone di vincoli successivi che non rendono credibile la conclusione suggerita (ma non scritta) dagli estensori del paper, e subito accettata come buona dalla maggior parte dei cosiddetti divulgatori.

Nessuno ha esplicitamente detto che RSA-2048 può essere decodificato con hardware esistente. Ma come si è giunti allora al clamoroso titolo?

“Qualcuno aveva precedentemente annunciato di essere in grado di violare la crittografia asimmetrica tradizionale con computer classici usando ”, cita Schneier da un’e-mail di Roger Grimes (altro esperto internazionale di sicurezza), “ma i revisori hanno trovato un errore e l’articolo è stato ritirato”.

A questo punto entra il team cinese, dichiarando (con il paper in questione) che l’errore in questione potrebbe essere risolto da piccoli computer quantistici. Le loro verifiche hanno funzionato, e da qui è venuto il paper.

Il problema però è che l’algoritmo risultante si basa comunque su un recente paper del matematico Claus-Peter Schnorr, ancora controverso nella comunità internazionale. Questo suo algoritmo funzionerebbe bene con moduli piccoli, all’incirca dello stesso ordine di quelli testati dal gruppo cinese, ma non funziona se le dimensioni dei moduli sono maggiori, come quelle richieste per decifrare RSA-2048. Quindi se l’algoritmo di Schnorr non scala, è molto probabile che nemmeno possa scalare la soluzione proposta dal team cinese, che infatti non fa nessuna dichiarazione apodittica. Ma poiché nel testo l’esempio fatto è proprio RSA-2048, ecco che la frase ingannatrice -suggerita ma mai scritta dai ricercatori- è diventata titolo per molti siti e giornali.

“L’algoritmo si basa su quello classico, in cui c’è solo una parte difficile”, riprende Gisin. “Si dimostra la fattorizzazione usando solo un processore da 10 qubit con connessioni adiacenti. Per me, la domanda principale che questo documento lascia aperta è: quanto rumore può essere tollerato, specialmente quando si passa a processori quantistici più grandi? Sono sicuro che presto ne sapremo di più”.

Quantum computing e crittografia: un tema da affrontare ora

Anche se Schneier e la comunità crittografica sono concordi sul fatto che il metodo proposto difficilmente reggerà alla prova dei fatti, il breakthrough quantistico in campo crittografico è qualcosa con cui bisogna cominciare a fare i conti ora. Anche se come è probabile il metodo proposto da questo paper non si dimostrerà praticabile, si tratta comunque di un avvicinamento a un momento che molto probabilmente prima o poi arriverà, e le piccole e grandi organizzazioni devono cominciare ora a prepararsi.

Il cambiamento di un sistema crittografico non è qualcosa che si possa fare dalla sera alla mattina, sia per quanto riguarda le comunicazioni, sia per i dati archiviati. E anche se questo fosse possibile, rimane un problema: molti dei dati trafugati nel corso di attacchi informatici sono in forma cifrata, e quindi inutilizzabile al momento (uno su tutti, si spera, l’archivio con le password degli utenti di LastPass).

Nel momento in cui sarà disponibile un metodo per infrangere la crittografia, questi dati diventeranno disponibili ai criminali che li hanno già sottratti. Alcuni buoi sono già scappati, insomma, ma bisogna quanto meno chiudere la stalla (applicare metodi di cifratura resistenti agli attacchi quantistici) ai dati che ancora non sono stati rubati.

Il National Institute of Standards and Technology (NIST), l’ente governativo americano che stabilisce standard e pratiche tra cui il celebre Cybersecurity Framework, ha già identificato quattro metodi crittografici Quantum-Resistant, ed è il caso di cominciare a farne la conoscenza.

(Articolo pubblicato il 10 gennaio 2023 e aggiornato il 2 febbraio per includere il parere di Nicolas Gisin)