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\) #.

## No comments:

## Post a Comment