# 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 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.

### 2 responses to “ElGamal Encryption Algorithm in Python”

1. Sherry Lee says:

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!

2. Vybz says:

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