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 = 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 xor yk, where xor denotes the bit-wise exclusive-or. Bob sends (y1 ,y2) to Alice. Upon receiving the ciphertext, Alice computes m = (y1a mod p) xor 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 crea
