Information Security Stack Exchange is a question and answer site for information security professionals. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose I am using RSA for my security system. Now someone discovers find a polynomial time algorithm for RSA. Then what measure should one that such that RSA never breaks. Maybe large number of used bits or something else.

share|improve this question
Partial duplicate of How will security need to be changed if P=NP? – Polynomial Nov 5 '12 at 14:57
Depends on the exact performance characteristics of that hypothetical algorithm. Polynomial can be anything from O(n) to O(n^1000). So this question is unanswerable. – CodesInChaos Nov 5 '12 at 14:59
@Polynomial No, I don't think this question is a duplicate. It's more specific, and calls for more specific answers. – Gilles Nov 5 '12 at 16:23
up vote 8 down vote accepted

If it is proven that P=NP then this means that a polynomial time algorithm for breaking RSA exists. Finding that algorithm might be challenging, though. On the other hand, P could be distinct from NP and yet factoring could accept a polynomial-time algorithm. Integer factorization is not proven to be a NP-complete problem.

Moreover, "polynomial" is an asymptotic behaviour, which describes how the running time of an algorithm behaves on sufficiently large inputs. Nothing says that common RSA key sizes are "sufficiently large" for the asymptotic behaviour to be a reasonably accurate estimate of performance on these key sizes. Finally, "polynomial" does not necessarily mean "fast"; an algorithm with cost O(n12) (for a RSA modulus of n bits) would have cost 2120 for a 1024-bit RSA key, i.e. totally unachievable in practice.

That's the problem with reasoning on poorly-defined hypothetical scenarios: anything can happen, really. So the question cannot be answered, except by gut feelings. My own guts tell me that if a polynomial factorization algorithm is found, then it will probably be quite expensive for "normal" integer sizes, and use sufficiently advanced mathematics that we will have a few months or years before practical implementations appear, which should give use enough time to switch to something else (e.g. elliptic curves). But, of course, my guts are just digestive organs, good at breaking down food into nutriments; what do they really know about cryptography ?

share|improve this answer
Bowel-based crypto needs more study. I propose a new field: Gastrocryptography – Polynomial Nov 5 '12 at 15:49
MMM. Sounds yummy. I'll bring the S-boxes. – tylerl Nov 6 '12 at 4:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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