Given 2 signature $(D_1, r_1, S_1)$ and $(D_2, r_2, S_2)$ and the Signature is generated as $S=D\times k^r \mod N$ where $N$ is a product of 2 primes and $r_1$, $r_2$ is co-prime. How do you solve for $k$?

I got the following equations :

\begin{align} S_1 &= D_1 \times k^{r_1} \mod N \\ S_2 &= D_2 \times k^{r_2} \mod N \end{align}

I get that the hint should come from the co-primes of $r_1$, $r_2$. But I can't see why.


1 Answer 1


Given that $\gcd(r_1, r_2) = 1$, using the extended Euclidean algorithm we can find $a,b$ such that $a \cdot r_1 + b \cdot r_2 = 1$. If $D_1$ and $D_2$ are invertible $\mod N$ (which is quite likely; they only have to be coprime to the two large primes that make up $N$), we can compute $$k^{r_1} = S_1 \cdot {D_1}^{-1}$$ $$k^{r_2} = S_2 \cdot {D_2}^{-1}$$

Then we can compute $$(k^{r_1})^a \cdot (k^{r_2})^b = k^{a \cdot r_1} \cdot k^{b \cdot r_2} = k^{a \cdot r_1 + b \cdot r_2} = k^1 = k$$


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.