Suppose for a RSA system I have the following variables given:
modulus $n$, expononent $e$, $d_p$ and $d_q$

Where, $d_p = d\bmod(p-1)$ and $d_q = d\bmod(q-1)$,

Is it possible to find the private exponent $d$ ?

Note: $p$, $q$, $p-1$ and $q-1$ are not known

  • $\begingroup$ Hint: it holds that $e\,d_p\equiv1\bmod(p-1)$. $\endgroup$ – fgrieu Apr 14 at 7:07
  • $\begingroup$ I understand that, but I can't figure out where to use it $\endgroup$ – TheBlueFlame121 Apr 14 at 7:17
  • 1
    $\begingroup$ Thank you, I finally got the solution. I iterated k over the range or e and the checking condition was as follows : math.gcd(65537, p1) == 1 and isprime(p1+1) == True and n % (p1+1) == 0 $\endgroup$ – TheBlueFlame121 Apr 14 at 9:36
  • 2
    $\begingroup$ That method works fine in the small $e$ case, For large $e$, you could compute $\gcd( r^{e \cdot d_p} - r, n)$ for random $r$, this is (with good probability) $p$. $\endgroup$ – poncho Apr 14 at 12:51
  • 1
    $\begingroup$ @poncho: you should make an answer with that one, it is much cleaner, and I had missed it. $\endgroup$ – fgrieu Apr 14 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.