The ElGamal discrete log cryptosystem reference article from the English Wikipedia on 24-Jul-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

ElGamal discrete log cryptosystem

The ElGamal algorithm is an asymmetric key encryption algorithm for public key cryptography which is based on discrete logarithms. It was created by Taher ElGamal. The ElGamal algorithm is used in the free GNU Privacy Guard software, recent versions of PGP, and other crypto systems. It can be used for encryption/decryption, and also for digital signatures. NSA's Digital Signature Algorithm is based on ElGamal, and is very similar.

The algorithm works as follows:

• Alice calculates for for a large prime , and publishes as the public key. is retained as her private key.
• If Bob wants to send a message to Alice, he first converts his message into a number .
• Bob then generates a random integer and calculates and and sends to Alice.
• Alice can then reconstruct the message by calculating .

Note that:

If a message needs to be split up into multiple 's, several values of can be transmitted. Also, in general, we do not have to use , but can use any group as long as it is cyclic.

Breaking ElGamal is, in most cases, at least as hard as solving the discrete logarithm problem. If the discrete logarithm problem could be solved efficiently, then ElGamal could be broken. However, it remains possible that there may be some way to break ElGamal without having to solve that problem.

This is the "ElGamal discrete log cryptosystem" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.