In a cryptography exercise, I have to factor $N$ only knowing $e$ and $d_p+d_q$ (not $d_p$ and $d_q$ separately).

I came up with the following equations: $$e*(d_p+d_q) = 2+K_p(p-1)+K_q(q-1)$$ $$e*d_p \equiv 1 \pmod{p-1} \implies 1 +K_p(p-1)\bmod e = 0 $$ $$e*d_q \equiv 1 \pmod{q-1} \implies 1 +K_q(q-1)\bmod e = 0 $$

Probably have to bruteforce Kp and Kq, but am not sure on how to proceed.

  • $\begingroup$ On second thought, the idea of brute-forcing the possible values of $(K_p,K_q)$ seems good. For each, the first equation gives a relation between $p$ and $q$, which on top of $N=pq$ leads to (at most) two solutions in reals that we could find. We are looking for one that is in integers. $\endgroup$
    – fgrieu
    Mar 30 at 18:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.