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].