ElGamal Encryption Scheme
This week, we will see the ElGamal encryption scheme; we are considering public key cryptography, so we use public and secret keys to achieve this encryption scheme.
The ElGamal encryption scheme is run using a cyclic group of order (size) q and with generator g. Recall that the generator of a group is an element from which the whole group can be formed by applying the group operation.
The encryption scheme:
You will recall from a previous tutorial, that an encryption scheme is made up of three algorithms: key generation, encryption and decryption. We will assume the encryption scheme is run between Alice and Bob, where Bob is encrypting a message, m, to send to Alice, who then decrypts it.
Key generation
Alice must generate a public key for herself and an associated secret key that she will use to decrypt the message. She does this by:
- Randomly selecting an element, x, of the set {0, …, q — 1}.
- Calculates h= gx.
- Alice publishes h as her public key and keeps x as her private key.
Encryption
For simplicity, we assume the message (m) to be encrypted is an element of the group. In order to encrypt a message (m) for Alice to decrypt, Bob must encrypt it using Alice’s public key in the following way:
- Randomly selecting an element, y, of the set {0, …, q — 1}.
- Calculates c1 = gy.
- Calculate s= hy. Note that s= gx.y.
- Calculate c2 = m . s.
- Bob sends (c1, c2) to Alice.
Decryption
Alice has (c1, c2) and her secret key (x) at her disposal to decrypt the message. She does so as follows:
- Calculates s = c1x.
- To decrypt the message she computes m = c2 . s-1.
This is the whole encryption scheme! Simple, no? One reason this scheme is widely used is that it is efficient, there are not many steps to it. It is of particular interest that there are only two exponentiations in the encryption algorithm; minimising the number of exponentiations is a good way to keep the run time of the algorithm down.
Question:
Write a proof that this encryption scheme is correct.
Hint: to do this we need to show that if we follow the three algorithms correctly, the decryption algorithm will always return the original encrypted message.
The solution is at the very end of this article.
This article was written by David Butler, one of the course creators and teachers at Oxbridge Inspire. David is studying for a PhD at the Alan Turing Institute in London.
Oxbridge Inspire delivers innovative STEM education and provides guidance and inspiration to young people wishing to pursue STEM subjects at University and beyond. To find out more about Oxbridge Inspire and the courses and activities we offer, visit our website.
Solution:
Alice computes c2 . s-1. We need to show this is equal to m. We can see this is true by the following.
c2 . s-1 = m . hy . (gxy)-1 = m . gxy . (gxy)-1 = m
We can see that the decryption will always produce the original message.
