Nessun risultato ha fatto per il calcolo quantistico quello che ha fatto l'algoritmo di Shor. Nel 1994 ha trasformato una speculazione da fisici in un problema di sicurezza planetario, dimostrando che un computer quantistico sufficientemente grande fattorizza numeri interi in tempo polinomiale e quindi rompe la crittografia RSA. Questa guida lo affronta senza sconti e senza allarmismi. Copre il problema che risolve, la meccanica della riduzione alla ricerca del periodo, il ruolo della trasformata di Fourier quantistica, le stime realistiche di risorse per una chiave vera, lo stato delle esecuzioni sperimentali, la minaccia "harvest now, decrypt later" e le difese già standardizzate, fino a come studiarlo concretamente in emulazione quantistica.
Che cos'è l'algoritmo di Shor?
L'algoritmo di Shor è una procedura quantistica per la fattorizzazione di numeri interi, pubblicata da Peter Shor nel 1994 nell'articolo che fondò la crittoanalisi quantistica, oggi liberamente leggibile su arXiv. Il suo tempo di esecuzione cresce polinomialmente con il numero di cifre dell'intero da fattorizzare, mentre il miglior metodo classico noto, il crivello dei campi di numeri, cresce in modo superpolinomiale. Per chiavi di dimensioni crittografiche il divario diventa quello tra ore e miliardi di anni. Fu la prima dimostrazione che il vantaggio quantistico esponenziale esiste su un problema di enorme valore pratico, e per questo resta il riferimento con cui ogni altro claim del settore viene misurato. Trent'anni dopo, quando si vuole spiegare a un consiglio di amministrazione perché il calcolo quantistico non è solo ricerca di base, si parte ancora da qui.
Quale problema risolve esattamente?
Dato un intero composto N, trovare un suo fattore non banale. Sembra aritmetica da scuola, ma sulla difficoltà di questo problema per numeri di centinaia di cifre poggia mezzo secolo di sicurezza informatica. Va detto con precisione. La fattorizzazione non è mai stata dimostrata difficile, è soltanto resistita a ogni attacco classico noto; l'algoritmo di Shor non viola quindi alcun teorema, ma sfrutta un modello di calcolo diverso in cui il problema cade in una classe trattabile. Lo stesso schema risolve il logaritmo discreto, il che estende la minaccia dalla crittografia RSA a Diffie-Hellman e alle curve ellittiche, cioè praticamente a tutta la crittografia a chiave pubblica pre-quantistica. Restano invece fuori dalla portata dell'algoritmo di Shor la crittografia simmetrica come AES e le funzioni hash, contro cui il quantistico offre al più il vantaggio quadratico di Grover; lì basta allungare le chiavi per ristabilire il margine di sicurezza.
Perché la fattorizzazione minaccia la crittografia RSA?
RSA fonda la sua sicurezza su un'asimmetria. Moltiplicare due primi grandi è immediato, risalire ai fattori dal prodotto è classicamente proibitivo. La chiave pubblica contiene il prodotto N, e chi sapesse fattorizzarlo ricaverebbe la chiave privata, con essa la capacità di decifrare ogni comunicazione e di falsificare ogni firma. L'algoritmo di Shor colpisce esattamente questa asimmetria, e non con un margine negoziabile. Raddoppiare la lunghezza della chiave, che è la difesa classica contro i progressi degli attacchi, aumenta il costo quantistico solo polinomialmente, quindi di poco. Non esiste una versione "abbastanza lunga" di crittografia RSA che resista, perciò la risposta deve essere un cambio di matematica, come spiegato nella pagina sulla crittografia post-quantistica.
Cosa è il sistema di crittografia a chiave pubblica RSA
RSA prende il nome dagli inventori Rivest, Shamir e Adleman, che lo pubblicarono nel 1977, ed è il sistema a chiave pubblica più diffuso al mondo. Permette a due parti di comunicare in modo cifrato senza essersi prima scambiate alcun segreto, grazie a una coppia di chiavi legate matematicamente. Con la chiave pubblica, distribuibile a chiunque, si cifra; con la chiave privata, custodita dal solo destinatario, si decifra; il meccanismo inverso genera le firme digitali. La coppia nasce da due numeri primi molto grandi p e q, il cui prodotto n entra nella chiave pubblica. Cifrare significa calcolare c = me mod n, decifrare significa calcolare m = cd mod n, dove l'esponente privato d si ricava solo conoscendo p e q. Tutta la sicurezza sta quindi nella difficoltà di fattorizzare n, il problema che l'algoritmo di Shor rende trattabile. Nella pratica RSA protegge lo scambio di una chiave simmetrica usa e getta, ad esempio AES, con cui viene cifrato il traffico vero e proprio; è il modello ibrido dietro HTTPS, VPN, firme digitali e transazioni bancarie, ed è il motivo per cui la portata della minaccia descritta in questa pagina è così ampia.
Come funziona la riduzione alla ricerca del periodo
Il colpo di genio è classico prima che quantistico. Scelto a caso un intero a coprimo con N, si considera la successione delle potenze di a modulo N. Questa successione è periodica, e la teoria dei numeri garantisce che dal periodo r, se pari e "ben posto", si estraggono fattori di N con un massimo comune divisore, un calcolo immediato. Tutta la difficoltà si concentra quindi nel trovare r, un compito in cui i metodi classici tornano esponenziali perché il periodo può essere enorme. Ed è qui che entra in gioco il quantistico. La funzione viene valutata in sovrapposizione su tutti gli esponenti insieme, e la periodicità globale diventa una proprietà estraibile per interferenza, invisibile a qualunque campionamento locale. In altre parole, il computer quantistico non prova i divisori uno per uno, ma interroga la struttura nascosta del problema, che è esattamente il tipo di compito in cui questo modello di calcolo eccelle.
Che ruolo ha la trasformata di Fourier quantistica?
Approfondimento per il lettore con formazione scientifica
Preparato lo stato Σx|x⟩|ax mod N⟩ e misurato il secondo registro, il primo collassa su una sovrapposizione dei soli esponenti che condividono lo stesso residuo, una struttura a pettine di passo r. La trasformata di Fourier quantistica applicata a questo registro concentra l'ampiezza sui multipli di 2n/r, così la misura restituisce un valore da cui l'algoritmo delle frazioni continue ricava r con alta probabilità. La QFT su n qubit costa O(n²) porte, ed è questa efficienza a rendere polinomiale l'intero schema. Il resto, elevamento modulare controllato compreso, è aritmetica reversibile, laboriosa da implementare ma concettualmente ordinaria. Chi ha seguito questo passaggio possiede il cuore dell'algoritmo; tutto il dibattito sulle risorse, nella sezione che segue, riguarda quanto costa realizzarlo su hardware reale.
Quante risorse servono per violare RSA-2048?
Le stime più citate in letteratura collocano l'impresa nell'ordine di ventimila qubit logici con correzione d'errore, ovvero, con i codici e i tassi d'errore attuali, alcuni milioni di qubit fisici, per un'esecuzione di ore. I processori odierni contano qubit fisici nell'ordine delle migliaia, rumorosi e non corretti. Mancano tre ordini di grandezza e, soprattutto, manca la correzione degli errori su larga scala. Le stime scendono a ogni progresso algoritmico e ingegneristico, e su questo la ricerca è vivace, ma i numeri vanno maneggiati con rigore. Chi annuncia RSA violato domani mattina e chi lo dichiara impossibile per sempre sbagliano entrambi, e per la stessa ragione, perché confondono la traiettoria, che è chiara, con i tempi, che restano incerti. Per il decisore il numero da ricordare non è una data, ma un rapporto. Servono ancora nell'ordine di mille qubit fisici per ogni qubit logico utile, ed è quel rapporto, più del conteggio totale di qubit, l'indicatore da monitorare nei report annuali sullo stato dell'hardware.
È mai stato eseguito davvero?
Sì, su numeri da manuale. Il record fondativo è la fattorizzazione di 15 con la risonanza magnetica nucleare nel 2001; sono seguiti 21 e pochi altri interi minimi su fotoni, ioni e superconduttori. Vanno lette per ciò che sono, cioè dimostrazioni di principio, spesso con circuiti semplificati che sfruttano la conoscenza anticipata della risposta, un compromesso dichiarato nelle stesse pubblicazioni. Periodicamente circolano annunci di "fattorizzazioni record" ottenute però con metodi diversi da Shor, tipicamente varianti di ottimizzazione che non scalano; distinguere i due casi è il primo test di competenza nella lettura delle notizie di settore. Nessuna esecuzione onesta e completa dell'algoritmo di Shor su un numero crittograficamente interessante è mai avvenuta, né è alle porte. Il valore di questi esperimenti è ingegneristico, cioè verificare che ogni blocco della catena funzioni, non crittoanalitico. Il divario con RSA-2048 resta quello descritto sopra.
Cosa significa "harvest now, decrypt later"?
È la ragione per cui il problema è urgente oggi nonostante l'hardware non esista ancora. Un avversario paziente può intercettare e archiviare adesso traffico cifrato, con costi di storage irrisori, per decifrarlo quando l'hardware sarà maturo. Ogni dato la cui riservatezza deve durare oltre l'orizzonte di arrivo del calcolo quantistico è quindi già a rischio, oggi. Per categorie come segreti industriali, dati sanitari, comunicazioni diplomatiche e proprietà intellettuale, il calendario della migrazione non lo detta l'arrivo della macchina, ma la vita utile del dato. È il criterio con cui agenzie di sicurezza e regolatori, in Europa e negli Stati Uniti, hanno già fissato scadenze di transizione per le infrastrutture critiche.
Come difendersi con la crittografia post-quantistica
La difesa non è quantistica ma matematica. Consiste nel sostituire i problemi vulnerabili, fattorizzazione e logaritmo discreto, con problemi per cui non si conoscono attacchi quantistici efficienti, come quelli sui reticoli. Il NIST ha standardizzato nel 2024 i primi schemi, tra cui ML-KEM per lo scambio di chiavi e ML-DSA per le firme, e la migrazione è iniziata nei protocolli di rete e nelle infrastrutture critiche. Per un'organizzazione il lavoro è di inventario e pianificazione. Bisogna censire dove vive la crittografia vulnerabile, spesso annidata in fornitori, librerie e dispositivi che nessuno ha mai mappato, e sequenziare la sostituzione partendo dai dati a vita lunga. L'esperienza insegna che l'inventario è la parte più lunga del percorso, e conviene avviarlo prima che le scadenze regolatorie lo trasformino in un'emergenza. Il tema rientra a pieno titolo nel perimetro delle tecnologie critiche.
Come si studia l'algoritmo di Shor in emulazione?
Nel modo più istruttivo possibile, cioè eseguendolo per intero su numeri piccoli, con ogni registro ispezionabile. In un ambiente di emulazione come la piattaforma EQM si prepara la sovrapposizione degli esponenti, si osserva letteralmente il pettine di periodicità formarsi nel registro dopo la misura parziale, si applica la trasformata di Fourier e si vede l'ampiezza concentrarsi sui multipli giusti. La catena logica smette di essere una narrazione e diventa un esperimento riproducibile. È anche il banco su cui si studiano le varianti moderne a basso consumo di qubit e si formano i team che dovranno governare la transizione crittografica, perché capire l'attacco è il primo passo per dimensionare la difesa.
Capisci la minaccia, dimensiona la difesa
Con HumanQ esegui l'algoritmo di Shor in emulazione, formi il tuo team e valuti l'esposizione crittografica della tua organizzazione. Approfondisci la crittografia post-quantistica, valuta la tua quantum readiness o contatta il team HumanQ.