## 5/16/2016

### cryptography14

Cryptography 14

Elgamal Cryptographic System

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

Elgamal Cryptographic algorithm:

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)$.

User A can decrypt the message :

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

How user A can recover the K value to decrypt the message M?

K value is defined during the encryption process
$K = {Y}_{a}^{k} mod(q)$  ----> 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)$ ---> 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$ #.