RSA with Multiple Keys

Question

I'm having some trouble understanding the answers to the following questions:

(a)

Why would it make sense for Eve to test out the $gcd(77, 35)$ ?

I understand that she has the following mapping

$e(x) = x^7\,mod\,35$

$e(x) = x^7\,mod\,77$

(b)

I believe this answer follows from (a)

Answer 1

Note that Eve has been eavesdropping since the beginning of the communication so she knows the exchanged secret $x$ and public keys $(e,N_i)$ of the participants.

Eve is wondering herself how to decipher this secret $x$. Then she realizes that factoring one of the modulus $N_i$ will yield the private key for deciphering the secret.

Why would it make sense for Eve to test out the $gcd(77, 35)$? But she knows that factoring is a hard way to go.

This is when Eve's comes to a bright idea. She's able to check if any of the modulus share a common factor. She picks $N_1 = 77, N_2=35$ from the public key list. Then GCD both and gets $7$ as a common factor of both, so Eve has instantly factored $N_1$ and $N_2$ therefore she's able to compute both private keys associated with these modulus, now she can forge and decipher the communication between these two parties.

For option $(b)$ she checks if any modulus share a common factor with other, but she isn't able to find a factor, so she will have to test other way to solve the underlying RSA problem.

Answer 2

Imagine four different primes: $a_1, a_2, a_3, a_4$

Two public keys: $N_1 = a_1 \cdot a_2$ and $N_2 = a_3 \cdot a_4$

$N_1$ and $N_2$ must be relatively prime to each other. It shouldn't be any number other than $1$ that both of them are divisible by, otherwise it would have to be one of our four primes. $N_1$ is not divisible by $a_3$ || $a_4$, neither $N_2$ by $a_1$ or $a_2$. This is the uniqueness of prime factorisation.

What happened here is someone has re-used a prime number between two RSA keys. We have now $a_1, a_2, a_3$.

So the public keys are now $N_1 = a_1 \cdot a_2$ and $N_2 = a_2 \cdot a_3$. Since calculating GCD is quite fast and easy this leads to cracking both keys, cos now it's easy to calculate:

$a_1 = \frac{N_1}{a_2}$

$a_3 = \frac{N_2}{a_2}$

Someone can decide out of curiosity to calculate $GCD(N_1, N_2)$ and we know that for $GCD(p, q)$ where $p$ and $q$ are prime numbers the result is $1$ - but in this case $N_1$ and $N_2$ are evenly divisible by $a_2$.