kinda new here, I had a question pertaining to someone being able to factor one's RSA keys through the GCD. Anyways the question goes that there are two people: A and B. A makes his/her private key as $N_a = p_a\cdot q_a$ and B does the same with $N_b = p_b \cdot q_b$. I'm assuming here that both random primes are of length n bits and so I'm wondering whats the probability of the two keys sharing a common prime. I was considering that it may have something to do with the Prime number theorem but not entirely sure.

  • $\begingroup$ remember that PNT is an asymptotic distribution, so your probability will be approximate. That said, sounds like you are on the right track. What is the probability that one of the probability that the intersection of $\{p_a,q_a\}$ and $\{p_b,q_b\}$ is non-empty? $\endgroup$
    – mikeazo
    Dec 10, 2014 at 16:14
  • $\begingroup$ I understood that but I'm just having a problem connecting it to the n bit length. $\endgroup$
    – Marorin
    Dec 10, 2014 at 16:32
  • $\begingroup$ Well, a $n$-bit number lies between $2^{n-1}$ and $2^n-1$ (inclusive). $\endgroup$
    – fkraiem
    Dec 10, 2014 at 16:49
  • 1
    $\begingroup$ If $\pi(x)$ is the number of primes less than $x$ (which $x/\ln(x)$ approximates), then it would be $\pi(2^n-1)-\pi(2^{n-1})$. So you can approximate it using the formula. $\endgroup$
    – mikeazo
    Dec 10, 2014 at 18:00
  • 3
    $\begingroup$ Similar question: How many RSA keys before a collision? $\endgroup$ Dec 11, 2014 at 9:12


Browse other questions tagged or ask your own question.