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.

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}$

share|improve this question

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.

share|improve this answer

Your Answer

 
discard

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

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