Crittografia post-quantistica con Python e Linux

Crittografia con Python e Linux

Guida per principianti

Se crediamo a Edward Snowden, la crittografia è “l’unica vera protezione contro la sorveglianza” [1]. Tuttavia, i progressi nella tecnologia quantistica potrebbero mettere a rischio questa sicurezza. Nel nostro articolo discutiamo perché la computazione quantistica rappresenta una minaccia per la sicurezza dei dati e cosa fare al riguardo. Invece di un’analisi puramente teorica, ci basiamo su esempi di codice con l’uso di Python, C e Linux.

Fondamenti della fisica quantistica

Quando gli scienziati di Google hanno riportato il primo caso di supremazia quantistica nel 2019, hanno suscitato grande entusiasmo. Una delle aree in cui la computazione quantistica potrebbe avere un impatto significativo è la crittografia. Per capire questo problema, dobbiamo discutere alcuni concetti di base.

A differenza dei computer classici, gli algoritmi per i computer quantistici non si basano sui bit, ma sui qubit. Un bit può assumere lo stato 0 o 1. Quando misuriamo un bit più volte, otteniamo sempre lo stesso risultato. Con i qubit, le cose sono diverse. Per quanto strano possa sembrare, un qubit può assumere contemporaneamente il valore 0 e 1. Quando lo misuriamo ripetutamente, c’è solo una certa probabilità di ottenere il risultato 0 o 1. Nello stato iniziale di un qubit, la probabilità di misurare 0 è comunemente del cento percento. Attraverso la sovrapposizione, tuttavia, possono essere generate diverse distribuzioni di probabilità. Le cause risiedono nella meccanica quantistica, che segue leggi diverse dalla “normale” vita quotidiana.

Il principale vantaggio dei computer quantistici è la loro natura probabilistica. I computer classici eccellono nei problemi in cui abbiamo bisogno in modo affidabile di un singolo risultato. Le macchine quantistiche, d’altra parte, sono eccellenti nel trattare con probabilità e combinatoria. Quando eseguiamo un’operazione su un qubit in uno stato sovrapposto, viene applicata contemporaneamente a entrambi i valori 0 e 1. Man mano che il numero di qubit aumenta, aumenta anche il vantaggio rispetto a un computer classico. Una macchina quantistica con tre qubit può elaborare fino a otto valori (2³) contemporaneamente: ovvero i numeri binari 000, 001, 010, 011, 100, 101, 110 e 111.

• Le complessità dell’implementazione della risoluzione delle entità
• I ricercatori di DeepMind presentano AlphaStar Unplugged un balzo in avanti nell’apprendimento con rinforzo offline su larga scala, padroneggiando il gioco di strategia in tempo reale StarCraft II.
• L’IA generativa rivoluziona la nuova era nell’industria automobilistica, dalla progettazione e ingegneria alla produzione e vendite

La letteratura scientifica concorda sul fatto che i computer quantistici aiuteranno a risolvere problemi che in passato sembravano irrisolvibili. Tuttavia, non esistono ancora macchine quantistiche ottimali. La generazione attuale di computer quantistici è definita noisy intermediate-scale quantum (NISQ). Queste macchine hanno una potenza di elaborazione limitata e sono sensibili agli errori. I dispositivi moderni offrono fino a diverse centinaia di qubit. Un esempio è il chip Osprey da 433 qubit introdotto da IBM nel 2022. Ora, l’azienda ha pianificato di sviluppare una macchina con 100.000 qubit entro il 2033.

Il nostro articolo spiega perché questa evoluzione rappresenta una minaccia per la sicurezza dei dati. Utilizzando esempi di codice, mostriamo perché i computer quantistici potrebbero violare determinate forme di crittografia e discutiamo soluzioni alternative. Il codice sorgente è disponibile su GitHub. È stato sviluppato su Kali Linux 2023.2 utilizzando Anaconda con Python 3.10.

Crittografia e fattori primi

Quando si cripta un messaggio, un modo relativamente semplice è applicare un algoritmo simmetrico. Questo metodo utilizza la stessa chiave sia per la crittografia del testo in chiaro che per la decrittografia del testo cifrato. Una sfida principale con questo approccio è lo scambio sicuro della chiave tra mittente e destinatario. Una volta che la chiave privata diventa nota a una terza parte, questa ha la possibilità di intercettare e decrittare il messaggio.

La crittografia asimmetrica sembrava essere la soluzione a questo problema. Metodi come RSA utilizzano chiavi diverse per la crittografia e la decrittografia. Qui la crittografia viene eseguita con una o più chiavi pubbliche che il destinatario mette a disposizione di tutti. Per la decrittografia, il destinatario utilizza una chiave privata, che è nota solo a lui. In questo modo, il mittente può ottenere la chiave pubblica senza rischi, poiché non è segreta in ogni caso. Solo la chiave privata del destinatario deve essere protetta. Ma come può essere resa più sicura una procedura del genere, quando potenziali attaccanti conoscono la chiave pubblica? A questo scopo, gli algoritmi asimmetrici si basano su problemi matematici come la fattorizzazione in numeri primi.

La fattorizzazione in numeri primi è meglio compresa attraverso un esempio. In Python, possiamo utilizzare la funzione factorint della libreria SymPy per determinare i fattori primi di un certo numero intero.

>>> import sympy>>> sympy.factorint(10){2: 1, 5: 1}>>> 2**1 * 5**110>>> sympy.factorint(1000){2: 3, 5: 3}>>> 2**3 * 5**31000>>> sympy.factorint(55557){3: 2, 6173: 1}>>> 3**2 * 6173**155557>>>

La console di output sopra illustra che ogni numero naturale può essere espresso come prodotto di numeri primi. Questi sono chiamati fattori primi. Ripensando ai giorni della scuola, un numero primo è divisibile solo per 1 e per se stesso. Ad esempio, il numero 10 può essere espresso dal termine 10=2¹ * 5¹. Quindi, i fattori primi di 10 sono 2 e 5. Analogamente, il numero 55557 può essere espresso dall’equazione 55557=3² * 6173¹. Quindi, i fattori primi di 55557 sono 3 e 6173. Il processo di trovare i fattori primi di un dato numero intero è chiamato fattorizzazione primaria.

Con i computer classici, la fattorizzazione primaria è semplice per numeri piccoli, ma diventa sempre più difficile per grandi numeri interi. Ogni numero aggiuntivo aumenta drasticamente la somma delle possibili combinazioni. Oltre un certo punto, diventa praticamente impossibile per un computer classico determinare i fattori primi. Ad esempio, consideriamo il seguente numero (RSA-260) dalla RSA Factoring Challenge, terminata nel 2007. Al momento della scrittura, non è ancora stato fattorizzato.

#!/usr/bin/env pythonimport sympyrsa_260 = 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199print("Inizio fattorizzazione...")fattori = sympy.factorint(rsa_260)# Probabilmente non verrà raggiuntoprint(fattori)

Gli algoritmi asimmetrici come RSA utilizzano la difficoltà computazionale della fattorizzazione primaria e problemi simili per garantire la crittografia. Purtroppo, il mondo quantistico segue le sue leggi.

Algoritmi quantistici

Riguardo alla crittografia, due algoritmi quantistici sono di particolare preoccupazione. L’algoritmo di Shor offre un modo efficiente di fattorizzazione primaria. Quando eseguito su un grande dispositivo quantistico, può teoricamente rompere metodi asimmetrici come RSA. Dal punto di vista pratico, questo scenario si trova nel futuro. Un articolo di Nature del 2023 menziona il numero di almeno 1.000.000 qubit richiesti. Oltre all’hardware, è anche difficile trovare implementazioni dell’algoritmo che si scalino in modo affidabile su grandi macchine quantistiche. Il framework Qiskit di IBM aveva cercato di implementare una funzione, ma l’ha deprecata con la versione 0.22.0. Tuttavia, implementazioni sperimentali dell’algoritmo di Shor possono essere trovate online.

L’algoritmo di Grover rappresenta una minaccia per la crittografia simmetrica. Conosciuto anche come algoritmo di ricerca quantistica, offre un’accelerazione per la ricerca non strutturata dell’input per una funzione data. I computer quantistici possono usarlo per accelerare gli attacchi a forza bruta alle informazioni crittografate simmetricamente. Tuttavia, a differenza dell’algoritmo di Shor, l’accelerazione offerta non è esponenziale. In termini semplici, ciò significa che aumentando la lunghezza della chiave utilizzata per la crittografia, la ricerca diventa eccessivamente più costosa. Ad esempio, eseguendo un attacco a forza bruta su una chiave di 128 bit richiede un massimo di 2¹²⁸ iterazioni. Supponendo che la ricerca di Grover riduca questo numero a 2⁶⁴, raddoppiando la lunghezza della chiave a 256 bit, il numero torna a essere di 2¹²⁸ iterazioni. Questo apre la possibilità di possibili soluzioni alternative.

Soluzione alternativa simmetrica

In determinate condizioni, la crittografia simmetrica è un modo semplice e pronto all’uso per contrastare gli algoritmi quantistici. Il motivo è che la ricerca di Grover non scala in modo esponenziale e l’algoritmo di Shor minaccia solo gli approcci asimmetrici. Secondo le conoscenze attuali, gli algoritmi simmetrici con un alto grado di difficoltà possono essere considerati resistenti ai quanti. Attualmente, sia l’NIST americano che il BSI tedesco includono AES-256 in questa categoria [2][3]. L’acronimo AES sta per Advanced Encryption Standard e il numero 256 rappresenta la lunghezza in bit della chiave. In Linux, AES-256 è implementato da GNU Privacy Guard (GnuPG). Lo script shell seguente mostra come un file può essere crittografato e quindi decrittografato utilizzando AES-256.

# Crittografaziogpg --output encrypted.gpg --symmetric --cipher-algo AES256 plain.txt# Decrittografaziogpg --output decrypted.txt --decrypt encrypted.gpg

Lo script sopra crittografa il contenuto del file “plain.txt”, scrive il testo cifrato nel documento “encrypted.gpg”, lo decrittografa nuovamente e infine salva l’output nel file “decrypted.txt”. Prima della crittografia, GnuPG richiede una passphrase per generare la chiave privata. Per motivi di sicurezza, è fondamentale scegliere una passphrase robusta e mantenerla segreta. GnuPG potrebbe memorizzare la passphrase e non richiederla nuovamente durante la decrittografia. Per cancellare la cache, è possibile eseguire il seguente comando shell.

gpg-connect-agent reloadagent /bye

L’integrazione di GnuPG in Python è relativamente semplice con il modulo subprocess. Un’implementazione prototipo della crittografia con AES-256 è mostrata nel frammento di codice qui sotto.

#!/usr/bin/env pythonimport subprocessimport getpass# Leggi la passphrasepassphrase = getpass.getpass("Passphrase:")passphrase2 = getpass.getpass("Passphrase:")if passphrase != passphrase2:  raise ValueError("Passphrase non identiche!")# Esegui la crittografiazionestampa("Crittografia...")args = [  "gpg",  "--batch",  "--passphrase-fd", "0",  "--output", "encrypted.gpg",  "--symmetric",  "--yes",  "--cipher-algo", "AES256",  "plain.txt",]result = subprocess.run(  args, input=passphrase.encode(),  capture_output=True)if result.returncode != 0:  raise ValueError(result.stderr)

Per ottenere una passphrase, lo script sopra utilizza il modulo getpass. Dopo la conferma, la passphrase viene trasferita a GnuPG tramite l’input standard. Ciò è indicato dall’argomento passphrase-fd 0. In alternativa, le passphrase possono essere inviate a GnuPG come stringa o tramite file con argomenti della riga di comando. Tuttavia, poiché questi argomenti sono visibili ad altri utenti, entrambe le opzioni sono state respinte per il prototipo. Un altro modo più sicuro sarebbe quello di utilizzare GPG-Agent. Quale opzione scegliere dipende dal livello di sicurezza desiderato. Qui viene fornita una prova di concetto che include la crittografia e la decrittografia. Come alternativa a GnuPG, esistono altre implementazioni di AES-256. È fondamentale scegliere una fonte affidabile.

Soluzione asimmetrica

Nella ricerca di una soluzione asimmetrica, il programma di standardizzazione della crittografia post-quantistica del NIST è un buon punto di partenza. Dal 2016, ha valutato diverse soluzioni per algoritmi resistenti ai calcolatori quantistici. Uno dei vincitori è Kyber. Il sistema implementa un meccanismo di incapsulamento chiave sicuro. Come altri algoritmi, Kyber si basa su un problema difficile da risolvere per proteggere lo scambio di chiavi tra due parti. Invece della fattorizzazione dei numeri primi, si basa su un problema chiamato “apprendimento con errori”. Il livello di protezione offerto da Kyber dipende dalla lunghezza della chiave. Ad esempio, Kyber-1024 mira a un livello di sicurezza “approssimativamente equivalente ad AES-256” [4].

Un’implementazione di riferimento di Kyber, scritta in C, è disponibile su GitHub. In Linux, possiamo clonare e compilare il framework eseguendo i comandi di shell qui sotto. L’installazione richiede alcuni prerequisiti, che sono documentati nel README del progetto.

git clone https://github.com/pq-crystals/kyber.gitcd kyber/ref && make

Esistono diversi modi per integrare l’implementazione di riferimento in Python. Uno di questi è scrivere un programma in C e chiamarlo. La funzione C qui sotto utilizza Kyber per eseguire uno scambio di chiavi tra due parti fittizie, Alice e Bob. Per il codice sorgente completo, vedere qui.

#include <stddef.h>#include <stdio.h>#include <string.h>#include "kem.h"#include "randombytes.h"void round_trip(void) {    uint8_t pk[CRYPTO_PUBLICKEYBYTES];    uint8_t sk[CRYPTO_SECRETKEYBYTES];    uint8_t ct[CRYPTO_CIPHERTEXTBYTES];    uint8_t key_a[CRYPTO_BYTES];    uint8_t key_b[CRYPTO_BYTES];    //Alice genera una chiave pubblica    crypto_kem_keypair(pk, sk);    print_key("Chiave pubblica di Alice", pk);    //Bob deriva una chiave segreta e crea una risposta    crypto_kem_enc(ct, key_b, pk);    print_key("Chiave condivisa di Bob", key_b);    print_key("Chiave di risposta di Bob", ct);    //Alice usa la risposta di Bob per ottenere la sua chiave condivisa    crypto_kem_dec(key_a, ct, sk);    print_key("Chiave condivisa di Alice", key_a);}

Senza entrare nei dettagli, si può notare che Kyber utilizza più chiavi pubbliche e private. Nell’esempio sopra, Alice genera una chiave pubblica (pk) e una chiave privata (sk). Successivamente, Bob utilizza la chiave pubblica (pk) per derivare una chiave condivisa (key_b) e una chiave di risposta (ct). Quest’ultima viene restituita ad Alice. Infine, Alice utilizza la chiave di risposta (ct) e la sua chiave privata (sk) per generare un’istanza della chiave condivisa (key_a). Finché entrambe le parti mantengono segrete le loro chiavi private e condivise, l’algoritmo offre protezione. Quando si esegue il programma, si ottiene un output simile al testo qui sotto.

Chiave pubblica di Alice: F0476B9B5867DD226588..Chiave condivisa di Bob: ADC41F30B665B1487A51..Chiave di risposta di Bob: 9329C7951AF80028F42E..Chiave condivisa di Alice: ADC41F30B665B1487A51..

Per chiamare la funzione C in Python, possiamo utilizzare il modulo subprocess. In alternativa, è possibile creare una libreria condivisa e invocarla con il modulo ctypes. La seconda opzione è implementata nello script Python di seguito. Dopo aver caricato la libreria condivisa, generata dal codice C di Kyber, la procedura round_trip viene chiamata come qualsiasi altra funzione Python.

#!/usr/bin/env pythonimport osimport ctypes# Carica la libreria condivisalibname = f"{os.getcwd()}/execute_round_trip1024.so"clib = ctypes.CDLL(libname, mode=1)print("Libreria condivisa caricata con successo:")print(clib)# Chiama la funzione round_tripprint("Esecuzione del round trip:")clib.round_trip()

Oltre all’implementazione di riferimento di Kyber, altri fornitori hanno implementato l’algoritmo. Esempi sono i progetti open-source Botan e Open Quantum Safe.

Conclusioni

Come la nostra analisi rivela, la tecnologia quantistica è ancora nelle prime fasi. Ma non dovremmo sottovalutare la minaccia che essa rappresenta per la crittografia e altri metodi crittografici come le firme. L’innovazione disruptiva può accelerare lo sviluppo in qualsiasi momento. Gli attaccanti possono archiviare i messaggi ora e decifrarli in seguito. Pertanto, è necessario adottare misure di sicurezza immediatamente. Soprattutto perché ci sono soluzioni alternative disponibili. Quando utilizzati correttamente, gli algoritmi simmetrici come AES-256 sono considerati resistenti alla crittografia quantistica. Inoltre, le soluzioni asimmetriche come Kyber stanno progredendo. Quali alternative utilizzare dipende dall’applicazione. Seguendo un modello di Zero Trust, una combinazione di approcci offre la migliore protezione. In questo modo, la minaccia quantistica potrebbe finire come il problema Y2K – come una profezia autodistruttiva.

Informazioni sugli autori

Christian Koch è un Enterprise Architect presso BWI GmbH e docente presso l’Istituto di Tecnologia Georg Simon Ohm di Norimberga.

Lucie Kogelheide è la responsabile della tecnologia per la crittografia post-quantistica presso BWI GmbH e responsabile dell’avvio del processo di migrazione dell’azienda verso la crittografia sicura quantistica.

Raphael Lorenz è il fondatore e CISO di Lorenz Systems e si specializza in soluzioni di sicurezza olistiche.

Riferimenti

1. Snowden, Edward: Permanent Record. Macmillan, 2019.
2. Istituto Nazionale di Standard e Tecnologia: Crittografia post-quantistica NIST: FAQS. 29 giugno 2023. Accesso: 02 agosto 2023.
3. Ufficio Federale per la Sicurezza delle Informazioni (BSI): Crittografia sicura quantistica – fondamenti, sviluppi attuali e raccomandazioni (PDF). Ottobre 2021. Accesso: 02 agosto 2023.
4. CRYSTALS – Suite crittografica per reticoli algebrici: Kyber Home. Dicembre 2020. Accesso: 02 agosto 2023.

Disclaimer

Si prega di notare che la sicurezza delle informazioni è un argomento critico e che gli autori non forniscono alcuna garanzia per i contenuti pubblicati.