written 6.0 years ago by |
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:
Select a large prime number ‘p’
Select encryption key $‘e_1’$ to be primitive root of mod p
Select decryption key ‘d’ such that $1≤d≤p-2$
Select encryption key $‘e_2’$ such that
$\hspace{1.5cm}e_2 = e_1^d \ mod \ p$
Form the set i,e public key $(e_1, e_2, p)$ to be announced publicly
Private Key 'd' to be kept secret.
B. EI gamal key encryption:
Select a random number ‘r’
Compute the first part of ciphertext $‘c_1’ , c_1 = e_1^r mod p$
Compute the second part of ciphertext $‘c_2’ , c_2 = (e_2^r * PT) mod p$
C. EI gamal key decryption:
- 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}$