4
$\begingroup$

Hi I know there have been other questions like this on here, namely here.

But of all the solutions I have seen of this problem, $e_1$ and $e_2$ are relatively prime, which is how we can get to the final equation $m \equiv c_1^{\,a} \cdot c_2^{\,b} \pmod n $, where $a$ and $b$ are from the equation $a\cdot e_1 + b\cdot e_2 =\gcd(e_1,e_2)$ from the extended euclidean algorithm.

However I'm wondering how to do it where $\gcd(e_1, e_2) >1$. I can get to a point where I have $m^{\gcd(e_1,e_2)} \equiv c_1^{\,a} \cdot c_2^{\,b}$ (as with the other solutions). But with $\gcd(e_1,e_2) \neq 1$, I am at square one with having $m$ under an exponent.

Is there another way to do this or a way to solve this problem?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

Is there another way to do this or a way to solve this problem?

We hope not; otherwise, you can break RSA.

Suppose you did have a way that, given $m^{e_1} \bmod n$ and $m^{e_2} \bmod n$ (and $e_1$ and $e_2$), you could recover $m$ (even if $e_1, e_2$ were not relatively prime).

Then, given $m^e \bmod n$ and $e$ (which is standard RSA), here is what you can do: you can select random values $r_1, r_2$ and compute $e_1 = e \cdot r_1$ and $e_2 = e \cdot r_2$. Then, you compute $(m^e)^{r_1} = m^{e_1} \pmod{n}$ and $(m^e)^{r_2} = m^{e_2} \pmod {n}$. You can then give these values to the method, and since you have satisfied all the requirements, your method will give you $m$, and so solving the RSA problem.

Again, we certainly hope RSA can't be broken that easily...

Improve this answer
$\endgroup$
6
  • $\begingroup$ I was at first concerned that $e$ here could be an improper exponent for the modulus (see the first sentence here) rendering this actually insecure. But after thinking about it some, that would ultimately make the two larger exponents invalid as well, making the whole scenario problematic to begin with. So assuming the two exponents encountered are "correct", I believe the reduced exponent should be as well. This wasn't immediately obvious to me, though, so I figured I'd call it out. $\endgroup$
    – thesquaregroot
    Sep 24, 2021 at 4:40
  • $\begingroup$ @thesquaregroot: actually, there is no security issue with small $e$ (as long as it's $> 1$, of course), if you did the padding correctly. If you don't, well, my advise would be ... do the padding correctly... $\endgroup$
    – poncho
    Sep 24, 2021 at 13:20
  • $\begingroup$ With $e=2$ you don't have RSA but the Rabin cryptosystem, which surprisingly works albeit a bit differently. $\endgroup$
    – R.. GitHub STOP HELPING ICE
    Sep 24, 2021 at 15:33
  • $\begingroup$ @poncho My concern wasn't about small $e$ values, it was $e$ values that are not relatively prime to p-1 for all primes p which divide the modulus. The post I linked to is specifically about how small $e$ values aren't problematic if you do padding correctly. I originally just wanted to make sure that your logic was true regardless of the value of $e$, for a given modulus. My conclusion was that if $e$ would be insecure, so would $e_1$ and $e_2$, so the problem would be more trivial on those grounds. $\endgroup$
    – thesquaregroot
    Sep 24, 2021 at 17:51
  • 1
    $\begingroup$ @thesquaregroot: there isn't a security problem with values of $e$ not relatively prime to $p-1$; it's rather that you can't uniquely decrypt them. As for the security, you can make an even better security claim for such an $e$, that is, if you have a black box that, given $m^e \bmod n$ (and given that such an $m$ exists) for such an $e > 0$, finds a possible value of $m$, then you can efficiently factor $n$ (!) - that is not known for standard RSA. $\endgroup$
    – poncho
    Sep 24, 2021 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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