# Given 2 Digital Signature generated by $S=D\times k^r$ how do you solve for $k$?

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.

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