Are there any standards of multi-prime RSA key generation?

Question

FIPS 186-3 specifies a method to generate DSA parameters.

Is there anything similar (official standard or widely-accepted recommendation) that shows how to generate the primes for multi-prime RSA?

Answer 1

Multi-prime RSA (also known as RSA-MP) is supported by PKCS#1v2. This standard supports a public key $(n,e)$ where the modulus $n$ is the product of $u≥2$ distinct odd primes: $n=\prod_{i=1}^u{r_i}$, with $1<e<n$ and $\gcd(r_i-1,e)=1$ (implying $e$ odd). The private exponent $d$ is such that $1<d<n$, and $e⋅d≡1\pmod{\operatorname{lcm}_{i=1}^u(r_i-1)}$. No other requirement on $(n,e,d)$ is given by PKCS#1v2. RSA-MP is $u>2$. Make $u=2$, $p=r_1$, $q=r_2$, and you are back to RSA in PKCS#1v1.

I know no standard about generation of RSA-MP key. However, for advice on the question of the bit size of $n$ and the number of factors $u$, one recommendable paper is Unbelievable Security: Matching AES security using public key systems, by Arjen K. Lenstra. See in particular the synthetic table giving $u:⌈\log_2\min(r_i)⌉$ for a given security level (in bits, with 2K3DES 95-bit), on a given year (with that parameter accounting for the author's evaluation of improvements on the algorithms, but not Moore's law), and according to two models.

Corrected: Following that size advice even at the 2K3DES level (for any entry starting Y2010), adding about $32/u$ bits per year to account for Moore's law (previously forgot that!), and choosing primes of one key randomly, my opinion is there's no need to worry about factorization attacks on that key till the Y2030 limit of that table. Notice that my endorsement assume that an adversary has no significant interest in factoring a single random key among extremely many.

I also like the short and graphical Multi-prime RSA trade offs, although it is restricted to 2048-bit modulus.

---

The main things to consider regarding $\log_2n$, $\log_2r_i$, and $u$, are:

• $n$ should be large enough that GNFS factorization is not to fear. Considerations are just the same for regular RSA and RSA-MP, since the multiplicity $u$ of factors, or their size $\log_2r_i$, does not influence the expected run time of GNFS; only $\log_2n$ matters.

• Each $r_i$ should be large enough that $n$ is safe from factorization by known algorithms primarily influenced by the size of a factor extracted (rather than the size of the composite to factor), in particular ECM (among such algorithms, ECM is the most likely to factor one particular key). In regular RSA, it is customary to choose the two primes of equal (or nearly equal) size: this makes it overwhelmingly likely that GNFS subsumes all other known factorization algorithms, including ECM, by a large factor. However, that does not hold for RSA-MP; and while finding one $r_i$ does not by itself make it possible to forge signatures or decipher, it must still be considered a fatal disaster, for GNFS can then tackle the factorization of the composite $n/r_i$ at greatly reduced cost. Therefore, it is customary to choose the minimum size of a factor based on estimation of the running time of ECM (considered a function of $\log_2r_i$, often ignoring the relatively marginal influence of $\log_2n$).

• Then the best choice of $u$ is ${\log_2n}\over{\log_2r_i}$, rounded in some direction.

For this, I trust the aforementioned Unbelievable Security.

Details on the choice should take into account that typically $⌈\log_2n⌉$ is prescribed, in which case we'll probably use $\log_2r_i\approx ⌈\log_2n⌉/u$; if not, there is often little or no performance cost in rounding up $⌈\log_2r_i⌉$ up to the next multiple of a word size, like 32 or 64 bits, then use $log_2n\approx ⌈\log_2r_i⌉⋅u$.

---

It is customary that key generation standards for RSA key pairs add extra requirements in addition to those in PKCS#1v2. FIPS 186-3, a widely accepted standard, has the following requirements in section B.3.1; I'm trying my best to give the rationale:

1. The public exponent $e$ shall verify $2^{16}<e<2^{256}$. The lower bound is here because some attacks on poor RSA-based schemes are often easier when $e$ is small; the higher bound is for interoperability of public-key operations.
2. The bit size of $n$, $nlen=⌈\log_2n⌉$, should be 1024, 2048, or 3072 (note: in appendix B.3.1 of FIPS 186-3, the are references to 1024-bit, 2048-bit and 3072-bit primes; that shall be understood as the bit size of $n$, although that is composite). The limited choice maximize the critical interoperability of public keys; the lower bound also enforces a baseline security (according to NIST Special Publication 800-131A, for signature generation, 1024-bit is acceptable through 2010, deprecated from 2011 through 2013, and disallowed after 2013); the lack of 4096-bit or more is seen by some as an indication that ECDSA is the way to go.
3. The prime factors $p$, $q$ of $n$ shall be in range $[2^{(nlen-1)/2},2^{nlen/2}]$; this is primarily to ease interoperability of private keys across implementation.
4. $|p–q|>2^{nlen/2–100}$; this is a legacy of ANSI X9.31, where AFAIK it was introduced as a simple way to repel the rhetorical argument "but even Pierre de Fermat knew a factorization algorithm that could defeat RSA".
5. Primes $p$ and $q$ shall be chosen at random using the same algorithm (with $e$ an input), chosen among a few approved algorithms, falling into two main categories (random primes, and random primes with condition, with subdivisions depending on if the primes are probable or provable primes). This avoids poor algorithms, prevents optimizations of $d$, $dP$, $dQ$ giving questionable security, and eases validation of implementation, even allowing Known Answer Tests.
6. These approved algorithms are such that for $p$ of 512-bit, $p-1$ (resp. $p+1$) shall have a prime factor $p_1$ (resp. $p_2$) of more than 100 bits; same for $q$; if a similar condition is used (that's optional) for $p$ of 1024-bit (resp. 1536-bit), that should be more than 140 (resp. 170) bits. These requirements are intended to give insurance against Pollard's $p-1$ and William's $p+1$ factoring algorithm.
7. These approved algorithms come with a maximum size of the primes $p_1$ and $p_2$ discussed in (6.) AFAIK this just precludes choosing these primes $p_1$ and $p_2$ so big that the choice of primes $p$ is reduced to a point where this becomes an issue.

---

If I had to propose an adaptation of FIPS 186-3 for generating RSA-MP keys, it could be:

1. Unchanged (though personally I would choose $e=2^{16}+1$; and if you ask, I'd ease the lower bound to $e=3$, with no security impact when good schemes are used; but that's independent of RSA-MP).
2. $nlen=⌈\log_2n⌉$ among 1024, 2048 or 3072 for full interoperability with FIPS-based signature verification devices; or changed to $1024≤nlen≤16384$ with $nlen≡0\pmod{64}$ on condition of agreement with potential signature verifiers, for more flexibility and future-openness. Recommendations on $nlen$ and $u$ based on the Unbelievable Security reference above, although with $u≤nlen/512$ no matter what.
3. Adapted to $2^{64⋅⌊(nlen/64+i−1)/u⌋-1/u}<r_i<2^{64⋅⌊(nlen/64+i−1)/u⌋}$. This ensures $⌈\log_2r_i⌉≡0\pmod{64}$, $⌈\log_2\prod_{i=1}^u{r_i}⌉=nlen$, and at most two different $⌈\log_2r_i⌉$.
4. Replaced by a test that any two $r_i$ differ in at least one of their 100 high-order bits (more in order to catch faults than for fear of Fermat factoring).
5. Kept for algorithms in the "random primes with condition" categories, with only the parameters of the approved algorithms adapted; see justification in (6.) below.
6. Kept, with the requirement that $⌈\log_2p_1⌉$ and $⌈\log_2p_2⌉$ are more than $60+5⋅⌈\log_2p⌉/64$. This linearly scales the value 100 and 140 in FIPS 186-3, and removes the option to ignore that for $⌈\log_2p⌉>1024$ by using an algorithm in the "random prime" category. My opinion is that this requirement makes sense in the context of RSA-MP: a rational adversary content with factoring any of many modulus (rather than factoring a particular modulus) should not start to use ECM on one or a few modulus; but rather should first try Pollard's p-1 on all the modulus, as the ECM strategy has a markedly lesser chance of success for a given effort (argument: Pollard's p-1 is used with great benefit by state-of-the-art factoring programs such as gmp-ecm; also see this related answer).
7. Kept; this really is just not changing the approved algorithms.

Answer 2

If you consider the security of an RSA key to be the ease of factoring (there are other considerations), then you should pretty obviously make them the same size.

You can think of a conventional N-bit key to be composed of two primes, but you can also look at it the other way -- that you take two primes that are $M_1$ and $M_2$ bits long and produce a key that is $M_1 + M_2$ bits long.

It's pretty obvious that you want the primes to be reasonably close in size and having them be the same bit-length long is just good practice. If they were lopsided, then it would be easier to factor the number.

We can extend that to say that you want multi-prime RSA, you want them all to be approximately the same size, as well. Take the example of a 2048-bit RSA key that consists of two 1000-bit primes and a 48-bit prime. It is straightforward to just declare this key to have the same strength as a 2000-bit two-prime key because it's easy to factor out the 48-bit prime. If you told people you had done that, they'd say that you had thrown away 48 bits.

If you create a two-prime RSA key with lopsided primes and tell people, they will get rightfully irritated. One could argue that the major reason for a multi-prime RSA key at all is to have a long key with shortened security. I believe that this is the reason you typically don't see them. It's hard to know what problem you're solving other than making the crypto weaker.