ElGamal

Da Wikipedia, l'enciclopedia libera.

ElGamal è un sistema di cifratura a chiave pubblica, proposto dal ricercatore egiziano-americano Taher Elgamal nel 1985. Lo schema è basato sulla difficoltà del calcolo del logaritmo discreto.

Fasi della cifratura[modifica | modifica sorgente]

Ci sono tre fasi in questo algoritmo:

Generazione delle chiavi[modifica | modifica sorgente]

L'utente A genera e rende nota una chiave pubblica:

Y_A = (\alpha^{X_A} \bmod q)

Analogamente l'utente B genera la sua chiave pubblica:

Y_B = (\alpha^{X_B} \bmod q)

Dove:

  • q numero grande primo (es. dell'ordine di 10100), parametro globale.
  • α radice primitiva di q, parametro globale.
  • XA scelto a caso in maniera uniforme tra [1,(q-1)], che costituisce la chiave privata di A e deve essere mantenuto segreto.
  • XB scelto a caso in maniera uniforme tra [1,(q-1)], che costituisce la chiave privata di B e deve essere mantenuto segreto.

Cifratura[modifica | modifica sorgente]

L'utente A che vuole inviare un messaggio M a B, con M < q, sceglie a caso un numero k nell'intervallo [1,(q-1)] e calcola:

K_A = (Y_B)^k \bmod q

Dopodiché genera il messaggio da inviare come una coppia (C1,C2) formata da:

C_1 = \alpha^k \bmod q
C_2 = K_AM \bmod q

Decifratura[modifica | modifica sorgente]

Il testo cifrato (C1,C2) viene inviato a B il quale recupera M nel seguente modo:

K_B = (C_1^{X_B}) \bmod q
M = (C_2 \cdot K_B^{-1}) \bmod q

Correttezza[modifica | modifica sorgente]

Si ha che KA = KB in quanto:


K_A = (Y_B^{k}) \bmod q =
 = ((\alpha^{X_B} \bmod q)^{k}) \bmod q =
 = (\alpha^{kX_B}) \bmod q
K_B = (C_1^{X_B}) \bmod q =
 = ((\alpha^k \bmod q)^{X_B}) \bmod q =
 = (\alpha^{kX_B}) \bmod q

Siccome KA = KB = K si ha che:

M = (C_2 \cdot K_B^{-1}) \bmod q
 = ((K_A M \bmod q) K_B^{-1}) \bmod q =
 = (K_AMK_B^{-1}) \bmod q =
 = (KMK^{-1}) \bmod q =
 = M \bmod q = M

Conclusioni[modifica | modifica sorgente]

Tutte le operazioni coinvolte sono algoritmicamente fattibili, in maniera efficiente. I costi computazionali di cifratura e decifratura sono paragonabili all'RSA però abbiamo una espansione del testo cifrato di un fattore 2 rispetto al testo in chiaro.

Questo algoritmo è resistente ad attacchi di tipo crittanalitico, l'unico modo di ricavare informazioni segrete dai dati pubblici è effettuare il logaritmo discreto. Ancora oggi non è conosciuto un algoritmo efficiente per calcolare tali valori.

Collegamenti esterni[modifica | modifica sorgente]

Vulnerabilità delle firme ElGamal