# Factoring RSA when reusing N

Suppose in two RSA instances the same $$p,q,N$$ are used, but different public keys $$a,b$$ (and corresponding private keys)

Suppose now we have the two equations

$$c_{1}=m^{a} \bmod N$$

$$c_{2}=m^{b} \bmod N$$

Is it possibe to retrieve the original message $$m$$ with this information?

• You might want to modify the title - this attack would not lead to a factorization of $N$... Jul 19, 2021 at 18:41

It is possible to retrieve $$m$$ if $$a$$ and $$b$$ are coprime.

This means $$GCD(a,b)=1$$. Then, applying the Extended Euclidiean Algorithm we have $$ax+by=GCD(a,b) = 1$$ Therefore, $$c_1^x.c_2^y = m^{ax}.m^{by} = m^{ax+by} = m\bmod N$$

So just like that, we could recover $$m$$ but this gives us no information about the factorization of $$N=pq$$.

Is it possible to retrieve the original message $$m$$ with this information?

Well, this is a standard exercise for beginners (that is, you're supposed to learn from it), and so I won't spell out the answer.

I will give you a hint: if you know $$N, c_1 = m^a \bmod N, c_2 = m^b \bmod N$$, can you compute the value of $$c_3 = m^{a-b} \bmod N$$? If so, how could you exploit that?

And, at the end, what condition must exist between $$a$$ and $$b$$ to allow you to recover $$m$$?

• Removed answer so only the hint is left... congrats :) Jul 20, 2021 at 0:14
• in case he wants to see an example. math.stackexchange.com/questions/2730675/…
– SSA
Jul 20, 2021 at 4:40