0
$\begingroup$

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$?

$\endgroup$
  • $\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 '18 at 13:23
  • 1
    $\begingroup$ But the public key is not given $\endgroup$ – user59119 May 22 '18 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$ – Squeamish Ossifrage May 22 '18 at 14:59
  • 1
    $\begingroup$ @SqueamishOssifrage: "up to equivalence"; I suspect that's the trick that textbook is looking for... $\endgroup$ – poncho May 22 '18 at 15:11
  • $\begingroup$ But this problem has already been solved before, I'm just wondering how it was done. $\endgroup$ – user59119 May 22 '18 at 17:48

Your Answer

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