The ElGamal signature scheme presented in class is weak against Existential Forgery. Here is the basic exis-

tential forgery attack. Choose u, v such that gcd(v, p ? 1) = 1. Compute r = y^v g^u mod p and s = ?rv^?1

mod p ? 1.

(a) Prove the claim that the pair (r, s) is a valid signature on the message m = su mod p ? 1.

(b) Suppose a hash function h is used and the signature must be valid for h(m) instead of m. Explain how

this scheme protects against existential forgery