Criptanalisi quantistica

Vogliamo qui evidenziare cosa potrebbe significare la futura introduzione di un computer quantistico per la crittografia attuale.

Un risultato eccezionale ottenuto da Peter Shor nel 1994 [Shor94] è stato quello di trovare un algoritmo efficiente per la fattorizzazione di numeri interi e per il calcolo del logaritmo discreto tramite l'uso di un calcolatore quantistico.

Due delle più importanti tecniche della crittografia attuale verrebbero a perdere della loro sicurezza una volta che questo algoritmo diventasse realizzabile: RSA sfrutta proprio la difficoltà di fattorizzare numeri interi molto grandi per garantire la sua sicurezza, ed il protocollo di scambio delle chiavi ideato da Diffie ed Hellman poggia le sue basi sulla difficoltà di calcolo del logaritmo discreto.

L'algoritmo di Shor consente di fattorizzare un numero in fattori primi in un numero di passi proporzionale al quadrato della lunghezza del numero (in simboli $\mathcal{O}({(\log N)}^2)$ dove $N$ è il numero da fattorizzare), un notevole passo avanti rispetto agli algoritmi attuali; un esempio di algoritmo banale di fattorizzazione è il seguente: il nostro numero in esame è $N$ con $L$ cifre (quindi si ha $N   \approx   {10}^L$) e lo dividiamo per 2, 3, ..., $\sqrt{N}$ (possiamo naturalmente limitarci ai soli numeri primi tra 2 e $\sqrt{N}$) controllando il resto delle divisioni. Nel caso peggiore sono richieste $\sqrt{N}   \approx   {10}^{\frac{L}{2}}$ divisioni, un numero che cresce esponenzialmente con la lunghezza di $N$.

Questo risultato è molto importante in quanto è da secoli che si cerca un modo efficiente per fattorizzare i numeri e, vista la difficoltà di questo compito, si ritiene che non sia possibile fare molto meglio dell'algoritmo banale su un computer classico.

Quello di Shor non è l'unico algoritmo quantistico esistente: nel 1996 Lov Grover ha trovato un modo [Grover97] per recuperare un elemento da una lista disordinata di $N$ elementi in un tempo proporzionale a $\sqrt{N}$, contro un tempo proporzionale ad $N$ per gli algoritmi classici; l'attacco a DES, il cifrario a chiave condivisa più utilizzato, richiede proprio la ricerca in una tabella di grandi dimensioni per essere portato a termine, e questo incremento prestazionale lo rende ancora più attuabile.

Morpheus 2004-01-07