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
modificaCi sono tre fasi in questo algoritmo:
Generazione delle chiavi
modificaL'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
modificaL'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
modificaIl testo cifrato (C1,C2) viene inviato a B il quale recupera M nel seguente modo:
Correttezza
modificaSi ha che KA = KB in quanto:
Siccome KA = KB = K si ha che:
Conclusioni
modificaTutte 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
modifica- Vulnerabilità delle firme ElGamal