Every week Bob updates his public RSA modulus $n=p*q$ and encryption exponent $e$ by picking a new pair of primes $p$ and $q$ and a new exponent $e$. After several weeks, bob becomes lazy and decides to keep the prime $p$ fixed and only updates the other prime $q$ every week. Eve hears about this. How can she exploit this information to decrypt messages sent to Bob using his public key ?

I don't know how to solve it, any help or hint would be much appreciated.
I understand we need to retrieve $p$ and then we can get any $q_i$, and from there decipher the messages, but how can we do that ? okay so $n_1 = pq_1, n_2 = pq_2 , n_3 =pq_3$ , so on ... How do we get $p$


The question spezifies $n_1 = p*q_1$, $n_2 = p*q_2$. With that we can calculate $gcd(n_1,n_2) = p$ which lets us solve $n_1 / p = q_1$ and $n_2 / p = q_1$. Now we have every information needed to calculate the private part of Bob's key and thereby decrypt all messages sent to him.

| improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.