Il sistema crittografico di Elgamal
Il crittosistema di Elgamal è un metodo di crittografia asimmetrica basato sul problema del logaritmo discreto.
Un mittente cifra un messaggio usando la chiave pubblica del destinatario e un valore casuale, producendo una coppia di valori crittografati.
Solo il destinatario, con la propria chiave privata, può decifrare il messaggio originale. La sicurezza si basa sull'impossibilità pratica di risolvere il logaritmo discreto.
Come funziona
Si sceglie un campo finito \( F_q \) di riferimento e un elemento generatore $ g $ del campo \( F_q^* \).
Ogni utente \( A \) ha a propria disposizione due chiavi:
- Chiave privata: Un intero segreto \( a \) scelto casualmente (\( 0 < a < q-1 \))
- Chiave pubblica: Calcolata come \( g^a \)
Codifica del messaggio
Se l’utente \( B \) vuole inviare un messaggio \( P \) all’utente \( A \), procede così:
- Sceglie casualmente un intero \( k \). Il numero \( k \) deve essere \( < q \) e deve cambiare ogni volta che \( B \) invia un messaggio.
- Calcola due valori:
- \( y_1 = g^k \), dove \( g^k \) è un numero generato a partire da \( g \) e \( k \).
- \( y_2 = P \cdot g^{ak} \), cioè il messaggio \( P \) moltiplicato per \( g^{ak} \). Questo valore dipende dalla chiave pubblica \( g^a \) di \( A \). - Invia la coppia \( (y_1, y_2) \) all'utente destinatario \( A \). Questa coppia rappresenta il messaggio crittografato.
Decodifica del messaggio
Quando \( A \) riceve \( (y_1, y_2) \), può calcolare \( P \) (il messaggio originale) seguendo questi passi:
- Eleva \( y_1 \) alla sua chiave privata \( a \): \( (y_1)^a = (g^k)^a = g^{ak} \)
- Calcola il reciproco \( (g^{ak})^{-1} \) e lo usa per ricavare \( P \): $$ P = y_2 \cdot (g^{ak})^{-1} $$
La sicurezza si basa sul fatto che chi intercetta \( y_1 \) e \( y_2 \) non può calcolare \( g^{ak} \) facilmente, perché questo richiede risolvere il problema del logaritmo discreto che è computazionalmente difficile.
Inoltre, anche conoscendo \( g^a \) (chiave pubblica di \( A \)), non si può risalire ad \( a \) (chiave privata di \( A \)) senza risolvere lo stesso problema.
In sintesi, il messaggio è cifrato usando \( g^{ak} \), calcolabile solo da chi conosce la chiave pubblica di \( A \). Solo \( A \), conoscendo la propria chiave privata, può decifrare il messaggio.
Nota: Il sistema crittografico di Elgamal, come altri (ad esempio RSA), non è intrinsecamente indecifrabile. La sua sicurezza si basa sul fatto che, al momento, decifrare un messaggio richiederebbe un'enorme quantità di risorse computazionali e tempo. Tuttavia, con l'avanzare della tecnologia, non si può escludere che in futuro problemi oggi considerati irrisolvibili possano essere risolti in tempi brevi.
Un esempio pratico
Supponiamo che il campo \( F_q \) sia definito da un numero primo \( q = 23 \) e che l'elemento generatore \( g \) sia \( g = 5 \).
Nota. Sono valori appositamente bassi per rendere più comprensibile l'esempio. Nella realtà si lavora con numeri di centinaia di cifre.
L'utente \( A \) sceglie una chiave privata \( a = 6 \) ovvero un numero casuale tra \( 1 \) e \( q-1 \))
Poi calcola la chiave pubblica \( g^a \mod q \):
$$ g^a = 5^6 \mod 23 = 15625 \mod 23 = 8 $$
La chiave pubblica di \( A \) è quindi \( (g = 5, g^a = 8) \).
La cifratura del messaggio
L'utente \( B \) vuole inviare un messaggio \( P \) ad \( A \). Supponiamo che il messaggio \( P = 15 \).
Per prima cosa l'utente \( B \) sceglie un valore casuale \( k \). Ad esempio, sceglie \( k = 3 \).
Poi calcola il primo valore della coppia \( y_1 = g^k \mod q \)
$$ y_1 = 5^3 \mod 23 $$
$$ y_1 = 125 \mod 23 = 10 $$
E il secondo valore della coppia \( y_2 = P \cdot g^{ak} \mod q \)
Per calcolare \( g^{ak} \), usa la chiave pubblica di \( A \) ovvero \( g^a = 8 \)
$$ g^{ak} = (g^a)^k \mod q $$
$$ g^{ak} = 8^3 \mod 23 $$
$$ g^{ak} = 512 \mod 23 = 6 $$
In questo modo può ottenere il secondo valore della coppia \( y_2 \):
$$ y_2 = P \cdot g^{ak} \mod q $$
$$ y_2 = 15 \cdot 6 \mod 23 $$
$$ y_2 = 90 \mod 23 = 21 $$
A questo punto \( B \) invia ad \( A \) la coppia \( (y_1, y_2) = (10, 21) \).
La decifratura del messaggio
L'utente \( A \) ricevuta la coppia di valori \( (y_1, y_2) = (10, 21) \).
Per decifrarli calcola \( (y_1)^a \mod q \)
$$ (y_1)^a = 10^6 \mod 23 $$
$$ (y_1)^a = 1000000 \mod 23 = 6 $$
Poi calcola l’inverso di \( (y_1)^a \mod q \).
L’inverso di \( 6 \mod 23 \) è \( 4 \) perché \( 6 \cdot 4 \equiv 1 \mod 23 \).
Infine, recupera il messaggio originale \( P \) in chiaro.
$$ P = y_2 \cdot ((y_1)^a)^{-1} \mod q $$
$$ P = 21 \cdot 4 \mod 23 $$
$$ P = 84 \mod 23 = 15 $$
Il messaggio originale \( P = 15 \) è stato recuperato correttamente da \( A \).
Perché il logaritmo discreto non può essere risolto?
Il logaritmo discreto è difficile da risolvere a causa della natura dei calcoli modulari su numeri molto grandi, perché lo spazio di ricerca cresce esponenzialmente.
Per un problema del tipo \( g^x \mod p = y \), anche conoscendo \( g \), \( p \) e \( y \), trovare \( x \) richiede una ricerca esaustiva tra i possibili valori di \( x \), che cresce esponenzialmente con la dimensione di \( p \).
Questo problema non può essere risolto algoritmicamente in modo efficiente.
Non esistono algoritmi noti che possano risolvere il logaritmo discreto in tempo polinomiale per i numeri molto grandi, quelli tipicamente usati in crittografia dove \( p \) ha centinaia o migliaia di bit.
Nota. Esistono algoritmi in grado di risolvere il problema, noti come il baby-step giant-step o il Number Field Sieve, ma sono efficienti solo per numeri \( p \) relativamente piccoli. Questi algoritmi diventano impraticabili per numeri molto grandi \( p \).
Inoltre, se il numero \( p \) è scelto con attenzione (ad esempio, un grande numero primo), il gruppo moltiplicativo \( F_p \) ha proprietà che rendono il problema ancora più difficile.
Quindi, si verifica una asimmetria computazionale tra le operazioni.
In altre parole, il calcolo dell'esponenziazione modulare \( g^x \mod p \) è veloce, ma l'operazione inversa (trovare \( x \)) è un'operazione computazionalmente proibitiva.
Questa "asimmetria" è ciò che rende il logaritmo discreto ideale per la crittografia.
Tuttavia, è importante ricordare che non si tratta di un "problema impossibile", ma solo "computazionalmente difficile" con gli strumenti attuali.
La scoperta di algoritmi nuovi o l'arrivo di nuove tecnologie di calcolo, come i computer quantistici, potrebbe rendere il problema risolvibile in futuro.
E così via.
