Elgamal encryption

Elgamal encryption

Elgamal encryption invented by Taher El Gamal is an asymmetric key encryption algorithm for public-key cryptography based on discrete logarithm and Diffie-Hellman key exchange. It consists of three components the key generator, the encryption algorithm, and the decryption algorithm.

The following section describes the basics of elgamal algorithm.

Key generator

Let p be a large prime number and g be a generator of the multiplicative group Zp of the integers modulo p in the range {1… p-1}.

The group of units U (Zp) is the group of all integers relatively prime to p under multiplication mod p. All arithmetic here is done modulo p. Then we find the generators from the group of units U (Zp). Finding a Key generator is further generalized in section generator.

Public key and Private Key

Elgamal encryption consists of a public key and a private key corresponding to it. The public key and private key can be created as follows,

Choose a random number a in the range {1… p-2}.Then Computes A ,

A = ga mod p

Public key is (p, g, A) and Private Key is a.

Encryption algorithm

Let Message is an integer m in the range {1… p-1} and select a random number k in the range {1… p-2}. The Encrypted message is generated as follows,

C1 = gk mod p

C2 = m (g -a) k mod p

C= (C1, C2)

The cipher text C is send to the Receiver.

Decryption algorithm

To recover plaintext m from C (cipher text), the Receiver should need private key A and prime number p.

Decryption of the cipher text using el gamal, to retrieve the original message is as given.

M = C1-a *C2 mod p

M = C1-a *C2 mod p

= m (g -a) k * C1-a mod p

= m (ga) k *(g -a) k mod p

= m

Generator

A generator g is a number less than p for which g n mod p gives different values for every different value of n between 1 and p-1. Thus n = p-1 is the first and only time that gk mod p = 1. For example 3 is a generator for prime number 17, but 2 is not a generator for 17 because 2 8

mod 17 = 1.