Nel contesto dell’evoluzione dei computer quantistici, che minacciano la sicurezza delle attuali comunicazioni digitali, è fondamentale esplorare algoritmi innovativi come Falcon.
Questo algoritmo rappresenta una risposta avanzata e robusta alle sfide poste dalla crittografia post quantistica.
Indice degli argomenti
Introduzione alla crittografia post quantistica
La crittografia post quantistica è un ambito della crittografia che si occupa di studiare e sviluppare algoritmi crittografici che, ad oggi, sono ritenuti sicuri perfino contro attacchi eseguibili da un computer quantistico.
La crittografia post quantistica è completamente distinta dalla cosiddetta crittografia quantistica. La prima, sfruttando la matematica pura, crea algoritmi crittografici eseguibili su computer convenzionali attuali che permettono la trasmissione di un certo messaggio su un canale di trasmissione non sicuro. La seconda, invece, punta alla creazione diretta di un certo canale di comunicazione sicuro per lo scambio di messaggi tra due entità, e si basa su proprietà della meccanica quantistica fornite dalla fisica.
La crittografia post quantistica (in inglese riassunta con l’acronimo PQC, ovvero “Post-Quantum Cryptography”) è stata studiata ed analizzata sia da programmatori che da studiosi specialmente in questi ultimi anni. Il motivo è semplice: vista l’incessante evoluzione dei computer quantistici, si presume che essi saranno a breve resi disponibili a persone comuni, ed è quindi molto importante iniziare presto la lenta e lunga sostituzione degli algoritmi crittografici comunemente usati oggi. Per intuire il rischio causato dall’avvento di un computer quantistico venduto su larga scala, è utile comprendere quali algoritmi siano coinvolti durante una comunicazione via Internet.
Come si comunica in maniera sicura via Internet
L’Internet è, per sua costruzione, un canale di comunicazione non sicuro. Nonostante questo, categorie di algoritmi crittografici come le firme digitali, lo scambio di chiave e la crittografia simmetrica permettono comunque a due entità di comunicare in maniera sicura su questo canale.
Per esempio, immaginiamo che un consulente bancario voglia inviarci informazioni private riguardo il nostro patrimonio dentro un file PDF. Con alta probabilità, per trasmettere tale documento, la banca offre a noi e al nostro consulente un sistema di messagistica apposito, che tipicamente svolge tre azioni principali.
Subito dopo che il consulente preme “INVIA”, un algoritmo di firma digitale viene applicato sul PDF. Tale algoritmo crea una firma digitale, una serie di dati aggiuntivi inviati insieme al PDF che, una volta verificata, ci permette di verificare l’identità del consulente, di assicurarci dell’integrità del documento trasmesso (cioè, del fatto che nessuna entità ha modificato le informazioni contenute nel PDF durante la trasmissione) e di dimostrare che la firma è davvero stata generata dal consulente (in gergo, questa è la proprietà del non ripudio).
Dopo la firma, il sistema di messaggistica esegue un algoritmo di scambio di chiave. In crittografia, la “chiave” è una certa informazione digitale comune tra due entità, ma ignota a qualsiasi entità esterna. L’algoritmo di scambio di chiave ha come scopo quello di fare ottenere una medesima chiave a noi e al consulente. Risulta possibile, ma relativamente complicato, scambiare una chiave solo tra due entità con messaggi che passano attraverso un canale di comunicazione insicuro come l’Internet. Le procedure e gli algoritmi che ottengono questo scambio usano molteplici messaggi e alcune computazioni aggiuntive che rendono l’intero algoritmo relativamente lento ed inefficiente. Infatti, gli algoritmi di scambio di chiave sono usati per inviare solo piccole chiavi alla volta.
Una volta completato lo scambio di chiave tra noi e il consulente, il sistema di messaggistica conclude eseguendo un algoritmo di crittografia simmetrica. Questi algoritmi sono veloci da eseguire, facili da implementare e di piccola dimensione. Sono infatti appositamente progettati per trasmettere in modo sicuro lunghi messaggi o molteplici messaggi tra due entità. Tramite la chiave del consulente, l’algoritmo di crittografia simmetrica critta il PDF avente informazioni sul nostro patrimonio e la firma corrispondente, mascherando e ingarbugliando l’uno e l’altra. A questo punto, il sistema di messaggistica bancaria recapita a noi questi dati mascherati, utilizza la nostra copia della chiave per estrarre il PDF e la firma, e verifica la firma.
Tenendo a mente questo esempio, vediamo come la sicurezza delle tre categorie di algoritmi elencati sopra sarà intaccata dal commercio di computer quantistici.
Minacce dei computer quantistici agli algoritmi crittografici
Tutto sommato, gli algoritmi di crittografia simmetrica resisteranno bene all’avvento dei computer quantistici. AES (acronimo per “Advanced Encryption Standard”) è un famoso algoritmo di crittografia simmetrica che è stato standardizzato dal NIST tramite una competizione pubblica all’inizio degli anni 2000. AES sarà soddisfacentemente resistente a questi nuovi computer grazie a un semplice aggiornamento dove prenderà in considerazione chiavi lunghe il doppio di quelle attuali.
Invece, la situazione per gli algoritmi di firma digitale e di scambio di chiave è alquanto preoccupante. Entrambe queste categorie di algoritmi sono sotto-categorie della più vasta crittografia asimmetrica e, sfortunatamente, i computer quantistici minano la loro base comune.
Evitando di entrare troppo nel dettaglio, ci basta notare come i più comuni algoritmi di crittografia asimmetrica – quali RSA, ElGamal ed ECDSA – garantiscono la loro sicurezza. Essi sfruttano il fatto che, per un computer tradizionale, è facile moltiplicare tra di loro due quantità ottenendo un risultato, mentre risulta arduo estrarre gli elementi ignoti che sono stati moltiplicati tra di loro per avere tale risultato. Gli algoritmi della crittografia asimmetrica, infatti, devono essere basati su questa dualità, sull’esistenza di un calcolo semplice da svolgere in una direzione ma difficile da svolgere nella direzione opposta (a meno che non si conosca qualche dettaglio aggiuntivo).
Ebbene, nel contesto di computer quantistici, è stato già ideato il cosiddetto algoritmo di Shor, che è in grado di risolvere in tempo utile proprio il problema di estrarre gli elementi moltiplicati tra loro. Ecco perché la situazione è così critica. A poco serve che RSA consideri interi, che ElGamal lavori con campi finiti e che ECDSA usi curve ellittiche. Questo algoritmo quantistico intacca l’estrazione degli elementi di una moltiplicazione a prescindere dal luogo matematico sfruttato.
L’algoritmo di Shor è tuttora teorico e non è ancora stato implementato su larga scala. Ma i crittografi di tutto il mondo stanno già reagendo alla possibilità dell’esistenza di una banalizzazione del problema principale attraverso il quale sono resi sicuri gli algoritmi di crittografia asimmetrica. Aggiornare gli attuali sistemi di crittografia richiederà tempo, ed è dunque necessario giocare di anticipo. Bisogna ideare e standardizzare presto nuovi algoritmi di crittografia asimmetrica che, almeno in teoria, possono resistere ad ogni attacco finora conosciuto lanciabile sia da computer tradizionali sia da quelli quantistici.
I processi di standardizzazione del NIST per la crittografia post quantistica
L’istituto statunitense NIST (National Institute of Standard and Technology) spicca sicuramente tra i vari enti che hanno sottolineato la necessità di standardizzare nuovi algoritmi crittografici in grado di resistere agli algoritmi quantistici finora conosciuti. Il NIST si occupa di rilasciare linee guida e standard che devono essere seguiti attentamente da ogni ente governativo USA che tratta dati sensibili. Chiaramente, gli standard rilasciati dal NIST sono presi molto in considerazione anche nelle altre parti del mondo, perché i file provenienti dall’istituto, grazie anche alla loro selezione pubblica e trasparente, sono ottime referenze per un utilizzo generale, per rendere inter-operabili i sistemi informatici e per generare altri standard nazionali o internazionali.
Gli studiosi e i programmatori porgono particolare attenzione sul fatto che il processo di selezione di nuovi algoritmi non sia privato. Infatti, la storia mostra che algoritmi prodotti in segretezza, o con un design tenuto segreto, o senza ascoltare opinioni pubbliche (come gli algoritmi GOST, DES e RC4) sono risultati deboli e sono stati deprecati (ovvero, il loro uso è sconsigliato e sono considerati non sicuri). Ad oggi, si applica il più possibile il cosiddetto principio di Kerckhoffs, che afferma quanto segue: la sicurezza di un algoritmo crittografico deve dipendere dalla scelta e dalla segretezza della chiave, mentre ogni altro aspetto dell’algoritmo deve essere dominio pubblico.
Il processo di standardizzazione per la crittografia post quantistica aperto dal NIST nel 2016 ha riscosso molto successo e interesse. L’obiettivo di tale processo è stato quello di selezionare algoritmi crittografici asimmetrici resistenti ad attacchi quantistici. All’inizio, 82 algoritmi sono stati canditati e sottomessi allo scrutinio del NIST e della comunità crittografica mondiale. Dopo vari anni di analisi, raffinamento, studio, scoperta di attacchi su alcuni algoritmi proposti e round di selezione sempre più esclusivi, siamo ora giunti di fronte a 4 algoritmi vincitori. Tre di essi sono già diventati standard nell’agosto del 2024 (ML-KEM del FIPS 203, ML-DSA del FIPS 204 e SLH-DSA del FIPS 205), mentre il quarto (Falcon) è un algoritmo di firma digitale che sarà presto rilasciato all’interno di uno standard. Per analizzare al meglio quest’ultimo algoritmo, però, ci servono due concetti informatici su cui vale spendere alcune parole a riguardo, visto la loro importanza in generale a prescindere dal loro uso in Falcon: le funzioni di hash e i cosiddetti numeri in virgola mobile.
Le funzioni crittografiche di hash
Dato un messaggio di lunghezza qualsiasi in entrata, una funzione di hash produce in uscita un risultato (detto digest) di una certa lunghezza stabilita. Tale lunghezza può essere sempre uguale (come nel caso delle varianti di SHA3) oppure può essere impostata a un valore idoneo (queste funzioni di hash prendono il nome di eXtendable Output Function, in acronimo XOF). Si richiedono queste tre proprietà per avere una funzione crittografica di hash: dato un certo digest, deve essere arduo risalire a un messaggio in entrata che possa generare tale digest (la cosiddetta resistenza alla preimmagine); dato un certo messaggio in entrata, deve essere arduo trovare un secondo messaggio distinto dal primo tale che i loro digest coincidano (la cosiddetta resistenza alla preimmagine secondaria); dati due messaggi distinti, deve essere difficile che i loro digest coincidano (la cosiddetta resistenza alle collisioni). Per ottenere quest’ultima proprietà, tipicamente il digest dipende strettamente dal messaggio in entrata e cambia in modo imprevedibile anche se si cambia una virgola nel messaggio in entrata.
Grazie alle proprietà elencate sopra, le funzioni crittografiche di hash sono usate in maniera efficace e sicura in alcuni algoritmi di firme digitali e, in generale, in ogni algoritmo che richiede autenticazione (ovvero, in ogni algoritmo che richiede di confermare la verità di un’informazione sostenuta vera da qualche entità).
Numeri in virgola mobile
Il motivo principale per cui i computer sono stati costruiti è quello di aiutare noi umani a svolgere calcoli. Questo, in particolare, implica che un computer deve aver modo sia di conservare al suo interno tutti i numeri o valori necessari per il calcolo, sia di svolgere tutte le operazioni necessarie considerando un insieme di questi valori. In particolare, interessiamoci su come un computer riesca a conservare numeri al suo interno.
Scendendo a fondo nel cuore di un computer, si realizza presto che esso lavora esclusivamente utilizzando una sequenza fatta di numerosi bit, dove un bit può avere solo o un valore zero o un valore uno. Un numero intero è facilmente scrivibile come sequenza di bits, a patto di usare una sequenza sufficientemente lunga e a patto di scrivere tale numero in base 2 (con solo due possibili cifre, ovvero 0 e 1, al contrario della nostra tipica base 10, con le cifre dallo 0 al 9 che usiamo ogni giorno).
Ma a scuola abbiamo imparato che non esistono solo numeri interi. Infatti, esistono anche i numeri con la virgola, e spesso essi permettono di svolgere calcoli altrimenti non risolvibili usando semplici numeri interi. La domanda, dunque, sorge spontanea: come possiamo convertire un numero con una virgola in una sequenza di bit?
Una risposta a cui sono giunti i programmatori è la seguente. Fissiamo una certa lunghezza della sequenza di bit in cui vogliamo salvare un certo numero intero, e stabiliamo in maniera precisa quali di questi bit indicano la parte prima della virgola, e quale quella dopo. Questa rappresentazione di un numero con la virgola è detta numero in virgola fissa (in inglese, fixed-point number).
I numeri in virgola fissa sono ancora usati in specifiche circostanze, ma hanno la caratteristica di rappresentare solo una piccola fetta della nostra idea scolastica di numeri con la virgola. Risulta impossibile salvare un numero così grande che non rientra all’interno dei bit che abbiamo stabilito come quelli prima della virgola, e similmente abbiamo problemi a salvare numeri talmente piccoli da non poter essere scritti all’interno dei bit designati a cifre dopo la virgola.
Nei casi in cui un computer debba lavorare con numeri sia molto piccoli che molto grandi (o comunque dove non sappiamo se i numeri che salveremo rientreranno dentro limiti ben stabiliti) si preferisce usare la rappresentazione detta numero in virgola mobile. Come si può intendere dal nome, questa rappresentazione è in grado di spostare la virgola in un luogo più idoneo, permettendoci così di rappresentare così un intervallo di numeri più grande. La sequenza finita di bit che rappresenta un numero in virgola mobile ha specifici bit dedicati a rappresentare un esponente e altri bit dedicati a rappresentare la mantissa. Nella mantissa viene specificato un numero con la virgola compreso tra 1 e 2, mentre l’esponente serve a specificare di quanto spostare la virgola. Tecnicamente parlando, quando usati nelle operazioni, questi numeri in virgola mobile potrebbero essere leggermente meno accurati nell’approssimare il risultato rispetto a numeri in virgola fissa, ma è possibile lavorare intorno a questa perdita di accuratezza nelle implementazioni, e in pratica sono molto più largamente utilizzati numeri in virgola mobile rispetto a quelli in virgola fissa.
L‘algoritmo Falcon
Falcon è il quarto algoritmo ad essere stato selezionato vincitore dal NIST nel 2022 alla conclusione del processo di standardizzazione pubblico della PQC. Ci si aspetta che, a breve, rientrerà all’interno del documento FIPS 206 con il nome di FN-DSA.
Falcon è un algoritmo di firma digitale. Il problema matematico che utilizza per garantire la sua sicurezza in italiano si traduce come “problema della soluzione intera corta su reticoli”. Certo, questo nome potrebbe quasi sembrare uno scioglilingua, ma possiamo comunque sorvolare alcuni dettagli tecnici soffermandoci solo sull’ottenere un’idea ad alto livello di come Falcon funziona.
Falcon consiste di tre fasi principali. La prima è chiamata generazione di chiavi. Queste chiavi sono distinte da quella chiave che era stata scambiata tra noi e il consulente bancario nell’esempio precedente. Quella singola chiave, infatti, in gergo viene spesso chiamata “chiave simmetrica”, visto che è utilizzata dentro algoritmi di crittografia simmetrica.
La generazione di chiavi di Falcon, invece, genera una chiave privata e una chiave pubblica. La chiave privata è una sequenza di bit così chiamata perché l’entità che la genera deve proteggerla e tenerla nascosta da altre entità. Nell’esempio precedente, l’app di messagistica bancaria tiene la chiave privata dentro il dispositivo del consulente da cui parte il messaggio.
La chiave pubblica, d’altro canto, è una sequenza di bit che non solo può essere letta da qualsiasi entità esterna (visto che la correlazione tra chiave privata e chiave pubblica rende impossibile indovinare quella privata conoscendo solo quella pubblica), ma deve anche essere recapitata a chiunque debba verificare la firma.
Chiavi private e chiavi pubbliche sono comunemente utilizzate nella crittografia asimmetrica, e Falcon è l’algoritmo di firma post quantum che risulta sicuro offrendo lunghezze soddisfacentemente piccole per queste due chiavi.
Fasi dell’algoritmo Falcon
In Falcon, i numeri in virgola mobile sono brevemente usati per assicurare una generazione sicura e sufficientemente casuale di chiavi, ma compaiono in una maniera molto più prorompente nella seconda fase dell’algoritmo: la generazione della firma. Per generare la firma, Falcon inizia trovando una prima soluzione a un problema matematico. Questa soluzione consiste in una serie di valori interi che, moltiplicati per la chiave pubblica, producono il digest del messaggio da firmare, computato usando una funzione di hash. A questo punto, usando numerosi numeri in virgola mobile, la prima soluzione e la chiave privata, Falcon scova per lo stesso problema una seconda soluzione composta di soli valori interi molto piccoli. Questa seconda soluzione è la firma del messaggio.
La terza e ultima fase di Falcon è quella della verifica. Essa è eseguita da chi riceve il messaggio firmato e consiste nel controllare sia che la firma-soluzione è composta di piccoli numeri, sia che la firma moltiplicata per la chiave pubblica coincida con il digest del messaggio.
Conclusioni e prospettive future
L’avvento della crittografia post quantistica e algoritmi come quello di Shor minacciano la sicurezza degli attuali algoritmi di firma digitale e di scambio di chiave. Attualmente, i computer quantistici esistenti non hanno ancora potenza computazionale sufficiente per essere considerati pericolosi, e sono molto costosi da produrre. Ma tali computer sono in costante evoluzione, e nell’ultima manciata di anni abbiamo assistito a un costante progresso verso la creazione di computer quantistici per consumatori.
Se un computer quantistico di larga scala verrà effettivamente venduto, non avremo più garanzie di sicurezza per gli algoritmi di crittografia asimmetrica comunemente utilizzati. Ricordando che una sostituzione su vasta scala degli algoritmi crittografici richiede sempre molto tempo, bisogna prepararsi adeguatamente all’arrivo di questa nuova tipologia di computer iniziando a modificare i sistemi esistenti già da ora.
Con Falcon e gli altri algoritmi vincitori, il NIST offre le prime soluzioni standardizzate di algoritmi alternativi a quelli odierni e resistenti agli attacchi quantistici trovati finora. Questo segna sicuramente un passo nella direzione giusta per essere adeguatamente preparati all’era tecnologica quantistica. Questi standard porteranno molte compagnie ad iniziare la transizione agli algoritmi post quantistici. Ad esempio, Google sta già iniziando ad implementare e testare in pratica gli standard PQC del NIST nel suo famoso browser Chrome.
Certo, stiamo osservando ancora gli albori di una totale transizione ad algoritmi crittografici resistenti ad attacchi eseguibili su computer quantistici. A dir la verità, il NIST tiene ancora aperta una competizione riguardo ad algoritmi post quantistici. Infatti, gli algoritmi selezionati finora, per quanti sicuri e scrutinati a fondo dalla comunità crittografica, hanno alcuni difetti.
Sono lenti, si basano quasi tutti su un solo luogo matematico (quello dei reticoli modulari) relativamente complicato da studiare ed analizzare, e sono meno efficienti rispetto agli algoritmi moderni anche dal punto di vista di spazio di archiviazione utilizzato (la dimensioni delle chiavi private e delle firme coincide circa con quella di un breve messaggio vocale). Per questo motivo, il NIST e la comunità scientifica non sono ancora completamente soddisfatti, e stanno ancora scrutinando sia un quarto round di algoritmi di scambio di chiave che non si basano su reticoli modulari, sia un nuovo insieme di algoritmi di firma digitale.
