0
$\begingroup$

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?

$\endgroup$
8
  • $\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
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Using the multiplier improvement to Fermat's method for example: en.wikipedia.org/wiki/… $\endgroup$
    – Daniel S
    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.