The professor left us a question on ElGamal signatures:
Given the hash function $H$ and message $M$, choose a random $r$ and compute $h=g^r$ and $H(M||h)$. Show that, if $H(M)$ is used instead of $H(M||h)$, the signature can be existentially forged.
I am struggling with the problem, and I think that maybe we can get one known message signed twice with different $(M, c_1, h_1)$ and $(M, c_2, h_2)$, and then use that to sign some other messages $M'$, but I have no idea how to proceed. Can anyone give me some hints?