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

Ogni utente A genera e rende nota una chiave pubblica $K^+_a$ = (p,σ,σ^amod p) dove:

• p numero grande primo (es. dell'ordine di 10¹⁰⁰);
• σ radice primitiva di p;
• a scelto a caso in maniera uniforme tra 1 ....(p-2), questo numero costituisce la vera chiave privata e deve essere mantenuto segreto;

Cifratura

Il mittente che vuole inviare un messaggio ad A, con m (messaggio) appartenente ad Z_p, sceglie a caso un numero k nell'intervallo 1....(p-2) e calcola il testo cifrato (y,Δ) dove

• y= σ^k mod p;
• Δ= m * ((σ)^a)^k mod p.

Decifratura

Il testo cifrato viene inviato ad A il quale recupera m nel seguente modo:

Ricevuta la coppia (y,Δ) applica y ^{− a}

dove:

y ^{− a}*Δ = m*σ^ak*(σ^k) ^{− a} (mod p) = m*σ^{ak − ak}=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 di σ^a oppure di σ^k mod p.

Ancora oggi non è conosciuto un algoritmo efficiente per calcolare tali valori.

Collegamenti esterni

Vulnerabilità delle firme ElGamal

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

Portale Crittografia

Portale Sicurezza informatica