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
?