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?

  • 3
    $\begingroup$ 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. $\endgroup$ Feb 27, 2013 at 12:22
  • 2
    $\begingroup$ It would useful to clarify how the question relates to the ElGamal signature scheme $\endgroup$
    – fgrieu
    Feb 27, 2013 at 12:40

2 Answers 2


It's not a complete answer because an adversary needs control on the random choice of a signing algorithm.

  1. First let me define ElGamal signature to not get lost in notation. $x \in N$ is the secret key. $p$ is a prime, it defines $Z_p^*$. $g$ is a generator of $Z_p^*$. $y=g^x$ and the public key is $(p, g, g^x)$. Then $k$ is picked at random from $0<k<p-1$, $r = g^k \bmod p$, $s = (H(m) - xr)k^{-1} \bmod (p-1)$ and the signature is $(r,s)$.

  2. Suppose we know two signatures of the message $m$ for different $k$-s: $\sigma_1 = (g^{k_1} \bmod p, (H(m) - xr)k_1^{-1} \bmod (p-1)) = (r_1, s_1)$ and $\sigma_2 = (g^{k_2} \bmod p, (H(m) - xr)k_2^{-1} \bmod (p-1)) = (r_2, s_2)$.

Let $\sigma_3=(r_1r_2 \bmod p, s_1 + s_2 \bmod (p-1))$.

  1. Verification of $\sigma_3$ leads us to an equation $(k_1+k_2)(k_1^{-1}+k_2^{-1})\equiv 1 \bmod (p-1)$. If an attacker can choose $k_1, k_2$, then he can probably find proper $p$ and $k_1, k_2$. Otherwise - still a problem.
  • $\begingroup$ How is this an answer to the question? $\endgroup$
    – poncho
    Jun 14, 2015 at 1:15

Daniel Bleichenbacher has described such kind of attacks in his article Generating ElGamal signatures without knowing the secret key. (PDF)

He noticed that if verifier would accept signatures where $r$ is larger than $p$ then any signature $(r,s)$ on $H(M)$ could be used to generate a signature $(r2, s2)$ on arbitrary hash value $H(M2)$.

For that attacker should calculate $u=H(M2)H(M)^{-1} \bmod (p-1)$. This implies $g^{H(M2)}=g^{uH(M)}=y^{ru}r^{su}$. $s2$ could be setting as $s2=su\bmod (p-1)$ and $r2$ could be computing by using Chinese Remainder Theorem for two equations $r2=ru\bmod (p-1)$ and $r2=r\bmod p$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.