The Elgamal Cryptography Algorithm | Baeldung on Computer Science

1. Overview

In this tutorial, we present the Elgamal cryptographic algorithm. It uses asymmetric cryptography to encrypt messages.

2. Symmetric Cryptography

In symmetric cryptography, we use a secret key $k$ to apply an encryption algorithm $e_k(\cdot)$ to a message $m$ . Consequently, the algorithm’s output is cipher text $c=e_k(m)$ .

Then, $c$ can be sent to any recipient while $m$ remains secret from anyone who doesn’t know $k$ ‘s value. However, knowing $k$ , we can apply the decryption algorithm $d_k(c)$ to the cipher text $c$ . Since decryption is the inverse of encryption, we have $d_k(e_k(m)) = m$ .

2.1. Applying Encryption and Decryption Algorithms

Let’s assume that Alice would like to send a secret message $m$ to her friend Bob. Therefore, Alice encrypts $m$ with $k$ , using some encryption algorithm $e_k(\cdot)$ . She thus obtains a cipher text $c=e_k(m)$ and sends it to Bob via email, for instance.

Also, in the email, Alice mentions the name of the algorithm she used (Advanced Encryption Standard, for instance). Then, after receiving $c$ , Bob needs to know $k$ ‘s value to apply the AES decryption algorithm. But, the problem now is that $k$ needs to remain secret.

2.2. Key Distribution

As we’ve seen in the case of Alice and Bob, the distribution of secret keys is a challenge. In fact, it is one of the main difficulties in implementing a symmetric encryption algorithm in a network environment. Researchers have therefore developed key distribution algorithms tailored for different applications. Nevertheless, the key distribution problem was one of the main drives behind the development of asymmetric cryptography.

3. Asymmetric Cryptography

In asymmetric cryptography, keys come in pairs: a public key $k$ and its corresponding private key $k^{-1}$ . Each communicating party/agent owns a pair. Then, an agent, say Bob, shares the value of his public key $k_B$ with all other agents. This possibility of sharing public keys eliminates the problem of having to distribute secret keys over public communication channels. On the other hand, Bob is the only one who knows the value of his private key $k_B^{-1}$ .

If Alice wants to send a secret message $m$ to Bob, she encrypts it with Bob’s public key $k_B$ to obtain cipher text $c$ . In contrast, decryption uses private keys. So, Bob is the only one who can decrypt $c$ and get $m$ .

3.1. Algorithms of Asymmetric Cryptography

An algorithm that implements the general idea of asymmetric cryptography usually provides the following:

a method for generating a public/private key pair
an encryption function that uses the public key
a decryption function making use of the private key
a proof of the algorithm’s security

The Elgamal cryptographic algorithm relies on modular multiplication and discrete logarithms. This is what we’ll discuss in the following sections.

3.2. Modular Multiplication

Let’s consider an integer $a$ and a non-negative integer $n$ . Further, we can find two integers $q$ and $r$ : $a = q \times n + r$ and $0 \leq r \leq n-1$ . Then, we say that $a$ modulo $n = r$ , abbreviated as $a$ mod $n = r$ . For instance, we have $8$ mod $3 = 2$ since $8 = 3 \times 2 + 2$ .

Moreover, we can compute multiplication modulo $n$ , i.e., $a \times b$ mod $n$ . In multiplication, the multiplicative inverse of $a$ , denoted as $a^{-1}$ is a number such that $a \times a^{-1}$ mod $n = 1$ . Consider, for instance, multiplication modulo $10$ :

3.3. Existence of Multiplicative Inverses

We can notice that not all numbers have multiplicative inverses. In fact, only 3, 7, and 9 have multiplicative inverses mod $10$ . These are the rows colored in red, where $1$ appears as a result of multiplication. So, for instance, the multiplicative inverse of 3 is $3^{-1} = 7$ . This is because $3 \times 7 = 21 = 1$ mod $10$ .

Moreover, a known property of modular multiplication is that a number $a$ has a multiplicative inverse mod $n$ if and only if it is relatively prime to $n$ . Two numbers are relatively prime if they have no common factors other than 1. In fact, 3, 7, and 9 are relatively prime to 10. That’s why they are the only numbers in the table above with multiplicative inverses.

3.4. The Discrete Logarithm

If we multiply a number $a$ by itself $e$ times, we write $a^e$ mod $n = b$ . We call $a$ the base and $e$ the exponent or logarithm. Also, we write $\log_a(b)$ mod $n = e$ . The $\log(.)$ function here is the discrete logarithm since it deals with whole numbers. Moreover, there is no efficient algorithm to compute discrete logarithms. Therefore, computing discrete logarithms is difficult (computationally complex).

4. Elgamal Cryptographic Algorithm

The Elgamal algorithm makes use of the difficulty of computing discrete logarithms. This difficulty provides security to the algorithm, as we will show. But first, we need to introduce the concept of a primitive root.

4.1. Primitive Roots

Let’s consider the set $\mathbb{Z}_n^*$ of all numbers that have multiplicative inverses mod $n$ . As we mentioned previously, these numbers in the range from 0 to $n-1$ are relatively prime to $n$ . Therefore, as we already know, $\mathbb{Z}_{10}^* = \{1,3,5,7\}$ . Moreover, if $n$ is a prime $p$ , then $\mathbb{Z}_p^*=\{1, 2, \ldots, p-1\}$ since all numbers from $1$ to $p-1$ are relatively prime to $p$ .

Also, if there is a number $\alpha \in \mathbb{Z}_p^*$ such that the set $\{\alpha$ mod $p$ , $\alpha^2$ mod $p, \ldots \alpha^{p-1}$ mod $p \} = \mathbb{Z}_p^*$ , then $\alpha$ is called a primitive root of $p$ . Let’s assume $p=7$ , the table below shows that only $3$ and $5$ are its primitive roots.

$\begin{array}{c|cccccc|l} a & a^1 & a^2 & a^3 & a^4 & a^5 & a^6\\ \hline \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 &\\ 2 & 2 & 4 & 1 & 2 & 4 & 1 &\\ 3 & 3 & 2 & 6 & 4 & 5 & 1 & \text{All distinct values from } 1 ~ \text{to} ~ 6\\ 4 & 4 & 2 & 1 & 4 & 2 & 1 &\\ 5 & 5 & 4 & 6 & 2 & 3 & 1 & \text{All distinct values from } 1 ~ \text{to} ~ 6\\ 6 & 6 & 1 & 6 & 1 & 6 & 1 & \\ \hline \end{array}$

If $\alpha$ is a primitive root of $p$ , then, for any $1 \leq b \leq n-1$ , $\log_\alpha b$ mod $p$ is a distinct value. This shows in the table above: $\log_5(2)$ mod $7 = 4$ (a unique value). However, $\log_4(2)$ mod $7 = 2$ or $5$ . This follows from the definition of primitive roots.

4.2. Encryption

Let’s assume Alice would like to send a secret message $m$ to Bob. Bob has already chosen $p$ as a prime and $\alpha$ a primitive root of $p$ . He also chose a private key $k_B^{-1} = r$ , where $1 \leq r \leq p-1$ . Finally, Bob computed his public key $k_B = u = \alpha^r$ mod $p$ . Then, he sent Alice the values $p, \alpha, u$ over any public channel.

To encrypt $m$ , Alice applies the following algorithm:

$\begin{algorithm}[H] \setcounter{algocf}{0} \KwIn{$p, \alpha, u$ and $m$} \KwOut{Cipher texts $c_1$ and $c_2$} Choose a random value $x$, $1 \leq x \leq p-1$;\\ Compute $c_1 = \alpha^x$ mod $p$;\\ Compute $c_2 = m u^x$ mod $p$;\\ \Return $c_1, c_2$ \; \caption{Elgamal Encryption Algorithm} \end{algorithm}$

4.3. Decryption

To decrypt $m$ , Bob applies the following algorithm:

$\begin{algorithm}[H] \setcounter{algocf}{1} \KwIn{Cipher texts $c_1$ and $c_2$} \KwOut{Message $m$} Compute $c_1^r = \alpha^{rx}$ mod $p$;\\ Compute $c_2 (c_1^r)^{-1} = m u^x (\alpha^{rx})^{-1} = m \alpha^{rx} (\alpha^{rx})^{-1}$ mod $p = m$;\\ \Return $m$ \; \caption{Elgamal Decryption Algorithm} \end{algorithm}$

4.4. Analysis

As we already know, discrete logarithms are hard to compute. Therefore an intruder knowing the public information $p, \alpha, u$ will find it hard to compute the private key $r$ . This is because, to know $r$ , the intruder has to compute the discrete logarithm $\log_{\alpha} u$ mod $p$ .

5. Conclusion

In this tutorial, we talked about Elgamal cryptographic algorithm. We showed how to use the algorithm for both encryption and decryption.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex