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

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

Public elements:
qprime number a aqand a is a primitive root of
q

Public key: Y = a^Xmod q

To sign a message M, compute
h=
H(M), which is the hash code of the message. We gcd(h, q - 1)=1 require that . If not, append the hash to the message and calculate a new hash. Continue this process until a hash code is produced that is relatively prime to (q- 1) .Then calculate Zto satisfy .The * h = X(mod q - 1)signature of the message is a
^Z
.To verify the signature, a user verifies that Y = (a^Z)h = a^Xmodq.

a. Show that this scheme works. That is, show that the verification process produces an equality if the signature is valid.

b. Show that the scheme is unacceptable by describing a simple technique for forging a user’s signature on an arbitrary message.