We all know classic RSA and that we should pick moduli of at least 2048-bit length to get decent (112 bit) security.

Now there's also multi-prime RSA, which can yield significant speed-ups using the Chinese Remainder Theorem (CRT).

However, the security considerations for this aren't well-known to most people, so I'm asking here:
Given a security level of n-bits, what's the minimal size the factors of a modulus need to have in order to achieve that level?

Please note, that side-channel attacks and similar attacks on bad choices of the primes should not be exploited here.

If it's not possible to give a generic strategy for all security levels, concrete numbers for $n\in\{112,128,192,256\}$ should be included.

As for my own research, I realize that the ECM is the best method at factoring and that it has a similar run-time behavior to the quadratic sieve, but actual numbers and security estimates are sparse and that's what I'm interested in.

  • 2
    $\begingroup$ Related question $\endgroup$ – fgrieu Nov 15 '16 at 18:28
  • $\begingroup$ The second answer there from D.W. has a nice table. Note that I feel something is not entirely right with regards to the rapid increase of the number of primes in time, I'd stick to the year 2001 predictions. $\endgroup$ – Maarten Bodewes Nov 15 '16 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.