### What is the
ElGamal Cryptosystem?

The ElGamal system 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* = *g*^{a}* *(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

*y*_{1} = *g*^{k}
(mod *p*) and *y*_{2} = *m* xor
*y*^{k},

where xor denotes the bit-wise
exclusive-or. Bob sends (*y*_{1} ,*y*_{2})
to Alice. Upon receiving the ciphertext, Alice computes

*m = (y*_{1}^{a}*
mod p) xor y*_{2} .

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.