Multiple-prime RSA; how many primes can I use, for a 2048-bit modulus?

In standard RSA, the modulus $n=p_1 p_2$ is a product of two primes $p_1,p_2$ of the same size. Suppose we construct the modulus as a product of multiple primes $p_1,\dots,p_k$, i.e., $n=p_1 p_2 \cdots p_k$, where all the primes are of about the same size. I'm wondering how much this reduces the security of RSA, for typical modulus sizes.

Let me be more concrete. I want security comparable to that obtained with standard RSA with a 2048-bit modulus. Can I use $k=3$ (three primes) without significant loss of security? $k=4$? What's the largest number of primes $k$ that I can use, without significant loss of security? Assume that each prime is $2048/k$ bits long, so all the prime factors are of equal length.

If we consider an RSA modulus $N$ of $n$ bits ($n=2048$ in the question) product of $k$ primes of about $n/k$ bits, how high can be $k$ without loosing security? That's a problem studied even before Multiprime-RSA was named, with no definitive answer other than: we can't err on the unsafe side with $k=2$.

Why would we want $k>2$?

• For classical multiplication algorithms implemented in software or hardware with fixed word size (which covers all hardware and many software implementations I know), using the standard method described here, there's a potential effort saving of the RSA private-key function by a factor up to about $k^2/4$ compared to $k=2$, and a lot of that speedup is achieved in practice; plus it allows simple and efficient parallelization on $k$ cores.
• When there is hardware to perform modular multiplication that enforces a maximum modulus width, increasing $k$ is the only way to increase $n$ (thus security against factoring) while making any use of this hardware resource.
• The algorithms [GNFS and previously (MP)QS] that hold factoring records for $k=2$ have run time dependent of $n$ with no influence of $k$; thus the security against factorization attacks using these algorithms remains unchanged when $k$ grows with constant $n$.
• Given a public-key and its certificate, and (side-channel-free) access to a black box implementing the RSA private-key function $x\mapsto x^d\bmod N$, the best known way to tell if $k=2$ involves factoring $N$; thus we can increase $k$ without fear of interoperability with devices concerned only with the public-key.

Why would we want to summarily stick to $k=2$?

• That's mandated by US standard FIPS 186-4 ever since it includes RSA, and by reference for compliance to some or all of FIPS 140; by French official RGS recommendations; and by pretty much every security authority making recommendations on key size as listed by this reference website, last time I checked; and then some.
• In countless cases $k=2$ is the only thing compatible with what's around. One example out of many, in the field of Smart Cards: the Java Card 3 Classic API.
• While PKCS#1 standardizes Multi-Prime RSA and even a private-key exchange format for that, there are devices, including some claiming PKCS#11 compatibility, that do not support it. If you want to move the private-key to a different device, or even make a backup of a key generated on-board in a future-proof format, beware!
• Some modular exponentiation hardware or software wants prime factors $p$ which exact bit size is multiple of something (usually a power of two, e.g. 64); that's another interoperability hurdle (and in the context of $n=2048$, $k=3$, being a multiple of 64 would force one prime to be 640-bit, rather than 683-bit). Note: it can be worked around by reducing modulo an appropriate multiple of the prime during modular exponentiation, then doing a final reduction.
• There has been patents (now expired) delivered at least in USA and Europe (US 5,848,159, US 7,231,040, EP0950302) that created fear, uncertainty and doubt as to whether using Multiprime-RSA cames with a legal risk.

What other things are to be considered when pondering $k>2?$

1. Main one, by far: the effort (by any measure) of factorization attacks using ECM increases (faster than polynomially) with $n/k$, thus tremendously decreases with $k$ for constant $n$. And the adversary (which, we must assume, knows $k$) has the choice of the factorization method, and will choose ECM if advantageous. All the literature I know (listed below) on deciding $k$ thus aims at choosing it as high as possible so that the expected effort (or runtime, cost..) of ECM is no lower than that of GNFS, sometime with a projection of these expected efforts in the future; the $k$ of the crossover is of course rounded down.
2. ECM is easy to distribute on many commodity computers that need almost no communication with each others, when as far as we know the matrix step in GNFS requires a heavily connected supercomputer with enormous amounts of memory (or perhaps, spending some binary orders of magnitude more computing power in the sieving step that dominates the computing effort for current parameterizations). That somewhat invalidates comparisons between GNFS and ECM that consider computing work, effort or runtime, rather than some attempted measure of cost [Comparatively minor related aside: ECM reportedly can take advantage of GPU; but that might not be much of an argument, since GNFS could in the future benefit from GPU, by way of using ECM internally].
3. Since the advent of computers, and even in this century, we have not had a precise crystal ball when it comes to future runtime (much less cost) of published factorization algorithms (and that can only be worse for their relative cost, or if we consider unpublished improvements or algorithms). Whatever comparison we make between ECM and GNFS, the more in the future we want security, the more margin we should take on the ground of these uncertainties, and shift the balance towards lower $k$ (before rounding).
4. AFAIK, no implementation of Multiprime-RSA has been checked for side-channel attacks by a certification lab. That's not a mere certification issue: it is not unreasonable to fear that either the smaller primes, or the final CRT step (necessary to get any speed benefit) makes an implementation more vulnerable to side-channel leakage. That's a potential issue at least in HSMs operated in non-trusted environments, and Smart Cards.
5. When using ECM, odds that the factorization will be found after a fraction $\epsilon$ of the expected work are about $\epsilon$ (for $2^{-20}\le\epsilon\le0.3$ and common ECM parameters). That's in contrast with GNFS and QS, where we simply can't get the factorization until the last few percents of the expected work. If we want residual risk $\epsilon$ that an adversary succeeds with a certain work, we should aim for at least that work for GNFS, and at least $1/\epsilon$ times that work for ECM; that shifts the crossover towards lower $k$ (before rounding). In security, there is no consensus on acceptable residual risk to known attacks, and I have seen such $\epsilon$ entirely ignored, or set from 5% (for an overall system) to $2^{-40}$ (for symmetric cryptography where admittedly there is no strong incentive to tune that).
6. When we want to generate $m$ keys, and the adversary would be content to factor any single one (as is often the case when the keys are used for authentication or signature in a machine-to-machine application), we should pay some attention to two other factorization algorithms: Pollard's p-1 and Williams' p+1. Problem is: with primes of size $n/k$ chosen randomly, these algorithms (especially the first) substantially surpass ECM on the standpoint of the ratio $\text{odds to factor}\over\text{runtime}$ for small $\text{odds to factor}$. Thus an adversary will get a benefit by trying Pollard's p-1, then Williams' p+1, on the $m$ moduli available, before using ECM; and can do so with benefit on a fraction of the expected work proportional to $m$. To confirm this: GMP-ECM practitioners use that strategy, with significant success for p-1, and to a lesser extend for p+1. Rather than assessing this risk, we can generate the primes $p$ in a way such that $p-1$ and $p+1$ have a known high prime factor, which makes these algorithms useless (that's feasible efficiently if not simply, e.g. as explained in FIPS 186-4 appendix B.3, which for $k=2$ mandates that for primes of 512 bits, but not 1024 bits).
7. It should also be taken into account in the balance that ECM is expected to require near $k$ times less work to factor a Multiprime-RSA $N$ than a random $N$ of comparable size with lower prime factor of size $n/k$.

References

Restricting to the current century, I know only 4 references that deal with finding a balance for $k$:

The later reference briefly touches the nearly identical problem of the size of $p$ in unbalanced RSA (1. differs in the rounding to get $k$, 4. may differ w.r.t. final CRT step, 7. does not apply). The authors conclude that $n=2048$, $p=560$ gives a good balance; from which it would follow that $k=3$ is fine, but $k=4$ is not. This is based on an analysis of ECM and GNFS (taking into account only 1. as far as I can tell) with reference to:

A recent data point about ECM: in late 2013, Ryan Propper reported using GMP-ECM 6.4.3 + GMP 5.1.0 to find a 274-bit factor from the 787-bit composite $(7^{337}+1)/8/101020140256422276570987002251440602782290400709$ product of two unknown primes, on a commodity CPU using less than 6GB of RAM. He further reports that was a 10-day effort on Stanford's University cluster, and the factorization was found after 5000 curves. By extrapolating the log I get a runtime of 16 hours/curve and an expected $2^{21}$ curves (about $2^{12}$ core.years), and if that's any close to correct, an average of more than 300 cores have been used, and odds of finding that factorization so fast where 1/400; "this was quite the lucky find" is an understatement. The second largest of the ECM records is also quite a lucky one; which, if one considers 5. above, is to be expected!

For a 2048-bit modulus, based on current knowledge of attacks: you can use up to $k=3$ primes without any loss in security. Using $k=4$ primes apparently causes some loss in security (it's not clear to me exactly how much loss it causes, though).

I've found two sources that support this conclusion:

• The blog post Multi-prime RSA trade offs analyzes the security of a 2048-bit $k$-prime modulus against the NFS and ECM factoring algorithms. For $k=2$ and $k=3$, the security level is 107 bits (NFS is the best attack). For $k=4$, the article claims that the security level is 106 bits (ECM is slightly faster than NFS for four primes), so we've lost about one bit of security, though this estimate seems like it might over-simplify.

• Table 3 of the paper Unbelievable Security: Matching AES security using public key systems also addresses this issue. It suggests that, for a 2048-bit modulus, $k=3$ primes offers no measurable loss of security. Starting in 2030, $k=4$ primes will offer no loss in security (it changes over time because NFS factoring speeds up faster than ECM factoring). Here is Table 3: • This disregard an issue: with say 1% of the expected work to factor a given realistic modulus, ECM has odds 1% to factor it; but GNFS just can't conceivably succeed. If we want a very low residual risk that an adversary succeeds with a given effort, we MUST take this into account, and that shifts the result significantly, in the direction of allowing less factors.
– fgrieu
Apr 25 '14 at 22:11
• Independently: In Lenstra's table 3, 1024-bit column, the 5 and 4 on the right side (denoting use of a computationally equivalent model) are unreasonable. In 2013, GMP-ECM pulled a 274-bit factor from a 787-bit number product of two unknown primes. Pulling that from a 1024-bit number would not be too much harder, when 1024-bit GNFS factorization is way out of reach using comparable resources. [Note: it was found $16559819925107279963180573885975861071762981898238616724384425798932514688349020287$ from $(7^{337}+1)/8/101020140256422276570987002251440602782290400709$ ].
– fgrieu
Apr 25 '14 at 22:46
• @fgrieu, awesome, thank you for the detailed comments! Would you like to either create your own answer or to edit this answer into a form that addresses these issues? I'm not quite sure how to take into account the first issue you mention (about 1% chance of success), so would need help on that. Thank you again!
– D.W.
Apr 26 '14 at 5:38
• I tried to make an answer, but hardly got past exposition of the facts and references. I quote another one leading to $k=3$.
– fgrieu
Apr 27 '14 at 19:55