# ElGamal Hash Function

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