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

No comments:

Post a Comment