Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I would like to ask what happens if we build an RSA system with modulus a product of more than 2 primes, for example let $n=p_{1}p_{2}...p_{L}$. I know only the classical RSA system with $n=pq$ with $p$ and $q$ large prime numbers. I guess the modulus $n=p_{1}p_{2}...p_{L}$ will be not a good idea, because one can use the Chinese Remainder Theorem to decrypt easily the message?
Can anybody explain how we deal with such moduli products of many primes?
Having more than two prime factors is supported by the PKCS#1 standard. This is called a "multi-prime" key.
On the plus side, this may offer some performance improvement. The Chinese Remainder Theorem still applies (see for instance in section 5.1.2, the description accommodates more than two primes). For instance, if you have a 1536-bit modulus which is the product of three 512-bit primes, then the CRT replaces one 1536-bit exponentiation with three 512-bit exponentiations which are, individually, 27 times faster (assuming a classic cubic modular exponentiation algorithm), for a total speedup of 9, compared to the usual 4 with two factors. More generally, with $k$ factors, the expected CRT speedup is in about $k^2$.
On the negative side, using too small factors may weaken the modulus. The best known factorization algorithms have a cost which depends on the modulus size, not on the size of the individual factors, so using more smaller factors should have no impact... unless the factors are small enough to enter the range of the feasible with ECM: that algorithm has a cost which depends (mostly) on the size of the smallest factor. For normal, bi-prime RSA modulus, ECM is not competitive with GNFS; but if you make your factors too small, this can lower your security.
Bottom-line is that, for usual sizes, three or four primes should be tolerable and offer a nice performance boost, but don't go beyond that. Public-key operations are not impacted in any way. Note also that other somewhat related cryptosystems (e.g. Rabin) might not accept a multi-prime modulus.
RFC 8017 supports so-called "multi-prime" RSA where the modulus may have more than two prime factors. The benefit of multi-prime RSA is lower computational cost for the decryption and signature primitives, provided that the CRT is used. Better performance can be achieved on single processor platforms, but to a greater extent on multiprocessor platforms, where the modular exponentiations involved can be done in parallel.
Multi-prime RSA is implemented in openssl-1.1.1 .
