# An existential forgery attack on ElGamal [closed]

From an old exam question:

Consider this existential forgery attack on ElGamal. Choose $u$, and $v$ such that $\operatorname{gcd}(v, p - 1) = 1$.

Compute $r := y^v g^u \mod p$ and $s := -r·v^{-1} \mod (p-1)$. (Recall that $y := g^x \mod p$.)

$s$ will be used as part of the forged signature.

(a) Prove that $σ = (m, r, s)$ is a valid signature for $m := s^u \mod (p-1)$.

(b) Suppose that a secure hash function $h$ is used and the signature must be valid for $h(m)$ instead of $m$. Explain how this protects against existential forgery.

-
For (a), just look at the verification equation $g^m\, \overset?=\, y^r·r^s$, replace your values for $s$, $r$ and $m$ (and $y$), and do some simplifications until you have the same stuff at both sides. –  Paŭlo Ebermann Nov 28 '11 at 22:43
About your (reverted) edit: Don't forget $y = g^x$ in your calculations, as well as all occurrences of $r$ and $s$. –  Paŭlo Ebermann Nov 30 '11 at 9:01
Does it actually verify? I got $g^{(u^s)}$ on the LHS and $(g^u)^s$ on the RHS which aren't the same. I did it quickly though... –  PulpSpy Nov 30 '11 at 15:58