The ElGamal system [Elg85] is a public-key cryptosystem based on the discrete logarithm problem. It consists of both encryption and signature algorithms. The encryption algorithm is similar in nature to the Diffie-Hellman key agreement protocol (see Question 24).
The system parameters consist of a prime p and an integer g, whose powers modulo p generate a large number of elements, as in Diffie-Hellman. Alice has a private key a and a public key y, where y = ga (mod p). Suppose Bob wishes to send a message m to Alice. Bob first generates a random number k less than p. He then computes
y1 = gk (mod p) and y2 = m
yk,
where denotes the bit-wise exclusive-or. Bob sends (y1
,y2) to Alice. Upon receiving the ciphertext, Alice computes
m = (y1a mod p) y2 .
The ElGamal signature algorithm is similar to the encryption algorithm in that the public key and private key have the same form; however, encryption is not the same as signature verification, nor is decryption the same as signature creation as in RSA (see Question 8). DSA (see Question 26) is based in part on the ElGamal signature algorithm.
Analysis based on the best available algorithms for both factoring
and discrete logarithms shows that RSA and ElGamal have similar
security for equivalent key lengths. The main disadvantage of
ElGamal is the need for randomness, and its slower speed (especially
for signing). Another potential disadvantage of the ElGamal system
is that message expansion by a factor of two takes place during
encryption. However, such message expansion is negligible if the
cryptosystem is used only for exchange of secret keys.