Uno studio inviato ai Proceedings del 35o Simposio annuale della Foundations of Computer Science tenutosi nel 1994 da un ricercatore presso l’AT and T Bell Laboratories, negli Stati Uniti, di nome P. W. Shor riportava queste “allarmanti” parole:
“Questo studio fornisce algoritmi … per la ricerca di logaritmi discreti e per la fattorizzazione di numeri interi su un computer quantistico che hanno bisogno di un numero di passi che è polinomiale nella dimensione dell’ingresso, per esempio, il numero di cifre del numero intero da fattorizzare. Questi due problemi sono generalmente considerati difficili su un computer classico e sono stati (quindi) usati come base di differenti sistemi crittografici proposti.”
Questo allarme, un po’ criptico per i non addetti ai lavori, si riferisce soprattutto ai sistemi di crittografia asimmetrica (o a chiave pubblica) che costituiscono l’ossatura delle comunicazioni sicure su Internet, e in generale di tutte le transazioni sicure a distanza. Infatti i sistemi di crittografia simmetrica risultano anche interessati, ma in misura meno significativa. Ma vediamo prima insieme a cosa ci si riferisce quando si parla di sistemi di crittografia simmetrica e asimmetrica.
L’imposizione dei sistemi di crittografia asimmetrica nell’era dell’informazione
Da sempre, spie e servizi militari hanno potuto contare su sistemi di crittografia, via via sempre più complessi e difficili da decodificare, per lo scambio di informazioni su canali pubblici. Ma tutti questi sistemi fino agli anni 70 però prevedevano che le due parti conoscessero e condividessero una chiave, unica, per cifrare e decifrare il messaggio. Basta pensarci un po’ per capire che tali sistemi di crittografia sarebbero divenuti insostenibili in un mondo sempre più globale e ramificato che si stava affacciando nell’era dell’informazione.
Così, nel 1976, tre informatici statunitensi, Whitfield Diffie, Martin Hellman e Ralph Merkle, proposero un concetto rivoluzionario: la crittografia asimmetrica, o a chiave pubblica, che consentiva per la prima volta a due persone, che non si erano mai accordate in precedenza su una chiave da usare, di scambiarsi informazioni in modo sicuro su qualsiasi canale pubblico. L’idea si basa su una funzione matematica che utilizza due numeri: uno, che rappresenta la chiave pubblica, viene usato per cifrare un messaggio. Un altro, differente dal primo e che rappresenta la chiave privata, viene usato per decifrarlo.
In questo contesto, una prima persona che voglia ricevere un messaggio criptato può divulgare al mondo la propria chiave pubblica, usando qualsiasi mezzo, perfino un quotidiano. In questo modo, una seconda persona, che vuole comunicare in modo riservato e sicuro con la prima persona, potrà semplicemente usare la chiave pubblica nota per criptare il messaggio e inviarlo. Solo il destinatario, che conosce la chiave privata, potrà infatti decifrare il messaggio e leggerlo.
Questo sistema si basa, tra l’altro, sul fatto che i due numeri, la chiave pubblica e la chiave privata, sono legati da una relazione matematica. Solo la chiave privata associata alla chiave pubblica può decifrare il messaggio. Inoltre, la conoscenza della chiave pubblica non permette di risalire in tempi ragionevoli (i famosi passi polinomiali di prima) alla chiave privata.
Nei primi anni dell’era di Internet, il sistema crittografico più usato è stato l’RSA, dal nome dei suoi inventori, Ron Rivest, Adi Shamir e Leonard Adleman. L’RSA si basa sui numeri primi – numeri interi come 7 o 53 che sono divisibili solo per se stessi e per 1. La chiave pubblica è il risultato del prodotto di almeno due numeri primi, generalmente molto grandi. Solo chi ha generato la chiave pubblica conosce i fattori, ovvero i singoli numeri primi il cui prodotto è la chiave pubblica. Questi fattori, insieme, rappresentano la chiave privata. La velocità, la sicurezza e la robustezza di questo sistema sono garantite dal fatto che, sebbene moltiplicare due numeri grandi sia semplice, trovare i fattori primi sconosciuti di un numero molto grande è estremamente difficile. Questa operazione prende appunto il nome di fattorizzazione di numeri interi, che è stata appunto chiamata in causa dall’allarme di Shor.
In verità, alla prova dei fatti l’RSA si è rilevato debole anche ad attacchi di tipo classico. Ragion per cui dal 2018, il sistema di crittografia basato sull’RSA è stato sostituito con la crittografia a curva ellittica. Quest’ultima si basa sul calcolo dell’ennesima (n) potenza di un numero intero. Solo una parte conosce il numero n, che è la chiave privata. Calcolare l’esponenziale di un numero è facile, ma dato il risultato, è estremamente difficile scoprire l’esponente n. Questa tecnica si è rivelata più veloce e più sicura dell’RSA, almeno per gli attacchi di tipo classico. Infatti, come per la fattorizzazione dei numeri primi alla base dell’RSA, anche le operazioni matematiche alla base della crittografia a curva ellittica sono sensibili ad un attacco con un computer quantistico.
In attesa del Q-day
Ai tempi della pubblicazione dell’articolo di Shor, si trattava per lo più di un esercizio teorico, perché i computer quantistici erano poco più di un sogno per i fisici. Ma già nel corso degli anni 90 nacquero i primi embrioni di sistemi basati sul calcolo quantistico che usavano molecole in una macchina a risonanza magnetica nucleare. Nei primi anni 2000 ci fù la prima implementazione pratica dell’algoritmo di Shor su un computer quantistico, sebbene la potenza era tale che la fattorizzazione era in grado di essere eseguita con successo solo su numeri a due cifre. Da allora i sistemi di calcolo quantistico hanno fatto molti progressi, ma l’esecuzione dell’algoritmo di Shor su un numero di cifre significative sembra essere ancora molto lontana.
Tuttavia, dopo l’allarme lanciato da Shor, il mondo della ricerca dei sistemi crittografici ha iniziato a prestare attenzione alla possibilità di un Q-day, il giorno in cui un sistema di calcolo quantistico sarà in grado di compiere praticamente un attacco ai sistemi di crittografia asimmetrici. Nell’attesa di quel giorno, che sembra ancora essere lontano un decennio, i maggiori esperti di crittografia hanno iniziato a studiare dei possibili nuovi algoritmi in grado di reggere a un attacco con un sistema di calcolo quantistico.
Algoritmi di crittografia post-quantistici
Il rischio di un Q-day è apparso talmente serio, che nel 2015, l’Agenzia per la sicurezza nazionale (National Security Agency, NSA) degli Stati Uniti, ha annunciato di ritenere vulnerabili gli attuali sistemi di crittografia, suggerendo quindi alle aziende e al governo degli Stati Uniti di sostituirli. L’anno immediatamente successivo, l’Istituto nazionale per gli standard e la tecnologia degli Stati Uniti (US National Institute of Standards and Technology, NIST) con sede a Gaithersburg, nel Maryland, ha invitato l’intera comunità mondiale degli esperti di crittografia a sottoporre i candidati algoritmi post-quantistici a un processo di qualità. In effetti, in seguito all’allarme lanciato da Shor, l’intera comunità ha pubblicato e proposto centinaia di algoritmi. Di questi ne sono stati sottomessi 82 al NIST, 65 dei quali hanno superato i test iniziali. Da allora l’elenco è stato ridotto da 65 a 15, e infine a 3.
Di pochi giorni fa è infatti la notizia che il NIST ha finalmente suggerito tre algoritmi per la crittografia post Q-day, rivolgendo l’invito a tutte le agenzie di implementarli in tutti i sistemi. Questi tre algoritmi includono un algoritmo per la gestione della cifratura dei messaggi e due algoritmi per proteggere l’identità digitale di utenti o dispositivi noti. L’algoritmo di cifratura dei messaggi prende il nome di CRYSTALS-Kyber. Secondo gli esperti del NIST l’applicazione di questi algoritmi su sistemi software come Internet browser e App dovrebbe essere abbastanza rapida e indolore per la maggior parte degli utenti. Invece, la loro implementazione su sistemi hardware dedicati tramite firmware potrebbe essere più lenta.
Sebbene l’algoritmo CRYSTALS-Kyber sia stato ritenuto essere resistente agli attacchi realizzati tramite i sistemi di calcolo quantistici, in realtà nessun algoritmo di crittografia a chiave pubblica esistente è stato dimostrato essere completamente sicuro dal punto di vista matematico. I ricercatori e gli esperti continuano attivamente a lavorare su possibili alternative. Lo stesso NIST, in un comunicato, ha infatti dichiarato che sta valutando altri algoritmi che un giorno potrebbero servire come standard di riserva.
Riferimenti:
Shor, P. W. Proc. 35th Annu. Symp. Found. Comput. Sci. 124–134 (IEEE, 1994). https://doi.org/10.1109/SFCS.1994.365700
