# Generating a valid signature on El-Gamal without knowing the private key

Suppose we are given $p$, the large prime, $g$ which is the primitive root for $p$, $b$ which is calculated as $b=g^x$ mod $p$ where $x$ is the private key and $0<x<p-1$.

Also suppose we know $y=g^r$ mod $p$ where $r$ is some random number and $0<r<p-1$ and is the discrete log of $y$. We also know $s=(M-xy)(r^{-1})$ mod $(p-1)$ where $M$ is a padded message.

But now, lets suppose that we do not know $x$ but rather we know $r$, the discrete log of $y$. Now we want to forge/generate a valid signature for the message, $M2.$ Given all this information, how can we do this?

I found an article about this which states it in section 3 but I did not understand the process which can be seen at: ftp://ftp.inf.ethz.ch/pub/crypto/publications/Bleich96.pdf. I was hoping if anyone knew the simpler step for it or to put it in a simpler way, that would be great.

Any input is much appreciated. Thanks a lot.

-

First, I think you have a typo in your question since in the original article $s = (M - x y)(r^{-1}) \mod p-1$, and not $s = (M - x^y)(r^{-1}) \mod p-1$.

Knowing that, then we can construct $s_2$ from $s, r, M$ and $M_2$:

$s_2 = s + (M_2 - M)r^{-1} = (M - x^y)r^{-1} + (M_2 - M)r^{-1} = (M - x^y + M_2 - M)r^{-1} = (M_2 - x y)r^{-1}$

A valid signature for $M_2$ is then $(y, s_2)$

It is easy to see that this signature is valid:

$y^{s_2} b^y = (g^r)^{(M_2 - x y)r^{-1}} (g^x)^y = g^{M_2 - x y} g^{x y} = g^{M_2}$

-
Can you be more explicit with the calculation of s2? I'm not exactly seeing why they are equal. – Kairos Dec 2 '14 at 13:33
E.g. Add a little bit more detail to why $s + (M2 - M)r^{-1} = (M-xy) r^{-1} mod p-1$ – Kairos Dec 2 '14 at 13:40
OK, I have just edited the answer to add more detail on that – cygnusv Dec 2 '14 at 15:28