0
$\begingroup$

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?

Thanks

$\endgroup$

Your Answer

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