Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

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

Original Elgamal signature is defined $S(m, \alpha) = (r, s)$, where

$$r = g^k \bmod p$$

$$s = (m – r*α)k^{-1} \bmod (p – 1)$$

more information on Elgamal signature can be found here.

Variant of a Elgamal signature scheme is defined as

$$s = (r*\alpha + k)m^{-1} \bmod (p-1) $$

I was stuck in the question that: "Show that attacker Eve who has observed the signature of a message m can obtain the signature of any message she likes."

share|improve this question
I edited your question to make it more readable. Please check if I introduced any bugs. – DrLecter Apr 12 '14 at 9:30
Thanks for your effort. DrLecter – user12992 Apr 12 '14 at 10:37
up vote 2 down vote accepted

You have just to look at the signing/verification relation.

Just write it as $$m\cdot s \equiv r\cdot \alpha + k \bmod (p-1)$$

And the verification relation should be $$g^{s\cdot m}\stackrel{?}{\equiv} y^r\cdot r \bmod p$$ where $y=g^\alpha$ is the public key and you eavesdrop a signature $(r,s)$ for $m$.

Obseve that you can take any multiplicative decomposition of the left hand side of the verification relation that yields the value $$m\cdot s \bmod (p-1)$$ to compute a signature for an arbtirary message $m'$ (I let the details to you, this should be easy to figure out). Let $r$ be identical to the eavesdropped signature and just adjust your new $s'$ to the chosen $m'$ and you will have a valid siganture $(r,s')$ for any message $m'$ of your choice.

share|improve this answer

Your Answer


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