It is tempting to try to develop a variation on the Diffie-Hellman protocol that could be used as a digital signature

It is tempting to try to develop a variation on the Diffie-Hellman protocol that could be used as a digital signature. Here is one that is simpler than DSS and that does not require a secret random number in addition to the public key:

Public elements: q a prime number, and α a primitive root of q (here α < q).

Private key: X an integer with 0 ≤ X < q. Public key: Y = α X mod q.

Signing: To sign a message m, compute H = h(m), the hash value of the message.

We require that gcd(H, q−1) = 1. If not, append the hash value to the message and calculate a new hash value. Continue this procedure until a hash value is produced that is relatively prime to (q − 1). Then calculate Z to satisfy Z × H ≡ X mod (q − 1). The signature of the message is α^Z mod q.

Verifying: To verify the signature, a user verifies that (α^Z ) ^H mod q = Y. a. Show that this scheme works. That is, show that the verification process produces an equality if the signature is valid. [Hint: You may use Fermat's theorem, which is available on the Internet.]