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 = gx mod p
3) Bob generates two cipher text,
C1 = gy mod p
C2 = M Ky (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 = C1-x C2 (mod p)
Example :
Suppose, p = 17, g = 6, x = 5, y = 10, M = 13
Public key, K = 65 mod 17 = 7
C1 = 610 mod 17 = 15
C2 = 13 * 710 mod 17 = 9
Then, plain text = 15-5 * 9 (mod 17) = 13 (15-5 mod 17 can be found out by Euler’s theorem)