El-gamal digital signature scheme:

• This scheme used the same keys but a different algorithm

• The algorithm creates two digital signatures, these two signatures, are used in the verification phase.

• The key generation process is the same as that of EI-gamal algorithms

• The public key remains ($e_1, e_2, p$) and the private key continues to be d

Signature

This process works as follows

1. The sender selects a random number r

2. The sender computes the first signature $s_1$ using $s_1 = e_1^rmodp$

3. The sender computes the second signature $s_2$ using the equation

$s_2$ =$(M-d Xs_1) X r^{-1}mod (p-1)$

Where P= large prime number

M= original message that needs to be signed

1. The sender sends $M, s_1, s_2$ to the receiver.

For eg. Let $e_1$ = 10, $e_2$ = 4, p=19, M=14, d=16 & r=5

Then, $s_1 = e_1^{R} modp $= $10^5mod19$= 3

$s_2 =(M-d X s_1) X r^{-1}mod (p-1) = (14-16 X 3) X 5^{-1}mod (18) $= 4

Then these signatures $s_1 and s_2$ are sent to the receiver.

Verification:

This process works as follows.

1.The receiver performs the 1st part of verification called $v_1$ using the equation

$v_1 = e_1^M mod P$

2.The receiver performs the 2nd part of verification called as $v_2$ using the equation

$v_2 = e_2^{s_1} s_1^{(s_2)}mod p$

Eg

$v_1 = e_1^M mod p$ = $10^{14} mod 19$ = 16

and

$v_2 = e_2^{s_1} s_1^{(s_2)}mod p = 4^3 X 3^4 mod p$ = 5184 mod 19 = 16

Since $v_1$=$v_2$, the signature is valid.