ElGamal

L'algorithme ElGamal est un algorithme de cryptographie asymétrique basé sur les logarithmes discrets. Il a été crée par Taher ElGamal. Cet algorithme est utilisé par le logiciel libre GNU Privacy Guard, de récentes versions de PGP, et d'autres systèmes de chiffrement, et n'a jamais été sous la protection d'un brevet contrairement à RSA. Il peut être utilisé pour le chiffrement et la signature électronique. L'algorithme DSA du NIST est basé sur ElGamal.

L'algorithme fonctionne comme suit :

Alice calcule $h = g^x \,$ for $g, h\in \mathbb{Z}_p$ pour un grand nombre premier $p$ , et divulgue sa clé publique $(p, g, h)$ . La valeur $x$ est sa clé privée.
Si Bob veut envoyer un message à Alice, il convertit d'abord son message sous la forme d'un nombre $m\in \mathbb{Z}_p$ .
Bob génère un nombre entier $k$ aléatoirement et calcule $c 1 = g k$ et $c_2=m\cdot h^k$ . Il envoie $(c 1, c 2)$ à Alice.
Alice peut reconstruire le message initial $m$ en calculant $c_2/c_1^x$ .

On remarque que :

$\frac{c_2}{c_1^x} = \frac{m\cdot h^k}{g^{xk}} = \frac{m\cdot g^{xk}}{g^{xk}} = m$

Il n'est pas obligatoire d'utiliser $\mathbb{Z}_p$ . Tout groupe cyclique convient.

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.

Image manquante
Key-crypto-sideways.png

Portail Cryptologie - Accédez d'un seul coup d’œil à toute la série des articles « Cryptologie » de Wikipédia.

ElGamal

See also: ElGamal, Brevet, Chiffrement, Cryptanalyse, Cryptographie asymétrique, Digital Signature Algorithm, GNU Privacy Guard, Groupe (mathématiques)