La crittografia nell'era dei computer quantistici

Si sta affermando sempre di più l’importanza dei computer quantistici e di come potranno portare una rivoluzione in tutti i campi delle scienze. Assieme a nuove possibilità, l’era delle macchine quantistiche porterà con sé molte sfide per l’informatica, soprattutto per quanto riguarda la crittografia.

La scrittura di messaggi segreti

La crittografia può essere definita come l’insieme delle tecniche che ci permette di scrivere messaggi segreti e impedire a persone non autorizzate di leggerli. Esse prevedono l’utilizzo di un algoritmo matematico e di una chiave, che altro non è che un dato numerico.

Il procedimento può essere riassunto nel modo seguente:

• Il messaggio in chiaro (leggibile) viene cifrato e reso illeggibile attraverso un procedimento matematico che usa una chiave.
• Viene trasmesso il messaggio cifrato.
• Quando il messaggio raggiunge il destinatario viene ri-trasformato in quello originale.

Esistono due famiglie principali di algoritmi crittografici: simmetrici e asimmetrici.

Gli algoritmi simmetrici utilizzano la stessa chiave per cifrare e decifrare e quindi, se il mittente e il destinatario condividono una chiave, la possono usare per comunicare in maniera sicura. La crittografia simmetrica è molto potente e resistente ma ha in sé un grandissimo problema: come faccio a trasmettere la chiave al destinatario? Se un ipotetico avversario se ne impossessasse, riuscirebbe a leggere tutti i messaggi scambiati.

Questo problema ha afflitto gli informatici e i matematici fino agli anni ‘60 quando furono inventati i primi algoritmi asimmetrici. Questi sistemi prevedono che ogni persona possegga due diverse chiavi. Una pubblica, utilizzata solo per cifrare, e una privata, che permette di decifrare i messaggi.

Questo sistema risolve il problema della trasmissione delle chiavi. Chiunque voglia trasmettere un messaggio basta che ottenga la chiave pubblica del destinatario e la usi per cifrare il messaggio.

Per capire meglio questo concetto facciamo un esempio pratico: quando navighiamo in rete e ci sentiamo sicuri vedendo i siti HTTPS (evidenziati da un lucchetto verde) dovremmo sapere che dietro questa protezione vi è un algoritmo di cifratura asimmetrica.

Nel momento in cui accediamo ad un sito, possiamo leggere la sua chiave pubblica e quando, poi, inviamo informazioni, la usiamo per cifrarle. Una volta che i messaggi saranno arrivati a destinazione, il proprietario del sito utilizzerà la sua chiave privata per decifrare i messaggi. Ovviamente si suppone che la chiave privata rimanga segreta e conosciuta solo dal proprietario del sito.

In realtà, i più esperti sapranno che il sistema è leggermente più complesso di così, ma questo esempio è sufficiente per arrivare a parlare di crittografia post-quantistica.

La classificazione dei problemi

Gli schemi di cifratura asimmetrici si basano sull’assunzione che esistano problemi che risultano essere difficili da calcolare in tempi brevi persino dal più potente dei computer.

In informatica esistono degli studi che si occupano di dividere i problemi e di raggrupparli per tipologie, dette classi. Un problema si definisce appartenente alla classe P (polinomiale) se esiste un algoritmo che, quando viene eseguito da un computer, è in grado di arrivare ad una soluzione in tempo accettabile.

Per coloro che preferiscono una definizione più formale è possibile definire un problema in P nel modo seguente:

Un problema appartiene alla classe P se esiste un algoritmo sempre corretto che richiede, nel caso peggiore, un numero di operazioni elementari f(n) = O(n^d), dove d è una costante e n è la dimensione dell’istanza.

Esiste poi una classe NP (polinomiale non deterministico) che, semplificando al massimo, possiamo dire racchiuda in sé tutti i problemi che una macchina può risolvere a prescindere dal tempo impiegato.

Come possiamo notare dalla figura l’insieme P è molto più piccolo dell’insieme NP, quindi esistono effettivamente molti problemi che un computer tradizionale non riesce a risolvere in tempi brevi. Facciamo il più classico degli esempi: la fattorizzazione di un numero.

Consideriamo un numero N che è dato dal prodotto di 2 numeri primi P e Q (N = P x Q). Se N è abbastanza grande (ad oggi 4096 bit) anche il computer più potente del mondo impiegherebbe secoli a ricavare P e Q partendo da N.

La fattorizzazione di un numero, come anche il calcolo del logaritmo discreto, sono i problemi che oggi sono usati negli algoritmi di crittografia asimmetrica che ci proteggono ogni volta che navighiamo sul web.

Definiamo ora una classe chiamata BQP che comprende tutti quei problemi risolvibili in tempi accettabili da un computer quantistico. Possiamo dire che un computer quantistico sia più potente di un computer tradizionale, nonostante non sia ancora chiaro per noi come poterli produrre in modo economico.

Come si osserva dall’immagine, la classe BQP è più grande della classe P e, inoltre, comprende proprio i problemi di fattorizzazione e calcolo del logaritmo discreto che utilizziamo. Questo vuol dire che un computer quantistico può arrivare a decifrare tutti i messaggi che ad oggi utilizzano crittografia asimmetrica, che ricordiamo essere quella che utilizziamo quando navighiamo o anche quando andiamo a fare un pagamento con una carta elettronica.

La soluzione

Si è reso necessario trovare problemi che siano fuori dalla classe BQP e che possano essere usati per la crittografia asimmetrica. Fortunatamente per noi, in questi anni è stato fatto uno sforzo a livello mondiale per cercare di creare algoritmi di crittografia asimmetrica che da qui a qualche anno andranno a sostituire quelli che usiamo tutti i giorni.

I problemi identificati per la crittografia che neanche un computer quantistico riesce a risolvere in modo rapido sono: codici di correzione di errori e crittografia lattice-based (particolari strutture matematiche). Nel 2017, il NIST ha indetto un “concorso” a livello mondiale per raccogliere i nuovi schemi crittografici e alla fine del 2021 dovrebbero essere proclamati i vincitori.

Il NIST, in seguito, procederà a pubblicare tutta la documentazione necessaria per far sì che tutti i protocolli in uso oggi possano adattarsi ai nuovi standard crittografici post quantistici, utilizzando le nuove funzioni matematiche.