Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
I tried to clean up your question a bit, but there were some places where I wasn't really sure what you meant. Could you please check that I didn't introduce any mistakes, and maybe try to clarify your question further. –  Ilmari Karonen Feb 27 '13 at 12:22
It would useful to clarify how the question relates to the ElGamal signature scheme –  fgrieu Feb 27 '13 at 12:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.