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: \(\quad q\) prime number

\[\alpha \quad \alpha

Private key:

\[X X

Public key:

\[Y=\alpha^{X} \bmod q\]

To sign a message \(M\), compute \(h=H(M)\), which is the hash code of the message. We require that \(\operatorname{gcd}(h, q-1)=1\). 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 \(Z\) to satisfy \(Z \times h \equiv X(\bmod q-1)\). The signature of the message is \(\alpha^{Z}\). To verify the signature, a user verifies that \(Y=\left(\alpha^{Z}ight)^{h}=\alpha^{X} \bmod q\).

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.