ElGamal Encryption Algorithm in Python
By Shagun BidawatkaElgamal 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.
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!
Could you explain the code step by step. What the code is doing please.