## El Gamal explained

### May 19, 2010

This is a work in progress. I need to check as there is an Error in the Decryption ! I will edit when I get time to fix the issue.

El-Gamal (Simplified)

Key generation

Alice has a prime number (p) Special Number (g) and a random number for her private key (a)

• (p) is the key so needs to be long (1024\2048)
• (g) must be a primitive element modulo (p)
• (a) must be bigger than 1 and smaller than p-1

The algorithm is A = ga mod p

Alice’s public key is A

Alice’s private key is a.

The system-wide parameters are p & g

Simplified key generation Example

p = 23

g = 11

a = 6

Therefore, A = ga (mod p)

Therefore 9 = 116 (mod 23)

Alice’s public key is 9 (A), and her private key is 6 (a).

The public key is known to everyone and the parameters p & g are known to everyone

Simplified Encryption Example

The example message Bob sends is 10 (M)

Bob generate a random number 3 (k).

Compute C1 and C2 where C1=gk mod p and C2=MAk mod p

Bob sends (C1,C2) to the Alice, this contains the message and value k.

Therefore if C1=gk mod p and C2=MAk mod p

Then C1=113 mod 23 and C2=10*93 mod 23

C1=20, C2= 22

The cipher text is (20, 22)

Simplified Decryption Example