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.

Any ideas about if it is possible this adaption?


1 Answer 1


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.
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Commented Mar 20, 2020 at 18:05
  • 1
    $\begingroup$ @fgrieu: no, it doesn't. However, solving the RSA problem for any public exponent $> 1$ would be an advancement... $\endgroup$
    – poncho
    Commented Mar 20, 2020 at 18:07

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.