ElGamal Encryption Algorithm
ElGamal encryption is a 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 ga and gk, it is extremely difficult to compute gak.
Idea of ElGamal cryptosystem:
Suppose Alice wants to communicate with Bob.
- Bob generates public and private keys:
- Bob chooses a very large number q and a cyclic group Fq.
- From the cyclic group Fq, he choose any element g and
an element a such that gcd(a, q) = 1. - Then he computes h = ga.
- Bob publishes F, h = ga, 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 = gk and s = hk = gak.
- She multiples s with M.
- Then she sends (p, M*s) = (gk, M*s).
- Alice selects an element k from cyclic group F
- Bob decrypts the message :
- Bob calculates s′ = pa = gak.
- He divides M*s by s′ to obtain M as s = s′.
Following is the implementation of the ElGamal cryptosystem in Python
Python3
# 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, the original message M is masked by multiplying gak to it. To remove the mask, a clue is given in form of gk. Unless someone knows a, he will not be able to retrieve M. This is because finding discrete log in a cyclic group is difficult and simplifying knowing ga and gk is not good enough to compute gak.
Advantages:
- Security: ElGamal is based on the discrete logarithm problem, which is considered to be a hard problem to solve. This makes it secure against attacks from hackers.
- Key distribution: The encryption and decryption keys are different, making it easier to distribute keys securely. This allows for secure communication between multiple parties.
- Digital signatures: ElGamal can also be used for digital signatures, which allows for secure authentication of messages.
Disadvantages:
- Slow processing: ElGamal is slower compared to other encryption algorithms, especially when used with long keys. This can make it impractical for certain applications that require fast processing speeds.
- Key size: ElGamal requires larger key sizes to achieve the same level of security as other algorithms. This can make it more difficult to use in some applications.
- Vulnerability to certain attacks: ElGamal is vulnerable to attacks based on the discrete logarithm problem, such as the index calculus algorithm. This can reduce the security of the algorithm in certain situations.
Contact Us