Here is an improved version of the scheme given in the previous problem. As before, we have a global elliptic curve, prime \(p\), and "generator" \(G\). Alice picks a private signing key \(X_{A}\) and forms the public verifying key \(Y_{A}=X_{A} G\). To sign a message \(M\) :

- Bob picks a value \(k\).

- Bob sends Alice \(C_{1}=k G\).

- Alice sends Bob \(M\) and the signature \(S=M-X_{A} C_{1}\).

- Bob verifies that \(M=S+k Y_{A}\).

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

b. Show that forging a message in this scheme is as hard as breaking (ElGamal) elliptic curve cryptography. (Or find an easier way to forge a message?)

c. This scheme has an extra "pass" compared to other cryptosystems and signature schemes we have looked at. What are some drawbacks to this?