RSA Security 5.2.2 manual How Many Primes?, Two-Prime RSA 48.8 17.5 Three-Prime RSA 10.9

MultiPrime

Two-Prime RSA	48.8	17.5	0.8
Three-Prime RSA	48.8	10.9	0.8

This means 3-prime private operations can be about 38% faster than 2-prime operations. Or with 2-prime RSA, you can perform about 57 signatures per second, but with 3-prime RSA, you can perform about 91 signatures per second.

How Many Primes?

Using three primes is faster than using two primes. Is 4-prime RSA faster than 3- prime? Yes, but there is a security tradeoff. One way to break RSA is to factor the modulus. Current technology (machinery and factoring algorithms) are such that a 1024-bit modulus is safe from attack and will be safe for many years to come. However, the more primes that make up a number, the easier it is to factor using what is known as the Elliptic Curve Method (ECM).

Currently, no one trying to factor a 2-prime RSA modulus would use the ECM, since there is another method, known as Number Field Sieve (NFS), that is faster. With NFS, the number of primes does not matter; factoring will always take the same amount of time.

What this means is that the attacker will decide which method to use, NFS or ECM, based on the number of primes that make up the modulus. With fewer primes, NFS will be used; with more primes, ECM will be used.

However, there is one more issue to think about: key size. The longer the modulus, the harder it is to factor. The difficulty of ECM increases more than the difficulty of NFS with modulus size. That means the longer the key, the safer it is to use more primes. For instance, with two primes at 768 bits, NFS is faster than ECM. But with three primes at 768 bits, ECM is faster. Using three primes to build a 768-bit RSA key pair means you have less security than two primes. It does not necessarily mean you do not have enough security; it just means you have less.

On the other hand, with two primes or three primes at 1024 bits, NFS is faster than ECM. With four primes at 1024 bits, ECM is faster. So if your 1024-bit RSA key pair is made up of three primes, you have the same level of security as with two primes. Since with three primes private key operations are faster, you might as well use three primes. At 1024 bits, you don't start sacrificing security until you use four primes. At what point is it safe to use four primes? Some researchers say 4096 bits; others say 1536 bits.

Starting with Crypto-C 5.1, we have taken a more conservative approach. The toolkit

C h a p t e r 7 P u b l i c - K e y O p e r a t i o n s 2 1 9