Reference no: EM13720421

El-­-Gamal Signature schemes works as follows:

Choose a prime number p and integers g, d < p;

Compute y = gd mod p. -­--­--­--­--­--­--­--­--­--­-- ­--­--­--­--­- (Equation 1) Public key: (y, g, p); Private key: d

To sign contract m:

* Choose k relatively prime to p-1, and not yet used

* Compute a = gk mod p -­--­--­--­--­--­--­--­--­--­--­--­--­--­--­-

(Equation 2)

* Find b such that m = (da + kb) mod p-1   -­--­--­--­--­--­--­--­--­--­--­--­--­--­--­-

(Equation 3)

The signature is (a, b).

The signature verification test is [yaab mod p = gm mod p]

To answer the following question you will need to use Fermat's little theorem ap-1= 1 mod p. You may use the following two consequence of Fermat's little theorem of [g a mod (p-1) mod p = ga mod p] and [ ab mod p-1 mod p = ab mod p].

Question: Prove that the equation yaab mod p = gm mod p holds for the signature values chosen by Equation 1, 2 and 3].