As I understand, for RSA $n = p \cdot q$. For the key to be safe enough from getting factored, $p$ and $q$ have to be far from each other. How far do they have to be? For example, if I have two $1024$-bit primes that both start with a 1 and the difference between them $(p-q)$ is ~$1022$-$1023$ bits, is that good enough?
-
1$\begingroup$ you could give a look to this answer: crypto.stackexchange.com/questions/15744/… $\endgroup$– ddddavideeDec 15, 2015 at 21:38
-
1$\begingroup$ When you generate two random prime numbers of the same size, their difference is around the same size of the numbers (minus few bits, usually 2). That's enough to have a state of the art key generation. You just need to enforce that the two primes numbers are indipendentely generated. $\endgroup$– ddddavideeDec 15, 2015 at 21:44
2 Answers
Yes, it is good enough. In the case of random primes the distance as large as the numbers with high probability.
With the recommended key-size ($2048$-bit) one only needs to generate two random primes of the right size ($1024$-bits each). This is generally done throwing a random number of $1024$ bits, forcing the first one and the last one bits equals to 1 (the Most significant bit is equal to 1 to guarantee the right size and the Less significant bit is equal to one to get an odd number) and check the primality of this integer. Sometimes the second most significant bit is set to 1, too. As fgrieu explained in his comment mandating that the second highest-order bit of $p$ and $q$ is set insure that $N=pq$ has exactly as many bits as the sum of the numbers of bits in $p$ and in $q$, because $(\frac{3}{4})^2>\frac 1 2$. That's not quite the way ANSI X9.31 and derivatives (including FIPS 186-4) RSA key generation methods do this; they tend to prescribe $2^{(n−1)/2}<p<2^{n/2}; 2^{(n−1)/2}<q<2^{n/2}$; and (w.r.t. Fermat/Lehman factorization) $|p–q|>2^{n/2–100}$ where $n$ is the number of bits in $N=pq$, with $n$ multiple of $2^6$ or some higher power of two.
-
1$\begingroup$ Mandating that the second highest-order bit of $p$ and $q$ is set insure that $N=pq$ has exactly as many bits as the sum of the numbers of bits in $p$ and in $q$, because $(3/4)^2>1/2$. That's not quite the way ANSI X9.31 and derivatives (including FIPS 186-4) RSA key generation methods do this; they tend to prescribe $2^{(n-1)/2}<p<2^{n/2}$; $2^{(n-1)/2}<q<2^{n/2}$; and (w.r.t. Fermat/Lehman factorization) $|p–q|>2^{n/2–100}$ where $n$ is the number of bits in $N=pq$, with $n$ multiple of $2^6$ or some higher power of two. $\endgroup$– fgrieu ♦Dec 16, 2015 at 7:32
The risk if $p,q$ are close is that the Fermat factorization method can be used. If $p>q$ and $p-q = 2b$, then $n = pq = (p-b)^2 - b^2$. If we know that $b$ is small, we can try all possible values of $b$ until we find one such that $pq - b^2$ is a perfect square. We can test for perfect squares (and find their square roots) in polynomial time, so if we find $b$ then we can also compute $p$.
So, we want the size of $b$ to be prohibitively large as to avoid such a search.
-
$\begingroup$ The question is not about the risk of having a too small difference but if it is enough $\endgroup$ Dec 16, 2015 at 5:58