6
$\begingroup$

Let $N=pq$ where $p$ and $q$ are safe primes. If the adversary knows the inverse of $p$ mod $q$ and the inverse of $q$ mod $p$, can this help him factor $N$ or break the textbook RSA?

$\endgroup$
  • $\begingroup$ Well the point is that you can't calculate $p \bmod q$ because you don't have $p$ and $q$, or did I understand something wrong in your question? $\endgroup$ – AleksanderRas Apr 9 at 12:44
  • 1
    $\begingroup$ The adversary is assumed to know $p^{-1}\bmod q$. But is s/he assumed to additionally know $q^{-1}\bmod p$, or $q\bmod p$ ? The question (v2) can be read either way. $\endgroup$ – fgrieu Apr 9 at 13:35
  • 1
    $\begingroup$ I'm pretty sure that $q^{-1} \bmod p$ is meant; if you know $q \bmod p$ (where $q < p$), well, that fairly obviously gives the game away... $\endgroup$ – poncho Apr 9 at 16:56
4
$\begingroup$

Santanu Sarkar and Subhamoy Maitra show in Some Applications of Lattice Based Root Finding Techniques the deterministic polynomial time equivalence between factoring $N$ ($N=p\cdot q$, where $p>q$ or $p,q$ are of same bit size) and knowledge of $q^{−1} \bmod p$ (cited from the abstract).

$\endgroup$
  • $\begingroup$ I should have mentioned that they use a variation of the "usual" Coppersmith techniques. $\endgroup$ – j.p. Apr 9 at 18:03

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.