# Why is it a security problem that two RSA moduli are not co-prime?

I found this security problem, for example:

• Alice has an RSA public key: $e = 37$ and $\phi$ (totient, $N_A = (pa-1)(qa-1)$) is $55$, so the key is $(37, 55)$.
• Bob has an RSA public key: $e = 37$ and $\phi$ (totient, $N_B$ = $(p_B-1) (q_B-1)$) is $77$, so the key is $(37, 77)$.

So I see that $\gcd(55, 77)$ is $11$. But what does it mean for the security issues?

It sounds like it is then much simpler factorize the totient. But how? I can see that $55 = 11 \times 5$ and $77 = 11 \times 7$ also without calculating the gcd. Even when dealing with big numbers (say 2048 bits), what does it help me with to find a gcd not equal 1? $N_A$ could be a multiplication of 100 different prime numbers and of course it will have commonalities with some other totient values (say $N_b$), but the commonality may not be the whole $p$ or $q$.

Say:

Na = (pa-1)*(qa-1) = (a*b*c*d*e*f)*(g*j*i*k)
Nb = (pb-1)*(qb-1) = (l*m*n*e*f)*(r*g*u*v*w*x*y*z)


so the gcd of Na and Nb is e*f*g. Where does it help me to find the initial pa, qa, pb, qb?

• Are you talking about $\phi(p,q) = (p-1)(q-1)$? Well, we typically don't expose that value (that makes the factorization problem easy). And, contrary to your examples, that's always even. Are you talking about the modulus ($p \times q$)? – poncho Jul 23 '13 at 19:33
• yep, thanx, already understood :) – static Jul 23 '13 at 19:50

The public key is actually $(n,e)$ where $n = p \, q$: it's the modulus, which is the product of the two primes, that appears in the public key.
Suppose that you have two public keys $(n_A, e_A)$ and $(n_B, e_B)$ with $n_A \neq n_B$, and that $\gcd(n_A, n_B) \neq 1$. You have a common divisor of both $n_A$ and $n_B$. But $n_A$ and $n_B$ have only two divisors each, the two primes. Therefore $\gcd(n_A,n_B)$ is one of the secret primes of both keys, and the other secret primes are trivially $n_A / \gcd(n_A,n_B)$ and $n_B / \gcd(n_A,n_B)$.
Knowing a factor of the two totients may or may not reveal the private key. If the factor you have is $4$, that doesn't give you any information: $(p-1)(q-1)$ is always a multiple of $4$. If the factor you have happens to be $p-1$ or to let you find $p-1$, that's obviously a problem. But since the totient is not normally exposed anywhere, this isn't a common concern.