ElGamal encryption is one of the most common public-key cyphers which is based on the DH key exchange. Here, we will go through the overview of ElGamal encryption and show some Python code implementation. Finally, we will discuss the security of ElGamal.
Overview
key generation scheme:
Choose a random prime p and a number g where 2 < g < p. Here, g is a primitive element. Which means that g^i != 1 mod p holds for 0 < i< p-1. Next, generate a random number x in the range 1 < x < p. x is the private key. Finally, calculate y = g^x mod p and this is the public key.
encryption scheme
The receiver of the sender’s public key y, and chooses a random number r in the range 1 < r < p-1. To encrypt a message m, compute Enc(m) = (g^r, my^r) = (c1, c2).
decryption scheme
To decrypt a cypher text, use the private key x and calculate Dec(c) = c2*c1^(p-1-x) mod p or c2/(c1^x) mod p. Here, / means the division of finite objects. This equation holds because of Fermat’s Little Theorem. Fermat’s Little Theorem claims that for prime p and a where a and p is coprime, a^(p-1) ≡ 1 mod p. We now have Dec(c) = my^r/(g^r)^(x) mod p = m(g^x)^r/(g^r)^(x) mod p = m, so we could the message m is recovered.
Implementation
#generate key
def key_elgamal (bits):
#generate random prime p
p = number.getPrime(bits-1)
while True:
g = number.getRandomRange(3, p+1) #check if (g^i != 1 mod p) for 0 < i < p-1
for i in range(1, p-1):
if (pow(g, i, p) == 1):
break
break #private key
x = number.getRandomRange(2, p-1) #public key
y = pow(g, x, p) return x, y, p, g#encryption
def encrypt_elgamal(g, p, m, y):
r = number.getRandomRange(2, p-1) #cipher text
c1 = pow(g, r, p)
c2 = (m * pow(y, r, p)) % p return c1, c2
#decryption
def decrypt_elgamal(c1, c2, x, p):
#message
m = (c2 * pow(c1, p-1-x, p)) % p return m
Is ElGamal secure?
Under the CDH assumption, the ElGamal cypher remains unidirectional. The CDH assumption is the assumption that the DH problem is difficult to solve. The DH problem is the following:
“Calculate g^ab mod p when we have g, p, g^a mod p, g^b mod p”
Under the DDH assumption, ElGamal cryptosystem does not allow anyone who does not know the secret key to decrypt the plaintext from the ciphertext. The DDH assumption is that the DDH problem is difficult. The problem is as follows:
“When we have g, g^a, g^b, and for random c, we have z_i which is either z1 = g^ab or z2 = g^c, judge whether i is 1 or 2.”
Also, it is a stochastic algorithm because it uses random numbers for encryption, which means that every time you use the same input, it generates a different cypher text.
So is ElGamal absolutely safe? Well, not really.
Suppose that when the plaintext m is encrypted, a random attacker is able to gain the cypher text c, and the attacker falsifies it.
Where Enc(m) = (c1, c2), let’s change (c1', c2') = (c1, 2*c2).
Now the receiver getsthe (c1', c2') and decrypted it. The receiver computes Dec(c1', c2') = 2m, which is different from the original plaintext.
When attacking c = Enc(m), if the attacker gives the receiver c’ = 2c and ask the receiver to decrypt it, the attacker is able to get m’, and m = m’/2 gives us the original plaintext m.
This shows that the ElGamal cypher is not robust and is not IND-CCA2 secure.
So, the ElGamal system is never used by itself, and but is sometimes used as a part of the hybrid encryption system.
