Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
You can use multiple primes as long as they're large enough. It gives you less security for a given modulus size, but it can give you a better performance/security trade-off. –  CodesInChaos Oct 25 '13 at 19:39
1  

1 Answer 1

up vote 5 down vote accepted

Having more than two prime factors is supported by the PKCS#1 standard. This is called a "multi-prime" key.

On the plus size, 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.

share|improve this answer
    
Thank you very much! –  CryptoBeginner Oct 25 '13 at 19:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.