# Deducing a secret key from two different public keys

Show that if two different RSA public keys $$p_k$$s are known to an attacker for the same secret key $$s_k$$, then $$s_k$$ can be broken

I've deduced that that if the 2 public key exponents are $$e_1,e_2$$ then they have the same remainder modulo $$\phi$$, but that still doesn't help me determine $$d$$.

• Hint: the common secret key $S_k$ is $(n,d)$. A public key $p_k$ is $(n,e)$. That's the same $n$.
– fgrieu
Commented Oct 3, 2022 at 8:22

The intended approach to take is not to recover $$d$$ directly; instead, it is to factor the modulus $$n$$ (and once you have that, recovering $$d$$ is easy).
So, if you have the value $$n$$ and the value $$k \phi(n)$$ for some unknown integer $$k$$, how could you factor?
One simple approach would work if you assume $$k$$ isn't too large. There are fancier approaches where you don't have to make that assumption, but why don't you start with the simplifying assumption...
(BTW: you actually have the value $$k \lambda(n)$$ for $$\lambda(n) = \text{lcm}(p-1, q-1)$$, however that doesn't really matter for this question...)
You should take a look at how $$p_{k_1}$$ and $$p_{k_2}$$ are derived from $$s_k$$ (or more concretely how $$e_1$$, $$e_2$$ are derived from $$d$$). Once You understand it, see if there is a way to deduce the modulus of this operation and from this compute the $$s_k$$.