Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

$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?

share|improve this question
    
Welcome to crypto.stackexchange. By m_1^d did you mean ${m_1}^d\bmod N$ (which we can enter as ${m_1}^d\bmod N$)?. Please also state if we are given $N$. –  fgrieu Dec 15 '12 at 8:26
add comment

1 Answer

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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