ImperialViolet

Multi-prime RSA trade offs (09 Apr 2011)

(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.

image/svg+xml Produced by GNUPLOT 4.2 patchlevel 6 0 500 1000 1500 2000 2 3 4 5 6 7 8 0 50 100 150 ops/s security (bits) Num primes Security Speed

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)

nops/sECM security
21807104
3268086
4430575

2048-bits (107-bit NFS security)

nops/sECM security
2279148
3524121
4872106
5104795
6126387
7157981
8199777

4096-bits (144-bit NFS security)

nops/sECM security
238213
377173
4135150
5193135
6254123
7288114
8409107