The ElGamal Encryption

The ElGamal Encryption

13 July 2021

The ElGamal Encryption is an asymmetric key encryption which means it uses public and private keys. The public key is ment to encrypt a message and the private key can then be used to decrypt it again. The choice of these keys is based on the pulic key system of the Diffie-Hellman key exchange.

The alorithm is prooven to be IND-CPA secure under the assumption that the Diffie-Hellman problem (the solving of the discrete logarithm) is nearly impossible to solve.

But let's not get into too much technical detail and have a look at the actual algorithm and a few examples.

The Algorithm

The initial set-up for the ElGamal encryption is similar to the Diffie-Hellman Key Exchange. Let's assume that Alice wants to send an encrypted message to Bob. First, they have to agree on some common parameters: a cyclic group GG of order qq with generator gg.1^1 Then each of them needs to choose a secret key. Alice picks her secret key aGa\in G, calculates QA=gaQ_A = g^a and sends her public key QAQ_A to Bob. He chooses his private key BGB\in G simultaneously and calculates his public key QB=gbQ_B = g^b.

Before Alice can send her message MM she needs to map it to an element mGm\in G (or several elements miGm_i\in G). She then chooses a random number yGy\in G and calculates

c=gyc = g^y


d=mQBy.d = m\cdot Q_B^y.

The tuple (c,d)(c, d) then represents the encrypted message and Alice can send it to Bob.

Bob can now decipher the message (c,d)(c, d) as follows:

dcqb=mQBy(gy)qb=m(gb)y(gy)qb=m(gy)b(gy)qb=me    (further explanation here2)=m\begin{align} d\cdot c^{q-b} &= m\cdot Q_B^y\cdot (g^y)^{q-b}\\ &= m\cdot (g^b)^y\cdot (g^y)^{q-b}\\ &= m\cdot (g^y)^b\cdot (g^y)^{q-b}\\ &= m\cdot e\;\;\textrm{(further explanation here}^2\textrm{)}\\ &= m \end{align}

Example of a Simple Mapping Algorithm

Before presenting an example of the ElGamal Algorithm, it might be interesting to see how a text message MM could be converted to elements in GG.

To make it as easy as possible, we will use the cyclic group G=Z/29ZG=\Z/29\Z of order q=29q = 29 and consider only capital letters, space ' ', period '.' and comma ',' as possible signs in out message MM. Furthermore, we identify the signs as follows: A=0A = 0, B=1B = 1, C=2C = 2, ..., ' ' =26= 26 , .=27. = 27 and ,=28, = 28.

If Alice now wanted to send the message "HELLO BOB.", she would use "M=7411111426114127M=7\: 4\: 11\: 11\: 14\: 26\: 1\: 14\: 1\: 27" for the ElGamal Encryption.

Of course, not every cyclic group GG has such a convenient and obivious mapping algorithm. In addition, the group Z/29Z\Z/29\Z is far too small to guarantee any kind of security for the ElGamal algorithm. In reality the prime numbers (here 2929) are much bigger and therefore other and more complicated mapping algorithms are used.

ElGamal Encryption in Z/11Z\Z/11\Z

As an example we choose the finite group G=Z/11ZG=\Z/11\Z of order q=10q=10 with the generator g=2g=2.3^3 g=2g=2 is a generator of the group Z/11Z\Z/11\Z because

Z/11Z={0,1,2,3,4,5,6,7,8,9,10}={0,20,21,28,22,24,29,27,23,26,25}.4\Z/11\Z = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} = \{0, 2^0, 2^1, 2^8, 2^2, 2^4, 2^9, 2^7, 2^3, 2^6, 2^5\}.^4

Now, that the basic framework is defined, Bob chooses his secret key b=3Z/11Zb=3\in\Z/11\Z, calculates

QB=ga=23=8mod11Q_B=g^a=2^3=8\: mod\: 11

and sends QBQ_B to Alice. She has already mapped a message MM to m=7Z/11Zm=7\in\Z/11\Z and chooses a random number y=4Z/11Zy=4\in\Z/11\Z. Then, Alice encrypts her message mm as follows:

c=gy=24=16=5mod11d=mQBy=784=28672=6mod11.\begin{align} &c=g^y=2^4=16=5\: mod\: 11\\ &d=m\cdot Q_B^y=7\cdot 8^4=28672=6\: mod\: 11. \end{align}

Alice sends the tuple (5,6)(5, 6) to Bob and he deciphers it with the help of bb:

dcqb=65103=657=678125=468750=7mod11=m\begin{align} d\cdot c^{q-b} &= 6\cdot 5^{10-3}\\ &=6\cdot 5^7\\ &=6\cdot 78125\\ &=468750\\ &=7\: mod\: 11\\ &=m \end{align}

These examples are certainly insecure and not appropriate for modern cybersecurity. Nevertheless, the method is definitley used by big internet applications. Like the Diffie-Hellman Key Exchange, the ElGamal encryption can also be used in different mathematical environments or can even be used as a base for a digital signature algorithm.

1^1 A cyclic group GG is a group generated by some element gg with G=g={gkkZ}{e}G=\langle g\rangle = \{g^k|k\in\Z \}\cup\{e\}. GG has order qq if G=g={e,g,g2,...,gq1}G=\langle g\rangle = \{e, g, g^2, ..., g^{q-1}\} and gi=gjg^i=g^j whenever i=jmodqi=j\: mod\: q.

2^2 In a cyclic group of order qq the inverse of xyx^y can be written as xqyx^{q-y} since xyxqy=xy+qy=xq=x0=1x^y\cdot x^{q-y}=x^{y+q-y}=x^q=x^0=1 with 0=qmodq0=q\: mod\: q.

3^3 Note that g=2g=2 is not the only possible generator. g=6g=6, g=7g=7, or g=8g=8 could also be used.

4^4 The neutral element ee is here represented through e=0e=0.