Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is the ElGamal Encryption system?
2.1.
Cyclic Group
3.
Elgamal Encryption
3.1.
Key Generation
3.2.
Encryption
3.3.
Decryption 
4.
Implementation 
5.
Frequently Asked Questions
5.1.
What do you mean by semantic security?
5.2.
What do you mean by discrete logarithm problem?
5.3.
What is Dilfie-Hellman's key exchange?
5.4.
Where is ElGamal Encryption used?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Semantic Security of ElGamal System

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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.

introduction

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

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}

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Elgamal Encryption

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 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 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 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()

Output:

Original Message: coding ninjas
y used:  23245481994774532532903097403453866069002518027122
y^x used:  2317054898458703255588589435116521263585573453156
y^m used:  3379743857550514228078130844379351111225888022151
y^xm used:  42148854767868814732705021946726918046550028046456
Decrypted Message: coding ninjas

Frequently Asked Questions

What do you mean by semantic security?

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.

Refer to the Basics of C++ with Data StructureDBMS, and Operating System by Coding Ninjas, and keep practising on our platform Coding Ninjas Studio. You can check out the mock test series on code studio.

You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in domains like Data Structures and AlgorithmsCompetitive ProgrammingAptitude, and many more! Refer to the interview bundle if you want to prepare for placement interviews. Check out interview experiences to understand various companies' interview questions.

Give your career an edge over others by considering our premium courses!

Happy Learning!

Previous article
Bit Security of Discrete logarithms
Next article
Again Hellman, Diffie-Hellman Problems
Live masterclass