ElGamal encryption is an example of public-key or asymmetric cryptography. The cryptosystem takes its name from its founder the Egyptian cryptographer Taher Elgamal who introduced the system in his 1985 paper entitled “A Public Key Cryptosystem and A Signature Scheme Based on Discrete Logarithms”.

As this title suggests the security of this cryptosystem is based on the notion of discrete logarithms. This is the ‘one way function’ at the heart of ElGamal’s encryption and decryption algorithms.

Diffie-Hellman key exchange algorithm is also based on the discrete logarithm, and allows two people to establish a shared secret key. This key establishes an initial handshake, and can serve as the key for any symmetric key algorithm for further communication.

The discrete logarithm problem, why it is secure and attacks upon it are discussed below.

Discrete Logarithms

Discrete logarithm problem

The discrete logarithm problem is the problem of determining to which power some value was raised in order to attain the result when working in a modular ring (usually, modulo some prime). Precisely, the problem is as follows:

Fix a prime p. Let α and β be integers not divisible by p, then the discrete logarithm problem is the problem of finding x in the following:

For small values of p this can be found through exhaustive search, since there will only be p – 1 possible exponents (as per the Euler-Fermat theorem). However, for large primes p, the problem has no known useable algorithmic solution. Hence it may be used with large primes as the basis for a secure cryptosystem.

Since we are working modulo p there will be infinitely many values for x (the congruent class mod p – 1) but generally the problem is taken to be to find the smallest value of x. We define x as:

For example if p = 13, α = 2 and β = 9 the discrete log problem is to find x such that:

Since 2⁸ = 256 which is 9 (mod 13), x = 8 is a valid solution to the above problem. This value x = 8 was computed by brute-force, i.e. trying all possible values of x starting from 1.

A similar problem to that of finding the exponent x is to find the base that when raised to the exponent x yields the congruent set to β (mod p). This problem does not have its own name and is not the base for a cryptosystem but it offers extra security in case the exponent is (partially) revealed if the value of the base α is kept secret.

Primitive root

Often α is taken to be a primitive root modulo p. A primitive root is a value modulus some prime p that can be used to form each value of the ring of integers modulo p simply by multiplying up by itself. That means that each possible value modulo p can be expressed as a power of the primitive root modulo p. Formally, a primitive root, α, modulo p is an integer 1 < α < p such that the powers of this integer are all distinct integers modulo p. Let’s consider an example of a primitive root modulo 5. p = 5, α = 2. The powers of α are as below:

We can see that the primitive root can be used to generate each congruence modulo 5.

Something worth noting from the definition of a primitive root is that if α is a primitive root mod p, p – 1 is the smallest positive exponent n such that αⁿ (mod p) ≡ 1. This aids in understanding the Euler-Fermat theorem when applied to primitive roots (this special case is also known as Fermat’s little theorem). For our above examples with p = 5, α = 2, we can see that α^p-1 ≡ 1 (mod p).

There is no specific formula for finding primitive roots. A primitive root is generally found through trial and error. Generally the candidate primitive roots are tested using powers that are equal to p - 1 divided by each of the prime factors of p - 1 in turn. This highlights areas where the candidate may fall down by returning to 1 rather than continuing to generate values and only reaching 1 at the (p - 1)^th power.

We can work out the probability of success in picking a primitive root first time since it is possible to calculate the number of primitive roots for any given prime by the following where s_p is the number of primitive roots of the prime p:

Where φ(p) denotes Euler’s function.

Where p|x is the set of distinct prime factors of x.

Applying this to the value x = 52 which has prime factorization 52 = 2² × 13 gives:

We may therefore deduce that there are 24 values co-prime to 52.

Fermat’s little theorem

Let us state Fermat’s little theorem. Let p be a prime. Let a be an integer such that GCD(a, p) = 1. Then:

We may now see that by the nature of primitive roots and the fact that the exponents modulo a prime are themselves in a ring modulo p – 1 that the following can only be true for the primitive root α, the exponents x and y and the prime p when x ≡ y (mod p – 1):

ElGamal Encryption and Decryption

Alice wants to send a message m to Bob using the ElGamal cryptosystem. The steps of doing this are as follows:

1. Bob chooses a large prime p and a primitive root α (mod p). These are the public keys of the cryptosystem. Bob also chooses a private integer z.
2. Bob computes β ≡ α^z (mod p).
3. The public key (p, α, β) is made public.
4. Alice downloads the public key (p, α, β) and formulates the message m.
5. If necessary m is split into smaller blocks so that all messages fall in the interval 0 < m < p.
6. Alice chooses a secret integer k at random and computes r ≡ α^k (mod p).
7. Alice computes t ≡ β^km (mod p).
8. Alice sends the pair (r, t) to Bob.
9. Bob decrypts the message by computing the following: m ≡ tr^-z (mod p). This is true because of the following:

Example

As and example lets assume Bob chooses his prime as 31 and primitive root 3. His private key is 7. Therefore:

Bob’s public key is the set (31, 3, 17).

Alice wishes to send the message m = 13 and picks a private key k = 5. She then computes and sends the following:

Bob then receives the pair r, t and decrypts the message as below.

The exponent of 23 is used in decryption as this is equivalent to -z ≡ -7 ≡ 27 (mod 30). We work modulo 30 because by Euler’s theorem we work modulo p - 1 in the exponent.

We have used small values in our example so that it is easy to follow. In actual use, large primes must be used, else the system can be easily broken using brute force attacks.

Repeated squares

The exponents are generally calculated through the process of repeated squares. For example, if the exponent were 13 then it can be expressed as the product of the 8^th, 4^th and 1^st powers (i.e. x¹³ = x¹ * x⁴ * x⁸), where 1, 4 and 8 are all powers of 2. Each of these powers can be found by repeated squaring of the base.

Given x, we first calculate

and then we calculate

This allows us to calculate x¹³ by performing only 5 multiplications, instead of 12. In general, it allows us to compute xⁿ by only performing O(log n) multiplications.

Attacks

In general, due to the difficulty of solving discrete logarithm problems attacks on the ElGamal cryptosystem are few and often only work in specific and complex cases.

Different private key for each message

When using ElGamal it is important to use a different private key for each message to maximise security both in sending and receiving. Take the case where Alice uses the same private key k when sending two different messages m₁ and m₂. In this case r will be the same for each message (r­₁ = r₂). The ciphertext pairs are therefore (r­, t₁) and (r­, t₂).

If Eve manages to attain the plaintext m₁, she can also determine m₂ by the following. First note:

Since Eve knows t₁ and t­₂ as they are communicated on an open channel she may compute m₂ from the knowledge of m₁ as follows:

This vulnerability is depending on Eve attaining one of the messages (m­₁ in our example) however it does highlight the increased vulnerability induced by repeated use of the value of k.

Simple attack for ‘is x even or odd’

The simplest attack on the discrete logarithm problem with a primitive root (α) enables us to tell whether or not x is even using Fermat’s little theorem. By Fermat’s little theorem:

Therefore by taking square roots we attain:

Hence considering the equivalence β ≡ α^x (mod p) and raising both sides to the ½ (p - 1) power we attain:

This follows from the assumption based in Fermat’s little theorem that p - 1 is the smallest power of α that results in -1.

Therefore if:

x must be odd.

Else if:

x must be even.

The Diffie-Hellman Key Exchange

An important issue in cryptography is how to establish keys for use in a cryptosystem when the two communicating parties are far apart and can only communicate on an open channel (requiring the keys to be set up first before encrypted communication can begin). One solution from this can be seen in public key or asymmetric cryptosystems. The Diffie-Hellman key exchange offers another solution enabling the use of private key cryptosystems by enabling keys to be shared between communicators whilst maintaining privacy. The protocol is based on discrete logarithms which provide the security necessary for it to be effective.

Below is the description of the basic Diffie-Hellman Key exchange which allows Alice and Bob to establish a shared private key K.

1. Either Alice or Bob selects a large prime p and a primitive root α (mod p). Both p and α can be made public.
2. Alice chooses a secret random integer x where 1 < x < p – 1 and Bob chooses a secret random integer y where 1 < y < p – 1.
3. Alice sends α^x (mod p) to Bob and Bob sends α^y (mod p) to Alice.
4. Alice and Bob both take the messages they have received and raise them to their own private values so that they both attain α^xy ≡ K (mod p). K is the shared private session key.

Clearly if an attacker Eve is eavesdropping then she will be able to attain α, p, α^x (mod p) and α^y (mod p). But without being able to compute discrete logs she has no way of attaining x or y and hence cannot construct the key K.

Example

Alice and Bob settle on the prime p = 37 and the primitive root α = 2. Alice’s private key is x = 7 and bob’s private key is y = 15. Alice sends Bob α^x ≡ 2⁷ ≡ 128 ≡ 17 (mod 37) and Bob sends Alice α^y ≡ 2¹⁵ ≡ 32768 ≡ 23 (mod 37).

Bob and Alice then each raise the message they receive to their private key to attain their shared private key α^xy.

The shared secret or private key is therefore 14.

We have used small values in our example so that it is easy to follow. In actual use, large primes must be used, else the system can be easily broken using brute force attacks.

Other problems similar to discrete logarithms

The problem of trying to attain the key K from the public information generated by the Diffie-Hellman key exchange can be expressed several different ways. The above poses it as a problem of solving discrete logarithms. We end this section by considering two alternative formulations that are akin to solving discrete logarithms but do not require it. It is not known whether or not solving these problems is harder than solving discrete logarithms.

The Computational Diffie-Hellman Problem: Let p be prime and let α be a primitive root mod p. Given α^x (mod p) and α^y (mod p) find α^xy (mod p).

The Decision Diffie-Hellman Problem: Let p be prime and let α be a primitive root mod p. Given α^x (mod p), α^y (mod p) and β ≢ 0 (mod p) decide whether or not α^xy ≡ β (mod p).

It is not known if solving the computational Diffie-Hellman problem also solves the decision Diffie-Hellman problem or vice versa. There are analogous problems to those considered here involving elliptic curves where a fast solution is known for the decision Diffie-Hellman problem but no solution is known for the computational Diffie-Hellman problem.

Practical use and Applications

The ElGamal cryptosystem is usually used in a hybrid cryptosystem. The message itself is encrypted using a symmetric cryptosystem and ElGamal is used to encrypt the key used for the symmetric cryptosystem. This is because asymmetric cryptosystems like ElGamal are usually slower than symmetric ones for the same level of security, so it is faster to encrypt the symmetric key (which most of the time is quite small compared to the size of the message) with ElGamal and the message (which can be arbitrarily large) with a symmetric cipher.

Diffie-Hellman Key Exchange is also popularly used for the user-case described above. In fact, it was specifically designed for the above use case of establishing a shared secret key, and is faster than ElGamal.

Forward secrecy is the property of a communication protocol in which past sessions are protected against future compromises of secret keys or passwords. Protocols that achieve forward secrecy generate new key pairs for each session and discard them at the end of the session. The Diffie–Hellman key exchange is a frequent choice for such protocols, because of its fast key generation.

Conclusion

The ease of calculating exponents modulo a prime makes encryption and decryption easy when the keys are known but the one-way nature of this operation renders such encryption secure. This function can be considered one way due to the difficulty of calculating discrete logarithms, that is working out the exponent required to attain the necessary result modulo p (where p is a prime).

This cryptosystem is usually implemented using primitive roots and a full understanding of discrete logarithms and the ElGamal cryptosystem will draw on the theorems of Euler and Fermat regarding primitive roots and the calculations of exponents on modular rings.

This is an asymmetric or pubic key cryptosystem and the ideas behind its security can be applied to communicating keys in the Diffie-Hellman Key exchange. There are further applications including in Elliptic curve cryptography. The cryptosystem is secure provided it is well implemented, meaning that keys should be changed often and kept secret.