2
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ 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$)? $\endgroup$
    – poncho
    Jul 23, 2013 at 19:33
  • $\begingroup$ yep, thanx, already understood :) $\endgroup$
    – static
    Jul 23, 2013 at 19:50

1 Answer 1

6
$\begingroup$

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)$.

This shows that it's critical that in an RSA key, both primes are unique.

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.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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