Cryptosystème de ElGamal

Un article de Wikipédia, l'encyclopédie libre.

L'algorithme ElGamal est un algorithme de cryptographie asymétrique basé sur les logarithmes discrets. Il a été créé 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 \,$ avec $g, h\in \mathbb{Z}_p$ pour un grand nombre premier $p$ , g étant un élément générateur de $\mathbb{Z}_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.