# 5.6: The ElGamal Cryptosystem

- Page ID
- 28658

\(\newcommand{\RR}{\mathbb R}\)

\(\newcommand{\QQ}{\mathbb Q}\)

\(\newcommand{\ZZ}{\mathbb Z}\)

\(\newcommand{\Cc}{\mathcal C}\)

\(\newcommand{\Dd}{\mathcal D}\)

\(\newcommand{\Ee}{\mathcal E}\)

\(\newcommand{\Ff}{\mathcal F}\)

\(\newcommand{\Kk}{\mathcal K}\)

\(\newcommand{\Mm}{\mathcal M}\)

\(\newcommand{\Pp}{\mathcal P}\)

\(\newcommand{\ind}{\operatorname{ind}}\)

\(\newcommand{\ord}{\operatorname{ord}}\)

As mentioned in the previous section, exponentiation in mod \(p\), where \(p\) is a prime known to the public, is a good candidate one-way function: It is fast (feasible) in the forward direction; its inverse, being discrete log with respect to a primitive root \(r\) mod \(p\) is thought to be infeasible – even when that root is known to the public. This was behind the security of DHKE, and now we discuss how to use this one-way function to set up a more usual public-key cryptosystem: the ElGamal Cryptosystem.

The RSA public-key cryptosystem did its actual encryption by exponentiation in mod \(n=pq\). The decryption then was by exponentiation with the multiplicative inverse in mod \(\phi(n)\) of the encryption exponent. The owner of the private key – \((p,\ q)\) – knows also the decryption exponent, entirely because \(\phi(n)\) can be computed.

Similarly, ElGamal uses an elementary arithmetic operation – multiplication of a numerical form of the message by a random number in some mod – to do the scrambling needed for encryption. Enough information is also passed along in the ciphertext so that the intended recipient, who knows the value of a certain discrete log, can cancel out this scrambling multiplication. Here are the details:

Definition: ElGamal Cryptosystem

To start, Alice picks a large prime \(p\), a primitive root \(r\) mod \(p\), and a secret value \(\alpha\in\NN\) satisfying \(2\le\alpha\le p-1\). She computes the value \(a=r^\alpha\) and then posts her **ElGamal public** [**encryption**] **key** \((p,r,a)\) on her website.

Alice’s **ElGamal private** [**decryption**] **key** is \((p,r,\alpha)\). The association of decryption to encryption keys is by \(\Ee:(p,r,\alpha)\mapsto(p,r,r^\alpha)\).

The message space is \(\Mm=\{m\in\ZZ\mid 2\le m\le p-1\}\), which we will assume can be interpreted as meaningful messages encoded numerically by some widely known scheme.

Say Bob wishes to send Alice the cleartext \(m\in\Mm\). For each new such message \(m\), he generates a random number \(\beta\in\NN\) such that \(2\le\beta\le p-2\) and builds the ciphertext for **ElGamal encryption** as the two pieces \[c=e_{(p,r,a)}(m)=(r^\beta\pmod*{p},\ m\cdot a^\beta\pmod*{p})\ .\]

When Alice gets the ciphertext \(c=(c_1,c_2)\), she can recover the cleartext by **ElGamal decryption** \[d_{(p,r,\alpha)}(c_1,c_2) = c_2\cdot c_1^{p-1-\alpha}\ .\]

All of the above parts together form the **ElGamal cryptosystem**.

We first need to know this is correct, in the sense that

Proposition \(\PageIndex{1}\)

With the notation as above in the Definition of ElGamal Cryptosystem, we have \[d_{(p,r,\alpha)}(e_{(p,r,a)}(m)) = m\quad\forall m\in\Mm\ .\]

**Proof**-
Just compute: \[\begin{aligned} d_{(p,r,\alpha)}(e_{(p,r,a)}(m)) &\equiv m\cdot a^\beta\pmod*{p}\cdot(r^\beta)^{p-1-\alpha}\pmod{p}\\ &\equiv m\cdot (r^\alpha)^\beta\cdot(r^\beta)^{p-1-\alpha}\pmod{p}\\ &\equiv m\cdot r^{\alpha\beta+\beta(p-1)-\alpha\beta}\pmod{p}\\ &\equiv m\cdot (r^{p-1})^\beta\pmod{p}\\ &\equiv m\cdot 1^\beta\pmod{p}\\ &\equiv m\pmod{p}\end{aligned}\] Note that the power \(p-1-\alpha\) as the exponent of the \(c_1\) term in decryption is to make \((c_1^{-1})^\alpha\) without using negative powers, by applying Theorem 5.1.2.

Graphically:

**ElGamal Cryptosystem:**

Alice | on public network | Bob |

pick a prime \(p\) | ||

find a primitive root \(r\) | ||

choose \(\alpha\ \mid\ 2\le\alpha\le p-1\) | ||

compute \(a=r^\alpha\pmod{p}\) | ||

publish public key | \(\rightarrowtail(p,r,a)\) | download public key |

given message \(m\in\Mm\) | ||

(so \(2\le m\le p-1\)) | ||

choose \(\beta\ \mid\ 2\le\beta\le p-2\) | ||

compute \(c_1=r^\beta\pmod*{p}\) | ||

and \(c_2=m\cdot a^\beta\pmod*{p}\) | ||

receive ciphertext | \((c_1,c_2)\leftarrowtail\) | transmit ciphertext |

compute cleartext | ||

\(m = c_2\cdot c_1^{p-1-\alpha}\) |

There is a nice digital signature algorithm associated with ElGamal:

Definition: ElGamal Signature

Suppose Alice has ElGamal private key \((p,r,\alpha)\) and wishes to digitally sign the message \(m\in\Mm\). She first chooses a random \(\gamma\in\NN\) satisfying \(1<\gamma<p-1\) and \(\gcd(\gamma,p-1)=1\).

The digital signature on \(m\) is \((r^\gamma\pmod*{p},\gamma^{-1}\cdot(m-\alpha r^\gamma)\pmod*{p-1})\), where the inverse is taken in mod \(p-1\).

To verify the signature \((x,y)\) on message \(m\) using Alice’s public key \((p,r,a)\), Bob checks to see if \(a^x x^y\equiv r^m\pmod{p}\): if so, he accepts; if not, he rejects.

Again, we would like to know this does the right thing:

Proposition \(\PageIndex{2}\)

Using the notation as above, Bob will accept all signed messages produced by Alice.

**Proof**-
Assuming the signed message \((m,x,y)\) was produced by Alice as above, we compute: \[\begin{aligned} a^x x^y &\equiv a^{r^\gamma} (r^\gamma)^{\gamma^{-1}(m-\alpha r^\gamma)}\pmod{p}\\ &\equiv (r^\alpha)^{r^\gamma} (r^\gamma)^{\gamma^{-1}(m-\alpha r^\gamma)}\pmod{p}\\ &\equiv r^{\alpha r^\gamma+\gamma\gamma^{-1}(m-\alpha r^\gamma)}\pmod{p}\\ &\equiv r^{\alpha r^\gamma+m-\alpha r^\gamma}\pmod{p}\\ &\equiv r^m\pmod{p}\end{aligned}\] So Bob will accept.

Graphically:

**ElGamal Digital Signatures:**

Alice | on public network | Bob |

find prime \(p\) and | ||

primitive root \(r\) | ||

choose \(\alpha\ \mid\ 2\le\alpha\le p-1\) | ||

compute \(a=r^\alpha\pmod{p}\) | ||

publish public key | \(\rightarrowtail(p,r,a)\) | download public key |

given message \(m\in\Mm\) | ||

(so \(2\le m\le p-1\)) | ||

pick random \(\gamma\) s.t. \(1<\gamma<p-1\) | ||

and \(\gcd(\gamma,p-1)=1\) | ||

compute \(s_1=r^\gamma\pmod*{p}\) and | ||

\(s_2=\gamma^{-1}\cdot(m-\alpha r^\gamma)\pmod*{p-1}\) | ||

transmit signed message | \(\rightarrowtail(m,s_1,s_2)\) | receive signed message |

if \(a^{s_1}\cdot s_1^{s_2}\equiv r^m\pmod*{p}\) | ||

accept | ||

otherwise, | ||

reject |

Exercise \(\PageIndex{1}\)

1. You instructor still likes the prime \(p=11717\) with primitive root \(r=103\) from an earlier exercise (Exercise 5.5.1(2)) on DHKE. In addition, your instructor has calculated the value \(a=1020\) to complete an ElGamal public key \((p,r,a)=(11717,103,1020)\).

Using this public key, you want to send a message to your instructor, which should consist of the number \(42\) (it is, after all, the answer to “life, the universe, and everything”). What ciphertext will you send? Show your work!

2. Now your instructor wants to send you your grade on a recent test by e-mail, and to prove that this e-mail does in fact originate with your instructor, the email contains both the score value of \(97\) and the addendum “This score value signed with an ElGamal Digital signature using my public key [the same instructor’s public key as above in Exercise 5.6.1(1) being \((p,r,a)=(11717,103,1020)\)]; the signature has the value \((6220, 10407)\).”

Do you accept this as truly coming from your instructor? Show your work!

3. Create an ElGamal public key and e-mail it to your instructor. Wait for a reply message which is ElGamal encrypted, then mail the cleartext back to your instructor.

Also, use your public key to sign the number (=message) \(17\). Send the signed number to your instructor and wait to hear if the signature is accepted or not.