I'm working on a problem that gives me two private keys $d_1,d_2$ that work with the same $(N,e)$ pair. The problem gives me the two private keys and $N$. Is it possible to find $p$ and $q$? Or how would I find $p$ and $q$ or the sum $p+q$?

  • $\begingroup$ A single private key and the matching public key is enough to factor the public modulus $N$; see this. This is why it is a bad idea that several public keys share the same modulus $N$. Further, if several private keys match the same public key $(N,e)$, then these private keys are functionally equivalent (they need not be equal). $\endgroup$
    – fgrieu
    May 22, 2018 at 13:23
  • 1
    $\begingroup$ But the public key is not given $\endgroup$
    – user59119
    May 22, 2018 at 13:57
  • $\begingroup$ The question as stated makes no sense: for fixed $N$ and $e$ there is only one possible value of the private key $p$, $q$, and $d$ (up to equivalence modulo $\lambda(N) = \operatorname{lcm}(p - 1, q - 1)$). $\endgroup$ May 22, 2018 at 14:59
  • 1
    $\begingroup$ @SqueamishOssifrage: "up to equivalence"; I suspect that's the trick that textbook is looking for... $\endgroup$
    – poncho
    May 22, 2018 at 15:11
  • $\begingroup$ But this problem has already been solved before, I'm just wondering how it was done. $\endgroup$
    – user59119
    May 22, 2018 at 17:48