10.5 The ElGamal Public Key Cryptosystem – Introduction to Cryptography with Coding Theory, 3rd Edition

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 p) is not the same as the set of possible ciphertexts (pairs of integers (r, t) mod p). However, this technical point will not concern us.

Alice wants to send a message m to Bob. Bob chooses a large prime p and a primitive root α. Assume m is an integer with 0m<p. If m is larger, break it into smaller blocks. Bob also chooses a secret integer b and computes βαb (mod p). The information (p, α, β) is made public and is Bob’s public key. Alice does the following:

  1. Downloads (p, α, β)

  2. Chooses a secret random integer k and computes rαk (mod p)

  3. Computes tβkm (mod p)

  4. Sends the pair (r, t) to Bob

Bob decrypts by computing

trbm(mod p).

This works because

trbβkm(αk)b(αb)kmαbkm(mod p).

If Eve determines b, then she can also decrypt by the same procedure that Bob uses. Therefore, it is important for Bob to keep b secret. The numbers α and β are public, and βαb (mod p). The difficulty of computing discrete logs is what keeps b secure.

Since k is a random integer, βk is a random nonzero integer mod p. Therefore, tβkm (mod p) is m multiplied by a random integer, and t is random mod p (unless m=0, which should be avoided, of course). Therefore, t gives Eve no information about m. Knowing r does not seem to give Eve enough additional information.

The integer k is difficult to determine from r, since this is again a discrete logarithm problem. However, if Eve finds k, she can then calculate tβk, which is m.

It is important that a different random k be used for each message. Suppose Alice encrypts messages m1 and m2 for Bob and uses the same value k for each message. Then r will be the same for both messages, so the ciphertexts will be (r, t1) and (r, t2). If Eve finds out the plaintext m1, she can also determine m2, as follows. Note that

t1/m1βkt2/m2(mod p).

Since Eve knows t1 and t2, she computes m2t2m1/t1 (mod p).

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 m corresponding to an RSA ciphertext c. It is easy to verify her claim: Compute me (mod n) and check whether this equal c. Now suppose instead that Eve claims to possess the message m corresponding to an ElGamal encryption (r, t). 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 p can be used to decide the validity of mod p ElGamal ciphertexts, and a machine that decides the validity of mod p ElGamal ciphertexts can be used to solve Decision Diffie-Hellman problems mod p.

Proof. Suppose first that you have a machine M1 that can decide whether an ElGamal decryption is correct. In other words, when given the inputs p, α, β, (r, t), m, the machine outputs “yes” if m is the decryption of (r, t) and outputs “no” otherwise. Let’s use this machine to solve the decision Diffie-Hellman problem. Suppose you are given αx and αy, and you want to decide whether or not cαxy. Let β=αx and r=αy (mod p). Moreover, let t=c and m=1. Input

p, α, β, (αx, αxy), 1

into M1. Note that in the present setup, x is the secret integer b and αy takes the place of the rαk. The correct decryption of (r, t)=(αy, αxy) is trbcrxcαxy. Therefore, M1 outputs “yes” exactly when m=1 is the same as cαxy (mod p), namely when cαxy (mod p). This solves the decision Diffie-Hellman problem.

Conversely, suppose you have a machine M2 that can solve the decision Diffie-Hellman problem. This means that if you give M2 inputs p, α, αx, αy, c, then M2 outputs “yes” if cαxy and outputs “no” if not. Let m be the claimed decryption of the ElGamal ciphertext (r, t). Input βαb as αx, so x=b, and input rαk as αy so y=k. Input tm1 (mod p) as c. Note that m is the correct plaintext for the ciphertext (r, t) if and only if mtratαxy, which happens if and only if tm1αxy. Therefore, m is the correct plaintext if and only if ctm1 is the solution to the Diffie-Hellman problem. Therefore, with these inputs, M2 outputs “yes” exactly when m 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 p can be used to decrypt mod p ElGamal ciphertexts, and a machine that decrypts mod p ElGamal ciphertexts can be used to solve computational Diffie-Hellman problems mod p.

Proof. If we have a machine M3 that can decrypt all ElGamal ciphertexts, then input βαx (so a=x) and rαy. Take any nonzero value for t. Then M3 outputs mtratαxy. Therefore, tm1 (mod p) yields the solution αxy to the computational Diffie-Hellman problem.

Conversely, suppose we have a machine M4 that can solve computational Diffie-Hellman problems. If we have an ElGamal ciphertext (r, t), then we input αx=αaβ and αyαkr. Then M4 outputs αxyαak. Since mtratαak, we obtain the plaintext m.