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?$
- 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.
- 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].
- 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).
- 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.
- 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).
- 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).
- 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$:
- Arjen K. Lenstra: Unbelievable Security: Matching AES security using public key systems, Asiacrypt 2001 (alternate link).
- Dan Boneh, Hovav Shacham: Fast variants of RSA, with abridged version in CryptoBytes, Vol. 5, No. 1, 2002.
- M. Jason Hinek: On the Security of Multi-prime RSA, Technical Reports of the Centre for Applied Cryptographic Research (CACR) at the University of Waterloo, 2006 (alternate link).
- Jean-Sébastien Coron, Aline Gouget, Pascal Paillier, Karine Villegas: SPAKE: A Single-Party Public-Key Authenticated Key Exchange Protocol for Contact-Less Applications (Financial Cryptography 2010 Workshops, pay-walled with free extract)
A recent answer!
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:
- Paul Zimmermann, Bruce Dodson: 20 Years of ECM, In Proceedings of the 7th Algorithmic Number Theory Symposium, 2006 (alternate pay-walled link).
- Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen Lenstra, Emmanuel Thomé, Joppe Bos, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Dag Arne Osvik, Herman te Riele, Andrey Timofeev, Paul Zimmermann: Factorization of a 768-bit RSA modulus, in the proceedings of Crypto 2010.
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!
