## 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 = g^{a} 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 = g^{a} (mod p)

Therefore 9 = 11^{6} (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=g^{k} mod p and C2=MA^{k} mod p

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

Therefore if C1=g^{k} mod p and C2=MA^{k} mod p

Then C1=11^{3} mod 23 and C2=10*9^{3} mod 23

C1=20, C2= 22

The cipher text is (20, 22)

**Simplified Decryption Example**

Alice receives (20,22)

The calculation is C2 / C1^{a}=(g^{k})^{a} mod p

where 20^{6} = (11^{3})^{6}^{ }mod 23. Both calculate as 16

(This is where the final calculation goes, when I figure it out !)