EI- Gamal Cryptography

EI gamal cryptography works in 3 steps/stages

$\hspace{1.5cm}$a. Key generation

$\hspace{1.5cm}$b. EI gamal encryption

$\hspace{1.5cm}$c. EI gamal decryption

A. EI gamal key generation:

1. Select a large prime number ‘p’

2. Select encryption key $‘e_1’$ to be primitive root of mod p

3. Select decryption key ‘d’ such that $1≤d≤p-2$

4. Select encryption key $‘e_2’$ such that

$\hspace{1.5cm}e_2 = e_1^d \ mod \ p$

1. Form the set i,e public key $(e_1, e_2, p)$ to be announced publicly

2. Private Key 'd' to be kept secret.

B. EI gamal key encryption:

1. Select a random number ‘r’

2. Compute the first part of ciphertext $‘c_1’ , c_1 = e_1^r mod p$

3. Compute the second part of ciphertext $‘c_2’ , c_2 = (e_2^r * PT) mod p$

C. EI gamal key decryption:

1. Calculate the PT

$\hspace{1.5cm}PT = (c_2 * (c_1^{p-1-d} )) mod p$

Example 1:

let Plaintext M = 7

$e_1$ = 2

d = 3

Random no 'r' = 4

1. Key generation:

$p= 11 \quad e_1 = 2 \quad d =3$

$\begin{aligned} e_2 &= e_1^d \ mod \ p \\ &= 2^3 mod 11 \\ &= 8 \ mod \ 11 \\ &= 8 \end{aligned}$

2. Encryption:

$\begin{aligned} &\text{Random no r} = 4 \\ \\ c_1 &= e_1^r \ mod \ p \\ &= 2^4 \ mod \ 11 \\ &= 16 \ mod \ 11 \\ &= 5 \\ \\ c_2 &= Pt * e_2^r \ mod \ p \\ &= 7 * 8^4 \ mod \ 11 \\ &= 28672 \ mod 11 \\ &= 6 \\ \end{aligned}$

3. Decryption:

$\begin{aligned} PT &= (c_2 * (c_1^{p-1-d} )) \ mod \ p \\ &= (7*5^{11-1-3}) \ mod \ 11 \\ &= 18 \ mod \ 11 \\ &= 7 \end{aligned}$

Example 2:

let Plaintext M = 6

$e_1 = 5 \quad d = 2 \quad Random no 'r' = 4$

1. Key generation:

$P= 7, \quad e_1 = 5 \text{ and } d = 2$

$\begin{aligned} e_2 &= e_1^d \ mod \ p \\ &= 5^2 \ mod \ 7 \\ &= 25 \ mod \ 7 \\ &= 4 \end{aligned}$

2. Encryption:

$\begin{aligned} &\text{Random no r } = 4 \\ \\ c_1 &= e_1^r \ mod \ p \\ &= 5^4 mod 7 \\ &= 625 mod 7 \\ &= 2 \\ \\ c_2 &= P t * e_2^r \ mod \ p \\ &= 6 * 4^4 mod 7 \\ &= 1536 mod 7 \\ &= 3 \end{aligned}$

3. Decryption:

$\begin{aligned} PT &= (c_2 * (c_1^{p-1-d} )) \ mod \ p \\ &= (3*2^{7-1-2}) \ mod \ 7 \\ &= 48 \ mod \ 7 \\ &= 6 \end{aligned}$