chiffre ElGamal

codage ElGamal
cryptosystème d’ElGamal
chiffrement El Gamal
système d’El Gamal

CALCUL

Le cryptosystème de ElGamal, ou chiffrement El Gamal ou système d’El Gamal est un algorithme de cryptographie asymétrique (ou à clé publique) fondé sur le problème du logarithme discret. Il a été créé par Taher Elgamal.
L’algorithme est décrit pour un groupe multiplicatif Zp* avec p premier, mais n’importe quel groupe cyclique fini pour lequel le problème du logarithme discret est difficie convient. On suppose que Bob veut envoyer un message à Alice.
Alice choisit deux paramètres non-secrets : un nombre premier p et une racine primitive de p (un nombre g dont les puissances modulo p engendrent Zp– {0}).
Elle choisit aléatoirement un nombre a dans l’intervalle [1, . . , p-2 ] et calcule α = (g^a mod p).
Elle publie sa clé (p, g, α) et garde secrète sa clé a.
Bob, qui désire envoyer un message m à Alice, l’exprime sous la forme d’un nombre entre 0 et p-1 (quitte à le décomposer en sous-blocs de la bonne longueur).
Il choisit aléatoirement un nombre b dans l’intervalle [1, . . , p-2 ] et calcule β = (g^b mod p).
Il chiffre alors son message m en m’ = α^b • m mod p.
Il transmet enfin à Alice le couple (β, m’)
Pour déchiffrer le message de Bernard, Alice détermine le nombre x = p – 1 -a.
Elle calcule β^x • m’ mod p et retrouve le message m initial

Ce cryptosystème repose sur la difficulté de la résolution du logarithme discret.
Il présente l’avantage de faire appel à deux processus aléatoires (les choix de a et de b), mais présente l’inconvénient de générer des messages chiffrés particulièrement longs.

Cet algorithme est utilisé par le logiciel libre GNU Privacy Guard, de récentes versions de PGP, et d’autres systèmes de chiffrement. Il peut être utilisé pour le chiffrement, mais aussi la signature électronique , par exemple l’algorithme DSA du NIST.
Casser l’algorithme ElGamal est dans la plupart des cas au moins aussi difficile que de calculer le logarithme discret. Cependant, il est possible qu’il existe des moyens de casser l’algorithme sans résoudre le problème du logarithme discret.