The ElGamal public key system
The ElGamal cryptographic algorithm is a public key system like the Diffie-Hellman system. It is mainly used to establish common keys and not to encrypt messages.
Introduction
The ElGamal cryptographic algorithm is comparable to the Diffie-Hellman system. Although the inventor, Taher Elgamal, did not apply for a patent on his invention, the owners of the Diffie-Hellman patent (US patent 4,200,770) felt this system was covered by their patent. For no apparent reason everyone calls this the "ElGamal" system although Mr. Elgamal's last name does not have a capital letter 'G'.
A disadvantage of the ElGamal system is that the encrypted message becomes very big, about twice the size of the original message m. For this reason it is only used for small messages such as secret keys.
Generating the ElGamal public key
As 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 messages
If Bob now wants to send a message m to Alice, he randomly picks a number k which is smaller than p. He then computes:
and sends c1 and c2 to Alice. Alice can use this to reconstruct the message m by computing
because