ElGamal Encryption Algorithm in Python

Elgamal Encryption is a type of asymmetric key algorithm used for encryption. It is used for public-key cryptography and is based on the Diffie-Hellman key exchange.

Here, I will include the introduction, uses, algorithm, and code in Python for Elgamal Encryption Algorithm.

This asymmetric-key encryption cryptography is on the basis of the difficulty of finding discrete logarithm in a cyclic group that means we know g^a and g^k, computes g^ak.

USE:  Hybrid cryptosystem uses this algorithm.

Algorithm:

Elgamal Encryption Algorithm has three parts

• A key generator
• The encryption algorithm
• The decryption algorithm.

Public Parameter: A trusted third party publishes a large prime number p and a generator g.

1.Key Generation:

• Alice chooses a secret key 1<=a<=p-1.
• Computes A=g^a mod p.
• Alice se1<=k<=p and the public key pk=(p, g, A) to Bob.

2. Encryption:

• Bob chooses a unique random number key 1<=k<=p-1.
• Uses Alice’s public key pk and key k to compute the ciphertext (c1,c2) =Epk(m) of the plaintext 1<=m<=p-1 where c1=g^k mod p and c2=m.A^k mod p.
• The ciphertext (c1,c2) is sent to Alice by Bob.

3. Decryption:

• Alice computes x=c1^a mod p  and its inverse x^-1 with the extended Euclidean algorithm.
• Computes the plaintext m’=Dsk(c1,c2)= x^-1.c2 mod p where m’=m.

Code:

import random
from math import pow

a=random.randint(2,10)

#To fing gcd of two numbers
def gcd(a,b):
    if a<b:
        return gcd(b,a)
    elif a%b==0:
        return b
    else:
        return gcd(b,a%b)

#For key generation i.e. large random number
def gen_key(q):
    key= random.randint(pow(10,20),q)
    while gcd(q,key)!=1:
        key=random.randint(pow(10,20),q)
    return key

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

#For asymetric encryption
def encryption(msg,q,h,g):
    ct=[]
    k=gen_key(q)
    s=power(h,k,q)
    p=power(g,k,q)
    for i in range(0,len(msg)):
        ct.append(msg[i])
    print("g^k used= ",p)
    print("g^ak used= ",s)
    for i in range(0,len(ct)):
        ct[i]=s*ord(ct[i])
    return ct,p

#For decryption
def decryption(ct,p,key,q):
    pt=[]
    h=power(p,key,q)
    for i in range(0,len(ct)):
        pt.append(chr(int(ct[i]/h)))
    return pt


msg=input("Enter message.")
q=random.randint(pow(10,20),pow(10,50))
g=random.randint(2,q)
key=gen_key(q)
h=power(g,key,q)
print("g used=",g)
print("g^a used=",h)
ct,p=encryption(msg,q,h,g)
print("Original Message=",msg)
print("Encrypted Maessage=",ct)
pt=decryption(ct,p,key,q)
d_msg=''.join(pt)
print("Decryted Message=",d_msg)

Input= CodeSpeedy

Output:

Enter message.CodeSpeedy
g used= 60635310250822910920670085797255424040413892864017
g^a used= 43614735900565768923384780647044097770719380284049
g^k used=  41675490433882378107772354864700362515626473012377
g^ak used=  17548756165231195763385969811276881943441214592545
Original Message= CodeSpeedy
Encrypted Maessage= [1175766663070490116146859977355551090210561377700515, 1947911934340662729735842649051733895721974819772495, 1754875616523119576338596981127688194344121459254500, 1772424372688350772101982950938965076287562673847045, 1456546761714189248361035494335981201305620811181235, 1965460690505893925499228618863010777665416034365040, 1772424372688350772101982950938965076287562673847045, 1772424372688350772101982950938965076287562673847045, 1754875616523119576338596981127688194344121459254500, 2123399495992974687369702347164502715156386965697945]
Decryted Message= CodeSpeedy

In this algorithm, someone can know your message only when he/she knows the value of a.

3 responses to “ElGamal Encryption Algorithm in Python”

1. Sherry Lee says:

   March 16, 2021 at 2:45 am

   How do I implement and verify the homomorphic property of ElGamal algorithm? I mean how do I allow users to input m1 and m2 from keyboard and verify that E(m1m2)=E(m1)E(m2) by adding some codes to above program? Thank you!

   Reply
2. Vybz says:

   March 31, 2021 at 5:53 am

   Could you explain the code step by step. What the code is doing please.

   Reply
3. moep1234 says:

   February 24, 2022 at 5:40 am

   If you don’t use a primitive root of p as g you could end up with g being subgroup of much reduced order which then would only generate numbers within the subgroup. This could lead to keystream reuse and therefore seriously weaken the encryption.

   Finding a primitive root g mod p with p >> 1024 Bit is not trivial, as one ends up with the same problem as with finding a huge prime. But simply using a random g could lead to serious security issues if this code would ever be used in a production environment with high security requirements. Its good enough to show the function, not good enough to be used as either teaching nor production material. The original paper by Taher Elgamal even states that g must be a primitive root mod p.

   Reply