2
$\begingroup$

Is there a rsa modulus size where security starts to decrease or is a larger rsa keysize always better? (of course I’m considering things like performance penalty)

$\endgroup$
2
$\begingroup$

With current known attacks increasing key size will improve security. Providing you follow current best practices for selecting p and q, not to close together neither to small. Etc. It is possible but unlikely there will be some future attack on RSA or integer factorization which gets easier beyond a certain size. We already have different best algorithms for integer factorization depending on size but bigger is still better. https://en.wikipedia.org/wiki/General_number_field_sieve is currently best for very large numbers (with no special form). But for numbers less than 100 digits or so https://en.wikipedia.org/wiki/Quadratic_sieve is faster.

Obviously standardized well known implementations are more secure than anything homegrown and this will likely trump key size.

Currently RSA is best attacked by integer factorization and this will likely remain in the near future, though there are no proofs RSA is as hard as Integer factorization.

$\endgroup$
2
  • $\begingroup$ All things being equal and if all goes well, Increasing key size will improve security , but how the factors are generated matters a lot; size might be considered secondary to avoiding some pitfalls. Best practices for selection $p$ and $q$ are much more complex than outlined, and arguably one needs not check they are not to(o) close together. It is not true that standardized well known implementations are more secure than anything homegrown; this is a confusion between being secure, and being trustable; many non-trustable things are secure. $\endgroup$ – fgrieu Jan 5 '18 at 10:39
  • $\begingroup$ I addded "etc." To clarify the list isn't conclusive. There are many pitfalls, in algorithmic and implementation details. This means it is unlikely a homegrown solution will be secure. Obviously skill and experience matter and mostly makes a difference how original. A minimal modification of a good solution for larger keys shouldn't be too difficult to do securely. Yet an implementation from scratch is riddled with traps. $\endgroup$ – Meir Maor Jan 5 '18 at 11:04
1
$\begingroup$

In terms of the difficulty of factoring and offline attacks, I'm not aware of any "upper bound" on RSA security. All integer factorization algorithms have complexity that continues to grow with the size of the integer being factored. OTOH, it seems likely that implementation bugs & side channel attacks would become more pronounced at very large sizes.

$\endgroup$
1
  • $\begingroup$ I was thinking about timings. $\endgroup$ – user2284570 May 3 '19 at 17:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.