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

Alice receives (20,22)

The calculation is C2 / C1a=(gk)a mod p

where 206 = (113)6 mod 23. Both calculate as 16

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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: