Take the 2-minute tour ×
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.

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 at 9:30
Thanks for your effort. DrLecter –  Alice and Bob Apr 12 at 10:37

1 Answer 1

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.

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