Andrew S. Tanenbaum Edition 5th Exercise 8 Question 18 (Page No. 873)

Question

Alice and Bob use RSA public key encryption in order to communicate between them.
Trudy finds out that Alice and Bob shared one of the primes used to determine the
number n of their public key pairs. In other words, Trudy found out that na = pa × q
and nb = pb × q. How can Trudy use this information to break Alice’s code?

Answer 1

According to the given question the intruder found out that A and B have a common prime factor

$(n_{a}, e_{a})$ and $(n_{b}, e_{b})$ are public keys

to find out the common factor the intruder finds GCD($n_{a}$, $n_{b}$)=q

as one of the common prime factors is found. The other primes can be found by

$p_{a}=\frac{n_{a}}{q}$ and $p_{b}=\frac{n_{b}}{q}$

now the intruder has both $n_{a}$ and $n_{b}$

next, the intruder can compute $\phi(n_{a})$ and $\phi(n_{b})$

to break A's ciphertext intruder needs private key of A which is $(d_{a}, n_{a})$

to find the private key, the intruder will simply apply

$e_{a}*d_{a}=1 MOD \phi(n_{a})$