Come un computer quantistico potrebbe violare la crittografia RSA a 2048 bit in 8 ore

Un primo piano del chip D-Wave Vesuvius Steve Jurvetson | Flickr

Molte persone temono che i computer quantistici saranno in grado di decifrare determinati codici utilizzati per inviare messaggi sicuri. I codici in questione crittografano i dati utilizzando funzioni matematiche botola che funzionano facilmente in una direzione ma non nell'altra. Ciò semplifica la crittografia dei dati ma la decodifica estremamente difficile senza l'aiuto di una chiave speciale.

Questi sistemi di crittografia non sono mai stati infrangibili. Invece, la loro sicurezza si basa sull'enorme quantità di tempo che un computer classico impiegherebbe a fare il lavoro. I moderni metodi di crittografia sono progettati specificamente in modo che la loro decodifica richieda così tanto tempo da essere praticamente indistruttibili.

Ma i computer quantistici cambiano questo modo di pensare. Queste macchine sono molto più potenti dei computer classici e dovrebbero essere in grado di decifrare questi codici con facilità.

Ciò solleva una domanda importante: quando i computer quantistici saranno abbastanza potenti per farlo? Dopo tale data, qualsiasi informazione protetta da questa forma di crittografia diventa insicura.

Quindi gli informatici hanno tentato di calcolare le risorse di cui un computer quantistico potrebbe aver bisogno e poi di calcolare quanto tempo ci vorrà prima che una macchina del genere possa essere costruita. E la risposta è sempre stata decenni.

Oggi, questo pensiero deve essere rivisto grazie al lavoro di Craig Gidney presso Google a Santa Barbara e Martin Ekerå presso il KTH Royal Institute of Technology di Stoccolma, in Svezia. Questi ragazzi hanno trovato un modo più efficiente per i computer quantistici di eseguire i calcoli di decifrazione del codice, riducendo le risorse di cui hanno bisogno per ordini di grandezza.

Di conseguenza, queste macchine sono significativamente più vicine alla realtà di quanto si sospettasse. Il risultato renderà una lettura scomoda per governi, organizzazioni militari e di sicurezza, banche e chiunque altro abbia bisogno di proteggere i dati per 25 anni o più.

Prima un po' di background. Nel 1994, il matematico americano Peter Shor scoprì un algoritmo quantistico che superava il suo equivalente classico. L'algoritmo di Shor tiene conto di grandi numeri ed è l'elemento cruciale nel processo per decifrare codici basati su botola.

Le funzioni della botola si basano sul processo di moltiplicazione, che è facile da eseguire in una direzione ma molto più difficile da eseguire al contrario. Ad esempio, è banale moltiplicare due numeri insieme: 593 per 829 fa 491.597. Ma è difficile iniziare con il numero 491.597 e capire quali due numeri primi devono essere moltiplicati per produrlo.

E diventa sempre più difficile man mano che i numeri aumentano. In effetti, gli informatici considerano praticamente impossibile per un computer classico fattorizzare numeri più lunghi di 2048 bit, che è la base della forma più comunemente utilizzata di crittografia RSA.

Shor ha mostrato che un computer quantistico sufficientemente potente potrebbe farlo con facilità, un risultato che ha inviato onde d'urto attraverso il settore della sicurezza.

E da allora, i computer quantistici sono aumentati di potenza. Nel 2012, i fisici hanno utilizzato un computer quantistico a quattro qubit per fattore 143. Poi nel 2014 hanno utilizzato un dispositivo simile per fattore 56.153.

È facile immaginare che a questo ritmo di progresso, i computer quantistici dovrebbero presto essere in grado di superare i migliori classici.

Non così. Si scopre che il factoring quantistico è molto più difficile in pratica di quanto ci si potrebbe aspettare. Il motivo è che il rumore diventa un problema significativo per i grandi computer quantistici. E il modo migliore attualmente per affrontare il rumore è utilizzare codici di correzione degli errori che richiedono essi stessi significativi qubit aggiuntivi.

Tenere conto di ciò aumenta notevolmente le risorse necessarie per fattorizzare i numeri a 2048 bit. Nel 2015, i ricercatori hanno stimato che un computer quantistico avrebbe bisogno di un miliardo di qubit per svolgere il lavoro in modo affidabile. È significativamente più dei 70 qubit dei computer quantistici all'avanguardia di oggi.

Su questa base, gli esperti di sicurezza avrebbero potuto giustificare l'idea che sarebbero passati decenni prima che i messaggi con crittografia RSA a 2048 bit potessero essere violati da un computer quantistico.

Ora Gidney ed Ekerå hanno mostrato come un computer quantistico potrebbe eseguire il calcolo con soli 20 milioni di qubit. In effetti, mostrano che un dispositivo del genere impiegherebbe solo otto ore per completare il calcolo. [Di conseguenza], la stima del caso peggiore di quanti qubit saranno necessari per fattorizzare interi RSA a 2048 bit è scesa di quasi due ordini di grandezza, dicono.

Il loro metodo si concentra su un modo più efficiente per eseguire un processo matematico chiamato esponenziazione modulare. Questo è il processo per trovare il resto quando un numero viene elevato a una certa potenza e quindi diviso per un altro numero.

Questo processo è l'operazione più dispendiosa dal punto di vista computazionale nell'algoritmo di Shor. Ma Gidney ed Ekerå hanno trovato vari modi per ottimizzarlo, riducendo notevolmente le risorse necessarie per eseguire l'algoritmo.

È un lavoro interessante che dovrebbe avere importanti implicazioni per chiunque memorizzi informazioni per il futuro. Un computer quantistico da 20 milioni di qubit sembra certamente un sogno lontano oggi. Ma la domanda che questi esperti dovrebbero porsi è se un tale dispositivo potrebbe essere possibile entro i 25 anni in cui vogliono proteggere le informazioni. Se pensano che lo sia, allora hanno bisogno di una nuova forma di crittografia.

In effetti, gli esperti di sicurezza hanno sviluppato codici post-quantistici che nemmeno un computer quantistico sarà in grado di decifrare. Quindi è già possibile salvaguardare i dati oggi contro futuri attacchi da parte dei computer quantistici. Ma questi codici non sono ancora usati come standard.

Per la gente comune, c'è poco rischio. La maggior parte delle persone utilizza la crittografia a 2048 bit, o qualcosa di simile, per attività come l'invio dei dettagli della carta di credito su Internet. Se queste transazioni vengono registrate oggi e interrotte tra 25 anni, si perderà poco.

Ma per i governi c'è di più in gioco. I messaggi che inviano oggi, ad esempio tra ambasciate o militari, potrebbero essere significativi tra 20 anni e quindi vale la pena tenerli segreti. Se tali messaggi vengono ancora inviati tramite la crittografia RSA a 2048 bit o qualcosa di simile, queste organizzazioni dovrebbero iniziare a preoccuparsi rapidamente.

Rif: arxiv.org/abs/1905.09749 : Come scomporre numeri interi RSA a 2048 bit in 8 ore utilizzando 20 milioni di qubit rumorosi

nascondere