Elgamal discrete logarithm 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 encryption algorithm works as follows:
- Alice calculates <math>h = g^x<math> for <math>g, h\in \mathbb{Z}_p<math> for a large prime <math>p<math>, and publishes <math>(p, g, h)<math> as the public key. <math>x<math> is retained as her private key.
- If Bob wants to send a message to Alice, he first converts his message into a number <math>m\in \mathbb{Z}_p<math>.
- Bob then generates a random integer <math>k<math> and calculates <math>c_1=g^k<math> and <math>c_2=m\cdot h^k<math> and sends <math>(c_1,c_2)<math> to Alice.
- Alice can then reconstruct the message <math>m<math> by calculating <math>c_2/c_1^x<math>.
Note that:
<math>\frac{c_2}{c_1^x} = \frac{m\cdot h^k}{g^{xk}} = \frac{m\cdot g^{xk}}{g^{xk}} = m<math>
If a message needs to be split up into multiple <math>m<math>'s, several values of <math>c_2<math> can be transmitted. Also, in general, we do not have to use <math>\mathbb{Z}_p<math>, but can use any group as long as it is cyclic.
ElGamal is a simple example of a semantically secure asymmetric key encryption algorithm. It is probabilistic, meaning that a single plaintext can be encrypted to many possible ciphertexts, with the consequence that a general ElGamal encryption produces a 2:1 expansion from plaintext to ciphertext.
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.
References
- Taher ElGamal, "A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms", IEEE Transactions on Information Theory, v. IT-31, n. 4, 1985, pp469–472 or CRYPTO 84, pp10–18, Springer-Verlag.
- , contains a detailed description of ElGamal Algorithm in (PDF file).
