An alternative algorithm developed by Taher ElGamal for performing public key cryptography, similar to RSA in intent and purpose. While RSA gets its security from the perceived intractability of factoring, the ElGamal scheme depends on the difficulty of calculating discrete logarithms in a finite group.
To generate a key pair for use in ElGamal, we choose any finite cyclic group G where the discrete logarithm problem is hard, such as the multiplicative group of integers Zp, the multiplicative group F2m of characteristic two, the group of points on an elliptic curve over a finite field (this is the basis of elliptic curve cryptography), among many others. Within that group (which probably should have a high cardinality), we choose a generator, α and a random integer k which is between 1 and the cardinality of G. The public key is thus (α, αa), and the private key is a.
Say Alice and Bob both have such private keys. If Alice wants to send a message to Bob, she should do the following:
- Obtain Bob's authentic public key (α, αa).
- Represent her message m to Bob as an element of the group G
- Choose a random integer k between 1 and the cardinality of G
- Compute γ = αk and δ = m * (αa)k
- Send the ciphertext c = (γ, δ) to Bob.
Now Bob has received the ciphertext c from Alice. For Bob to get Alice's message he must do the following:
- Since Bob knows a (it's his private key), he can calculate γa, which is just (αk)a, and compute this power's multiplicative inverse; let's call this value d.
- Now, to recover the plaintext m all he needs to do is compute d*δ.
It is very similar to the Diffie-Hellman key agreement scheme; in fact ElGamal can be thought of as using Diffie-Hellman to determine a session key αak, and then encrypting the message by multiplying it with the session key. Breaking the cryptographic system is thus equivalent to solving the Diffie-Hellman problem, which is thought to imply the ability to calculate discrete logarithms in a finite group.
One should never use the same random integer k to encrypt different messages. If the same random integer were used to encrypt two different messages m1 and m2, dividing the δ's of the resulting ciphertexts produces m1/m2, and m2 can thus be easily calculated if m1 were known.