The Elgamal digital signature scheme employs a public key consisting of the triple {y,p,g) and a private key x, where these numbers satisfy y = g x mod p. To sign a message M, choose a random number k...

The Elgamal digital signature scheme employs a public key consisting of the triple {y,p,g) and a private key x, where these numbers satisfy

y = g
^x
mod p.

To sign a message M, choose a random number k such that k has no factor in common with p — 1 and compute

a = g
^k
mod p.

Then find a value s that satisfies

M = xa + ks mod (p — 1)

which is easy to do using the Euclidean Algorithm. The signature is verified provided that

y
^a
a
^s
= g
^M
mod p.

a. Select values (y,p,g) and x that satisfy equation (4.9). Choose a message M, compute the signature, and verify that equation (4.10) holds.

b. Prove that the math in Elgamal works, that is, prove that equation (4.10) always holds for appropriately chosen values. Hint: Use Fermat's Little Theorem, which states that if p is prime and p does not divide z, then z
^{p ~ l}
= 1 mod p.