# Showing that security of a elgamal invariant is insecure

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

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

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

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.