Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

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

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

Downloads $(p, α, β)$ $(p, α, β)$
Chooses a secret random integer $k$ $k$ and computes $r \equiv α^{k} (mod p)$ $r \equiv α^{k} (mod p)$
Computes $t \equiv β^{k} m (mod p)$ $t \equiv β^{k} m (mod p)$
Sends the pair $(r, t)$ $(r, t)$ to Bob

Bob decrypts by computing

\begin{matrix} t r^{- b} \equiv m & (mod p) . \end{matrix}

$\begin{matrix} t r^{- b} \equiv m & (mod p) . \end{matrix}$

This works because

\begin{matrix} t r^{- b} \equiv β^{k} m (α^{k})^{- b} \equiv (α^{b})^{k} m α^{- b k} \equiv m & (mod p) . \end{matrix}

$\begin{matrix} t r^{- b} \equiv β^{k} m (α^{k})^{- b} \equiv (α^{b})^{k} m α^{- b k} \equiv m & (mod p) . \end{matrix}$

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

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

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

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

\begin{matrix} t_{1} / m_{1} \equiv β^{k} \equiv t_{2} / m_{2} & (mod p) . \end{matrix}

$\begin{matrix} t_{1} / m_{1} \equiv β^{k} \equiv t_{2} / m_{2} & (mod p) . \end{matrix}$

Since Eve knows $t_{1}$ $t_{1}$ and $t_{2}$ $t_{2}$ , she computes $m_{2} \equiv t_{2} m_{1} / t_{1} (mod p)$ $m_{2} \equiv t_{2} m_{1} / t_{1} (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$ $m$ corresponding to an RSA ciphertext $c$ $c$ . It is easy to verify her claim: Compute $m^{e} (mod n)$ $m^{e} (mod n)$ and check whether this equal $c$ $c$ . Now suppose instead that Eve claims to possess the message $m$ $m$ corresponding to an ElGamal encryption $(r, t)$ $(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$ $p$ can be used to decide the validity of mod $p$ $p$ ElGamal ciphertexts, and a machine that decides the validity of mod $p$ $p$ ElGamal ciphertexts can be used to solve Decision Diffie-Hellman problems mod $p$ $p$ .

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

p, α, β, (α^{x}, α^{x y}), 1

$p, α, β, (α^{x}, α^{x y}), 1$

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

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

Proof. If we have a machine $M_{3}$ $M_{3}$ that can decrypt all ElGamal ciphertexts, then input $β \equiv α^{x}$ $β \equiv α^{x}$ (so $a = x$ $a = x$ ) and $r \equiv α^{y}$ $r \equiv α^{y}$ . Take any nonzero value for $t$ $t$ . Then $M_{3}$ $M_{3}$ outputs $m \equiv t r^{- a} \equiv t α^{- x y}$ $m \equiv t r^{- a} \equiv t α^{- x y}$ . Therefore, $t m^{- 1} (mod p)$ $t m^{- 1} (mod p)$ yields the solution $α^{x y}$ $α^{x y}$ to the computational Diffie-Hellman problem.

Conversely, suppose we have a machine $M_{4}$ $M_{4}$ that can solve computational Diffie-Hellman problems. If we have an ElGamal ciphertext $(r, t)$ $(r, t)$ , then we input $α^{x} = α^{a} \equiv β$ $α^{x} = α^{a} \equiv β$ and $α^{y} \equiv α^{k} \equiv r$ $α^{y} \equiv α^{k} \equiv r$ . Then $M_{4}$ $M_{4}$ outputs $α^{x y} \equiv α^{a k}$ $α^{x y} \equiv α^{a k}$ . Since $m \equiv t r^{- a} \equiv t α^{- a k}$ $m \equiv t r^{- a} \equiv t α^{- a k}$ , we obtain the plaintext $m$ $m$ .

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 10.5 The ElGamal Public Key Cryptosystem

Create new playlist

Sign In

Sign Up

Table of Contents for
10.5 The ElGamal Public Key Cryptosystem