The ElGamal algorithm is an asymmetric key encryption algorithm for public key cryptography which is based on discrete logarithms. The ElGamal algorithm is used in the free GNU Privacy Guard software, recent versions of PGP, and other crypto systems. It can be used for encryption/decryption, and also for digital signatures. NSA's Digital Signature Algorithm is based on ElGamal, and is very similar.
It works as follows:
KEY GENERATION. Choose a large prime p, such that the discrete logarithm problem in the cyclic group (Zp)× (consisting of the congruence classes of 1, 2, ..., p-1 under multiplication modulo p) is intractable. Choose a primitive root modulo p and call it g; then g generates the group (Zp)×. Choose a random k with 1 < k < p-1. Calculate h = gk mod p (with exponentiating by squaring). Then the public key is (p, g, h), and the private key is (p, g, k).
ENCRYPTION. To encrypt a message using the public key (p, g, h), first encode the message as a number m with 1 ≤ m ≤ p - 1 using a known reversible protocol. Then pick a random s with 1 < s < p-1 and calculate c1 = gs mod p and c2 = m*hs mod p. The cryptogram is then (c1, c2).
DECRYPTION. To recover the original message m from (c1, c2) using the private key (p, g, k), calculate c1-k*c2 mod p. This works because c1-k*c2 = (gs)-k * m*hs = (gk)-s * m*hs = h-s * m*hs = m mod p.
Elgamal can also be used to implement digital signatures, as follows:
KEY GENERATION. Same as for the encryption system above.
SIGNING. To sign the message m with the secret key (p, g, k) choose a random s with 1 < s < p-1 and s coprime to p-1 (in order that s has a multiplicative inverse modulo p-1). Calculate s1 = gs mod p and s2 = (m - ks1)s-1 mod (p-1). The signature is (s1, s2).
VERIFICATION. To verify the signature (s1, s2) of the message m with the public key (p, g, h), verify that the following congruence holds: hs1 * s1s2 = gm (mod p).
