In Chapter 9, we studied a public key cryptosystem whose security is based on the difficulty of factoring. It is also possible to design a system whose security relies on the difficulty of computing discrete logarithms. This was done by ElGamal in 1985. This system does not quite fit the definition of a public key cryptosystem given at the end of Chapter 9, since the set of possible plaintexts (integers mod ) is not the same as the set of possible ciphertexts (pairs of integers mod ). However, this technical point will not concern us.
Alice wants to send a message to Bob. Bob chooses a large prime and a primitive root . Assume is an integer with . If is larger, break it into smaller blocks. Bob also chooses a secret integer and computes . The information is made public and is Bob’s public key. Alice does the following:
Chooses a secret random integer and computes
Sends the pair to Bob
Bob decrypts by computing
This works because
If Eve determines , then she can also decrypt by the same procedure that Bob uses. Therefore, it is important for Bob to keep secret. The numbers and are public, and . The difficulty of computing discrete logs is what keeps secure.
Since is a random integer, is a random nonzero integer mod . Therefore, is multiplied by a random integer, and is random mod (unless , which should be avoided, of course). Therefore, gives Eve no information about . Knowing does not seem to give Eve enough additional information.
The integer is difficult to determine from , since this is again a discrete logarithm problem. However, if Eve finds , she can then calculate , which is .
It is important that a different random be used for each message. Suppose Alice encrypts messages and for Bob and uses the same value for each message. Then will be the same for both messages, so the ciphertexts will be and . If Eve finds out the plaintext , she can also determine , as follows. Note that
Since Eve knows and , she computes .
In Chapter 21, we’ll meet an analog of the ElGamal method that uses elliptic curves.
Suppose Eve claims to have obtained the plaintext corresponding to an RSA ciphertext . It is easy to verify her claim: Compute and check whether this equal . Now suppose instead that Eve claims to possess the message corresponding to an ElGamal encryption . Can you verify her claim? It turns out that this is as hard as the decision Diffie-Hellman problem from Section 10.4. In this aspect, the ElGamal algorithm is therefore much different than the RSA algorithm (of course, if some randomness is added to an RSA plaintext through OAEP, for example, then RSA encryption has a similar property).
A machine that solves Decision Diffie-Hellman problems mod can be used to decide the validity of mod ElGamal ciphertexts, and a machine that decides the validity of mod ElGamal ciphertexts can be used to solve Decision Diffie-Hellman problems mod .
Proof. Suppose first that you have a machine that can decide whether an ElGamal decryption is correct. In other words, when given the inputs , the machine outputs “yes” if is the decryption of and outputs “no” otherwise. Let’s use this machine to solve the decision Diffie-Hellman problem. Suppose you are given and , and you want to decide whether or not . Let and . Moreover, let and . Input
into . Note that in the present setup, is the secret integer and takes the place of the . The correct decryption of is . Therefore, outputs “yes” exactly when is the same as , namely when . This solves the decision Diffie-Hellman problem.
Conversely, suppose you have a machine that can solve the decision Diffie-Hellman problem. This means that if you give inputs , then outputs “yes” if and outputs “no” if not. Let be the claimed decryption of the ElGamal ciphertext . Input as , so , and input as so . Input as . Note that is the correct plaintext for the ciphertext if and only if , which happens if and only if . Therefore, is the correct plaintext if and only if is the solution to the Diffie-Hellman problem. Therefore, with these inputs, outputs “yes” exactly when is the correct plaintext.
The reasoning just used can also be used to show that solving the computational Diffie-Hellman problem is equivalent to breaking the ElGamal system:
A machine that solves computational Diffie-Hellman problems mod can be used to decrypt mod ElGamal ciphertexts, and a machine that decrypts mod ElGamal ciphertexts can be used to solve computational Diffie-Hellman problems mod .
Proof. If we have a machine that can decrypt all ElGamal ciphertexts, then input (so ) and . Take any nonzero value for . Then outputs . Therefore, yields the solution to the computational Diffie-Hellman problem.
Conversely, suppose we have a machine that can solve computational Diffie-Hellman problems. If we have an ElGamal ciphertext , then we input and . Then outputs . Since , we obtain the plaintext .