Gli algoritmi di Shor e Grover spiegati

I computer quantistici non eseguono semplicemente gli algoritmi classici più velocemente: sfruttano la sovrapposizione e l'interferenza quantistiche per risolvere determinati problemi con una velocità esponenzialmente maggiore. Due algoritmi minacciano la maggior parte della crittografia attualmente in uso: quello di Shor (che compromette RSA/ECC) e quello di Grover (che indebolisce la crittografia simmetrica e gli hash).

L'algoritmo di Shor (1994) risolve la fattorizzazione degli interi e il logaritmo discreto in tempo polinomiale su un computer quantistico. Questo compromette direttamente RSA (basato sulla fattorizzazione), Diffie-Hellman (logaritmo discreto mod p) ed ECDH/ECDSA (logaritmo discreto su curve ellittiche).

L'ingrediente fondamentale dell'algoritmo di Shor è la Quantum Fourier Transform (QFT), una versione quantistica esponenzialmente più veloce della DFT. Per la ricerca del periodo, la QFT identifica il periodo di f(x) = a^x mod N, dal quale si ricavano i fattori di N tramite il GCD.

Per fattorizzare N: (1) scelga un valore casuale a < N e verifichi gcd(a,N)=1. (2) Trovi il periodo r di f(x)=a^x mod N usando la QFT. (3) Con alta probabilità, gcd(a^{r/2}±1, N) restituisce un fattore non banale. Il passaggio classico è O(log N); la ricerca quantistica del periodo è O((log N)^3), cioè polinomiale.

Il miglior metodo classico di fattorizzazione è GNFS, con complessità subesponenziale O(exp((64/9 log N)^{1/3} log log N)^{2/3})). L'algoritmo di Shor su un computer quantistico fault-tolerant ha complessità polinomiale O((log N)^3). RSA-2048 richiede circa 4000 qubit logici e circa 10^9 operazioni di gate. Gli attuali computer NISQ dispongono di circa 1000 qubit rumorosi: non rappresentano ancora una minaccia.

L'algoritmo di Grover (1996) offre un'accelerazione quadratica per la ricerca non strutturata. Per uno spazio di ricerca di N elementi, gli algoritmi classici richiedono O(N) interrogazioni; quello di Grover ne richiede O(√N). Applicato alla crittografia, compromette chiavi simmetriche di n bit in O(2^{n/2}) invece di O(2^n).

AES-128: sicurezza classica 2^128; l'algoritmo di Grover la riduce a 2^64, rendendola insicura contro un grande computer quantistico. AES-256: 2^256 → 2^128, quindi rimane sicuro. Soluzione: raddoppiare la dimensione delle chiavi simmetriche. Resistenza alle collisioni di SHA-256: 2^128 → 2^85 (birthday+Grover). Preimage di SHA-256: 2^256 → 2^128, quindi adeguata.

Gli attuali computer quantistici NISQ (IBM Heron: 133 qubit, Google Sycamore: 70 qubit) sono troppo piccoli e troppo rumorosi per eseguire calcoli rilevanti per la crittografia. Le stime per la compromissione di RSA-2048 indicano il periodo 2035-2050 con computer quantistici fault-tolerant. Gli attacchi harvest-now-decrypt-later rappresentano una minaccia attuale.

Gli avversari raccolgono oggi il traffico cifrato e lo archiviano. Quando sarà disponibile un computer quantistico, lo decifreranno retroattivamente. Questo rende vulnerabili già oggi i segreti destinati a durare a lungo, come i dati governativi classificati e le cartelle cliniche. Per questi dati, la migrazione alla PQC deve iniziare subito.

Problemi reticolari (LWE, SIS), problemi basati sui codici (McEliece), firme basate su hash (SPHINCS+), problemi multivariati: non è noto alcun algoritmo quantistico in tempo polinomiale. Questi problemi costituiscono la base degli standard post-quantistici NIST.

Gli standard PQC di NIST (ML-KEM, ML-DSA, SLH-DSA) sono stati finalizzati nel 2024. Le organizzazioni dovrebbero: inventariare l'uso attuale della crittografia, identificare i dati destinati a durare a lungo e dare priorità all'implementazione della PQC per lo scambio di chiavi, che è l'aspetto più urgente a causa degli attacchi harvest-now-decrypt-later. Per le firme c'è più tempo.

L'algoritmo di Shor (tempo polinomiale) compromette RSA, DH ed ECC. L'algoritmo di Grover (accelerazione quadratica) dimezza la resistenza delle chiavi simmetriche. Soluzione: migrare agli standard PQC di NIST (basati su reticoli). Prossimo argomento: CRYSTALS-Kyber KEM.