Cryptosystème de ElGamal

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le cryptosystème d'ElGamal, ou chiffrement El Gamal (ou encore système d'El Gamal ...) est un algorithme de cryptographie asymétrique fondé sur le problème du logarithme discret. 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, mais aussi la signature électronique, par exemple l'algorithme DSA du NIST.

L'algorithme est décrit pour un groupe multiplicatif ℤp*, p premier, mais n'importe quel groupe cyclique fini pour lequel le problème du logarithme discret est difficile convient. On suppose que Bob veut envoyer un message à Alice (le chiffrement est asymétrique).

  • Alice calcule deux clés, une clé publique et une clé privée : elle choisit d'abord p suffisamment grand pour que le calcul du logarithme discret soit infaisable pratiquement dans le groupe multiplicatif ℤp*, g un générateur de ce groupe et un entier naturel s, s < p, puis calcule h = gs mod p. L'entier s est la clé secrète, le triplet (p, g, h) la clé publique. Cette dernière seule est connue de Bob.
  • Le message clair de Bob est supposé être un m dans ℤp*. Bob choisit aléatoirement un nombre entier k puis calcule (dans ℤp*) c1 = gk et c2 = mhk. Le message chiffré est le couple (c1,c2) que Bob envoie à Alice.
  • Alice peut déchiffrer le message reçu en calculant m = c2 / c1s. En effet :
\frac{c_2}{{c_1}^s} = \frac{m\cdot h^k}{g^{ks}} = \frac{m\cdot h^{k}}{h^{k}} = m

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.