10
$\begingroup$

When generating RSA keys in the original RSA paper it is stated:

to gain additional protection against sophisticated factoring algorithms, p and q should differ in length by a few digits

Why is this? How many is "a few digits"? And how important is this?

$\endgroup$

migrated from security.stackexchange.com May 5 '16 at 4:48

This question came from our site for information security professionals.

  • 1
    $\begingroup$ Who said this? It's customary for say 2048-bit RSA to choose two 1024-bit primes that have the same length. That said there are efficient attacks on RSA if p-q is too small. See: en.wikipedia.org/wiki/Fermat%27s_factorization_method or trial division starting from the nearest odd integer to sqrt(N). (This technique is very efficient when |p-q| < O( N^(1/4) ) $\endgroup$ – dr jimbob May 5 '16 at 3:34
  • $\begingroup$ Also see: Cryptanalysis of RSA With Small Prime Difference $\endgroup$ – dr jimbob May 5 '16 at 3:35
  • $\begingroup$ Yes I realise I should probably have posted in crypto, The quote is directly from the original RSA white-paper people.csail.mit.edu/rivest/Rsapaper.pdf $\endgroup$ – gtrwoot May 5 '16 at 3:40
  • $\begingroup$ @gtrwoot - My guess is it was clear to Rivest et al, that if p and q were too close together there are ways to quickly factor N and undermine the security. They made the recommendation to ensure p and q differed in length by a few digits, so if p is the larger prime and is say 3 (decimal) digits longer you have p - q ≈ p - p/1000 ≈ .999 p ≈ p ≈ sqrt(N) >> N^(1/4). Hence Fermat factorization based on p being near q won't work when p and q differ in length. That said just randomly picking two n/2 bit primes will with high probability result in them being O(sqrt(N)) apart. $\endgroup$ – dr jimbob May 5 '16 at 4:13
7
$\begingroup$

The quoted recommendation is generally considered obsolete in the context of RSA with secure parameters, and is either disregarded, or replaced by asking that $\left|p–q\right|>2^{(n/2)–100}$ where $n$ is the number of binary digits for $N=pq$. This modern rule was in ANSI X9.31 (1998), and is still in FIPS 186-4 (2013), appendix B.3, criteria 2(d).

This quoted recommendation, and its modern counterpart, are intended to make $p$ and $q$ different enough to guard against Fermat factorization, and improvements thereof. The basic Fermat factorization technique enumerates integers $b$ from $0$ onward, stopping when $N+b^2$ is a square $a^2$, revealing $p$ and $q$ as $(a+b)/2$ and $(a-b)/2$ (within order). Numerous improvements exist allowing to skip some $b$, and reducing the cost of the squareness test.

However, with $p$ and $q$ of equal size and $n\ge512$, but $p$ and $q$ otherwise mostly random, all known improvements of Fermat factoring have fully negligible odds to succeed (because the number of $b$ to enumerate by the basic Fermat factoring method is $\left|p–q\right|/2$, which is higher than $2^{212}$ with odds better than $1-2^{-40}$, and none of the known improvements lowers the $2^{212}$ steps to something workable). Notice that $n=512$ is so small that it provides only very limited security (see this), and that the pointlessness of trying Fermat factorization (compared to other factorization techniques) grows when $n$ grows.

The quoted recommendation only makes sense for toy examples of RSA, say when $p$ and $q$ both are about 9-10 decimal digits (thus $n\approx64$). And then a few digits can safely be taken as 2 digits; or even (in decimal) reduced to a single digit, as long as the leading digit of the largest prime is not 1.

Rules in ANSI X9.31 and FIPS 186 prescribe (in the interest of interoperability of devices using RSA private keys they did not generate) that $p$ and $q$ are primes in range $[2^{(n-1)/2}\dots2^{n/2}]$, implying that they have the same number $n/2$ of binary digits (and that their number of decimal digits differs by at most one, if at all). This goes straight against the wording of the quoted recommendation. According to my memories of Robert Silverman's account: the requirement that $\left|p–q\right|>2^{(n/2)–100}$ (for $n\ge1024$) was introduced (although technically not needed) to please the ANSI X9.31 standard's committee, sponsored by bankers, who wanted a simple rebuttal to a court argument on the tune of: "I claim that my client did not produce that signature! One simple explanation is that the modulus has been factored. An expert has testified that Fermat factoring, known since the 17th century, potentially could do that, and allow such forged signature. No precaution against it was taken! Whoever carelessly specified that signature system must bear the consequences!".

$\endgroup$
6
$\begingroup$

If you choose $p$ and $q$ at random of the same length, then they will be far away from each other with extraordinarily high probability. Thus, this is not an issue.

In the past, there were those that recommend safe primes to make sure that neither $p-1$ nor $q-1$ would have all small factors. However, this isn't necessary (and is now not even recommended). Make sure that you have good randomness going in, and then taking random is fine. (And if you don't have good randomness, you're dead anyway and doing this isn't what's going to help you.)

$\endgroup$
  • $\begingroup$ FIPS 186-4 appendix B.3 still mandates safe primes for 1024-bit moduli (not 2048-bit); arguably, that is justified if you consider an adversary content with factoring any public moduli among many (like, to impersonate any member of a group): trying Polard's p-1 on all keys is a reasonable strategy, compared to attacking a single key with GNFS (the number of target public keys to make that workable is in the billions, I believe) $\endgroup$ – fgrieu May 5 '16 at 10:07
  • 2
    $\begingroup$ @fgrieu: actually, 186-4 doesn't ask for "safe primes" (commonly defined as primes $p$ with $(p-1)/2$ also prime), instead, it asks for primes $p$ with $p-1$ and $p+1$ both having a largish (>100 bit) prime factor. $\endgroup$ – poncho May 5 '16 at 13:15
  • $\begingroup$ @poncho: Indeed. I wish I wrote "strong primes in the sense that has for RSA", rather than using the unusual meaning of "safe prime" in this answer. $\endgroup$ – fgrieu May 4 '17 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy