Elgamal

Elgamal cryptographic system is a public-key algorithm based on discrete logarithm.
Elgamal cryptographic system is used in digital signature standard (DSS).

There are prime number q and primitive root of \(q = a\).
User A want to generate private and public keys as the following:
1- Generate a random integer \({X}_ {a}\) such that 1 < \({X}_{a}\) < \(q-1\).
2- Compute \({Y}_{a}=a^{{X}_{a}} mod(q)\).
\({X}_{a}\) is A’s private key and (q,a,\({Y}_{a}\)) is A’s public key.
If user B Has A’s public key then he can send him encrypted message as the following:
1- Represent the message as an integer M such that 0 <= M <= \(q-1\), and longer messages are send as a sequence of blocks, each block has integer value less than q.
2- Choose a random number k such that 1 <= k <= \(q-1\).
3- Calculate one-time key \(K = ({Y}_{a})^{k} mod(q)\).
4- Encrypt the message M as a pair of integer(C1,C2)
   \({C}_{1} = a^{k} mod(q) \\\  {C}_{2} = KM mod(q)\).

1- Recover the key by calculating \(K ={C}_{1}^{{X}_{a}} mod(q)\).
2- Calculate \(M = {C}_{2}*k^{-1} mod(q)\).

K value is defined during the encryption process
\(K = {Y}_{a}^{k} mod(q)\) which we can substitute \({Y}_{a}=a^{{X}_{a}} mod(q)\)
Then \(K = (a^{{X}_{a}} mod(q))^{k} mod(q)\)
Then \(K = a^{(k{X}_{a})} mod(q)\) which we substitute \(a^{k} mod(q) = {C}_{1}  ( {C}_{1} = a^{k} mod(q))\)
Then \(K = {C}_{1}^{{X}_{a}} mod(q)\).
Example:
In Elgamal public key scheme suppose prime number q = 19 and primitive root of 19 we choose a=10
User A generate private and public keys as the following:
1- User A choose \({X}_{a} = 5\).
2- \({Y}_{a} = a^{{X}_{a}} mod(q) = 10^{5} mod(19) = 13\)
User A’s public key = (19,10,3) and A’s private key=5
User B want to send encrypted message M to user A with M value = 17
1- User B choose k=6.
2- \(K = {Y}_{a}^{k} mod(q) = 3^{6} mod(19) = 7\).
Then \({C}_{1} = a^{k} mod(q) = 10^{6} mod(19) = 11\)
\({C}_{2} = KM\ mod(q) = 7*17 mod(19) = 5\)
Then user B send \({C}_{1} = 11 \ and \ {C}_{2} = 5\) to user A.
Then user A decrypt the message
1- User A calculate \(K = {C}_{1}^{{X}_{a}} mod(q) = 11^{5} mod(19) = 7\)
2- The \(K^{-1}\ in \ GF(19) = K^{-1} mod(19) = 7^{-1} mod(19) = 11\)
3- \(M = ({C}_{2}K^{-1})mod(q) = (5*11) mod(19) = 17\)