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 $G$ of order $q$ with generator $g$.$^1$ Then each of them needs to choose a secret key. Alice picks her secret key $a\in G$, calculates $Q_A = g^a$ and sends her public key $Q_A$ to Bob. He chooses his private key $B\in G$ simultaneously and calculates his public key $Q_B = g^b$.

Before Alice can send her message $M$ she needs to map it to an element $m\in G$ (or several elements $m_i\in G$). She then chooses a random number $y\in G$ and calculates

and

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

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

Example of a Simple Mapping Algorithm

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

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

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

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

ElGamal Encryption in $\Z/11\Z$

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

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

and sends $Q_B$ to Alice. She has already mapped a message $M$ to $m=7\in\Z/11\Z$ and chooses a random number $y=4\in\Z/11\Z$. Then, Alice encrypts her message $m$ as follows:

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

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$ A cyclic group $G$ is a group generated by some element $g$ with $G=\langle g\rangle = \{g^k|k\in\Z \}\cup\{e\}$. $G$ has order $q$ if $G=\langle g\rangle = \{e, g, g^2, ..., g^{q-1}\}$ and $g^i=g^j$ whenever $i=j\: mod\: q$.

$^2$ In a cyclic group of order $q$ the inverse of $x^y$ can be written as $x^{q-y}$ since $x^y\cdot x^{q-y}=x^{y+q-y}=x^q=x^0=1$ with $0=q\: mod\: q$.

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

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