title: ElGamal
text: # 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.
  
  