I have $n,e$ and $c$, $p$ and $q$ are prime, but $q$ is the inverse multiplication of $e$ and $p$ so $$q = e^{-1} \bmod p$$

How can $i$ get $p$ and $q$ back?

  • $\begingroup$ Welcome to Cryptography.SE. What is the origin of this question? What did you try to solve up to now? $\endgroup$ – kelalaka Mar 18 at 18:47
  • $\begingroup$ I looked for some properties to make it, for sure there is some trick $\endgroup$ – billst Mar 18 at 18:49
  • 1
    $\begingroup$ Also, if you're referring to the standard CRT parameters, we have $dp = e^{-1} \bmod p$ and $qinv = q^{-1} \bmod p$. Are you referring to one of them? $\endgroup$ – poncho Mar 18 at 18:49
  • $\begingroup$ but i dont have no one of then, i dont have d, p and q $\endgroup$ – billst Mar 18 at 18:53
  • $\begingroup$ what do you have? $\endgroup$ – poncho Mar 18 at 18:58

If $e$ is not too large, then it is easy.

The relation $q = e^{-1} \mod p$ can be rearranged to $qe = 1 + kp$ for some integer $k$; or in other words, $p/q \approx e / k$; that is, $p/q$ is extremely close to a simple rational, and that makes factorization easy.

  • $\begingroup$ Using the multiplier improvement to Fermat's method for example: en.wikipedia.org/wiki/… $\endgroup$ – Daniel Shiu Mar 19 at 7:15
  • $\begingroup$ Mhh ok, but im a little bit confused, i dont have p and q, so should I go trial and error? $\endgroup$ – billst Mar 19 at 13:10
  • $\begingroup$ @billst: obviously, you could try various values of $k$ (and you know that $k < e$, so there's a limited number); just checking $q \approx \sqrt{ (k/e) N }$ for the various $k$ should recover the value $q$ fairly quickly $\endgroup$ – poncho Mar 19 at 14:53
  • $\begingroup$ sorry, but I can write to you in private somewhere? $\endgroup$ – billst Mar 20 at 11:33

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.