Secondo il vescovo cattolico Charles-Maurice de Talleyrand, la più grande conquista dell’uomo è stata la parola, perché solo grazie a essa si possono mascherare i propri pensieri. In questo paradosso è riassunta l’essenza della crittografia: sin da quando l’uomo ha imparato a comunicare coi suoi simili in modo formale e standardizzato, ha avuto l’esigenza di indirizzare la sua comunicazione solo verso taluni individui e non verso altri, lasciando questi ultimi all’oscuro dei propri pensieri.
Crittografia, ecco i nuovi paradigmi per tutelare i nostri dati
E se ciò è stato relativamente facile in un mondo nel quale le sole comunicazioni erano quelle orali, nelle quali messaggio e messaggero si identificavano, è divenuto ben presto problematico quando si è dovuta considerare la forma scritta della comunicazione, dove il messaggio è una realtà oggettiva differente dal messaggero che lo reca.
Se il segreto è nato insieme alla parola, la crittografia è nata assieme alla scrittura e ne rappresenta il duale: si usa non per comunicare, ma per nascondere.
Internet e la comunicazione
I collegamenti telematici costituiranno nei prossimi anni uno dei principali strumenti di comunicazione tra cittadini, imprese e pubblica amministrazione. Personal computer sempre più potenti, tecnologie convergenti e un’ampia utilizzazione di internet hanno sostituito i precedenti “sistemi autonomi” dalle capacità limitate e operanti nell’ambito di reti prevalentemente isolate. Oggi, le parti interessate sono sempre più interconnesse e le connessioni superano i confini nazionali. Inoltre, internet è il supporto per infrastrutture vitali quali l’energia, i trasporti e le attività finanziarie e svolge un ruolo centrale nel modo in cui le imprese gestiscono le proprie attività, i governi assicurano i servizi ai cittadini e alle imprese e i cittadini comunicano e scambiano informazioni.
La natura e la tipologia delle tecnologie che costituiscono l’infrastruttura delle comunicazioni e dell’informazione hanno parimenti registrato una notevole evoluzione. Il numero e la natura dei dispositivi di accesso a tale infrastruttura si sono moltiplicati e differenziati per conglobare i terminali di accesso fissi, senza fili e mobili, e gli accessi tramite collegamenti permanenti sono in aumento. Ne consegue che la natura, il volume e il carattere sensibile dell’informazione scambiata sono aumentati in modo sostanziale. Con la loro accresciuta connettività, i sistemi e reti d’informazione sono ormai esposti a un aumento del numero di minacce e a una maggiore gamma di vulnerabilità: emergono quindi nuovi problemi di sicurezza.
Una nuova crittografia, contro i computer quantistici: ecco qualche possibile soluzione
Questo ha condotto ad una più elevata consapevolezza delle esigenze di protezione dei dati da ogni violazione, di garanzia di autenticità per gli stessi e di protezione dei sistemi dagli attacchi provenienti dalla rete. Pertanto, la crittografia e la sicurezza delle reti sono maturate portando allo sviluppo di applicazioni pratiche e di agevole uso in grado di consolidare la sicurezza nelle comunicazioni.
Quasi tutte le azioni effettuate online sono rese possibili dal ronzio silenzioso e implacabile degli algoritmi crittografici, ossia dai sistemi che codificano i dati per proteggere la nostra privacy, stabilire la nostra identità e proteggere i nostri pagamenti. E funzionerebbero bene in quanto, anche con l’ausilio dei più potenti supercalcolatori classici oggi disponibili, decifrare i codici su cui attualmente gira il mondo online sarebbe un’impresa quasi senza speranza.
Ma dal 1994, l’algoritmo di fattorizzazione di Shor è la spada di Damocle che mette a rischio i sistemi di crittografia convenzionale.
Il problema del key management
Nei sistemi crittografici il più annoso dei problemi rimane il key-management: la generazione, la distribuzione, la memorizzazione e il refresh delle chiavi crittografiche. Fino agli anni Settanta era richiesto che le due parti intenzionate a comunicare in segreto concordassero in anticipo un codice segreto.
Successivamente, grazie all’intuizione di tre scienziati informatici statunitensi, Whitfield Diffie, Martin Hellman e Ralph Merkle, fu escogitato il rivoluzionario concetto di crittografia a chiave pubblica, che consente a due persone di scambiarsi informazioni in modo sicuro anche senza un precedente accordo.
L’idea si basa sull’utilizzo di due chiavi: la prima, la chiave pubblica, viene utilizzata per crittografare un messaggio, la seconda, la chiave privata, per decifrarlo. Chi ha intenzione di ricevere messaggi riservati può annunciare la propria chiave pubblica al mondo, e chiunque può utilizzare tale la chiave per codificare il proprio messaggio e condividerlo apertamente. Solo il destinatario conosce la chiave privata, consentendogli di decifrare le informazioni e leggerle. In pratica, le chiavi pubbliche non vengono generalmente utilizzate per crittografare i dati, ma per condividere in modo sicuro una chiave simmetrica convenzionale, che entrambe le parti possono utilizzare per inviare dati riservati in entrambe le direzioni.
RSA e i numeri primi
Per i primi due decenni dell’era di Internet, a partire dalla metà degli anni Novanta, l’algoritmo di scambio di chiavi pubbliche più comunemente utilizzato è stato RSA, dal nome dei suoi inventori, Ron Rivest, Adi Shamir e Leonard Adleman. RSA si basa su numeri primi: numeri interi che non sono divisibili per nessun numero tranne sé stessi e 1.
La chiave pubblica è il prodotto di almeno due numeri primi. Solo una parte conosce i fattori che costituiscono la chiave privata. La privacy è protetta dal fatto che, sebbene moltiplicare due numeri grandi sia semplice, trovare i fattori primi sconosciuti di un numero molto grande è estremamente difficile. Quando i numeri sono sufficientemente grandi, non è noto alcun algoritmo di fattorizzazione di numeri interi efficiente che non sia quantistico (Shor 1994). Tuttavia, non è stato dimostrato che un tale algoritmo non esista.
Nel 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé e Paul Zimmermann hanno scomposto un numero di 240 cifre (795 bit) (RSA-240) utilizzando circa 900 core/year di potenza di calcolo. I ricercatori hanno stimato che un modulo RSA a 1024 bit impiegherebbe circa 500 volte di più.
Tra i numeri di 8 bit, i più difficili da fattorizzare utilizzando gli algoritmi esistenti sono quelli che sono prodotti di due numeri primi di dimensioni simili. Per tale motivo, questi sono i numeri interi utilizzati nelle applicazioni crittografiche. Il più grande di questi semi-primi mai scomposto è stato RSA-250, un numero a 829 bit con 250 cifre decimali, nel febbraio 2020. Il tempo di calcolo totale è stato di circa 2700 core/years di calcolo utilizzando Intel Xeon Gold 6130 a 2,1 GHz. Come tutti i recenti record, questa fattorizzazione è stata completata con un’implementazione altamente ottimizzata su centinaia di macchine.
Peter Shor e il quantum speed up
Nel 1994, Peter Shor ha scoperto un algoritmo quantistico che risolve il problema della fattorizzazione in un tempo polinomiale. L’algoritmo di Shor richiede solo tempo O(n3) e spazio O(n) su input numerici di n bit.
Nel 2001, l’algoritmo di Shor è stato implementato per la prima volta dai ricercatori dell’IBM Lieven M. K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood & Isaac L. Chuang, utilizzando un piccolo processore a 7 qubit.
L’algoritmo di Shor valuta una funzione periodica su una sovrapposizione di tutti gli input all’interno di un ampio intervallo. Applica una trasformata quantistica di Fourier per ottenere una sovrapposizione approssimata dei periodi della funzione e misura questa sovrapposizione per trovare un periodo casuale. La funzione periodica è e →aemodN, dove a è un intero casuale co-primo di N, la freccia indica “maps to”, e la notazione “mod N” indica il resto dopo la divisione per N.
Se N non è una potenza di un numero primo (un facile caso da riconoscere), allora un periodo casuale rivela un fattore di N con probabilità sufficientemente grande. Sono state condotte molte ricerche per analizzare e ottimizzare il costo esatto dell’algoritmo di Shor in termini di risorse fisiche: in particolare, il numero di bit quantistici (qubit) e il numero di operazioni richieste. Per esempio, una variante dell’algoritmo di Shor introdotta da Beauregard utilizza O(n3log(n)) operazioni su 2n + 3 qubit se N = pq rientra in n bit. Si può ridurre il numero di operazioni a n2 + o(1), con una certa spesa nel numero di qubit, dove o(1) significa qualcosa che converge a 0 per n → ∞. Si possono anche eseguire molte di queste operazioni in parallelo.
L’accelerazione esponenziale della fattorizzazione dei numeri interi da parte dell’algoritmo di Shor è una grande manifestazione della superiorità del calcolo quantistico e ha messo seriamente in discussione la sicurezza delle informazioni basata su sistemi crittografici a chiave pubblica. Tuttavia, l’esecuzione dell’algoritmo di Shor su un computer quantistico fault-tolerant richiede un numero notevolissimo di risorse fisiche.
Fino a oggi, il numero intero più grande scomposto in fattori dall’algoritmo di Shor negli attuali sistemi quantistici è 21. Questi algoritmi, se applicati a dimensioni di chiavi pubbliche ampiamente distribuite per RSA ed ECC, richiedono miliardi di operazioni su migliaia di qubit logici. Sembra probabile che gli attacchi fault-tolerant richiedano trilioni di operazioni su milioni di qubit fisici. Il calcolo quantistico incontrerà quindi un ostacolo fondamentale che gli impedisce di scalare con successo a tali dimensioni?
La fattorizzazione come problema di ottimizzazione
Per rompere lo schema RSA-2048 ampiamente utilizzato, sono necessari migliaia di qubit fisici, che vanno ben oltre le attuali capacità tecnologiche: nel novembre 2022, IBM ha annunciato il suo nuovo processore quantistico Osprey, con “soli” 433 qubit.
Tuttavia, sono state sviluppate soluzioni alternative all’algoritmo di Shor. Per bypassare le limitazioni di cui attualmente soffrono gli attuali processori quantistici, la fattorizzazione di interi può essere trasformata in un problema di ottimizzazione che può essere risolto mediante il Adiabatic Quantum Computing (AQC) o Quantum Approximate Optimization Algorithm (QAOA).
Nel calcolo quantistico adiabatico, un sistema viene inizializzato in uno stato fondamentale facile da preparare e l’hamiltoniano si evolve lentamente, in modo che il sistema rimanga in uno stato fondamentale. Lo stato fondamentale dell’hamiltoniano finale codifica la soluzione del problema di interesse. L’algoritmo di ottimizzazione approssimata quantistica è un metodo ampiamente studiato per risolvere problemi di ottimizzazione combinatoria su Noisy Intermediate-Scale Quantum devices (NISQ), cioè processori quantistici contenenti 50-100 qubit che non sono ancora sufficientemente avanzati da essere fault-tolerant o abbastanza grandi da raggiungere la supremazia quantistica.
Le applicazioni di QAOA sono ampie e di vasta portata e le prestazioni dell’algoritmo sono di grande interesse per la comunità di ricerca sull’informatica quantistica. Numeri più grandi sono stati fattorizzati utilizzando questi approcci, in vari sistemi fisici. Gli interi massimi fattorizzati sono 291311 (19 bit) con tecnologia NMR, 249919 (18 bit) nel quantum annealing D-Wave, 1099551473989 (41 bit) nei dispositivi a superconduttore. Tuttavia, va notato che alcuni degli interi fattorizzati sono stati accuratamente selezionati con strutture speciali, quindi l’intero più grande fattorizzato con un metodo generale in un sistema fisico reale è stato 249919 (18 bit).
Algoritmo di Schnorr e implementazione su processori NISQ
Claus Peter Schnorr, noto per le firme Schnorr, è un abile crittografo che ha lavorato sui problemi di factoring per almeno un decennio. Ha conseguito il dottorato di ricerca presso l’Università di Saarbrücken nel 1966 e la sua abilitazione nel 1970. Schnorr è noto per i suoi contributi alla teoria dell’informazione algoritmica e per aver creato un approccio alla definizione di una sequenza algoritmicamente casuale alternativa al concetto di casualità di Martin-Löf.
In crittografia, è noto per la firma di Schnorr, una firma digitale prodotta tramite l’omonimo algoritmo di Schnorr. Si tratta di uno schema per firme digitali di semplice implementazione, uno dei primi la cui sicurezza è basata sulla presunta difficoltà computazionale del calcolo di logaritmi discreti.
L’algoritmo è efficiente e le firme generate hanno dimensioni ridotte. Il suo brevetto è scaduto a febbraio 2008. Schnorr ha pubblicato due articoli importanti su nuovi metodi di fattorizzazione: Factoring integers by CVP algorithms e Fast factoring integers by SVP algorithms, corrected. Nell’abstract di quest’ultimo documento compare l’affermazione “Questo distrugge il sistema crittografico RSA”.
Partendo da questo algoritmo, un gruppo di ricercatori cinesi ha implementato l’algoritmo di Fast Factoring su un processore Nisq su tecnologia a superconduttore, come descritto nel preprint Factoring integers with sublinear resources on a superconducting quantum processor.
Il QAOA ha permesso di ottimizzare la parte più dispendiosa, in termini di tempo, dell’algoritmo di Schnorr per accelerare la fattorizzazione. Per un intero N di m bit, il numero di qubit necessari per l’algoritmo è stato O(m/logm), che è sublineare rispetto alla lunghezza in bit di N.
Questo lo rende l’algoritmo quantistico che consente di risparmiare più qubit per la fattorizzazione di interi rispetto agli altri esistenti, incluso l’algoritmo di Shor. Utilizzando questo algoritmo, i ricercatori sono stati in grado di fattorizzare con successo gli interi 1961 (11 bit), 48567227 (26 bit) e 261980999226229 (48 bit), rispettivamente con 3, 5 e 10 qubit mediante processore quantistico superconduttore. Il numero intero a 48 bit, 261980999226229, supera anche il numero intero più grande scomposto con un metodo generale in un dispositivo quantistico reale.
La stima, riportata nell’articolo, sulle risorse quantistiche necessarie per fattorizzare RSA-2048 è sorprendente: basterebbe un circuito quantistico con 372 qubit fisici e una profondità di migliaia per rompere RSA. È molto probabile che una tale scala di risorse quantistiche venga raggiunta sui dispositivi NISQ nel prossimo futuro. Sta quindi per arrivare il Q-Day?
Conclusioni
Di per sé, l’articolo di Schnorr è un documento alquanto controverso e nonostante l’affermazione “questo distrugge il sistema crittografico RSA” in astratto, non fa nulla del genere: l’algoritmo di Schnorr funziona bene con moduli più piccoli, all’incirca dello stesso ordine di quelli testati dal gruppo cinese, ma sembra non funzionare con dimensioni maggiori.
Il secondo punto è che nessuno sa se il QAOA renda la fattorizzazione di grandi numeri più veloce rispetto alla semplice esecuzione dell’algoritmo classico di Schnorr su un laptop. “Va sottolineato che l’accelerazione quantistica dell’algoritmo non è chiara”, scrivono gli autori.
In altre parole, sebbene sia garantito che l’algoritmo di Shor interrompa la crittografia in modo efficiente quando (e se) diventa disponibile un computer quantistico sufficientemente grande, la tecnica basata sull’ottimizzazione potrebbe essere eseguita su una macchina molto più piccola, ma potrebbe non portare a termine l’attività. Rimangono quindi i dubbi sulla capacità a breve termine di rompere i sistemi di sicurezza informatica finora utilizzati.
Ma come dice Bruce Schneier, crittografo e saggista statunitense: “In generale, la scommessa intelligente è che le nuove tecniche non funzionano. Ma un giorno, quella scommessa sarà sbagliata”. E bisogna correre ai ripari prima.
