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