ElGamal encryption

How it works

ElGamal encryption turns a Diffie-Hellman exchange into public key encryption. The private key is $x$ and the public key $h = g^x \bmod p$. To encrypt $m$, choose a fresh random nonce $k$ and send $c_1 = g^k$ and $c_2 = m \cdot h^k \bmod p$. The value $s = h^k = g^{xk}$ acts as a one-time mask; the receiver recomputes it as $s = c_1^x$ and divides it out: $m = c_2 \cdot s^{-1} \bmod p$.

The scheme is randomized, so encrypting the same message twice gives different ciphertexts. Its security (IND-CPA) rests on the decisional Diffie-Hellman assumption, which fails in all of $\mathbb{Z}_p^*$ (the Legendre symbol leaks information), so in practice messages are encoded in a subgroup of prime order, or an elliptic curve group is used.

The nonce must never be reused: two ciphertexts with the same $k$ share the mask $s$, and one known plaintext reveals the other. ElGamal is also multiplicatively homomorphic: multiplying two ciphertexts componentwise gives an encryption of $m_1 m_2$.