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 encryption algorithm works as follows:

Alice calculates h = g^x for $g, h\in \mathbb{Z}_p$ for a large prime p, and publishes (p,g,h) as the public key. x is retained as her private key.
If Bob wants to send a message to Alice, he first converts his message into a number $m\in \mathbb{Z}_p$ .
Bob then generates a random integer k and calculates c₁ = g^k and $c_2=m\cdot h^k$ and sends (c₁,c₂) to Alice.
Alice can then reconstruct the message m by calculating $c_2/c_1^x$ .

Note that:

$\frac{c_2}{c_1^x} = \frac{m\cdot h^k}{g^{xk}} = \frac{m\cdot g^{xk}}{g^{xk}} = m$

If a message needs to be split up into multiple m's, several values of c₂ can be transmitted. Also, in general, we do not have to use $\mathbb{Z}_p$ , 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.
Handbook of Applied Cryptography (http://www.cacr.math.uwaterloo.ca/hac/), contains a detailed description of ElGamal Algorithm in Chapter 8 (http://www.cacr.math.uwaterloo.ca/hac/about/chap8.pdf) (PDF file).

de:ElGamal-Kryptosystem pl:ElGamal

Categories: Asymmetric-key cryptosystems

This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia article. Browse Wikipedia for more information.