ElGamal

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

Ci sono tre fasi in questo algoritmo:

Generazione delle chiavi

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

${\displaystyle Y_{A}=(\alpha ^{X_{A}}{\bmod {q}})}$

Analogamente l'utente B genera la sua chiave pubblica:

${\displaystyle Y_{B}=(\alpha ^{X_{B}}{\bmod {q}})}$

Dove:

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

Cifratura

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:

${\displaystyle K_{A}=(Y_{B})^{k}{\bmod {q}}}$

Dopodiché genera il messaggio da inviare come una coppia (C₁,C₂) formata da:

${\displaystyle C_{1}=\alpha ^{k}{\bmod {q}}}$

${\displaystyle C_{2}=K_{A}M{\bmod {q}}}$

Decifratura

Il testo cifrato (C₁,C₂) viene inviato a B il quale recupera M nel seguente modo:

${\displaystyle K_{B}=(C_{1}^{X_{B}}){\bmod {q}}}$

${\displaystyle M=(C_{2}\cdot K_{B}^{-1}){\bmod {q}}}$

Correttezza

Si ha che K_A = K_B in quanto:

${\displaystyle K_{A}=(Y_{B}^{k}){\bmod {q}}=}$

${\displaystyle =((\alpha ^{X_{B}}{\bmod {q}})^{k}){\bmod {q}}=}$

${\displaystyle =(\alpha ^{kX_{B}}){\bmod {q}}}$

${\displaystyle K_{B}=(C_{1}^{X_{B}}){\bmod {q}}=}$

${\displaystyle =((\alpha ^{k}{\bmod {q}})^{X_{B}}){\bmod {q}}=}$

${\displaystyle =(\alpha ^{kX_{B}}){\bmod {q}}}$

Siccome K_A = K_B = K si ha che:

${\displaystyle M=(C_{2}\cdot K_{B}^{-1}){\bmod {q}}}$

${\displaystyle =((K_{A}M{\bmod {q}})K_{B}^{-1}){\bmod {q}}=}$

${\displaystyle =(K_{A}MK_{B}^{-1}){\bmod {q}}=}$

${\displaystyle =(KMK^{-1}){\bmod {q}}=}$

${\displaystyle =M{\bmod {q}}=M}$

Conclusioni

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

Vulnerabilità delle firme ElGamal

• (EN) GnuPG's ElGamal signing keys compromised, su lists.gnupg.org.
• (EN) Phong Q. Nguyen "Can We Trust Cryptographic Software? Cryptographic Flaws in GNU Privacy Guard v1.2.3." EUROCRYPT 2004: 555–570