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?
3
-
$\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$– AleksanderCHCommented Apr 9, 2019 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 ♦Commented Apr 9, 2019 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$– ponchoCommented Apr 9, 2019 at 16:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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).
-
$\begingroup$ I should have mentioned that they use a variation of the "usual" Coppersmith techniques. $\endgroup$– j.p.Commented Apr 9, 2019 at 18:03