ImperialViolet

(This is a technical post: casual readers should skip it.)

I couldn't find data on the speed/security trade offs of multi-prime RSA anywhere, so I gathered the data myself and hopefully this blog post can be found by people in the future.

I used the equations from Lenstra (Unbelievable security: Matching AES security using public key systems, in ASIACRYTPT 2001) and scaled them so that two prime, 1024 bit RSA is 80 bits. The speed numbers are from OpenSSL for a single core of a Xeon E5520 at 2.3GHz.

I'm assuming a 2048-bit modulus. The blue, horizontal lines are the estimated difficulty of the NFS for 2048 and 1024-bit composities. The blue curve is the estimated difficulty of factoring a multi-prime composite using ECM. Really you don't want to choose so many primes at this drops below the NFS level.

A couple of useful observations from this data: For 2048-bits, 3 primes is the most you want (this is confirmed by table 1 of this paper). Also, if your CA is requiring a 2048-bit modulus, you can use seven primes to get basically the same speed and security as a 1024-bit key.

This is the same data, in table form:

1024-bits (80-bit NFS security)

n	ops/s	ECM security
2	1807	104
3	2680	86
4	4305	75

2048-bits (107-bit NFS security)

n	ops/s	ECM security
2	279	148
3	524	121
4	872	106
5	1047	95
6	1263	87
7	1579	81
8	1997	77

4096-bits (144-bit NFS security)

n	ops/s	ECM security
2	38	213
3	77	173
4	135	150
5	193	135
6	254	123
7	288	114
8	409	107