In the ElGamal signature scheme we calculate a signature for a (hashed) message $m$ as

$r \equiv_p g^k$,

$s \equiv_{p-1} (m - xr) k^{-1}$

and verify it by checking

$g^m \equiv_p y^r r^s$.

Here $r$ is a group element which is in some cases used as an exponent. This is not a problem, as long as the group elements are just natural numbers, but using a different group, this causes complications (like in EC-DSA, where we have to use just one coordinate of $r$ when it ought to be an exponent).

Even though this is admittedly not a big problem, my question is: Why is it even necessary to include $r$ as an exponent in $s$? Would changing the calculation of $s$ to just

$s \equiv_{p-1} (m - x) k^{-1}$

and the verification condition to

$g^m \equiv_p y r^s$

be insecure in some way? So far I couldn't find a way to forge a signature or extract $x$ or $k$ from this modified scheme.

  • $\begingroup$ Choose arbitrary $s$ in $Z_{p-1}^*$ (i.e. invertible) and set $r=(y^{-1}g^m)^{s^{-1}}$. $\endgroup$
    – DrLecter
    Aug 20 '14 at 20:00

With your proposed modification of the ElGamal signature scheme you can produce forgeries for arbitrary (hashed) messages $m$.

By looking at the verification equation $$g^m = yr^s$$ you just have to set $r$ to $r=(g^my^{-1})^{s^{-1}}$ (just by rearranging the verification equation) which you can do for any $s$ from $\mathbb{Z}_{p-1}^*$, i.e., every $s$ that has a multiplicative inverse in $\mathbb{Z}_{p-1}$.


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.