ElGamal加密算法 | Baeldung中文网

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 to apply an encryption algorithm $e_k(\cdot)$ to a message . Consequently, the algorithm’s output is cipher text c=e_k(m) .

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

2.1. Applying Encryption and Decryption Algorithms

Let’s assume that Alice would like to send a secret message to her friend Bob. Therefore, Alice encrypts with , 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 , Bob needs to know ‘s value to apply the AES decryption algorithm. But, the problem now is that 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 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 to Bob, she encrypts it with Bob’s public key k_B to obtain cipher text . In contrast, decryption uses private keys. So, Bob is the only one who can decrypt and get .

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 and a non-negative integer . Further, we can find two integers and : $a = q \times n + r$ and $0 \leq r \leq n-1$ . Then, we say that modulo n = r , abbreviated as mod n = r . For instance, we have mod 3 = 2 since $8 = 3 \times 2 + 2$ .

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

Rendered by QuickLaTeX.com

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 . These are the rows colored in red, where 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 .

Moreover, a known property of modular multiplication is that a number has a multiplicative inverse mod if and only if it is relatively prime to . 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 by itself times, we write a^e mod n = b . We call the base and 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 . As we mentioned previously, these numbers in the range from 0 to n-1 are relatively prime to . Therefore, as we already know, $\mathbb{Z}_{10}^* = \{1,3,5,7\}$ . Moreover, if is a prime , then $\mathbb{Z}_p^*=\{1, 2, \ldots, p-1\}$ since all numbers from to p-1 are relatively prime to .

Also, if there is a number $\alpha \in \mathbb{Z}_p^*$ such that the set $\{\alpha$ mod , $\alpha^2$ mod $p, \ldots \alpha^{p-1}$ mod $p \} = \mathbb{Z}_p^*$ , then $\alpha$ is called a primitive root of . Let’s assume p=7 , the table below shows that only and 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 , then, for any $1 \leq b \leq n-1$ , $\log_\alpha b$ mod 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 . This follows from the definition of primitive roots.

4.2. Encryption

Let’s assume Alice would like to send a secret message to Bob. Bob has already chosen as a prime and $\alpha$ a primitive root of . 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 . Then, he sent Alice the values $p, \alpha, u$ over any public channel.

To encrypt , Alice applies the following algorithm:

algorithm ElgamalEncryptionAlgorithm(p, α, u, m):
    // INPUT
    //    p = a prime number
    //    α = a primitive root of p
    //    u = public key (α^r mod p)
    //    m = the message to be encrypted
    // OUTPUT
    //    c1, c2 = the cipher texts

    x <- choose a random value between 1 and p - 1
    c1 <- α^x mod p
    c2 <- m * u^x mod p

    return c1, c2

4.3. Decryption

To decrypt , Bob applies the following algorithm:

algorithm ElgamalDecryption(c1, c2):
    // INPUT
    //    c1 = the first part of the cipher text
    //    c2 = the second part of the cipher text
    // OUTPUT
    //    m = the decrypted message

    Compute c1^r as α^(rx) mod p
    m <- c2 * (c1^r)^(-1) // = m * u^x * (α^(rx))^(-1) = m * α^(rx) * (α^(rx))^(-1) mod p = m

    return m

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 . This is because, to know , the intruder has to compute the discrete logarithm $\log_{\alpha} u$ mod .

5. Conclusion

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

Persistence

REST

Security