RSA одно и то же сообщение отправляется с двумя разными показателями степени, но степени не являются взаимно простыми.

Привет, я знаю, что здесь были и другие подобные вопросы, а именно здесь.

Но из всех решений этой проблемы, которые я видел, $e_1$ и $e_2$ взаимно просты, и именно так мы можем получить окончательное уравнение $m \equiv c_1^{\,a} \cdot c_2^{\,b} \pmod n $, куда $а$ и $b$ находятся из уравнения $a\cdot e_1 + b\cdot e_2 =\gcd(e_1,e_2)$ из расширенного алгоритма Евклида.

Однако мне интересно, как это сделать, где $\gcd(e_1, e_2) >1$. Я могу добраться до точки, где у меня есть $m^{\gcd(e_1,e_2)} \equiv c_1^{\,a} \cdot c_2^{\,b}$ (как и в других решениях). Но с $\gcd(e_1,e_2) \neq 1$, я нахожусь на первом месте с наличием $м$ под показателем.

Есть ли другой способ сделать это или способ решить эту проблему?

Есть ли другой способ сделать это или способ решить эту проблему?

Мы надеемся, что нет; в противном случае вы можете сломать RSA.

Предположим, у вас есть способ, который, учитывая $m^{e_1} \bmod n$ и $m^{e_2} \bmod n$ (и $e_1$ и $e_2$), вы можете восстановить $м$ (даже если $e_1, e_2$ не были относительно простыми).

Затем, учитывая $m^e \bmod n$ и $е$ (который является стандартным RSA), вот что вы можете сделать: вы можете выбрать случайные значения $r_1, r_2$ и вычислить $e_1 = е \cdot r_1$ и $e_2 = е \cdot r_2$. Затем вы вычисляете $(м^е)^{r_1} = м^{е_1} \pmod{n}$ и $(m^e)^{r_2} = m^{e_2} \pmod {n}$. Затем вы можете передать эти значения методу, и, поскольку вы выполнили все требования, ваш метод даст вам $м$, и так решение проблемы RSA.

Опять же, мы, конечно, надеемся, что RSA не так легко взломать...