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.


1 Answer 1


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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