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.

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.

share|improve this question

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

share|improve this answer
    
Can you be more explicit with the calculation of s2? I'm not exactly seeing why they are equal. –  Kairos Dec 2 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 at 13:40
    
OK, I have just edited the answer to add more detail on that –  cygnusv Dec 2 at 15:28

Your Answer

 
discard

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.