# Necessity of changing $p$ and $q$ when your private key is exposed?

Suppose your private key $d_1$ has been exposed. Instead of changing $p$ and $q$, instead you just choose a new public and private key (say $e_2$ and $d_2$) and use these instead. What kinds of attacks could someone perform knowing $N,e_1,e_2,d_1$ (where $e_1$ is the first public key)?

-

If you know even a single key pair $(e,d)$, then you can factor $N$, so that's pretty much the ultimate attack — efficient, total key recovery. For a short, digestible proof of this, see the last fact on page three of Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem.
As an additional info: A. May published "Computing the RSA secret key is deterministic polynomial time equivalent to factoring", which shows that you don't even need a probabilistic algorithm (like the one in Boneh's paper). So yeah, if $d$ is compromised, the factorization is no longer safe. –  tylo Feb 19 '14 at 9:32