I have a question I can't solve from one of the courses I'm currently taking:

Show that given a legitimate ElGamal signature $(S,R)$ on a given message $m$, an attacker
can compute a signature on messages of the form: $m'=(m+bS)a\mod p - 1$,
when $b\in Z_p^*$ is chosen as the attacker wishes and $a=g^b\mod p$.

Hint: Observe the value of $g^{ma+baS}$


1 Answer 1


I assume that the deadline for the homework is passed, so I will provide an answer:

Let us assume that we have the public key $y=g^x \pmod p$ and the private key to be $x$.

Computing an ElGamal signature for a message $m \in Z_p^*$ amounts to:

  • choosing $k\in Z_p^*$
  • $r\equiv g^k \pmod p$
  • $s\equiv (m-xk)k^{-1} \pmod{p-1}$ which is equivalent to $m\equiv xr+sk \pmod{p-1}$

The signature for $m$ is the pair $(r,s)$ and verifying the signature amounts to checking whether $g^m \equiv y^r r^s$ holds and it is easy to check that this holds, since we have $y^r r^s \equiv g^{xr+sk} \equiv g^m \pmod p$.

We have to show that given a signature $(r,s)$ allows to forge signatures of the type $m'\equiv (m+bs)a \pmod{p−1}$ for $a=g^b$ with $b\in Z_p^*$ chosen by the adversary.

You got a hint $g^{m'} \equiv g^{am+abs}$, but it is better to see if you go one step further:

$g^{m'} \equiv g^{am+abs} \equiv g^{a(xr+sk)+abs}\equiv g^{axr+ask+abs} \pmod p.$

Now, on the right hand side of the verification equation $y$ is fixed. So we have to figure out how $r'$ and $s'$ need to look like such that the verification equation can hold:

$g^{axr+ask+abs} \equiv y^{r'}r'^{s'}$

Observe that for the first term we have to set $r'\equiv ra \pmod p$ which is equal to $g^{k+b}$. Consequently, we are still missing $a$ and thus set $s'\equiv as \pmod{p-1}$.

If we now look at the left hand side of the verification equation, we obtain:

$y^{r'}r'^{s'} \equiv y^{ra}r'^{as} \equiv g^{xra}(g^{k+b})^{as}\equiv g^{xra+ask+asb}\equiv g^{m'}$

which shows, that the verification relation holds for these types of forgeries.

  • $\begingroup$ I cannot comment on answer above but I wanted to add that if ar mod p is not equal to ar mod p-1 obtained signature would not be valid, as g^(xra) is not equal to g^(x*(ra)mod p) but to q^(x*(ra)mod p-1) $\endgroup$
    – Sobuch
    Nov 2, 2017 at 10:38
  • $\begingroup$ how to choose b? and how to get m' ? my understanding is to forge the signature for a specific desired m'. But a=g^b to get that? $\endgroup$ Dec 11, 2020 at 0:10

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.