# Common modulus attack with not coprime exponents

lets suppose we have the public keys $$(n,e_1)$$ and $$(n,e_2)$$, such that $$\gcd(e_1,e_2)=d>1$$, and the same message encrypted with these two keys.

I'm trying to see if common modulus attack on RSA can be adapted to these problem where $$e_1$$ and $$e_2$$ are not coprime, but I always get stuck at some point where I should calculate a discrete logarithm, which is obviouslly not viable in an attack to a cryptosystem.

No, it's not possible (or so we hope). If you could, you could break RSA.

Suppose you had an Oracle that, given $$n, e_1, e_2, m^{e_1}, m^{e_2}$$ with $$\gcd(e_1, e_2) = d$$, and which is able to output $$m$$. We can assume that the Oracle only works for a specific $$e_1, e_2$$ pair.

Then, suppose you were given $$c = m^d$$, and wanted to recover $$m$$. Here is what you could do:

• Compute $$c_1 = c^{e_1/d}$$, and $$c_2 = c^{e_2/d}$$

We note that $$c_1 = m^{e_1}$$ and $$c_2 = m^{e_2}$$.

• We give $$n, e_1, e_2, c_1, c_2$$ to our Oracle; our inputs matches the Oracle requirements and so it produces $$m$$, thus solving the original RSA problem.
• This (nicely) proves that the oracle can solve RSA with public exponent $\gcd(e_1,e_2)$. It does not prove that the oracle can help solve RSA with large random public exponent.
– fgrieu
Commented Mar 20, 2020 at 18:05
• @fgrieu: no, it doesn't. However, solving the RSA problem for any public exponent $> 1$ would be an advancement... Commented Mar 20, 2020 at 18:07