Limited Entropy Dot Com Not so random thoughts on security featured by Eloi Sanfèlix

Crypto Series – ElGamal Cryptosystem

In our last post we learnt about the Discrete Lograithm problem, why it is a difficult problem and how we can attempt to solve it if the numbers are manageable. Of course, in a real setting we wouldn't use 16 bit numbers as in my example, but at least 1024 bit numbers nowadays (and most likely even bigger numbers).

Now, we are going to see how to make  use of that problem to create a public key cryptosystem. We will look at how ElGamal uses the DL problem to provide public key encryption and digital signatures. Keep on reading if you are interested!

ElGamal encryption

So we have our friends Alice and Bob wanting to communicate securely. To that end, they first agree on the public settings of the ElGamal cryptosystem. They need a finite cyclic group G to work on (such as ) and a generator for that group, g. Of course, the group G must be a group where computing discrete logarithms is infeasible. Otherwise the system will not work.

With these numbers, Alice and Bob first generate their respective key pairs. First, they generate a random element in G, which will serve as a private key: and respectively. Now, they compute the corresponding secret keys as follows:

in G

in G

And now they can publish their public keys, , without any fear. Thanks to the difficulty of solving the discrete logarithm in G, their respective private keys remain safe even though everyone knows how they were generated.

So, now our friend Alice wants to send some message m to Bob. This message is represented as an element in the group G. First, she grabs Bob's public key. Then, she generates a random number r in the same group G. With that number and Bob's public key, she computes the following cryptogram:

It is needless to say that these operations always take place in the group G. Now, when Bob receives this message he can compute m like this:

This is good news, at least Bob can recover the message knowing . But that doesn't mean that the message will be safe from everyone else.

However, since the DL problem is difficult, it turns out that recovering r from R is difficult. Therefore, it is not easy to compute from the cryptogram and then recover m. It is also difficult to compute Bob's private key from his public key, which would be another way to recover the message.

And also, since r was random, R is randomized as well as S. Thus, an attacker has no information on the structure of the message and the system seems secure under the assumption that the DL problem is hard.

Example: ElGamal encryption

Let's continue with our previous example. We take again the same group, and its generator . Alice and Bob compute their respective private and public keys:

sage: G = IntegerModRing(17627)
sage: g = G(6)
sage: g.multiplicative_order()
17626
sage: xA = G.random_element()
sage: xB = G.random_element()
sage: hA = g^xA
sage: hB = g^xB
sage: hA
11094
sage: hB
1593
sage:

So now everyone knows the public keys of Alice (11094) and Bob (1593). Now let's imagine that Alice wants to send the message m (1337) to Bob. She has to create a new random number and compute the cryptogram:

sage: r=G.random_element()
sage: R = g^r
sage: m=1337
sage: S=hB^r*m
sage: (R,S)
(4831, 8533)
sage:

Alright, now Alice sends this pair of numbers to Bob and he receives it and tries to decrypt them:

sage: mp = S/(R^xB)
sage: mp
1337
sage:

Great, it works! However, note that this is not secure against chosen ciphertext attacks and the cryptogram is easily modifiable. For instance, one could modify the decrypted message by modifying only the S part of the cryptogram:

sage: Sp = 3*S
sage: mp = Sp/(R^xB)
sage: mp
4011
sage: 3*m
4011
sage:

Here an attacker has intercepted the message and modified S to be 3S. This results in the decrypted message being 3m instead of m. However, this kind of properties becomes very useful in multiparty computations such as electronic voting schemes.

ElGamal signature scheme

Now we know how to encrypt and decrypt messages using ElGamal. Next step is to see how ElGamal approaches digital signatures. The steps for generating the key pair are the same, i.e. each participant generates a random number as their private key and then computes as their public key.

Now, given a message m, Alice will first generate a cryptographic hash H(m). Then, she picks again a random number r and computes the following things:

Note that now we used the private key for the generation of the signature. Otherwise, we would not be able to prove that the message is linked to Alice since everyone knows the public key. If S turns out to be 0, Alice has to pick a new random number and compute the signature again.

The verification of the signature is performed by Bob as follows. Bob first computes the message H(m) and then performs the following two calculations:

Due to the way in which the values R and S have been computed, the two results should be the same if the signature and the message have not been modified:

So this tells us that the system is correct, and again in order to forge a signature one would need to either find collisions in the function H (see my post on hash functions) or solve a discrete logarithm. Both problems are believed to be hard. Note that the hash collision must occur over the group G, so that .

Further reading

Once again, I refer the interested readers to the Handbook of Applied Cryptography for more extensive and accurate information on these topics. In this case, the ElGamal public key system is described in chapter 8, section 8.4.