Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

migrated from security.stackexchange.com Jul 23 '13 at 17:27

This question came from our site for Information security professionals.

2  
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

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
great! thanx, I had a misunderstanding of n :) –  static Jul 23 '13 at 19:49
1  
Two links that you might find useful to understand exactly how often does that happen in real life freedom-to-tinker.com/blog/nadiah/… eprint.iacr.org/2012/064 –  Alexandre Yamajako Jul 23 '13 at 20:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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