0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.
| improve this answer | |
$\endgroup$
  • $\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 Mar 20 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 Mar 20 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.