ElGamal
# 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:

    $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 $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:

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

Dopodiché genera il messaggio da inviare come una coppia $(C_1,C_2)$ formata da:

    $C_{1}=\alpha ^{k}{\bmod {q}}$
    $C_{2}=K_{A}M{\bmod {q}}$

### Decifratura

Il testo cifrato $(C_1,C_2)$ 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

Si ha che $K_A$ = $K_B$ 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 $K_A$ = $K_B$ = K si ha che:

    $M=(C_{2}\cdot K_{B}^{-1}){\bmod {q}}$
       $=((K_{A}M{\bmod {q}})K_{B}^{-1}){\bmod {q}}=$
       $=(K_{A}MK_{B}^{-1}){\bmod {q}}=$
       $=(KMK^{-1}){\bmod {q}}=$
       $=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.

