In cryptography, the ElGamal encryption system is a public-key encryption algorithm based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1985. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of PGP, and other cryptosystems. 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 ${\displaystyle G}$, like multiplicative group of integers modulo n if and only if n is 1, 2, 4, p^k or 2p^k, where p is an odd prime and k > 0. Its security depends upon the difficulty of the Decisional Diffie Hellman Problem in ${\displaystyle G}$.

The algorithm can be described as first performing a Diffie–Hellman key exchange to establish a shared secret ${\displaystyle s}$, then using this as a one-time pad for encrypting the message. ElGamal encryption is performed in three phases: the key generation, the encryption, and the decryption. The first is purely key exchange, whereas the latter two mix key exchange computations with message computations.

The first party, Alice, generates a key pair as follows:

A second party, Bob, encrypts a message ${\displaystyle M}$ to Alice under her public key ${\displaystyle (G,q,g,h)}$ as follows:

Note that if one knows both the ciphertext ${\displaystyle (c_{1},c_{2})}$ and the plaintext ${\displaystyle m}$, one can easily find the shared secret ${\displaystyle s}$, since ${\displaystyle c_{2}\cdot m^{-1}=s}$. Therefore, a new ${\displaystyle y}$ and hence a new ${\displaystyle s}$ is generated for every message to improve security. For this reason, ${\displaystyle y}$ is also called an ephemeral key.

Alice decrypts a ciphertext ${\displaystyle (c_{1},c_{2})}$ with her private key ${\displaystyle x}$ as follows:

Like most public key systems, the ElGamal cryptosystem is usually used as part of a hybrid cryptosystem, where the message itself is encrypted using a symmetric cryptosystem, and ElGamal is then used to encrypt only the symmetric key. This is because asymmetric cryptosystems like ElGamal are usually slower than symmetric ones for the same level of security, so it is faster to encrypt the message, which can be arbitrarily large, with a symmetric cipher, and then use ElGamal only to encrypt the symmetric key, which usually is quite small compared to the size of the message.