Chapter 7 Public-Key Operations 219
MultiPrime
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
Two-Prime RSA 48.8 17.5 0.8
Three-Prime RSA 48.8 10.9 0.8