Is this attack for RSA possible?

Question

$N=p·q$ ($p$ and $q$ are prime numbers), $m_1, ..., m_x$ are the messages, $e$ and $d$ are RSA encryption and decryption exponents, respectively.

I am given $e, m_1, m_1^e, m_1^d, ..., m_x, m_x^e, m_x^d$. Is it possible for me to factor $N$ or derive $d$ from the above knowledge?

My tentative answer is "no" because this problem seems to be similar to the problem mentioned in RSA Without Padding?. Therefore, my problem is also similar to the open problem 1 mentioned in Twenty Years of Attacks on the RSA Cryptosystem.

Therefore, I think it's practically impossible to recover $d$ or factor $N$, but I cannot come up with the solid proof. Can anyone help?

Answer 1

The original question states that we are given $e,m_1,{m_1}^e,{m_1}^d,\dots,{m_x}^e,{m_x}^d$, but not $N$; and asks for $d$ or a factorization of $N$.

I suspect some gremlin crept in this statement, because if any of the ${m_j}$ is such that ${m_j}>1$, it is trivial to obtain $d$ from ${m_j}$ and ${m_j}^d$, as $d=\log({m_j}^d)/\log(m_j)$.

So I guess we are given $e, m_1, {m_1}^e\bmod N,{m_1}^d\bmod N,\dots,{m_x},{m_x}^e\bmod N,{m_x}^d\bmod N$. If we are not given $N$, and for non-trivial choice of messages, we can find $N$ with overwhelming probability as $N=\gcd_{j=1}^x(({m_j}^e)-({m_j}^e\bmod N))$. With $N$ known, the givens ${m_1}^e\bmod N$ can be eliminated, for we can recompute them.

---

Thus the problems likely boils down to: given $N,e,m_1,{m_1}^d\bmod N,\dots,m_x,{m_x}^d\bmod N$, can we find $d$ or a factorization of $N$?

If the givens (beside $N$) allowed to efficiently factor $N$, that would solve Open Problem 1 in Dan Boneh's survey given as the question's second reference, which is nearly that problem (in addition, there is freedom to choose the $m_j$).

Thus no, we do not know how the givens (beside $N$, or the givens that let us find $N$) help in factoring $N$, but we do not know how to prove that they do not help significantly. That's an open problem!

We however can state one provable fact: if the $m_j$ are chosen at random, then knowledge of the ${m_j}^d\bmod N$ can not help. Proof sketch: any efficient algorithm factoring $N$ from $(N,e,m_1,{m_1}^d\bmod N,\dots,m_x,{m_x}^d\bmod N)$ with the $m_j$ chosen at random could be turned into an efficient algorithm that factors $N$ from $(N,e)$ alone, by choosing some $c_1,\dots,c_x$ at random and computing the $m_j={c_j}^e\bmod N$.

---

Some triva:

If we knew $d$, or any working private exponent $d'$, then we could factor $N$ using an efficient probabilistic algorithm.

If we knew the factorization of $N$, we could find the smallest working private exponent $d_0=e^{-1}\bmod\lambda(N)$, such that $d\equiv d_0\pmod{\lambda(n)}$. And if we further knew that $d=e^{-1}\bmod\phi(N)$ (rather than just some working private exponent), we could find $d$.