|
ElGamalFrom CryptoDox, The Online Encyclopedia on Cryptography and Information SecurityThe 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. The inventor, Taher ElGamal, did not apply for a patent on his invention. 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 creation as in RSA. DSA 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.
Generating the ElGamal public keyAs with Diffie-Hellman, Alice and Bob have a (publicly known) prime number p and a generator g. Alice chooses a random number a and computes A = ga. Bob does the same and computes B = gb. Alice's public key is A and her private key is a. Similarly, Bob's public key is B and his private key is b. Encrypting and decrypting messagesIf Bob now wants to send a message m to Alice, he randomly picks a number k which is smaller than p. He then computes: c1 = gk mod p c2 = Ak * m mod p and sends c1 and c2 to Alice. Alice can use this to reconstruct the message m by computing c1-a * c2 mod p = m because c1-a * c2 mod p = (gk)-a * Ak * m = g-a * k * Ak * m = (ga)-k * Ak * m = A-k * Ak * m = 1 * m = m ReferencesSee AlsoExternal Links
|