The ElGamal signature scheme presented is weak to a type of attack known as existential forgery. Here is the basic existential forgery attack. Choose $u,v$ such that $\gcd(v, p — 1) = 1$. Compute $r = \beta^{v}\alpha^{u} \pmod{p}$ and $s = -rv^{-1} \pmod{p-1}$.

(a) Prove the claim that $(r, s)$ is a valid signature for the message $m = su \pmod{p-1}$.

(b) Suppose a hash function $h$ is used and the signature must be valid for $h(m)$ instead of $m$ (so we need to have $h(m) = su)$. Explain how this protects against existential forgery. That is, explain why it's hard to produce a forged, signed message by this procedure.

For (a), I showed

$$v_{1} \equiv \beta^{r}r^{-rv^{-1}} \equiv \beta^{r}(\beta^{v}\alpha^{u})^{-rv^{-1}} \equiv \alpha^{ar - arvv^{-1}-urv^{-1}} \equiv \alpha^{-urv^{-1}},$$

and $$v_{2}\equiv\alpha^{m}\equiv \alpha^{su} \equiv \alpha^{-ruv^{-1}},$$

which shows $v_{1}\equiv v_{2}$, meaning that the signature is valid.

For (b), a solution I have says the following:

"In part $(a)$, we choose the message by letting $m \equiv su\pmod{p - 1}$. Thus, once $u, v$ are chose, it is unlikely that $\alpha^{h(m)} \equiv \alpha^{m} \pmod{p - 1}$. So, the signature will probably not be valid."

I'm having trouble understanding their thought process in $(b)$. How did they get $\alpha^{h(m)} \equiv \alpha^{m} \pmod{p - 1}$? Why would showing this mean that the signature is valid? Also, why is it unlikely that they are congruent?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy