3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

The scheme you consider is the original ElGamal signature. This scheme is known to be existentially forgeable.

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.