# El Gamal existential forgery using Pointcheval–Stern signature algorithm

I found that there exists an algorithm that claims to make the El Gamal signature generation more secure. The algorithm can be found here as a pdf.

I'm mainly interested in the two-parameter forgery that goes as the following:

Let $1 < e,v < p-1$ be random elements and $gcd (v,p-1)=1$. If $r = g^e \cdot y^v \bmod{p}$ and $s = -r \cdot v^{-1} \bmod{p-1}$, the tuple $(r,s)$ is a valid signature for the message $m = e \cdot s \bmod{p-1}$.

My question is how does this work? Is there a well explained proof?

By definition, a valid original ElGamal signature on a message $m \in \{1, \dots, p-1\}$ is a pair $(r,s)$ satisfying $g^m \equiv y^r \cdot r^s \pmod p$.
With $r = g^e \cdot y^v \bmod p$ and $s = -r\cdot v^{-1} \bmod (p-1)$ for random integers $e$ and $v$ the pair $(r,s)$ is a valid signature on message $m = e \cdot s \bmod (p-1)$. To see it, you must check that $g^m \equiv y^r \cdot r^s \pmod p$:
1. For $m = e \cdot s \bmod (p-1)$, we have $g^m \equiv g^{e\cdot s} \pmod p$;
2. With $r = g^e \cdot y^v \bmod p$ and $s = -r\cdot v^{-1} \bmod (p-1)$, we have $y^r \cdot r^s \equiv y^r \cdot (g^e \cdot y^v)^s \equiv y^{r+v\cdot s}\cdot g^{e\cdot s} \equiv y^{r+v\cdot (-r\cdot v^{-1})}\cdot g^{e\cdot s} \equiv y^0 \cdot g^{e\cdot s} \equiv g^{e\cdot s} \pmod p$.
Since the two sides are equal modulo $p$, the signature is valid. Q.E.D.