Elgamal

ElGamal is a public-key cryptosystem proposed by Taher ElGamal in 1985. It is based on the difficulty of the discrete logarithm problem in a cyclic group, commonly the multiplicative group of integers modulo a prime p, or an elliptic curve group (EC-ElGamal). The scheme provides probabilistic encryption and can also be used for digital signatures as a related construction.

Key generation in a typical ElGamal setup involves choosing a prime p, a generator g of the group modulo p, and a private key x chosen from {1,...,p−2}. The corresponding public key is h = g^x mod p. A public key is the tuple (p, g, h), and the private key is x.

Encryption requires encoding the plaintext m as an element of the group (often via a padding or encoding step) and choosing a random ephemeral value y. The ciphertext is the pair (c1, c2) where c1 = g^y mod p and c2 = m · h^y mod p. Decryption uses the private key x: compute m = c2 · (c1^x)^{-1} mod p, recovering the original message.

Security of ElGamal rests on the hardness of the discrete logarithm problem and, in probabilistic form, on the decisional Diffie-Hellman assumption in the chosen group. The basic scheme is malleable and not semantically secure for raw messages, so it is typically used within a hybrid encryption framework: a symmetric key is encrypted with ElGamal, and the data is encrypted with a symmetric cipher. Variants include ElGamal digital signatures and EC-ElGamal for efficiency.