# ElGamal signature: Forging a signature of a specific form

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

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.

-