ElGamal Encryption Algorithm

ElGamal encryption is an public-key cryptosystem. It uses asymmetric key encryption for communicating between two parties and encrypting the message.
This cryptosystem is based on the difficulty of finding discrete logarithm in a cyclic group that is even if we know g^a and g^k, it is extremely difficult to compute g^ak.

Idea of ElGamal cryptosystem
Suppose Alice wants to communicate to Bob.

Bob generates public and private key :
- Bob chooses a very large number q and a cyclic group F_q.
- From the cyclic group F_q, he choose any element g and
  an element a such that gcd(a, q) = 1.
- Then he computes h = g^a.
- Bob publishes F, h = g^a, q and g as his public key and retains a as private key.
Alice encrypts data using Bob’s public key :
- Alice selects an element k from cyclic group F
  such that gcd(k, q) = 1.
- Then she computes p = g^k and s = h^k = g^{ak^.}
- She multiples s with M.
- Then she sends (p, M*s) = (g^k, M*s).
Bob decrypts the message :
- Bob calculates s^′ = p^a = g^ak.
- He divides M*s by s^′ to obtain M as s = s^′.

Following is the implementation of ElGamal cryptosystem in Python

# Python program to illustrate ElGamal encryption 
  
import random  
from math import pow
  
a = random.randint(2, 10) 
  
def gcd(a, b): 
    if a < b: 
        return gcd(b, a) 
    elif a % b == 0: 
        return b; 
    else: 
        return gcd(b, a % b) 
  
# Generating large random numbers 
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 
  
# Modular exponentiation 
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 
  
# Asymmetric encryption 
def encrypt(msg, q, h, g): 
  
    en_msg = [] 
  
    k = gen_key(q)# Private key for sender 
    s = power(h, k, q) 
    p = power(g, k, q) 
      
    for i in range(0, len(msg)): 
        en_msg.append(msg[i]) 
  
    print("g^k used : ", p) 
    print("g^ak used : ", s) 
    for i in range(0, len(en_msg)): 
        en_msg[i] = s * ord(en_msg[i]) 
  
    return en_msg, p 
  
def decrypt(en_msg, p, key, q): 
  
    dr_msg = [] 
    h = power(p, key, q) 
    for i in range(0, len(en_msg)): 
        dr_msg.append(chr(int(en_msg[i]/h))) 
          
    return dr_msg 
  
# Driver code 
def main(): 
  
    msg = 'encryption'
    print("Original Message :", msg) 
  
    q = random.randint(pow(10, 20), pow(10, 50)) 
    g = random.randint(2, q) 
  
    key = gen_key(q)# Private key for receiver 
    h = power(g, key, q) 
    print("g used : ", g) 
    print("g^a used : ", h) 
  
    en_msg, p = encrypt(msg, q, h, g) 
    dr_msg = decrypt(en_msg, p, key, q) 
    dmsg = ''.join(dr_msg) 
    print("Decrypted Message :", dmsg); 
  
  
if __name__ == '__main__': 
    main() 

Sample Output :

Original Message : encryption
g used :  5860696954522417707188952371547944035333315907890
g^a used :  4711309755639364289552454834506215144653958055252
g^k used :  12475188089503227615789015740709091911412567126782
g^ak used :  39448787632167136161153337226654906357756740068295
Decrypted Message : encryption

In this cryptosystem, original message M is masked by multiplying g^ak to it. To remove the mask, a clue is given in form of g^k. Unless someone knows a, he will not be able to retrieve M. This is because of finding discrete log in an cyclic group is difficult and simplying knowing g^a and g^k is not good enough to compute g^ak.

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top tutorials