Crittografia a chiave asimmetrica

In questa lezione esamineremo la crittografia a chiave asimmetrica, che costituisce la base di molte interazioni di rete sicure oggi.

Alla fine della lezione avremo trattato:

• Cos'è la crittografia a chiave asimmetrica
• L'utilizzo della crittografia a chiave asimmetrica, inclusi scambio di chiavi e firme digitali
• La sicurezza della crittografia a chiave asimmetrica in generale
• Ulteriori dettagli sugli algoritmi RSA, DSA ed Elliptic Curves e sulla loro sicurezza
• Alcuni esempi di codice Python che mostrano come funzionano gli algoritmi in pratica
• Le minacce a questi algoritmi provenienti sia da computer classici che quantistici

Introduzione alla crittografia a chiave asimmetrica

Come abbiamo imparato nell'ultima lezione, la crittografia a chiave simmetrica è molto veloce ed efficiente per proteggere le informazioni, ma presenta alcune limitazioni:

1. All'aumentare del numero di parti che desiderano scambiarsi informazioni sicure, il numero di chiavi necessarie cresce in modo combinatorio. Non fornisce alcun meccanismo per distribuire in modo sicuro queste chiavi tra mittenti e destinatari.
2. Non è prevista la non-repudiabilità. Qualsiasi parte è in grado di decifrare o cifrare messaggi senza alcun modo per garantire che un messaggio sia stato ricevuto o da dove provenga.

La soluzione a entrambi questi problemi è fornita dalla crittografia a chiave asimmetrica (AKC), nota anche come crittografia a chiave pubblica (PKC), che costituisce quindi un pilastro della sicurezza digitale moderna.

La crittografia a chiave asimmetrica (AKC) prevede l'uso di una coppia di chiavi — una pubblica, una privata. Le chiavi pubblica e privata sono collegate crittograficamente e tipicamente generate nello stesso momento come coppia di chiavi utilizzando un algoritmo matematico specializzato. La chiave pubblica, come suggerisce il nome, è destinata a essere distribuita liberamente, mentre la chiave privata è tenuta segreta dalla parte che genera la coppia di chiavi. La sicurezza delle comunicazioni che impiegano coppie di chiavi asimmetriche è garantita fintanto che la chiave privata rimane riservata.

Figura 1. Cifratura con chiave asimmetrica

L'AKC offre diverse funzioni utili, come:

1. Cifratura e decifratura per garantire la riservatezza delle comunicazioni.
2. Firme digitali per garantire autenticità, integrità e non-repudiabilità.
3. Scambio di chiavi sicuro per facilitare l'uso successivo di crittosistemi simmetrici.

Nelle applicazioni moderne, l'AKC viene utilizzata principalmente per firme digitali e scambio sicuro di chiavi. In questa lezione, introduciamo queste due funzioni chiave, e poi discutiamo diverse varianti di protocolli crittografici per tali funzioni.

Scambio di chiavi con crittografia a chiave asimmetrica

Uno dei problemi fondamentali della crittografia è lo scambio di chiavi in modo sicuro. Ad esempio, se due parti vogliono utilizzare la cifratura simmetrica, entrambe devono avere la stessa chiave per cifrare e decifrare i messaggi. Ma come si scambiano la chiave in modo sicuro? La crittografia a chiave asimmetrica affronta questo problema attraverso meccanismi di scambio di chiavi interattivi e non interattivi.

Scambio di chiavi interattivo

Un protocollo di scambio di chiavi interattivo si riferisce a un metodo in cui due parti collaborano per creare una chiave segreta condivisa su un canale di comunicazione non sicuro. Questa chiave segreta condivisa può poi essere utilizzata per compiti di cifratura e decifratura simmetrica.

Il più noto tra tali protocolli è l'algoritmo Diffie-Hellman (DH), ideato specificamente per facilitare lo scambio di chiavi. In questo protocollo, ogni parte genera una coppia di chiavi (pubblica e privata) e trasmette la propria chiave pubblica. Poi ciascuna parte usa la propria chiave privata e la chiave pubblica dell'altra parte per generare una chiave segreta condivisa. Il DH utilizza i principi dell'aritmetica modulare per garantire che entrambe le parti arrivino alla stessa chiave segreta condivisa anche se ciascuna ha accesso solo alla chiave pubblica dell'altra.

I crittosistemi moderni basati sulla crittografia su curve ellittiche (ECC) estendono questo concetto con lo scambio di chiavi Diffie-Hellman su curve ellittiche (ECDH). L'ECDH funziona in modo simile al DH ma utilizza le proprietà delle curve ellittiche, risultando in un sistema più sicuro ed efficiente.

Figura 2. Protocollo di scambio di chiavi

Scambio di chiavi non interattivo

A differenza dei protocolli di scambio di chiavi come DH e ECDH, che sono interattivi e richiedono comunicazione bidirezionale per stabilire la chiave simmetrica, l'AKC prevede anche modalità non interattive per stabilire una chiave segreta condivisa. In tali schemi, una parte genera una coppia di chiavi (pubblica e privata) e condivide la chiave pubblica con l'altra parte. Questa seconda parte genera quindi una chiave simmetrica casuale, la cifra con la chiave pubblica ricevuta e la rimanda alla prima parte. La prima parte utilizza la propria chiave privata per decifrare il messaggio ricevuto, ottenendo così la chiave simmetrica condivisa. Questo schema è non interattivo nel senso che la chiave simmetrica è determinata da una sola parte e semplicemente comunicata in modo sicuro all'altra parte in forma cifrata.

Una considerazione importante nello scambio di chiavi non interattivo riguarda la differenza di lunghezza in bit tra la chiave simmetrica che le parti desiderano scambiare e le dimensioni dei messaggi raccomandate nell'AKC. Tipicamente, le chiavi simmetriche moderne hanno una lunghezza compresa tra 128 e 256 bit, mentre i crittosistemi a chiave asimmetrica come RSA lavorano con dimensioni dei messaggi intorno a 1024-4096 bit. Pertanto, quando si utilizza l'AKC per trasmettere una chiave simmetrica, per sicurezza essa deve comunque essere codificata in un messaggio più lungo di 1024-4096 bit. Questo può essere ottenuto tramite due approcci:

• Scambio di chiavi basato su padding: In questo approccio, la chiave simmetrica più corta (128-256 bit) viene generata per prima e poi uno schema di padding reversibile concordato come OAEP viene utilizzato per incorporarla in un messaggio più lungo (1024-4096 bit). Questo messaggio più lungo viene cifrato tramite AKC e trasmesso come testo cifrato. Il destinatario prima decifra il testo cifrato e poi rimuove il padding per estrarre la chiave simmetrica più corta.

• Meccanismi di incapsulamento delle chiavi (KEM): Con lo scambio di chiavi basato su KEM, viene prima generato un messaggio in chiaro casuale e lungo (1024-4096 bit), dal quale è possibile estrarre una chiave simmetrica più corta (128-256 bit) utilizzando una funzione di derivazione delle chiavi (KDF) concordata. Il testo in chiaro più lungo viene cifrato tramite AKC e trasmesso al destinatario come testo cifrato. Il destinatario decodifica il testo cifrato usando la propria chiave privata e poi usa la KDF per estrarre la chiave simmetrica più corta (128-256 bit). Crittosistemi diffusi come RSA, con la loro capacità di cifrare direttamente i dati, possono essere utilizzati per implementare i KEM.

Figura 3. Meccanismo di incapsulamento delle chiavi

Firme digitali con crittografia a chiave asimmetrica

Le firme digitali sono un'altra potente applicazione della crittografia a chiave asimmetrica. Forniscono autenticazione, integrità e non-repudiabilità abilitate dal fatto che nell'AKC le entità possiedono chiavi private uniche. L'idea di base sottostante i protocolli di firma è che i mittenti di messaggi sicuri firmeranno digitalmente i messaggi usando la propria chiave privata univoca. Il destinatario verificherà poi la firma digitale usando la chiave pubblica del mittente. Nell'AKC, le firme digitali possono essere implementate usando algoritmi specificamente progettati a tale scopo o usando crittosistemi generici.

Figura 4. Firme digitali con crittografia a chiave asimmetrica

Algoritmi dedicati alle firme digitali

Attualmente, lo standard US Federal Information Processing Standard (FIPS) per le firme digitali è uno schema dedicato semplicemente intitolato Digital Signature Algorithm (DSA). In modo alquanto simile al protocollo Diffie-Hellman, il DSA utilizza le proprietà algebriche dell'esponenziale modulare e degli inversi moltiplicativi per la generazione e verifica delle firme.

L'algoritmo di firma digitale su curva ellittica (ECDSA) è una variante ECC del DSA, che fornisce le stesse funzionalità ma con chiavi significativamente più corte. Ciò comporta una maggiore efficienza, rendendolo una scelta popolare per sistemi con vincoli di risorse.

Sia DSA che ECDSA saranno illustrati più in dettaglio in seguito.

Schemi di firma digitale che utilizzano crittosistemi generici

Oltre agli algoritmi dedicati, le firme digitali possono essere generate anche usando crittosistemi asimmetrici generici, come RSA.

RSA, che sarà discusso in dettaglio in una sezione successiva, sfrutta anch'esso gli inversi moltiplicativi modulari e l'esponenziazione modulare come operazioni fondamentali, ma le combina in una sequenza diversa rispetto al DSA. In RSA, il firmatario tipicamente crea un hash del messaggio e poi cifra l'hash con la propria chiave privata, creando la firma digitale. Qualsiasi parte può quindi verificare questa firma decifrandola con la chiave pubblica del firmatario e confrontandola con il messaggio sottoposto ad hashing.

Applicazioni della crittografia a chiave asimmetrica

La crittografia a chiave asimmetrica è onnipresente nelle applicazioni tecnologiche digitali moderne. Le funzionalità di base dell'AKC descritte sopra costituiscono i mattoni di molti protocolli applicativi di livello superiore, tra cui:

1. Comunicazione Internet: La comunicazione sicura su Internet, come HTTPS, si basa fortemente sulla crittografia a chiave asimmetrica. Il Transport Layer Security (TLS) e il suo predecessore, Secure Sockets Layer (SSL), utilizzano la crittografia a chiave asimmetrica durante il processo di handshake iniziale per stabilire una chiave simmetrica, che viene poi utilizzata per il resto della sessione di comunicazione.

2. Autenticazione: La crittografia a chiave asimmetrica viene utilizzata per creare firme digitali, permettendo a un'entità di autenticare un documento o messaggio digitale come proveniente da un mittente specifico. Questo viene utilizzato in molti scenari, dalla verifica degli aggiornamenti software ai contratti digitali legalmente vincolanti.

3. Cifratura delle email: I protocolli di cifratura delle email come PGP (Pretty Good Privacy) e la sua alternativa open source GPG (GNU Privacy Guard) utilizzano la crittografia a chiave asimmetrica per garantire che solo il destinatario previsto possa leggere il contenuto dell'email.

4. Secure Shell (SSH): SSH è un protocollo per il login remoto sicuro e altri servizi di rete sicuri su una rete non sicura. Utilizza la crittografia a chiave asimmetrica per autenticare il server al client e, opzionalmente, il client al server.

5. VPN (rete privata virtuale): La cifratura a chiave asimmetrica viene utilizzata per stabilire connessioni sicure nelle VPN, garantendo comunicazioni sicure su reti pubbliche.

6. Blockchain e criptovalute: Le tecnologie blockchain, inclusi Bitcoin ed Ethereum, utilizzano la crittografia a chiave asimmetrica. Ad esempio, la proprietà di Bitcoin viene stabilita attraverso firme digitali che utilizzano la crittografia a chiave asimmetrica.

7. Autorità di certificazione: La crittografia a chiave asimmetrica viene utilizzata dalle autorità di certificazione (CA) per emettere e firmare certificati digitali, utilizzati nelle comunicazioni TLS, nella firma del codice, nella cifratura delle email e altro ancora. Un certificato digitale associa una chiave pubblica a un'entità specifica (ad esempio, una persona o un server).

Figura 5. Emissione e firma di certificati digitali con crittografia a chiave asimmetrica

Sicurezza della crittografia a chiave asimmetrica

Diversi concetti crittografici si combinano per abilitare una crittografia a chiave asimmetrica sicura, tra cui:

Segretezza della chiave privata: Il requisito di sicurezza più fondamentale dell'AKC è che la chiave privata rimanga segreta. Tuttavia, poiché la chiave privata deve essere matematicamente collegata alla chiave pubblica, la segretezza della chiave privata richiede anche che sia computazionalmente impossibile derivare la chiave privata dalla conoscenza della chiave pubblica. Gli schemi di generazione delle chiavi nell'AKC si basano su problemi matematici computazionalmente difficili per facilitare questo requisito.

Funzionalità trapdoor: Nell'AKC, le operazioni di cifratura e decifratura coinvolgono chiavi complementari diverse di una singola coppia di chiavi. Il testo cifrato generato dalla cifratura usando una delle chiavi (ad esempio la chiave pubblica) deve essere incomprensibile a terze parti mentre deve essere facilmente decifrabile da chi detiene la chiave complementare (in questo caso la chiave privata). In altre parole, la cifratura dovrebbe assomigliare a una funzione unidirezionale con trapdoor tale che le terze parti non possano invertire l'operazione e recuperare il testo in chiaro, ma la chiave privata fornisce una trapdoor segreta che consente una facile inversione. I popolari algoritmi AKC utilizzano l'esponenziazione modulare per impostare il comportamento della funzione unidirezionale con trapdoor.

Casualità: Il processo di generazione delle chiavi dovrebbe anche sfruttare la casualità per garantire che le chiavi siano imprevedibili, poiché qualsiasi schema o prevedibilità nella generazione delle chiavi potrebbe essere sfruttata da un aggressore. La casualità viene utilizzata anche per il padding durante la cifratura per generare testi cifrati semanticamente sicuri e negli schemi di firma digitale per produrre firme uniche anche quando lo stesso messaggio viene firmato più volte. Per questo motivo, l'uso di generatori di numeri casuali robusti è una parte importante dell'AKC.

Dimensione grande delle chiavi: Come nel caso dell'SKC, chiavi di grandi dimensioni garantiscono protezione contro gli attacchi a forza bruta. Tuttavia, poiché chiavi di grandi dimensioni aumentano anche il costo computazionale del processo di cifratura e decifratura, una soluzione ottimale deve bilanciare considerazioni di sicurezza ed efficienza. La tabella seguente mostra le dimensioni tipiche delle chiavi per vari protocolli e applicazioni di crittografia a chiave asimmetrica:

Protocollo	Dimensioni tipiche delle chiavi (in bit)	Applicazione
RSA	1024 (deprecato), 2048, 3072, 4096	Cifratura, firme digitali
DSA	1024 (deprecato), 2048, 3072	Firme digitali
DH	2048, 3072, 4096	Scambio di chiavi
ECDH	224, 256, 384, 521	Scambio di chiavi
ECDSA	224, 256, 384, 521	Firme digitali

Infrastruttura a chiave pubblica: Nell'AKC, le chiavi private devono essere tenute segrete dai proprietari mentre le chiavi pubbliche vengono condivise. È necessario un meccanismo sicuro per gestire e distribuire queste chiavi pubbliche tra gli utenti. L'infrastruttura a chiave pubblica (PKI) fornisce un modo per farlo usando i certificati digitali. Un certificato digitale fornisce la prova dell'identità del proprietario della chiave pubblica ed è emesso da un'autorità fidata come un'autorità di certificazione (che fa parte di una PKI). Quindi, la PKI svolge un ruolo fondamentale nella sicurezza delle applicazioni moderne che utilizzano l'AKC, abilitando la gestione delle chiavi su larga scala (creando, gestendo, distribuendo e revocando certificati digitali).

Rischi di sicurezza per la crittografia a chiave asimmetrica

Come indicato nella tabella precedente, i moderni algoritmi a chiave asimmetrica come RSA impiegano tipicamente dimensioni delle chiavi molto più grandi rispetto alle controparti a chiave simmetrica comunemente usate come AES-128. Anche i protocolli basati su ECC (ECDH ed ECDSA) che hanno chiavi più piccole impiegano un minimo di almeno 224 bit per le chiavi. Ciò implica a sua volta che un attacco a forza bruta che coinvolge una ricerca esaustiva dello spazio delle chiavi private per identificare la chiave corretta è computazionalmente intrattabile nel prossimo futuro. Questo rimane vero anche se i computer quantistici dovessero essere impiegati per questo compito. Pertanto, gli attacchi contro l'AKC di solito si concentrano sullo sfruttamento di altre potenziali debolezze di crittosistemi specifici. Alcune modalità di attacco ben documentate prendono di mira:

1. Debolezza algoritmica usando mezzi matematici e computazionali sofisticati per minare le ipotesi di durezza usate per formulare gli algoritmi a chiave asimmetrica. Ad esempio, la sicurezza di RSA è basata sulla difficoltà di fattorizzare grandi numeri primi, e recenti progressi computazionali hanno abilitato la fattorizzazione riuscita di chiavi RSA a 829 bit. Pertanto, RSA a 1024 bit è attualmente deprecato. Come verrà discusso in seguito, il rischio principale posto dai computer quantistici all'AKC rientra anch'esso in questa categoria.

2. Casualità imperfetta, che può portare a debolezze nel processo di generazione delle chiavi. Ad esempio, se il generatore di numeri casuali usato per creare le chiavi è difettoso e genera chiavi che non sono veramente casuali, un aggressore potrebbe essere in grado di prevedere le chiavi.

3. Difetti di implementazione come errori nell'implementazione degli algoritmi crittografici che rivelano inavvertitamente informazioni sulle chiavi. Ad esempio, un padding non corretto può potenzialmente rivelare dettagli sulle chiavi.

4. Canali laterali che si riferiscono alla perdita di informazioni dal sistema fisico che esegue la crittografia. Tali perdite potrebbero essere sotto forma di informazioni temporali, consumo di energia, o persino suoni, che possono essere sfruttati in un cosiddetto attacco a canale laterale. Ad esempio, analizzare quanto tempo impiegano le operazioni crittografiche potrebbe rivelare il numero di '1' in una chiave binaria. Questa perdita apparentemente innocente restringe significativamente lo spazio di ricerca, rivelando potenziali soluzioni a problemi che inizialmente sembravano insuperabili.

5. Scambio di chiavi intercettando le chiavi mentre vengono scambiate, come in un attacco man-in-the-middle (MITM). Il protocollo DH è suscettibile agli attacchi MITM se non vengono incorporati ulteriori passaggi di autenticazione.

6. Archiviazione delle chiavi mirando a rubare chiavi da archivi scarsamente sicuri. Ciò include attacchi fisici come la manipolazione o il furto di dispositivi di archiviazione.

Proteggere i crittosistemi a chiave asimmetrica dalla varietà di attacchi possibili è quindi un compito significativo che coinvolge considerazioni matematiche, hardware, software, logistiche e legali.

RSA

L'algoritmo RSA (Rivest-Shamir-Adleman) è uno dei primi crittosistemi a chiave pubblica ed è ampiamente utilizzato per la trasmissione sicura dei dati. È un crittosistema versatile in quanto fornisce le operazioni necessarie per abilitare cifratura, decifratura, firme digitali e scambio di chiavi all'interno di un framework comune.

In questa sezione, illustreremo la crittografia a chiave asimmetrica (AKC) usando RSA attraverso semplici esempi.

Utilizzeremo lo scenario standard di due parti, Alice e Bob, che desiderano comunicare in modo sicuro usando l'AKC.

L'algoritmo RSA

L'algoritmo RSA di base prevede quattro operazioni: generazione delle chiavi, distribuzione delle chiavi, cifratura e decifratura:

1. Generazione delle chiavi:

   Le chiavi pubblica e privata vengono generate sulla base di principi matematici relativi ai numeri primi, dove calcolarle è facile, ma il contrario è difficile.

   Faremo riferimento a queste:

   • Chiave pubblica: $(e, n)$
   • Chiave privata: $(d, n)$

   Nota che $n$ è comune sia alla chiave pubblica che alla chiave privata, ed è noto come modulo. Dovremo usarlo in seguito.

Dettaglio matematico

• Scegli due numeri primi distinti, $p$ e $q$.
  • scelti casualmente (per sicurezza).
  • Dovrebbero essere di grandezza simile, ma differire in lunghezza di qualche cifra, per rendere la fattorizzazione più difficile.
  • I numeri primi possono essere scelti in modo efficiente usando un test di primalità.
• Calcola $n = p*q$.
  • $n$ è il modulo sia per le chiavi pubblica che privata.
• Calcola il totiente $φ$$(n) = (p-1)*(q-1)$.
  • Il totiente deve essere tenuto segreto e tipicamente viene eliminato dopo la generazione delle chiavi.
• Scegli un intero $e$ tale che $1 < e <$$φ$$(n)$ e $gcd$$(e,$$φ$$(n)) = 1$.
  • ovvero, $e$ e $φ$$(n)$ devono essere coprimi.
  • Questo numero $e$ forma l'esponente della chiave pubblica e viene tipicamente scelto come un numero piccolo per l'efficienza computazionale.
  • Il numero primo $65537 = 2^{16} + 1$ viene spesso usato.
  • Calcola $d$ per soddisfare la relazione di congruenza $d*e ≡ 1 ($$mod$$φ$$(n))$.
    • Ovvero, $d$ è l'inverso moltiplicativo di $e$ modulo $φ$$(n)$.
    • Questo viene calcolato in modo più efficiente usando l'algoritmo euclideo esteso.
    • Questo numero $d$ è l'esponente della chiave privata.
• La chiave pubblica è composta da $(e, n)$, e la chiave privata è $(d, n)$.

2. Distribuzione delle chiavi:

   • La chiave pubblica $(e, n)$ viene resa pubblica a coloro che potrebbero desiderare di inviare un messaggio
   • La chiave privata $(d, n)$ viene tenuta segreta.

3. Cifratura:

   • Alice desidera inviare un messaggio $M$ a Bob. In questo caso un semplice intero
   • Alice usa la chiave pubblica di Bob $(e, n)$ per cifrare il messaggio nel testo cifrato $C$

   Dettaglio matematico

   • $M$ è un intero $0 ≤ M < n$.
   • $C ≡ M^e (mod n)$, dove $C$ è il testo cifrato.

4. Decifratura:

   • Bob riceve il testo cifrato $C$
   • Bob usa la sua chiave privata $(d, n)$ per decifrare il messaggio nel messaggio originale $M$

   Dettaglio matematico

   • $M ≡ C^d (mod n)$.

Questo è il profilo di base di RSA. In pratica, vengono applicati al testo in chiaro $M$ schemi di padding più sofisticati prima della cifratura per garantire che testi in chiaro uguali risultino in testi cifrati diversi. Questo previene una serie di possibili attacchi contro implementazioni ingenue di RSA e abilita la sicurezza semantica.

Illustrazione di RSA in Python

Nelle seguenti celle di codice, illustriamo un semplice esempio dell'algoritmo RSA usando piccoli interi e poi dimostriamo applicazioni pratiche di distribuzione delle chiavi e firma digitale usando librerie Python che implementano RSA.

nota

Nota: In questa sezione mostreremo i calcoli matematici in dettaglio come parte del codice Python

Generazione delle chiavi RSA

Percorriamo passo per passo una semplice istanza dell'algoritmo RSA che impiega piccoli numeri primi.

Dovremo essere in grado di calcolare il massimo comune divisore di due interi, poiché sarà necessario per testare se due interi sono coprimi.

Spiegheremo un semplice modo per calcolarlo, ma è molto più efficiente con interi più grandi usare la funzione Python math.gcd.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

import math

# Example function to compute the gcd (greatest common divisor)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# let's calculate some examples using algorithm
n1 = gcd(50, 10)
n2 = gcd(99, 33)
n3 = gcd(59, 9)

# do the same with the python library call

m1 = math.gcd(50, 10)
m2 = math.gcd(99, 33)
m3 = math.gcd(59, 9)

# Confirm they are the same
assert n1 == m1
assert n2 == m2
assert n3 == m3

# They are - print out the values for explanation
print("gcd(50,10) =", m1)
print("gcd(99,33) =", m2)
print("gcd(59,9) =", m3)

La prima fase del flusso di lavoro RSA è la generazione delle chiavi. Viene avviata scegliendo due numeri primi, che devono essere tenuti segreti dall'entità che genera le chiavi.

# Choosing two prime numbers and keep them secret
p = 13
q = 19
print("The secret prime numbers p and q are:", p, q)

Successivamente, il modulo $n$, che è semplicemente il prodotto dei due primi scelti, viene calcolato. Questo modulo verrà pubblicato come parte della chiave pubblica.

# Calculate n which is the modulus for both the public and private keys
n = p * q
print("modulus n (p*q)=", n)

La funzione totiente di Eulero $\varphi(n)$ viene calcolata successivamente, poiché è necessaria per l'operazione di inverso moltiplicativo modulare usata per determinare le chiavi in RSA. $phi$ è anche tenuto segreto e tipicamente eliminato dopo la generazione delle chiavi.

# Compute Euler's totient function, φ(n) and keep it secret
phi = (p - 1) * (q - 1)
print("The secret Euler's function (totient) [phi(n)]:", phi)

Ora siamo pronti per calcolare le chiavi pubblica e privata. In RSA, ciascuna di esse è specificata da una tupla di due interi. La prima voce di ciascuna tupla è un intero distinto, e la seconda voce è il modulo $n$ comune a entrambe le chiavi.

La prima voce nella chiave pubblica può essere qualsiasi intero maggiore di 1 che sia coprimo con $phi$. Due interi sono coprimi se il loro massimo comune divisore è 1. Quindi usiamo la funzione math.gcd per trovare un intero $e$ coprimo con $phi$.

# Choose an integer e such that e and φ(n) are coprime
e = 2
while e < phi:
    if math.gcd(e, phi) == 1:
        break
    else:
        e += 1
print("Public Key (e):", e)

La chiave privata richiede un intero $d$, che è l'inverso moltiplicativo di $e$ modulo $phi$; ovvero, soddisfa la relazione di congruenza $d*e\equiv 1 \pmod{\varphi(n)}$. Per questa semplice illustrazione dove trattiamo piccoli interi, possiamo semplicemente iterare sugli interi positivi per trovare un $d$ adatto. In contesti realistici, viene usato a tale scopo l'efficiente algoritmo euclideo esteso.

# Compute a value for d such that (d * e) % φ(n) = 1
d = 1
while True:
    if (d * e) % phi == 1:
        break
    else:
        d += 1
print("Private Key (d):", d)

Formiamo ora le tuple $(e, n), (d, n)$, che costituiscono rispettivamente le chiavi pubblica e privata. La chiave pubblica viene quindi pubblicata, mentre la chiave privata viene tenuta segreta.

# Public and Private Key pair
public = (e, n)
private = (d, n)

print(f"The Public key is {public} and Private Key is {private}")

La cifratura e la decifratura in RSA utilizzano l'operazione di esponenziazione modulare. Inoltre, le chiavi pubblica e privata sono complementari nel senso che entrambe possono essere usate per cifrare un messaggio che l'altra può poi decifrare.

Qui illustriamo il caso in cui la chiave pubblica $(e,n)$ viene usata per la cifratura e la chiave privata $(d, n)$ per la decifratura, definendo una funzione Python per ciascuna operazione.

Cifriamo e decifriamo quindi un messaggio intero $msg$.

# Encryption function
def encrypt(plain_text):
    return (plain_text**e) % n

# Decryption function
def decrypt(cipher_text):
    return (cipher_text**d) % n

# Simple message to encode
msg = 9

# encrypt then decrypt
enc_msg = encrypt(msg)
dec_msg = decrypt(enc_msg)

print("Original Message:", msg)
print("Encrypted Message:", enc_msg)
print("Decrypted Message:", dec_msg)

Mentre i piccoli interi usati sopra sono utili per delineare facilmente le idee principali dell'algoritmo RSA, nelle applicazioni reali RSA richiede l'uso di interi molto grandi. Ad esempio, RSA a 2048 bit prevede l'uso di un modulo $n$ lungo 2048 bit, i cui equivalenti interi decimali sono intorno a 10$^616$. Questi numeri davvero enormi sono necessari per la sicurezza pratica di RSA.

Scambio di chiavi simmetriche con RSA

Come discusso in precedenza, l'AKC consente a due parti che desiderano comunicare di stabilire in modo sicuro un segreto condiviso, che può essere usato, ad esempio, come chiave segreta per la successiva cifratura simmetrica del testo in chiaro in blocco.

Consideriamo il seguente scenario. Alice e Bob vogliono usare l'SKC per cifrare e decifrare i messaggi. Tuttavia, prima che questo processo possa essere avviato, devono concordare una chiave segreta comune. Un'opzione è che una delle parti — diciamo Alice — generi una chiave segreta e poi la trasmetta in modo sicuro a Bob. Per ottenere questo trasferimento sicuro, Alice decide di usare RSA come meccanismo di incapsulamento delle chiavi (KEM).

Questo comporta i seguenti passaggi:

• Prima, Alice genera una chiave simmetrica casuale, che intende condividere con Bob.
• Poi, Bob genera una coppia di chiavi asimmetriche e rende disponibile la sua chiave pubblica su un canale appropriato.
• Successivamente, Alice usa la chiave pubblica di Bob per cifrare la chiave simmetrica, incapsulandola così in un testo cifrato.
• Poi, Alice trasmette il testo cifrato su un canale affidabile ma non necessariamente sicuro.
• Infine, Bob riceve il testo cifrato e lo decifra usando la sua chiave privata. Ora ha accesso alla chiave simmetrica generata da Alice.

Figura 1. Scambio di chiavi simmetriche con RSA

Esempio di scambio di chiavi basato su padding in Python

Un flusso di lavoro pratico che utilizza RSA per lo scambio di chiavi non interattivo basato su padding viene ora illustrato usando la libreria Python cryptography.

Importa i moduli necessari dalla libreria Python cryptography. Se necessario, questa libreria può essere installata usando il comando pip install cryptography.

Alice genera quindi una chiave segreta casuale, che intende trasmettere a Bob.

# pip install cryptography
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.fernet import Fernet
from cryptography.hazmat.primitives import hashes

symmetric_key = Fernet.generate_key()
print(f"\nSymmetric key generated by Alice: {symmetric_key}")

Usando il modulo rsa dalla libreria cryptography, Bob genera una coppia di chiavi e poi trasmette la sua chiave pubblica. Chiunque può intercettare la chiave pubblica e leggere i numeri pubblici $(e,n)$ che formano la chiave.

# Bob generates a 2048-bit RSA key pair
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()
print(f"Public key broadcast by Bob: {bob_public_key}")
print(f"\nPublic numbers in Bobs' public key: {bob_public_key.public_numbers()}")

A questo punto, assumiamo che Alice abbia ricevuto la chiave pubblica trasmessa da Bob. La symmetric_key di Alice può ora essere cifrata usando la chiave pubblica di Bob per produrre il testo cifrato. In un contesto realistico, Alice userà anche metodi di padding aggiuntivi come OAEP per garantire la sicurezza semantica per le sue comunicazioni con Bob.

# Encryption
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

Alice trasmette quindi il testo cifrato su un canale aperto, fiduciosa che solo Bob con la corrispondente chiave privata sarà in grado di decifrarlo. Assumiamo che Bob abbia ricevuto il testo cifrato e possa ora decifrarlo usando la sua chiave privata riservata.

# Bob decrypts ciphertext to access the symmetric key
decrypted_symmetric_key = bob_private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted key:", decrypted_symmetric_key)
assert decrypted_symmetric_key == symmetric_key

A questo punto, sia Alice che Bob hanno accesso alla chiave simmetrica segreta, che possono usare per applicazioni SKC.

Simulazione di un meccanismo di incapsulamento delle chiavi con RSA in Python

Nel seguente flusso di lavoro, illustriamo l'uso di RSA per simulare un meccanismo di incapsulamento delle chiavi (KEM) mediante il quale un messaggio segreto casuale sufficientemente lungo viene scambiato in modo sicuro e successivamente convertito in un segreto condiviso della lunghezza appropriata usando una KDF.

Anche in questo caso Alice e Bob vogliono stabilire un segreto condiviso in modo non interattivo e Alice è la parte che decide quale segreto usare.

Iniziamo importando alcune librerie Python necessarie.

Bob genera quindi la sua coppia di chiavi RSA e trasmette la sua chiave pubblica.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from os import urandom

# Bob's RSA key pair
private_key_Bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key_Bob = private_key_Bob.public_key()

print("Bob's private and public keys created")

Alice genera prima un lungo segreto casuale da cui verrà eventualmente derivato il segreto condiviso. In un KEM puro, il lungo segreto sarà un elemento casuale della struttura algebrica sottostante il crittosistema. Nel caso di RSA a 2048 bit, questo sarebbe un intero casuale modulo il modulo RSA a 2048 bit. Poiché un KEM puro non richiede padding aggiuntivo, ma in questo esempio stiamo solo simulando un KEM usando RSA e la libreria cryptography richiede l'uso del padding quando si cifra con RSA, utilizzeremo un lungo segreto leggermente più corto che tuttavia è molto più lungo di una chiave AES standard a 256 bit.

Alice_long_secret = urandom(160)  # A 160 byte or 1280 bit random message
print("Alice's secret created")

Successivamente Alice cifra il lungo segreto usando la chiave pubblica di Bob e il segreto cifrato viene comunicato a Bob.

Alice_encrypted_secret = public_key_Bob.encrypt(
    Alice_long_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Alice's secret encrypted")

Bob decifra il segreto cifrato ricevuto da Alice usando la sua chiave privata.

Bob_decrypted_secret = private_key_Bob.decrypt(
    Alice_encrypted_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

assert Alice_long_secret == Bob_decrypted_secret, "Secrets do not match!"

# if we get here they match
print("Secrets match")

Infine sia Alice che Bob applicano separatamente una funzione di derivazione delle chiavi (KDF) concordata sul lungo segreto per derivare la chiave simmetrica.

Nota che il processo prevede un protocollo di hashing e l'uso di un salt casuale che garantisce unicità e imprevedibilità della chiave simmetrica condivisa nel caso in cui il lungo segreto venga mai riutilizzato (non raccomandato). Tuttavia il salt stesso non deve essere segreto e una volta generato casualmente, diciamo da Alice in questo esempio, può essere trasmesso a Bob insieme al lungo segreto cifrato.

Assumeremo quindi che sia Alice che Bob abbiano accesso allo stesso salt casuale.

def key_derivation_function(secret, salt):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,  # Desired key length
        salt=salt,
        info=None,
        backend=None,
    )
    return hkdf.derive(secret)

common_salt = urandom(16)  # Random salt accessible to both Alice and Bob

symmetric_key_Alice = key_derivation_function(Alice_long_secret, common_salt)
symmetric_key_Bob = key_derivation_function(Bob_decrypted_secret, common_salt)

assert symmetric_key_Alice == symmetric_key_Bob, "Derived keys do not match!"
print(
    f"A symmetric key of length {len(symmetric_key_Alice)*8} bits was successfully derived by both Alice and Bob!"
)

Firme digitali con RSA

Estenderemo ora lo scenario di comunicazione riservata sopra con Alice e Bob a uno che include anche la validazione con l'aiuto di una firma digitale.

Come prima, Alice invierà riservatamente a Bob un messaggio che incapsula una chiave simmetrica, ma lo firmerà digitalmente in modo che Bob, alla ricezione del messaggio, possa verificare che sia stata Alice ad originarlo e che il contenuto del messaggio non sia stato manomesso durante la trasmissione.

Più in generale, è auspicabile abilitare la validazione senza compromettere la riservatezza, dove qualsiasi parte interessata è in grado di verificare l'integrità, l'autenticità e stabilire la non-repudiabilità rispetto a una data comunicazione, anche se quella parte non ha accesso al messaggio in chiaro effettivo.

Considereremo questo contesto generale che comporta quindi i seguenti passaggi:

• Prima, sia Bob che Alice rendono disponibili le loro chiavi pubbliche su un canale aperto.
• Poi, Alice cifra il testo in chiaro usando la chiave pubblica di Bob, creando un testo cifrato.
• Successivamente, Alice crea un hash del testo cifrato con una funzione hash e cifra ulteriormente il testo cifrato sottoposto ad hashing usando la sua chiave privata. Questo hash cifrato è la firma.
• Poi, Alice trasmette sia il testo cifrato che la firma su un canale aperto.
• Poi, Bob usa la chiave pubblica di Alice per decifrare la firma, rivelando il testo cifrato sottoposto ad hashing.
• Successivamente, poiché Bob ha anche accesso al testo cifrato stesso, utilizza la stessa funzione hash usata da Alice per ricreare una seconda istanza del testo cifrato sottoposto ad hashing. Se quest'ultimo corrisponde a quello ottenuto decifrandando la firma di Alice, allora il messaggio è validato, anche se il testo cifrato stesso non è ancora stato decifrato.
• Infine, Bob, avendo validato il messaggio, decifra il testo cifrato usando la propria chiave privata.

Figura 2. Firme digitali con RSA

Questo flusso di lavoro per una firma digitale è illustrato di seguito.

Importiamo di nuovo alcuni moduli utili dalla libreria cryptography. Come prima, Alice intende inviare in modo sicuro una chiave simmetrica a Bob, ma desidera anche firmarla digitalmente. In questo caso, abbiamo bisogno delle chiavi pubbliche sia di Alice che di Bob. Pertanto, il primo passo è che sia Alice che Bob creino la propria coppia di chiavi usando RSA e trasmettano la propria chiave pubblica al mondo.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

# Generate keys for Bob
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()

# Generate keys for Alice
alice_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key = alice_private_key.public_key()

print("Private and Public keys generated for Bob and Alice.")

Nel passo successivo, come prima, Alice usa la chiave pubblica di Bob per cifrare la chiave simmetrica e prepara il testo cifrato.

# Alice encrypts the message using Bob's public key
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("ciphertext of symmetric key: ", ciphertext)

In questa fase, invece di trasmettere semplicemente il testo cifrato, Alice intende allegarvi una firma digitale in modo da poter dimostrare a Bob di essere la mittente del messaggio. Questo viene fatto in due passaggi:

1. Crea un hash del testo cifrato usando un algoritmo di hashing.
2. Cifra l'hash usando la chiave privata di Alice, il che equivale a una firma.

# Alice signs the ciphertext using her private key
digest = hashes.Hash(hashes.SHA256())
digest.update(ciphertext)
hash_to_sign = digest.finalize()

signature = alice_private_key.sign(
    hash_to_sign,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    Prehashed(hashes.SHA256()),
)

print("signature: ", signature)

Alice trasmette quindi il testo cifrato e la firma su una rete in modo che Bob possa intercettarli entrambi.

# Bob receives the ciphertext and signature
received_ciphertext = ciphertext
received_signature = signature

# Send signature and ciphertext here
print("Sending ciphertext and signature.....")

Dal lato di Bob, il primo compito è verificare l'integrità e l'autenticità del testo cifrato. Per farlo, Bob crea un hash del testo cifrato ricevuto usando lo stesso algoritmo di hashing usato da Alice.

# Bob creates a hash of the ciphertext using the same algorithm used by Alice
digest = hashes.Hash(hashes.SHA256())
digest.update(received_ciphertext)
hash_to_verify = digest.finalize()

print("hash to verify: ", hash_to_verify)

Poi, Bob decifra la firma ricevuta usando la chiave pubblica di Alice. Poiché Alice ha usato la sua chiave privata per creare la firma, Bob è in grado di decifrarla usando la chiave pubblica di Alice. La firma decifrata non è altro che un hash del testo cifrato creato dal lato di Alice. Se l'hash creato da Bob corrisponde alla firma decifrata, allora Bob ha verificato che il testo cifrato che ha ricevuto non è stato manomesso e che è stata Alice a firmare il testo cifrato.

Nel codice Python seguente, queste operazioni sono combinate in una utile funzione di utilità chiamata verify fornita da un oggetto associato alla chiave pubblica di Alice.

from cryptography.exceptions import InvalidSignature

def is_signature_valid(public_key, signature, data_hash):
    try:
        public_key.verify(
            signature,
            data_hash,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH
            ),
            Prehashed(hashes.SHA256()),
        )
        return True
    except InvalidSignature:
        return False

if is_signature_valid(alice_public_key, received_signature, hash_to_verify):
    print("The signature is valid.")
else:
    print("The signature is not valid.")

Avendo verificato l'integrità e l'autenticità del testo cifrato ricevuto, Bob può quindi decifrarlo usando la sua chiave privata poiché Alice ha creato il testo cifrato usando la chiave pubblica di Bob.

# Bob decrypts the message using his private key
decrypted_message = bob_private_key.decrypt(
    received_ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted message:", decrypted_message.decode())

Nello scenario di firma digitale sopra descritto, qualsiasi parte — non solo Bob — può verificare che Alice sia la mittente del testo cifrato perché tutti possono accedere alla chiave pubblica di Alice, al testo cifrato e alla firma digitale. Inoltre, dopo aver inviato il testo cifrato e la firma, Alice non può in seguito negare di averlo fatto perché la firma può essere decifrata in un hash significativo usando solo la sua chiave pubblica. Questo stabilisce la non-repudiabilità.

Abilitando la distribuzione sicura delle chiavi e supportando la non-repudiabilità, la crittografia a chiave pubblica pone le basi solide per una comunicazione digitale sicura.

Violare RSA

L'utilità e la sicurezza dell'algoritmo RSA descritto sopra si fondano su due assunzioni matematiche:

1. Trovare l'inverso moltiplicativo modulare $d$ avendo accesso solo a $(e, n)$ è computazionalmente infattibile.

2. Nell'ambito RSA, l'operazione di esponenziazione modulare si comporta come una funzione trapdoor unidirezionale. Quando viene usata per la cifratura, produce un testo cifrato incomprensibile e, senza accesso alla chiave privata, invertire l'operazione per recuperare il testo in chiaro dal testo cifrato non è fattibile. Tuttavia, con accesso alla chiave privata, che funge da trapdoor, il testo cifrato può essere facilmente decifrato.

L'attacco più noto all'algoritmo RSA mira a minare l'assunzione 1 recuperando efficientemente il numero di chiave privata $d$ tramite la fattorizzazione del modulo $n$. Come illustrato di seguito, è facile recuperare $d$ se si ha accesso ai fattori primi $p$ e $q$ di $n$ o al totiente $φ$$(n)$. Ricorda che $p$, $q$ e $φ$$(n)$ vengono tenuti segreti durante la generazione delle chiavi e scartati dopo. Una terza parte che recupera queste informazioni usando un computer classico o quantistico scopre essenzialmente la chiave privata, violando RSA. Quindi, la fattorizzazione in numeri primi è la primitiva computazionale fondamentale necessaria per violare RSA.

Il calcolo classico e RSA

La fattorizzazione in numeri primi di interi di grandi dimensioni è nota per presentare una scalabilità super-polinomiale o subesponenziale sui computer classici. Il miglior algoritmo classico conosciuto per la fattorizzazione di interi maggiori di $10^{100}$ è il crivello del campo numerico generale (GNFS)

Dettaglio matematico

$L_n[\frac{1}{3}, (\frac{64}{9})^{(\frac{1}{3})}] = e^{[((\frac{64}{9})^{(\frac{1}{3})} + o(1)) (log(n))^{\frac{1}{3}}(log(log(n))^{\frac{2}{3}})]}$

in funzione dell'intero $n$ da fattorizzare.

Questa scalabilità è super-polinomiale nel numero di bit necessari per rappresentare $n$.

Pertanto, la fattorizzazione in numeri primi è considerata inefficiente sui computer classici.

Attualmente, i più grandi interi fattorizzati su hardware classico sono nell'ordine di 829 bit o 250 cifre decimali. Dato il crescita esponenziale della potenza di calcolo classica testimoniata negli ultimi decenni, RSA a 1024 bit non è più considerato sicuro nel breve termine ed è ora deprecato. Tuttavia, nel prevedibile futuro, la fattorizzazione di interi a 2048 bit la cui grandezza è nell'ordine di $10^{617}$ è attualmente considerata infattibile sui sistemi classici, suggerendo una duratura vitalità. L'avvento dei computer quantistici, tuttavia, vanifica questa valutazione.

L'algoritmo quantistico di Shor e RSA

Probabilmente l'algoritmo quantistico più conosciuto oggi è l'algoritmo di Shor per trovare i fattori primi degli interi. Quando introdotto da Peter Shor nel 1994, fu riconosciuto come il primo algoritmo quantistico che offriva un speedup super-polinomiale rispetto agli algoritmi classici su un problema di grande importanza pratica, ovvero la fattorizzazione in numeri primi.

L'algoritmo di Shor può fattorizzare i numeri primi con $O(n^2)$ dove $n$ è il numero di bit.

Spiegazione matematica dell'algoritmo di Shor

Nel contesto di RSA, l'algoritmo di Shor funziona sfruttando la periodicità della funzione esponenziale modulare $f(x) = a^x (mod~n)$ e fornisce una primitiva quantistica per trovare il periodo che consente una fattorizzazione efficiente del modulo $n$.

Di seguito una sintesi semplificata dello schema generale di Shor per violare RSA:

1. Dato il modulo $n$, pubblicato come parte della chiave pubblica, scegli un numero $a$ coprimo con $n$, cioè $gcd(a,n) = 1$. Poiché sappiamo che $n = p*q$ ha esattamente due fattori primi $(p, q)$, quasi qualsiasi numero minore di $n$ scelto a caso è probabilmente coprimo con $n$.

2. Avendo scelto $a$, trova l'esponente $r$ tale che $a^r \equiv 1 (mod~n)$. Questo implica $a^r - 1 \equiv 0 (mod~n)$. L'esistenza di un esponente $r$ tale che vale la suddetta congruenza è garantita dalla proprietà di periodicità dell'esponenziazione modulare.

3. Se $r$ è pari, $a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$ per qualche intero $\gamma$. Il lato sinistro di quest'ultima uguaglianza deve contenere $p$ e $q$ come due dei suoi fattori primi poiché li contiene anche il lato destro. Se $r$ è dispari, torna al passo 1 e prova una scelta diversa per $a$.

4. Usa l'algoritmo di Euclide esteso per trovare $gcd((a^{r/2} - 1), n)$ o $gcd((a^{r/2} + 1), n)$. Il MCD calcolato è molto probabile che identifichi uno dei fattori primi $p$ o $q$. Dividi $n$ per questo fattore primo per recuperare l'altro.

5. Una volta noti $p, q$, usa i passi dell'algoritmo RSA originale per ricostruire il totiente $\phi(n)$ e generare il numero di chiave privata $d$ come l'inverso modulare del numero di chiave pubblica noto $e$.

Nell'agosto 2023, Oded Regev ha pubblicato un miglioramento sull'originale di Shor usando un approccio multidimensionale che risulta in $O(n^{1.5})$. La ricerca in questo settore continua, inclusa quella di Ragavan e Vaikuntanathan, che potrebbe migliorare il tempo, il costo o il numero di qubit necessari. Sebbene non possiamo dire quando l'esecuzione di tali algoritmi contro la crittografia RSA reale diventi effettivamente praticabile, ci stiamo avvicinando sempre di più.

Esempio Python che illustra la violazione della crittografia RSA

Nelle seguenti celle di codice, illustriamo un esempio di come trovare una chiave privata avendo accesso solo alla chiave pubblica. Useremo la computazione classica a forza bruta, ma mostriamo come potrebbe essere usato l'algoritmo di Shor — incluse le chiavi grandi.

nota

In questa sezione mostreremo i calcoli matematici in dettaglio come parte del codice Python

Nell'esempio, abbiamo una chiave pubblica $(5, 247)$ e recupereremo la chiave privata.

Passo 1: Il primo passo è scegliere un numero coprimo con 247. Quasi qualsiasi numero indovineremo andrà bene. Scegliamo 6.

n = 247  # the modulus
e = 5  # public key number
a = 6  # an integer coprime to n
assert gcd(a, n) == 1
print(f"Checked {n} and {a} are coprime")

Passo 2: Successivamente dobbiamo trovare il periodo $r$ tale che $6^r \equiv 1 (mod~247)$. In questo esempio, calcoliamo $r$ classicamente con la forza bruta, ma potremmo anche usare l'algoritmo di Shor su un computer quantistico usando Qiskit.

r = 0
rem = 100
while rem != 1:
    r += 1
    rem = (a**r) % n

print(f"period r is: {r}")
assert a**r % n == 1

print(f"Checked {a}^{r} mod {n} is 1")

Passo 3: Poiché il periodo $r = 36$ è pari, possiamo calcolare $f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$.

# explicitly use as integer
f1 = int(a ** (r / 2) - 1)
f2 = int(a ** (r / 2) + 1)

print(f"f1 = {f1}")
print(f"f2 = {f2}")

Passo 4: Trova il MCD di uno di quei fattori con $n$. Dividi semplicemente $n$ per il fattore primo già trovato per ottenere il secondo fattore primo.

q_found = gcd(f1, n)
print(f"One possible prime factor of n ({n}) is: {q_found}")

# explicit int (to avoid floating point)
p_found = int(n / q_found)
print(f"The second prime factor of n ({n}) is: {p_found}")

assert n == p_found * q_found

Passo 5: Avendo recuperato i fattori primi di $n = 247$ come $p_{found}=13$ e $q_{found}=19$, calcoliamo il totiente $\phi_{found} = (p_{found}-1)*(q_{found}-1)$.

La chiave privata è l'inverso modulare del numero di chiave pubblica $e=5$.

# Compute the totient
phi_found = (p_found - 1) * (q_found - 1)
print(f"The totient is: {phi_found}")

# Recover the private key number d_found by satisfying (d_found * e) % phi_found = 1
d_found = 1
while True:
    if (d_found * e) % phi_found == 1:
        break
    else:
        d_found += 1
print("Private Key number:", d_found)

Nello schema sopra, il passo 2 è l'operazione cruciale di ricerca del periodo per cui l'algoritmo di Shor usa due primitive quantistiche fondamentali, ovvero la trasformata di Fourier quantistica e la stima di fase quantistica. Per una spiegazione dettagliata degli aspetti quantistici dell'algoritmo di Shor, vedi la lezione sulla stima di fase e fattorizzazione nei Fondamenti degli Algoritmi Quantistici. I passi 1 e da 3 a 5 coinvolgono operazioni relativamente poco costose che possono essere facilmente eseguite su computer classici.

Facoltativamente, ecco un dettagliato walkthrough visivo dell'implementazione dell'algoritmo di Shor.

Sui computer quantistici, l'algoritmo di Shor può presentare una scalabilità polologaritimica favorevole come $O((log~n)^2 (log~log~n))$ in termini del modulo $n$, o una scalabilità polinomiale in termini del numero di bit necessari per rappresentare $n$. Questo è uno speedup super-polinomiale rispetto all'algoritmo GNFS classico.

Le recenti stime delle risorse indicano che, in base ad alcune assunzioni sulla configurazione hardware, saranno necessari da alcune decine di migliaia a diversi milioni di qubit per violare RSA a 2048 bit usando l'algoritmo di Shor. Non è inconcepibile che nel corso dei prossimi anni diventino disponibili computer quantistici con diverse decine di migliaia di qubit, rendendo accessibile l'estremità inferiore della stima delle risorse.

Scambio di chiavi Diffie-Hellman e algoritmo di firma digitale

Nella sezione precedente, abbiamo discusso il crittosistema RSA, la cui sicurezza si basa sulla difficoltà computazionale della fattorizzazione in numeri primi. Qui discuteremo due popolari protocolli crittografici a chiave asimmetrica, lo scambio di chiavi Diffie-Hellman (DH) e l'algoritmo di firma digitale (DSA), entrambi basati su un diverso problema matematico, ovvero il problema del logaritmo discreto (DLP).

Il problema del logaritmo discreto

Nella seguente equazione dobbiamo trovare $a$ avendo solo $e$,$M$,$c$

$a^e$ $mod$ $M = c$

Questo è considerato difficile con i computer classici a causa dell'uso dell'aritmetica modulare, ed è quindi una buona base matematica per un algoritmo di cifratura.

Questo è noto come il problema del logaritmo discreto (DLP).

Dettagli matematici del problema del logaritmo discreto

Il DLP è tipicamente formulato nel contesto dei gruppi ciclici ed è enunciato come segue.

Considera un gruppo ciclico $G$ generato da un elemento del gruppo $g \in G$ e, dato un elemento arbitrario $h \in G$, trova un intero $k$ tale che $h = g^{k}$.

Qui l'intero $k \equiv log_{g}h$ è il logaritmo discreto. La proprietà ciclica di $G$ garantisce che per ogni $h$ esiste un intero valido $k$.

Per la crittografia, il DLP sul gruppo moltiplicativo degli interi modulo un numero primo $p$ indicato con $(\mathbb{Z}_p)^{\times}$ si rivela utile. Gli elementi di $(\mathbb{Z}_p)^{\times}$ sono classi di congruenza etichettate da interi modulo $p$ che sono coprimi con $p$.

Per esempio:

$(\mathbb{Z}_5)^{\times} = \{[1],[2],[3],[4]\}~\mathrm{e}~(\mathbb{Z}_7)^{\times} = \{[1],[2],[3],[4],[5],[6]\}$

L'operazione di moltiplicazione $(\times)$ su questi gruppi è semplicemente la moltiplicazione ordinaria di interi seguita dalla riduzione modulo $p$ e l'esponenziazione per un intero $k$ è solo la moltiplicazione ripetuta $k$ volte e riduzione modulo $p$.

Illustriamo un'istanza del DLP su $(\mathbb{Z}_7)^{\times}$.

Questo gruppo moltiplicativo ha due generatori ${[3],[5]}$ noti anche come radici primitive. Useremo $[5]$ come generatore; cioè, genereremo ogni elemento di $(\mathbb{Z}_7)^{\times}$ usando potenze intere successive di 5.

#Generate elements of (Z_7)^{x} using generator [5].
g = 5
p = 7
print(f"Using generator {g}")
for k in range(3*p):
    print(f"{g}**{k} mod {p} ≡ {(g**k)%7}")

Vediamo che nell'aritmetica modulo 7, elevare 5 a potenze intere successive produce ogni elemento di $(\mathbb{Z}_7)^{\times}$ esattamente una volta prima che il ciclo si ripeta indefinitamente con un periodo $p-1 =6$.

Quindi il DLP su $(\mathbb{Z}_7)^{\times}$ con generatore [5] è:

$\mathrm{Dato}~h \in (\mathbb{Z}_7)^{\times} \mathrm{, trova~} k \mathrm{~tale~che~} 5^{k} \equiv h~(mod~7)$.

Dall'output della cella Python sopra vediamo che:

$h = 2 \implies k=4 \mathrm{~o~} 4 = log_5(2) (mod~7)$

$h = 6 \implies k=3 \mathrm{~o~} 3 = log_5(6) (mod~7)$

Nell'aritmetica dei numeri reali ordinari, l'esponenziazione è una funzione monotona e trovare il logaritmo di qualsiasi numero in qualsiasi base è computazionalmente semplice. Al contrario, come è evidente dal semplice esempio di $(\mathbb{Z}_7)^{\times}$ sopra, l'esponenziazione modulare è non monotona, e sebbene sia periodica con periodo $p-1$, è altrimenti altamente non banale. Quindi calcolare il suo inverso, il logaritmo discreto, risulta inefficiente per grandi $p$ sui computer classici.

Questa osservazione è alla base sia dello scambio di chiavi Diffie-Hellman (DH) che dell'algoritmo di firma digitale (DSA), discussi nella prossima sezione.

Il DLP può essere esteso a sottogruppi ciclici come segue:

• Considera $(\mathbb{Z}_p)^{\times}$ definito sopra e un elemento $g \in (\mathbb{Z}_p)^{\times}$ di ordine primo $r$, cioè $g^r \equiv 1 (~mod~p)$.
• L'insieme delle potenze intere di $g$: $\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$ è un sottogruppo ciclico di $(\mathbb{Z}_p)^{\times}$ con ordine del gruppo $r$.
• Un DLP può essere specificato su $\langle g \rangle$ scegliendo un $h \in \\langle g \rangle$ e chiedendo per $1 \le a \le r$ tale che $g^a~(mod~p) = h$

Scambio di chiavi Diffie-Hellman

Nel 1976, Whitfield Diffie e Martin Hellman proposero un protocollo di scambio di chiavi per consentire la creazione di una chiave segreta condivisa su canali di comunicazione non sicuri. La chiave segreta potrebbe poi essere usata dalle parti che la condividono per la cifratura simmetrica. L'algoritmo si basa sul DLP.

Figura 1. Scambio di chiavi Diffie-Hellman

Dettagli matematici dello scambio di chiavi Diffie-Hellman

Con Alice e Bob come le due parti in comunicazione, il protocollo funziona come segue:

• Prima, Alice e Bob concordano su un grande numero primo $p$ e una radice primitiva o generatore $a$.
• Poi, Alice sceglie casualmente un esponente segreto $k_A$ con $1 \le k_A \le p-2$ e calcola $h_A = a^{k_A}~(mod~p)$. $k_A, h_A$ sono rispettivamente la chiave privata e pubblica di Alice.
• Successivamente, Bob sceglie casualmente un esponente segreto $k_B$ con $1 \le k_B \le p-2$ e calcola $h_B = a^{k_B}~(mod~p)$. $k_B, h_B$ sono rispettivamente la chiave privata e pubblica di Bob.
• Poi, Alice invia a Bob $h_A$ e Bob invia ad Alice $h_B$ tramite un canale affidabile ma non necessariamente sicuro.
• Quindi, Alice usa l'$h_B$ ricevuto per calcolare la chiave segreta condivisa $\kappa = h_B^{k_A}~(mod~p)$.
• Infine, Bob nel frattempo usa l'$h_A$ ricevuto per calcolare la chiave segreta condivisa $\kappa = h_A^{k_B}~(mod~p)$.

Con questo protocollo,

• Alice e Bob sono garantiti di ottenere la stessa chiave segreta $\kappa$ perché $h_B^{k_A}~(mod~p) = (a^{k_B})^{k_A}~(mod~p) = a^{k_A k_B}~(mod~p) = (a^{k_A})^{k_B}~(mod~p) = h_A^{k_B}~(mod~p)$.
• Una terza parte che intercetta $h_A$ o $h_B$ non può costruire la chiave segreta $\kappa$ perché non ha accesso a $k_B$ o $k_A$ rispettivamente.
• Estrarre $k_A$ o $k_B$ usando le informazioni pubbliche $a$, $p$, $h_A$ e $h_B$ è computazionalmente difficile in quanto equivale a risolvere il DLP su $(\mathbb{Z}_p)^{\times}$.

Illustrazione del protocollo Diffie-Hellman in Python

Guardiamo un semplice esempio del protocollo DH in Python usando numeri primi piccoli:

nota

In questa sezione mostreremo i calcoli matematici in dettaglio come parte del codice Python

Passo 1: Alice e Bob concordano su un primo $p$ e una radice primitiva $a$. Scegliamo $p=11, a=7$.

# Step 1: Choose a prime `p` and a primitive root `a`
p = 11
a = 7

print(f"prime: {p}")
print(f"primitive root: {a}")

Passi 2, 3: Alice sceglie un esponente segreto $k_A$ e calcola $h_A = a^{k_A}~(mod~p)$. Analogamente, Bob sceglie un esponente segreto $k_B$ e calcola $h_B = a^{k_B}~(mod~p)$.

k_A = 4  # Alice's private key
h_A = (a ** (k_A)) % p  # Alice's public key

print(f"Alice's private key is {k_A} and public key is {h_A}")

k_B = 8  # Bob's private key
h_B = (a ** (k_B)) % p  # Bob's public key

print(f"Bob's private key is {k_B} and public key is {h_B}")

Passo 4: Le due parti trasmettono le loro chiavi pubbliche $h_A$ e $h_B$.

Passi 5, 6: Ciascuna parte combina la propria chiave privata con la chiave pubblica dell'altra parte per creare la chiave segreta condivisa.

secret_key_alice = h_B**k_A % p
secret_key_bob = h_A**k_B % p
assert secret_key_alice == secret_key_bob
print(f"The shared secret key is: {secret_key_bob}")

Alice e Bob possono ora usare la chiave segreta condivisa per la cifratura simmetrica.

Sicurezza dello scambio di chiavi Diffie-Hellman

Come notato sopra, la sicurezza di DH dipende dalla difficoltà computazionale di risolvere il DLP con grandi primi $p$. Nelle applicazioni tipiche, NIST raccomanda interi primi a 2048 o 3072 bit per lo scambio di chiavi DH, considerato sufficientemente sicuro contro i tentativi di risolvere il DLP usando computer classici.

Attacchi Man-in-the-middle (MITM): Il fatto che DH sia uno schema interattivo dove il segreto condiviso dipende dalla combinazione della chiave privata di una parte con la chiave pubblica dell'altra lo rende vulnerabile a un cosiddetto attacco Man-in-the-middle (MITM).

Dettagli matematici della sicurezza DH e degli attacchi MITM

In questo scenario, una terza parte — diciamo, Eve — intercetta le chiavi pubbliche $h_A, h_B$ durante la trasmissione e sostituisce la propria chiave pubblica $h_E$ a ciascuna di $h_A$ e $h_B$ prima di inoltrarle rispettivamente a Bob e Alice.

Poi, invece di usare $h_B$ per creare il suo segreto condiviso, Alice userà $h_E$ pensando di usare la chiave pubblica di Bob. Analogamente, invece di usare $h_A$ per creare il suo segreto condiviso, Bob userà $h_E$ pensando di usare la chiave pubblica di Alice.

Poiché $h_E$ è stata usata per creare il segreto condiviso di Alice (Bob), il testo in chiaro cifrato da Alice (Bob) può essere decifrato da Eve.

Pertanto, lo scambio di chiavi DH viene tipicamente usato in combinazione con un algoritmo di firma digitale per garantire che ciascuna parte usi una chiave pubblica autenticata per creare il proprio segreto condiviso.

L'algoritmo di firma digitale (DSA)

Sebbene i crittosistemi generici come RSA forniscano funzionalità di firma digitale, nel 1994 NIST adottò uno schema di firma specializzato basato sull'esponenziazione modulare e il problema del logaritmo discreto come standard federale per le firme digitali. Questo schema, che è diventato semplicemente noto come algoritmo di firma digitale (DSA), comprende quattro fasi distinte:

1. Generazione delle chiavi:

   Le chiavi DSA vengono generate da:

   • 2 numeri primi che soddisfano determinate regole
     • $p$ - tipicamente 256 bit (chiameremo questa lunghezza $N$)
     • $q$ - tipicamente 3072 bit (chiameremo questa lunghezza $L$)
   • Una funzione hash crittografica che converte da stringhe di lunghezza $L$ a $N$
   • Un parametro aggiuntivo $g$ (vedi i dettagli di seguito)

   Da questi scegliamo un numero casuale $x$ come chiave privata, e siamo in grado di calcolare una chiave pubblica $y$

   Dettagli matematici della generazione delle chiavi

   • Generazione dei parametri: Matematicamente, DSA coinvolge un sottogruppo ciclico di $(\mathbb{Z}_p)^{\times}$ generato da un elemento $g$ di ordine primo q < p. Il primo passo nel DSA è quindi selezionare due primi p, q per impostare le strutture matematiche necessarie.

     • Scegli un primo $q$ di $N$ bit.
     • Scegli un primo $p$ di $L$ bit tale che $p-1$ sia un multiplo di $q$. La scelta di $p$ specifica il gruppo $(\mathbb{Z}_p)^{\times}$
     • Scegli un intero $1 < h < p-1$ casualmente e calcola $g = h^{(p-1)/q}~mod~p$. Se $g=1$, cosa che accade raramente, prova un altro h.
     • Verifica che $g^q~mod~p = 1$. g è quindi un generatore di un sottogruppo ciclico $\langle g \rangle$ di $(\mathbb{Z}_p)^{\times}$ di ordine primo q.

     I parametri $(q, p, g)$ specificano un'istanza dell'algoritmo e sono informazioni pubbliche. Tipicamente, $N \sim 256$ e $L \sim 3072$ nelle applicazioni realistiche.

     Il protocollo richiede anche una funzione hash crittografica $H : \{0,1\}^L \rightarrow \{0, 1\}^N$ che mappa stringhe binarie di $L$ bit in stringhe di $N$ bit, per esempio, SHA-256.

   • Generazione della coppia di chiavi: Il firmatario deve generare una coppia di chiavi sul proprio lato.

     • Scegli un intero segreto casuale $x \in \{1,2...q-1\}$. $x$ è la chiave privata.
     • Genera $y = g^{x}~mod~p$. $y$ è la chiave pubblica del firmatario.

2. Distribuzione delle chiavi:

   Le seguenti informazioni vengono condivise con chiunque voglia validare una firma

   • I parametri usati $(p,q,g)$ che descrivono l'algoritmo
   • La funzione hash $H$
   • la chiave pubblica $y$

3. Firma:

   • Il firmatario può ora firmare un messaggio $m$. La firma risultante è $(r,s)$
   • Il messaggio e la firma vengono ora entrambi inviati al destinatario

   Dettagli matematici della firma di un messaggio

   Il firmatario firma un messaggio $m$ come segue:

   • Scegli un intero segreto k casualmente da $\{1,2...q-1\}$
   • Calcola $r = (g^k~mod~p)~mod~q$. Nel raro caso in cui $r=0$, prova un altro k casuale.
   • Calcola $s = (k^{-1} (H(m) + xr))~mod~q$. In rari casi se $s=0$, prova un altro k casuale.
   • La firma è la tupla $(r, s)$.
   • Il firmatario trasmette il messaggio $m$ nonché la firma $(r,s)$ al verificatore.

   Poiché sia $r$ che $s$ sono interi, modulo $q$ la dimensione della firma è dell'ordine di $N$ bit e non dei più lunghi $L$ bit.

4. Verifica:

   Il destinatario desidera ora verificare l'autenticità del mittente. Ha accesso alle informazioni pubbliche $(q, p, g, H, y, (r,s), m)$ Può eseguire un calcolo che dimostra che il mittente aveva accesso alla chiave privata $x$

   e cerca di accertare che il firmatario sia qualcuno con accesso alla chiave privata $x$.

   Dettagli matematici dello schema di verifica DSA

   • Verifica che $0 \lt r \lt q$ e $0 \lt s \lt q$, cioè $r, s$ sono interi validi modulo~q.
   • Calcola $w = s^{-1}~mod~q$.
   • Calcola $u_1 = H(m)w~mod~q$.
   • Calcola $u_2 = rw~mod~q$.
   • Calcola $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$.
   • La firma è verificata se $v = r$.

   Per le firme legittime, la correttezza dell'algoritmo DSA è facilmente dimostrata come segue:

   • Dal lato del firmatario: $s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$
   • Considerando il lato destro di quest'ultima uguaglianza, un verificatore può calcolare $s^{-1}, H(m)$ perché $s, q, m, H$ sono informazioni pubbliche.
   • Quindi, il verificatore calcola $w = s^{-1}~mod~q$ e $u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$.
   • Il verificatore calcola anche $u_2 = rw~mod~q = rs^{-1}~mod~q$ poiché $r$ è anch'esso pubblico.
   • Nota che $k = (u_1 + xu_2)~mod~q$.
   • Tuttavia, un verificatore non ha accesso a $x$ poiché è la chiave privata del firmatario, quindi $k$ stesso non può essere calcolato direttamente. Lo schema si basa invece sul fatto che, anche se il verificatore non può calcolare $k$, con un firmatario legittimo il verificatore dovrebbe invece essere in grado di ricalcolare $(g^k~mod~p)~mod~q = r$ con l'aiuto della chiave pubblica del firmatario $y = g^{x}~mod~p$.
   • Quindi, il verificatore calcola $v = (g^{u_1}y^{u_2}~mod~p)~mod~q = (g^{u_1}g^{xu_2}~mod~p)mod~q = (g^{u_1+xu_2}~mod~p)mod~q = (g^k~mod~p)mod~q$.
   • L'ultima uguaglianza segue perché $g$ ha ordine $q$ e stabilisce $v = r$ per le firme valide.

Illustrazione del DSA in Python

In questo esempio, useremo piccoli numeri primi per illustrare il processo DSA in uno scenario in cui Alice invia un messaggio firmato a Bob. Useremo piccoli interi in questo esempio. Uno scenario reale impiegherebbe numeri primi molto più grandi dell'ordine di 2048-3072 bit.

nota

Puoi provare a rieseguire questo esempio con valori diversi per vedere come si comporta l'algoritmo, ma assicurati di iniziare l'esecuzione dalla prima cella di questa sezione.

Iniziamo importando le librerie necessarie e scegliendo i nostri parametri. I parametri interi $p$, $q$, $g$ sono informazioni pubbliche e soddisfano le seguenti regole:

• $p$, $q$ sono entrambi primi
• $(p-1) \mod\ q = 0$
• $g \ge 2$
• $g \le (p-2)$
• $g^{(p-1)/q} \mod\ p \neq 1$

from random import randint

# parameter generation: select the primes q, p and generator g:
# EXPERIMENT with the values, they must meet certain rules
# this example code does not verify p,q are prime

q = 11
p = 23
g = 4

assert (p - 1) % q == 0
assert g >= 2
assert g <= (p - 2)
assert (pow(g, (p - 1) / q) % p) != 1

print(f"Public information is good: q={p}, p={q}, g={g}")

Successivamente il firmatario, Alice, genera la sua chiave privata.

La chiave privata, k (alice-private-key nel codice Python) deve soddisfare:

• $k \ge 2$
• $k \le (q-1)$

# Alice chooses an integer randomly from {2..q-1}
# EXPERIMENT with the values

alice_private_key = randint(2, q - 1)
# alice_private_key =

assert alice_private_key >= 2
assert alice_private_key <= (q - 1)

print(f"Alice's private key is {alice_private_key}")

Alice mantiene segreta la sua chiave privata.

Successivamente, Alice calcola la sua chiave pubblica usando l'esponenziazione modulare. Invertire questo passo per recuperare la chiave privata è un'istanza del DLP, quindi difficile da calcolare su computer classici dove si usano grandi primi.

Dalla spiegazione matematica sopra, sappiamo che questo può essere calcolato usando la formula:

$y = g^{x} \mod\ p$

alice_public_key = pow(g, alice_private_key, p)
# Alternatively can use (g ** alice_private_key) % p

print(f"Alice's public key is {alice_public_key}")

Come di consueto, Alice rende disponibile la sua chiave pubblica tramite un canale non necessariamente segreto.

Ora Alice può firmare un messaggio.

Per lo schema di firma digitale, dobbiamo generare un hash $H(m)$ del messaggio $m$ da firmare.

Supponiamo che Alice e Bob concordino di usare un particolare algoritmo di hashing con lunghezza hash $N$ uguale al numero di bit in $q$. In questo semplice esempio, limiteremo gli output della nostra funzione hash simulata a $q$. La funzione hash qui è banale, generando semplicemente un intero casuale.

hash_dict = {}

def mock_hash_func(input_message):
    print(input_message)
    if input_message not in hash_dict:
        hash_dict[input_message] = randint(1, q)
    return hash_dict[input_message]

alice_message = "Inspection tomorrow!"
alice_hash = mock_hash_func(alice_message)  # In reality, you'd use a hash function
print(f"Alice's message hash is: {alice_hash}")

Successivamente, Alice deve generare un numero segreto casuale per messaggio $k$ nonché il suo inverso moltiplicativo modulo $q$ per calcolare la firma.

Un semplice algoritmo a forza bruta può essere usato per calcolare l'inverso modulare. Tuttavia è meglio usare una delle funzioni Python integrate pow come mostrato di seguito

# brute-force implementation to find modular inverse
def modular_inverse(k, q):
    for i in range(0, q):
        if (k * i) % q == 1:
            return i
    print(f"error! no inverse found! for {k},{q}")
    return 0

# Let's compare this algorithm with the standard python 'pow' function

n1 = modular_inverse(3, 7)
n2 = modular_inverse(4, 11)
n3 = modular_inverse(7, 5)
m1 = pow(3, -1, 7)
m2 = pow(4, -1, 11)
m3 = pow(7, -1, 5)

assert n1 == m1
assert n2 == m2
# assert(n3==m3)

print(f"modular_inverse(3,7) = {m1}")
print(f"modular_inverse(4,11) = {m2}")
print(f"modular_inverse(7,5) = {m3}")

# Some numbers don't have modular inverses - our function throws an error
n4 = modular_inverse(2, 6)

# The python library will throw an exception, which must be caught
if math.gcd(2, 6) == 1:
    m4 = pow(2, -1, 6)
else:
    print("Exception from pow() - no modular inverse found!")

Alice può ora calcolare la firma.

• $r = (g^{k} \mod p) \mod\ q$
• $s = (k^{-1} (H(m) + xr)) \mod q$

Nota che ci sono alcune condizioni particolari che richiederanno di scegliere un valore diverso per $k$ nel caso in cui $r$ o $s$ calcolino a $0$. In questo caso genereremo un nuovo valore e ripeteremo.

# Start an infinite loop; we will 'break' out of it once a valid signature is found.
while True:
    k = randint(1, q - 1)  # Should be different for every message
    print("Using random k =", k)

    r = pow(g, k, p) % q
    # If r is 0, the value is invalid. Try again with a new k.
    if r == 0:
        print(f"{k} is not a good random value to use to calculate r. Trying another k")
        continue

    s = (pow(k, -1, q) * (alice_hash + alice_private_key * r)) % q
    # If s is 0, the value is also invalid. Try again with a new k.
    if s == 0:
        print(f"{k} is not a good random value to use to calculate s. Trying another k")
        continue

    # If we've reached this point, both r and s are valid. Break the loop.
    signature = (r, s)
    print(f"Alice's signature is : {(r,s)}")
    break

# After the loop, the valid r and s values can be used here.
# print(f"Generated Signature -> r: {r}, s: {s}")

Alice trasmette il messaggio e la sua firma al destinatario o verificatore, Bob.

Bob ha precedentemente intercettato la chiave pubblica di Alice e può ora verificare la firma per autenticare il suo messaggio.

Per farlo, esegue alcuni controlli, poi rigenera un hash del messaggio trasmesso da Alice e calcola le quantità ausiliarie $w, u_1, u_2$ e $v$.

• $0 < r < q$
• $0 < s < q$
• $w = s^{-1} \mod\ q$
• $u_{1} = H(m) . w \mod\ q$
• $u_{2} = r . w \mod\ q$
• $v = (g^{u1}y^{u2} \mod\ p) \mod\ q$

Infine, Bob controlla se $v$ è uguale a $r$. Se sono uguali, la firma è verificata.

# Bob re-generates message hash using Alice's broadcast message
bob_hash = mock_hash_func(alice_message)

# Bob computes auxiliary quantities w (using modular inverse), u1, u2 and v
w = (pow(s, -1, q)) % q
u1 = (bob_hash * w) % q
u2 = (r * w) % q
v = ((g**u1 * alice_public_key**u2) % p) % q

if v == r:
    print("Signature is valid!")
else:
    print("Signature is invalid!")

Sicurezza del DSA

Con il calcolo classico, la sicurezza del DSA può essere influenzata da diversi fattori:

1. Dimensione della chiave: Come sempre, la dimensione della chiave fornisce una protezione di base contro gli attacchi a forza bruta. Le applicazioni moderne che usano DSA impiegano dimensioni di chiave di almeno 2048 bit.

2. Qualità di $k$: Nel DSA, ogni firma necessita di un valore $k$ unico, casuale e segreto (vedi sopra). L'unicità, l'entropia e la segretezza di $k$ sono critiche, e la debolezza in uno qualsiasi di questi aspetti potrebbe portare alla compromissione della chiave privata $x$. I generatori di numeri casuali usati per generare $k$ devono essere sicuri a loro volta.

3. Robustezza della funzione hash: Poiché DSA usa una funzione hash come parte del processo di generazione e verifica della firma, una funzione hash debole potrebbe compromettere la sicurezza della firma digitale. Per esempio, l'uso di SHA-1 con DSA è deprecato e si raccomanda SHA-2 o superiore.

Oltre a questi, un'implementazione robusta del DSA dovrebbe anche proteggersi da altri tipi di attacchi che colpiscono la crittografia a chiave asimmetrica come precedentemente descritto.

Scambio di chiavi autenticato con Diffie-Hellman e DSA

I moderni protocolli di sicurezza di rete, come Transport Layer Security (TLS) e molti altri, coinvolgono la combinazione delle funzionalità di scambio di chiavi e autenticazione. Nel contesto di Diffie-Hellman, l'autenticazione è necessaria per proteggersi dagli attacchi MITM. Nelle seguenti celle di codice, illustriamo un esempio in cui Alice e Bob eseguono uno scambio di chiavi autenticato combinando i protocolli Diffie-Hellman e DSA. Per questo, useremo la libreria Python cryptography.

Figura 2. Scambio di chiavi autenticato con Diffie-Hellman e DSA

Prima, Alice e Bob concordano su un insieme di parametri DH e generano un insieme di coppie di chiavi pubbliche-private DH.

# import necessary library modules
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, dsa

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate Alice's DH private key and public key
alice_dh_private_key = parameters.generate_private_key()
alice_dh_public_key = alice_dh_private_key.public_key()

# Generate Bob's DH private key and public key
bob_dh_private_key = parameters.generate_private_key()
bob_dh_public_key = bob_dh_private_key.public_key()

print("Public and private keys generated for Bob and Alice")

Le chiavi pubbliche DH vengono trasmesse. Successivamente, sia Alice che Bob generano ciascuno una coppia di chiavi separata da usare con DSA. Queste chiavi saranno a loro volta usate per firmare le chiavi pubbliche DH da scambiare.

# Generate DSA keys for Alice and Bob
alice_dsa_private_key = dsa.generate_private_key(key_size=2048)
alice_dsa_public_key = alice_dsa_private_key.public_key()
bob_dsa_private_key = dsa.generate_private_key(key_size=2048)
bob_dsa_public_key = bob_dsa_private_key.public_key()

print("Additional key pair generated for signing")

Alice firma la sua chiave pubblica DH usando la sua chiave privata DSA.

# Alice signs
alice_public_bytes = alice_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
alice_signature = alice_dsa_private_key.sign(alice_public_bytes, hashes.SHA256())

print("Alice signed public key")

Analogamente, Bob firma la sua chiave pubblica DH usando la sua chiave privata DSA.

bob_public_bytes = bob_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
bob_signature = bob_dsa_private_key.sign(bob_public_bytes, hashes.SHA256())

print("Bob signed public key")

Le chiavi pubbliche DH e le firme corrispondenti vengono ora trasmesse da entrambi Alice e Bob. Avendo ricevuto la chiave pubblica e la firma della controparte, ciascuna parte verifica che la firma sia valida. In questo modo, è possibile prevenire un attacco MITM, poiché Alice, per esempio, sa che la chiave pubblica DH di Bob è stata effettivamente firmata da Bob e viceversa.

# Alice and Bob verify each other's DH public keys using DSA public keys
# An InvalidSignature exception will occur if they are not valid
alice_dsa_public_key.verify(alice_signature, alice_public_bytes, hashes.SHA256())
bob_dsa_public_key.verify(bob_signature, bob_public_bytes, hashes.SHA256())

print("Signatures are valid")

Dopo la verifica della firma, Alice e Bob generano il segreto condiviso, il che completa lo scambio di chiavi.

# Perform key exchange
alice_shared_key = alice_dh_private_key.exchange(bob_dh_public_key)
bob_shared_key = bob_dh_private_key.exchange(alice_dh_public_key)

print("Shared secrets generated")

Facoltativamente, per ulteriore sicurezza, Alice e Bob possono usare una funzione di derivazione delle chiavi specializzata come HKDF per generare una chiave simmetrica più sicura dal loro segreto condiviso usando tecniche di key stretching.

# Derive a shared symmetric key using key-stretching
def derive_key(shared_key):
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=None,
    ).derive(shared_key)

alice_symmetric_key = derive_key(alice_shared_key)
bob_symmetric_key = derive_key(bob_shared_key)

assert alice_symmetric_key == bob_symmetric_key
print("Keys checked to be the same")

Violazione di Diffie-Hellman e DSA

Sia il protocollo Diffie-Hellman (DH) che il DSA prevedono la generazione di chiavi pubbliche della forma $y = g^{x}~mod~p$, dove la chiave privata $x$ è il logaritmo discreto.

Un attaccante in grado di risolvere un'istanza del DLP può esporre la chiave privata di una delle due parti e, combinandola con la chiave pubblica dell'altra parte, ottenere accesso al segreto condiviso. Nel caso del DSA, un attaccante che riesce a risolvere il DLP può recuperare la chiave privata del firmatario, vanificando il presupposto fondamentale di una firma digitale.

Nei sistemi di calcolo classici, si ritiene che il DLP non abbia una soluzione in tempo polinomiale. Tuttavia, come ha dimostrato Peter Shor nel suo articolo originale del 1994, l'algoritmo di Shor risolve il DLP in tempo polinomiale anche sui computer quantistici.

L'algoritmo di Shor e il problema del logaritmo discreto

L'algoritmo di Shor è in grado di risolvere il problema del logaritmo discreto in tempo polinomiale. La sua efficienza deriva principalmente dall'utilizzo di algoritmi quantistici che possono trovare il periodo di una funzione dipendente dall'input del problema, il quale viene poi combinato con operazioni più convenzionali.

Dettagli matematici dell'algoritmo di Shor

L'algoritmo di Shor fornisce una soluzione efficiente al DLP mappandolo su un problema più generale della teoria dei gruppi noto come il problema del sottogruppo nascosto (HSP).

Nell'HSP, viene fornito un gruppo algebrico $G$ e una funzione $f: G \rightarrow X$ da $G$ a un insieme $X$ tale che $f$ sia costante su ogni coset di un sottogruppo $H$ di $G$ (e distinta su coset differenti). Il compito è quindi determinare $H$. È noto che i computer quantistici possono risolvere l'HSP su gruppi abeliani finiti in tempo polinomiale rispetto a $log~|G|$, dove $|G|$ è l'ordine del gruppo.

Nel caso del DLP intero discusso in questa lezione, la mappatura all'HSP è la seguente:

• Sia $p$ un numero primo e si consideri il DLP dato da $y = g^r~mod~p$ dove $g$ è un generatore di $(\mathbb{Z}_p)^{\times}$. Poiché $g^{p-1} \equiv 1~mod~p$, $g$ ha ordine $p-1$.
• Si scelga $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$ dove $\mathbb{Z}_{p-1}$ è il gruppo degli interi modulo $(p-1)$.
• Si scelga $f : G \rightarrow (\mathbb{Z}_p)^{\times}$ definita come $f(a, b) = g^a y^{-b}~mod~p \equiv g^{a-rb}~mod~p$.
• Il nucleo di $f$ è quindi il sottogruppo $H_0 = \langle (r, 1) \rangle = \{(a,b) \in G | f(a,b) \equiv 1~mod~p\} = \{ (a, b) \in G | a - rb \equiv 0~mod~(p-1)\}$.
• $f$ è costante sui coset $(\delta, 0) + H_0$ e "nasconde" il sottogruppo $H_0$, configurando un HSP.

Detto questo, l'algoritmo quantistico di Shor per il DLP intero utilizza un oracolo quantistico per valutare la funzione $f$ su uno stato che rappresenta una sovrapposizione uniforme su $G$, e poi impiega la trasformata di Fourier quantistica e misurazioni con la stima di fase per produrre stati quantistici che consentono di identificare il generatore $(r, 1)$ di $H_0$. Da questo è possibile estrarre $r$, il logaritmo discreto di interesse.

L'articolo originale di Shor contiene una descrizione dettagliata dell'algoritmo.

Crittografia a curva ellittica

La crittografia a curva ellittica (ECC), basata sulla matematica delle curve ellittiche, offre un approccio efficace alla crittografia a chiave asimmetrica. È noto che l'ECC fornisce un livello di sicurezza paragonabile a metodi come RSA, ma con chiavi più corte, rendendola più efficiente e particolarmente adatta a sistemi con risorse limitate, come i sistemi embedded e i dispositivi mobili, dove i vantaggi in termini di archiviazione e calcolo derivanti da chiavi di dimensioni ridotte sono molto desiderabili.

Principi fondamentali della crittografia a curva ellittica

Una curva ellittica ha tipicamente la forma $y^2 = x^3 + ax + b$ con alcune proprietà interessanti.

• È simmetrica orizzontalmente. Quindi, per qualsiasi punto $(x,y)$ sulla curva, anche la sua riflessione $(x,-y)$ si trova sulla curva
• Qualsiasi retta non verticale interseca la curva in al massimo tre punti

Figura 1. Operazioni di addizione e raddoppio di un punto su una curva ellittica. Il Facet 1 definisce P + Q = -R. Il Facet 2 illustra il raddoppio del punto 2Q = -P. Il Facet 3 definisce l'inverso additivo di un punto come la sua riflessione rispetto all'asse x, ovvero P = -Q

La crittografia a curva ellittica si avvale di una serie di operazioni aritmetiche applicate a punti sulla curva. Ciascuna di queste porta effettivamente a un nuovo punto sulla curva. Seguire questo processo in una direzione è semplice e, grazie a chiavi più corte, risulta più efficiente rispetto ad altri algoritmi come RSA; tuttavia, invertire questo processo è molto difficile, il che ne giustifica l'applicazione in crittografia.

Principi matematici della crittografia a curva ellittica

Una curva ellittica su un campo algebrico $K$ è definita da un'equazione matematica, tipicamente della forma $y^2 = x^3 + ax + b$ con coefficienti $a, b \in K$, e descrive punti $(x, y) \in K \otimes K$ con il requisito aggiuntivo che la curva non presenti cuspidi né auto-intersezioni.

Le proprietà delle curve ellittiche permettono di definire operazioni di "addizione" e "moltiplicazione scalare" coinvolgenti i punti sulla curva.

Addizione: Se $P$ e $Q$ sono due punti su una curva ellittica, allora $P + Q$ descrive un unico terzo punto identificato come segue: si traccia la retta che interseca $P$ e $Q$ e si trova il terzo punto, $R$, in cui la retta interseca nuovamente la curva. Definiamo quindi $P + Q = −R$, il punto opposto a $R$ riflesso rispetto all'asse $x$ (vedi figura sotto). Quando la retta passante per $P, Q$ non interseca la curva in alcun punto finito $(x, y)$, si dice che interseca la curva nel punto all'infinito $\mathbf{O}$.

L'addizione su curve ellittiche soddisfa le proprietà algebriche di un gruppo, con il punto all'infinito come identità additiva.

Raddoppio e moltiplicazione scalare: L'operazione di raddoppio di un punto, che corrisponde alla moltiplicazione scalare per $2$, si ottiene ponendo $P = Q$ nell'operazione di addizione e graficamente coinvolge la retta tangente in $P$. La moltiplicazione scalare generale per un intero $n$ definita come $nP = P + P + ...~n$ volte si ottiene tramite raddoppi e addizioni ripetute.

Problema del logaritmo discreto su curva ellittica

Il problema del logaritmo discreto su curva ellittica (ECDLP) presenta molte analogie con il problema del logaritmo discreto discusso in precedenza, basandosi sulle difficoltà nel trovare i fattori.

L'operazione di moltiplicazione scalare su curve ellittiche consente di definire il problema del logaritmo discreto su curva ellittica:

Dati i punti $P, Q$ su una curva ellittica tali che $Q = nP$, determinare $n$.

Questo problema è ritenuto intrattabile sui computer classici per $n$ grande e fornisce una base per la sicurezza crittografica.

Descrizione matematica dell'ECDLP

La crittografia a curva ellittica si basa principalmente sull'ECDLP formulato su certi campi finiti algebrici. Nel 1999, il NIST ha raccomandato dieci campi finiti per l'uso nell'ECC. Questi sono:

• Cinque campi primi $\mathbb {F} _{p}$ per primi $p$ di dimensione $\{192, 224, 256, 384, 521\}$ bit.
• Cinque campi binari $\mathbb {F} _{2^{n}}$ per $n \in \{163, 233, 283, 409, 571\}$.

Con la configurazione di cui sopra, un crittosistema a chiave asimmetrica basato su ECC nel caso dei campi primi può essere specificato come segue:

• Si sceglie un $p$ dall'elenco di valori raccomandati dal NIST per specificare $\mathbb {F} _{p}$.

• Si selezionano i parametri $a, b$ della curva ellittica.

• Si sceglie un punto base $G$ che "genera" un sottogruppo ciclico sulla curva di ordine $n$; ovvero il più piccolo intero tale che $nG = \mathbf{O}$.

• Si calcola il cofattore $h = |E(\mathbb {F} _{p})|/n$ dove $|E(\mathbb {F} _{p})|$ è il numero di punti sulla curva. $h$ è tipicamente un piccolo intero.

• I parametri di dominio $(p, a, b, G, n, h)$ consentono di specificare le chiavi asimmetriche nel seguente modo:

  • La chiave privata è un intero scelto casualmente $d$ con tanti bit quanti sono presenti nel primo $p$. Deve essere mantenuta segreta.
  • La chiave pubblica è il risultato della "moltiplicazione" del punto base $G$ per la chiave privata $d$. Viene tipicamente indicata come $Q = dG$.

Recuperare $d$ equivale a risolvere l'ECDLP, che si presume essere intrattabile per $d$ grande. L'ECDLP costituisce quindi la base per gli schemi di scambio di chiavi e di firma digitale in diretta analogia con gli schemi Diffie-Hellman e DSA definiti su $(\mathbb{Z}_p)^{\times}$ discussi in precedenza.

Scambio di chiavi con ECC

Uno degli utilizzi principali dell'ECC è nel protocollo di scambio di chiavi noto come Diffie-Hellman su curva ellittica (ECDH). In ECDH, ciascuna parte genera una coppia di chiavi privata-pubblica e poi scambia le chiavi pubbliche. Ogni parte utilizza quindi la propria chiave privata e la chiave pubblica dell'altra parte per calcolare un segreto condiviso, che può essere usato come chiave per la cifratura simmetrica.

Sebbene sia relativamente semplice eseguire l'addizione di punti su una curva ellittica e derivare una chiave pubblica da una chiave privata, è computazionalmente non fattibile invertire il processo e ricavare la chiave privata dalla chiave pubblica. Questo comportamento "a senso unico" garantisce la sicurezza dello scambio di chiavi ECDH.

Di seguito viene illustrato un esempio di come si potrebbe eseguire uno scambio di chiavi ECDH usando Python e la libreria cryptography.

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Each party generates a private key
private_key1 = ec.generate_private_key(ec.SECP384R1())
private_key2 = ec.generate_private_key(ec.SECP384R1())

# They exchange public keys
public_key1 = private_key1.public_key()
public_key2 = private_key2.public_key()

# Each party uses their own private key and the other party's public key
# to derive the shared secret
shared_key1 = private_key1.exchange(ec.ECDH(), public_key2)
shared_key2 = private_key2.exchange(ec.ECDH(), public_key1)

# The shared secrets are the same
assert shared_key1 == shared_key2
print("Keys checked to be the same")

Firme digitali con ECC

L'ECC può essere usata anche per generare firme digitali tramite l'Algoritmo di Firma Digitale su Curva Ellittica (ECDSA). In ECDSA, il firmatario crea una firma usando la propria chiave privata, e gli altri possono verificare la firma usando la chiave pubblica del firmatario. Proprio come con ECDH, la sicurezza di ECDSA si basa sull'ECDLP. È computazionalmente non fattibile per chiunque falsificare una firma senza accesso alla chiave privata del firmatario.

Il seguente è un esempio di una semplice transazione di firma e verifica usando ECDSA con Python e cryptography.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate a private key for use in the signature
private_key = ec.generate_private_key(ec.SECP384R1())

message = b"A message to be signed"

# Sign the message
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Anyone can verify the signature with the public key
public_key = private_key.public_key()

def check_ecdsa_signature(public_key, signature, message):
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

if check_ecdsa_signature(public_key, signature, message):
    print("The signature is valid.")
else:
    print("The signature is invalid.")

Nel codice sopra riportato, se si modifica il messaggio dopo che è stato firmato, la verifica fallirà, garantendo autenticità e integrità del messaggio.

Violazione di ECDH e ECDSA

In modo analogo al problema del logaritmo discreto su interi, l'ECDLP risulta difficile sui computer classici ma ha una soluzione efficiente sui computer quantistici, ancora una volta tramite l'algoritmo di Shor. Per un approfondimento relativo alla generalizzazione dell'algoritmo di Shor al caso ECDLP si rimanda alla letteratura recente.

Riepilogo

In questa lezione, abbiamo iniziato esaminando le principali caratteristiche della crittografia a chiave asimmetrica (AKC) e abbiamo discusso le considerazioni di sicurezza fondamentali su cui si basano i crittosistemi asimmetrici. In particolare, abbiamo introdotto le due principali applicazioni dell'AKC — ovvero lo scambio di chiavi e le firme digitali — entrambe componenti essenziali della moderna comunicazione basata su Internet.

Abbiamo poi esaminato il crittosistema RSA, che dagli anni '70 si è rivelato di immenso valore per la protezione delle comunicazioni digitali moderne, consentendo lo scambio di chiavi e le firme digitali all'interno di un framework semplice e versatile. La sicurezza crittografica di RSA rispetto al calcolo classico si basa sulla difficoltà di fattorizzare grandi interi e richiede chiavi di dimensioni comprese tra 2048 bit per garantire che gli interi utilizzati nelle applicazioni pratiche siano abbastanza grandi da resistere alla fattorizzazione.

Abbiamo poi esaminato lo scambio di chiavi Diffie-Hellman (DH) e l'Algoritmo di Firma Digitale (DSA). La sicurezza di questi schemi è fondata sul problema del logaritmo discreto intero (DLP), dove la chiave privata è computazionalmente difficile da estrarre dalla chiave pubblica, senza una soluzione in tempo polinomiale sui computer classici. L'uso di chiavi casuali e uniche garantisce ulteriore sicurezza contro gli attacchi. Sia le varianti su campo finito intero che quelle su curva ellittica dei protocolli DH e DSA trovano attualmente ampio utilizzo in molti moderni protocolli di comunicazione digitale come TLS, SSH e altri.

Infine abbiamo esaminato la crittografia a curva ellittica. Con le sue dimensioni di chiave efficienti e le sue forti proprietà di sicurezza, rappresenta attualmente un'ottima scelta per molte applicazioni crittografiche, dallo scambio di chiavi alle firme digitali.

Tutti questi algoritmi sono esposti ad attacchi da parte di algoritmi quantistici, poiché è possibile sviluppare soluzioni ai problemi matematici che ne costituivano il presupposto progettuale. Un esempio è l'algoritmo di Shor. Pertanto dovranno essere sostituiti da crittosistemi asimmetrici quantum-safe più resistenti agli attacchi quantistici e al contempo sicuri anche rispetto agli algoritmi classici. I problemi matematici su cui si basano possono essere risolti in modo efficiente dai computer quantistici, rendendo necessario lo sviluppo di crittosistemi asimmetrici quantum-safe in grado di resistere agli attacchi quantistici pur mantenendo la sicurezza classica.