# How can one show that an ElGamal-like signature verification scheme is valid?

For an ElGamal-like signature scheme, I am given two things:

1. The signing function,
2. the verification function.

How can I show that the verification function is valid?

Example 1:

Signing: $s := x^{-1}(m - k·r) \pmod {p - 1}$

Verification: $g^m = (g^x)^s · r^r \pmod p$

NOTES:

$g$ is the generator over the set $\mathbb Z^*_p$.

$x$ is the secret value, $g^x$ the public one.

$r := g^k \pmod p$

-
Your scheme is not the original ElGamal scheme, and I doubt that it is valid at all. First, ElGamal uses a hash of the message where you are using the message itself (which will make the scheme less secure, and only applicable for short messages, but verification should still work). Second, in the exponents of the verification you switched $s$ and $r$. Is this a typo (and you want actually a proof for the original ElGamal), or do you really search a proof for this modified scheme? –  Paŭlo Ebermann Nov 27 '11 at 13:23

Your scheme is not the "true" ElGamal signature scheme: you swapped $x$ and $k$. I assume that $m$ is the hash of the message to sign, not the message itself.

Your scheme is sound, which means that the verification algorithm will return "ok" for a signature which has been generated as you suggest. To see that, remember Fermat's Little Theorem which says that for a prime $p$ and every integer $a$ (not multiple of $p$), we have $a^{p-1} = 1 \pmod p$. This means that when dealing with exponents, we can compute them modulo $p-1$.

So, when looking at your verification equation:

\begin{eqnarray*} (g^x)^s r^r &=& (g^x)^{x^{-1}(m - kr)} (g^k)^r \cr &=& g^{m - kr} g^{kr} \cr &=& g^m \end{eqnarray*}

Soundness means that the algorithm works as intended, not that it is secure. This specific variant of ElGamal has been proposed in 1990 by Agnew, Mullin and Vanstone (the article is called "Improved Digital Signature Scheme based on Discrete Exponentiation"; I could not find a freely downloadable version). It has then been studied in a more general framework, called Meta-ElGamal Signature Schemes. As far as I know, it is still believed secure, but uninspiring (thus understudied), because, like most ElGamal variants, it leads to rather large signatures. DSA is preferred.

-
This answer should be included in the FAQ on how to make an anwser!Bravo.. +1! ;) –  Matteo Jun 20 '12 at 9:45