# 10.5 The ElGamal Public Key Cryptosystem

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:

1. Downloads 

2. Chooses a secret random integer  and computes 

3. Computes 

4. 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.

# 10.5.1 Security of ElGamal Ciphertexts

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).

# Proposition

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:

# Proposition

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 .