Cryptography

ElGamal Cryptosystem

Taher ElGamal proposed a cryptosystem in 1985 that is similar to the Diffie- Hellman key agreement protocol and published it in [8]

Setup

Suppose Alice wants to send an encrypted message to bob. First they select p and s

• p is a large prime number called the public prime

• s is a number in the range of 2 to p-1, called the public base

• Alice chooses a number a at random in the range of 2 to p-2, then calculates A = s^a Mod p and uses a as private key and A as public key

• Bob chooses a number b at random in the range of 2 to p-2, then calculates B = s^b Mod p and uses b as private key and B as public key

Message blocks must be number in the range of 2 to p-1

Encryption/Decryption 

• Alice wants to send a message X to Bob

• Choose a random number k in the range of 2 to p-2 (called session key).

• Calculate

• t =  s^k Mod p  and

• Y = (B^k * X) Mod p

• Send t and Y to Bob

• Bob receives t and Y

• Calculate (t^b)^-1 

  we know that t  = s ^k  

  (t ^b) = (s ^k ) ^b  = s ^{k b}          

  So (t ^b )^-1 = ( s ^bk ) ^-1

• Bob multiplies Y and (t^b)^-1 to obtain X

• Y *  (t^b)^-1 = (B^k * X  * (t^b)^-1) Mod  =( X *  s^bk * (s^bk)^-1 ) Mod  = X Mod p

Example

• Public Prime p = 79

• Public Base   s = 56

• Alice chooses a= 35

• Alice calculates A  = s^a Mod p = (56)³⁵ Mod 79 =  15366711764103772265936719131269189389773889471090594389426176 Mod 79 = 24

• Bob chooses b= 12

• Bob calculates B  = s^b Mod p  =  (56)¹² Mod 79 = 951166013805414055936 Mod 79 = 1  

• Alice chooses session key k = 41

• Alice calculates t =  s^k Mod p = (56)⁴¹ Mod 79 = 473924441822997958705856923323515237175789701663119727479121557644640256 Mod 79 = 24

• Alice want to encrypt the message represented by number 10.

• She calculates Y =  (B^k * X) Mod p = 1; and sends t and Y to Bob

• Bob calculates key X = ( X *  s^bk * (s^bk)^-1 ) Mod   =  10