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$
$\endgroup$
8
-
$\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$– user59119May 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$– Squeamish OssifrageMay 22, 2018 at 14:59
-
1$\begingroup$ @SqueamishOssifrage: "up to equivalence"; I suspect that's the trick that textbook is looking for... $\endgroup$– ponchoMay 22, 2018 at 15:11
-
$\begingroup$ But this problem has already been solved before, I'm just wondering how it was done. $\endgroup$– user59119May 22, 2018 at 17:48
|
Show 3 more comments