Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$


$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$

share|improve this question
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
up vote 5 down vote accepted

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.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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