ElGamal Encryption Algorithm in Python

By Shagun Bidawatka

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.

Leave a Reply