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

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

$$s = (m – r\cdotα)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\cdot\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."

  • 1
    $\begingroup$ I edited your question to make it more readable. Please check if I introduced any bugs. $\endgroup$ – DrLecter Apr 12 '14 at 9:30

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

Observe 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 arbitrary 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 signature $(r,s')$ for any message $m'$ of your choice.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy