ElGamal discrete log cryptosystem

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 (Z_p)^× (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 (Z_p)^×. Choose a random k with 1 < k < p-1. Calculate h = g^k 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 c₁ = g^s mod p and c₂ = m*h^s mod p. The cryptogram is then (c₁, c₂).

DECRYPTION. To recover the original message m from (c₁, c₂) using the private key (p, g, k), calculate c₁^-k*c₂ mod p. This works because c₁^-k*c₂ = (g^s)^-k * m*h^s = (g^k)^-s * m*h^s = h^-s * m*h^s = 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 s₁ = g^s mod p and s₂ = (m - ks₁)s^-1 mod (p-1). The signature is (s₁, s₂).

VERIFICATION. To verify the signature (s₁, s₂) of the message m with the public key (p, g, h), verify that the following congruence holds: h^s1 * s₁^s2 = g^m (mod p).

Security

Breaking ElGamal is believed to be, by most informed observers, generally as difficult as solving the discrete logarithm problem. If the discrete logarithm problem could be solved efficiently, then ElGamal could be broken. However, it remains possible that there may be some way to break ElGamal without having to solve that problem.

NB: When signing a message using the ElGamal algorithm, the per message random value s used may never be made public. Nor may the same s value be used to sign two different messages; doing so will enable an opponent to easily recover the secret key. (Proof left as exercise to reader.)