ElGamal Cryptosystem

ElGamal encryption is an asymmetric key encryption algorithm and is used for public key cryptography. The sender and receiver shares a prime number p and any of its primitive element g.

Let’s say Bob is sending the message and Alice is the receiver. Then, the process going on will be as follows:

1) Alice selects a private key x, where x ∈ Zp

2) Public key is generated, K = g^x mod p

3) Bob generates two cipher text,

C₁ = g^y mod p

C₂ = M K^y (mod p),  where 1<= y <= p-2, is an ephemeral key, which is discarded after every message, M.

4) Alice computes the plain text,

Plain text = C₁^-x  C₂ (mod p)

Bob sends the message to Alice

Example :

Suppose, p = 17, g = 6, x = 5, y = 10, M = 13

Public key, K = 6⁵ mod 17 = 7

C₁ = 6¹⁰ mod 17 = 15

C₂ = 13  * 7¹⁰ mod 17 = 9

Then, plain text = 15^-5 * 9 (mod 17) = 13   (15^-5 mod 17 can be found out by Euler’s theorem)