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:
Analogamente l'utente B genera la sua chiave pubblica:
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 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:
Dopodiché genera il messaggio da inviare come una coppia (C1,C2) formata da:
Decifratura Il testo cifrato (C1,C2) viene inviato a B il quale recupera M nel seguente modo:
Correttezza Si ha che KA = KB in quanto:
Siccome KA = KB = K si ha che:
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
Phong Q. Nguyen "Can We Trust Cryptographic Software? Cryptographic Flaws in GNU Privacy Guard v1.2.3." EUROCRYPT 2004: 555–570
Categoria:Crittosistemi asimmetrici Categoria:Protocolli di scambio della chiave