Editing ElGamal encryption (section)

{{Short description|Public-key cryptosystem}}
{{Redirect|ElGamal|signature algorithm|ElGamal signature scheme}}

In [[cryptography]], the '''ElGamal encryption system''' is an [[asymmetric key encryption algorithm]] for [[public-key cryptography]] which is based on the Diffie–Hellman key exchange. It was described by [[Taher Elgamal]] in 1985.<ref>{{cite journal |author=Taher ElGamal |title=A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms |journal=IEEE Transactions on Information Theory |volume=31 |issue=4 |year=1985 |pages=469–472 |doi=10.1109/TIT.1985.1057074 |url=https://caislab.kaist.ac.kr/lecture/2010/spring/cs548/basic/B02.pdf|citeseerx=10.1.1.476.4791 |s2cid=2973271 }} (conference version appeared in [[CRYPTO]]'84, pp. 10–18)</ref> ElGamal encryption is used in the free [[GNU Privacy Guard]] software, recent versions of [[Pretty Good Privacy|PGP]], and other [[cryptosystem]]s. The [[Digital Signature Algorithm]] (DSA) is a variant of the [[ElGamal signature scheme]], which should not be confused with ElGamal encryption.

ElGamal encryption can be defined over any [[cyclic group]] <math>G</math>, like [[multiplicative group of integers modulo n|multiplicative group of integers modulo&nbsp;''n'']] if and only if ''n'' is 1, 2, 4, ''p''<sup>''k''</sup> or 2''p''<sup>''k''</sup>, where ''p'' is an odd prime and {{nowrap|''k'' > 0}}. Its security depends upon the difficulty of the [[Decisional_Diffie–Hellman_assumption|Decisional Diffie Hellman Problem]] in <math>G</math>.