Do you think IIT Guwahati certified course can help you in your career?
Introduction
Hello ninjas, this blog will help you understand the Semantic Security of the ElGamal System.
Cryptography is the technique of sending information across a noise-ridden medium with hidden private details. The Elgamal System is an asymmetric key encryption that involves the discrete logarithm problem.
What is the ElGamal Encryption system?
The ElGamal encryption system is a public-key cryptography scheme that generates asymmetric key encryption based on the Diffie-Hellman key exchange.
Diffie-Hellman key exchange is a mathematical method for securely exchanging cryptographic keys through a public channel invented by Ralph Merkle and named after Whitfield Diffie and Martin Hellman.
ElGamal encryption applies to any cyclic group G, such as a multiplicative group of integers modulo n. Its security is determined by the complexity of a specific issue in G involving the computation of discrete logarithms.
Cyclic Group
A cyclic group is defined as a group that can be generated by a single element. This simply means, that all the elements of the group can be generated by repeatedly applying a binary operation on an element. For example, Let's consider a group G = {0, 1, 2, 3, 4, 5}.
Here, the cyclic subgroups can be created by applying ‘addition modulo 6’ operation on 1 or 5.
This can be shown as:
(1+0) % 6 = {1}
(1+1) % 6 = {2}
(1+2) % 6 = {3}
(1+3) % 6 = {4}
(1+4) % 6 = {5}
(1+5) % 6 = {0}
(5+0) % 6 = {1}
(5+1) % 6 = {2}
(5+2) % 6 = {3}
(5+3) % 6 = {4}
(5+4) % 6 = {5}
(5+5) % 6 = {0}
Elgamal Encryption
ElGamal is typically used as part of a hybrid cryptosystem, in which the message is encrypted with the help of a symmetric cryptosystem and then the encryption is done by ElGamal of only the symmetric key. Because asymmetric cryptosystems like ElGamal are typically not faster than symmetric ones for an equal level of security, it is preferable to encrypt the message, which can be arbitrarily large, with a symmetric cypher and then use ElGamal only to encrypt the symmetric key, which is typically quite minute in contrast to the size of the message.
The ElGamal encryption has three components:
Key Generation
Suppose Jan wants to encrypt the message using El Gamal Cipher. She will send the key as follows:
She will first choose a large number n and a cyclic group Fn.
She then will choose a random number from Fn,x and y such that GCD(x, n)=1
She then will compute h = y^x.
Jan will then publish h, Fn, y, and n as public keys and takes x as his private key.
Encryption
Suppose Jim wants to encrypt a message m using Jan’s public keys (h, Fn, n, y). He will do the as:
Jim will select a random element m from the cyclic group Fn such that GCD(m, n)=1.
Jim will then compute p = y^m and s = h^k = y^mx. (Here, x is private with Jan)
He will multiply m with s and sends (p,m*s) = (y^m,m*s)
Decryption
Jan will decrypt the message as follows:
Jan will decipher the news by calculating s
Jan will finally obtain m by dividing the ciphertext with s
Implementation
import random
from math import pow
x = random.randint(2, 10)
#function to calculate GCD
def GCD(a, b):
if a < b:
return GCD(b, a)
elif a % b == 0:
return b;
else:
return GCD(b, a % b)
# For the generation of large numbers
def key_gen(n):
Key = random.randint(pow(10, 20), n)
while GCD(n, key) != 1:
key = random.randint(pow(10, 20), n)
return key
# for Modular exponentiation
def power(a, b, c):
x = 1
y = a
while b > 0:
if b % 2 != 0:
x = (x * y) % c;
y = (y * y) % c
b = int(b / 2)
return x % c
# Asymmetric encryption by ElGamal
def encrypt(msg, n, h, y):
enc_msg = []
m = key_gen(n)# Private key for sender
s = power(h, m, n)
p = power(y, m, n)
for i in range(0, len(msg)):
enc_msg.append(msg[i])
print("y^m used : ", p)
print("y^xm used : ", s)
for i in range(0, len(enc_msg)):
enc_msg[i] = s * ord(enc_msg[i])
return enc_msg, p
def decrypt(enc_msg, p, key, n):
dcr_msg = []
h = power(p, key, n)
for i in range(0, len(enc_msg)):
dcr_msg.append(chr(int(enc_msg[i]/h)))
return dcr_msg
def main():
msg = 'coding ninjas'
print("Original Message :", msg)
n = random.randint(pow(10, 20), pow(10, 50))
y = random.randint(2, n)
key = key_gen(n)# Private key for receiver
h = power(y, key, n)
print("y used : ", y)
print("y^x used : ", h)
en_msg, p = encrypt(msg, n, h, y)
dcr_msg = decrypt(en_msg, p, key, n)
dmsg = ''.join(dcr_msg)
print("Decrypted Message :", dmsg);
if __name__ == '__main__':
main()
You can also try this code with Online C++ Compiler
A cryptosystem is called semantically secure if only negligible information can be extracted from the encrypted message or ciphertext.
What do you mean by discrete logarithm problem?
Discrete logarithms are logarithms that are defined in terms of multiplicative cyclic groups. If G is a multiplicative cyclic group and g is a generator of G, then we know that any element h in G may be expressed as g^x for some x according to the definition of cyclic groups.
What is Dilfie-Hellman's key exchange?
Diffie-Hellman key exchange is a mathematical method for privately trading cryptographic keys through a public channel that was invented by Ralph Merkle and named after Whitfield Diffie and Martin Hellman.
Where is ElGamal Encryption used?
Elgamal Encryption is used in hybrid cryptosystems, where the message is encrypted using a symmetric cryptosystem.
Conclusion
We hope this blog successfully helped you understand the concept of probability and its applications.
If you found this blog interesting and insightful, refer to similar blogs: Claude Shannon Cipher.
132+ registered 
