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

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 |