Guide

7.4 – ElGamal

Pubblicato nel 1985 da T. ElGamal, è una variante brevettata del Diffie-Hellman per lo scambio sicuro di messaggi. Come il D-H si basa sull’intrattabilità dei logaritmi discreti, è però più lento, e il maggior svantaggio è che raddoppia in grandezza l’informazione spedita, dettaglio poco importante se usato per lo scambio di chiavi segrete (l’appendice 4 fornisce l’algoritmo esatto), ma altrimenti lo rende molto poco pratico.

Il sistema di cifratura ElGamal è uno dei tanti schemi che utilizzavano la casualizzazione nel processo di codifica, che si può ottener in tre modi:

- Aumentando la grandezza dello spazio dei messaggi.

- Precludendo o diminuendo l’efficacia degli attacchi ad un messaggio scelto in virtù di un mappaggio uno-a-molti nella trasformazione da messaggio a testo cifrato.

- Precludendo o diminuendo l’efficacia degli attacchi statistici livellando la distribuzione di probabilità a priori degli ingressi.

Come il problema di fattorizzazione, anche il problema dei logaritmi discreti è considerato difficile (di tipo NP) e sebbene sia solo una congettura matematica, la possibilità di trovare una scorciatoia di tipo semplice (tipo P) per la sua soluzione è alquanto remota.