8
$\begingroup$

NIST key management guidelines suggest that 15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys. If a 15360-bit RSA key is the equivalent to a 256-bit symmetric key, does that mean a 15360-bit RSA key can prevent factoring by the strongest quantum computers in the next 100 years or so? If not, how can the following statement be true?

…a 15360-bit RSA key is the equivalent to a 256-bit symmetric key.

So, a 256-bit symmetric key could be reduced to 128-bit with Quantum computers (Grover's algorithm). Even if it takes 20 years or so from now to develop a strong enough quantum computer, once quantum computers become strong enough, a 256-bit symmetric key would still be strong enough to prevent brute forcing when the keys are random enough. So, do they think a strong quantum computer can factor 15360-bit RSA keys using Shor's algorithm (or any similar algorithm) in 100 years or so from now?

$\endgroup$
  • 2
    $\begingroup$ I think they would be wise at this point to qualify their statement to mean it would take, on average, approximately the same number of CPU cycles on a standard computer to break either encryption. As you point out, RSA is much more fragile in the face of quantum computing than symmetrical encryption is. If and when that becomes publicly available, with its polynomial-time factoring it will make RSA no more secure than ROT-13. $\endgroup$ – WDS Aug 14 '15 at 19:50
  • 2
    $\begingroup$ @WDS, RSA may still be useful if you're willing to dedicate two whole HDDs to store keys. Reference. However ROT13 has no key and is thus always broken ;) $\endgroup$ – SEJPM Aug 14 '15 at 19:52
  • $\begingroup$ Oh, that was a funny read, sorry, I'll give away the clue on the very last page of the presentation: "Concrete analysis suggests that RSA with $2^{31}$ 4096-bit primes provides $> 2^{100}$ security vs. all known quantum attacks. Key almost fits on a hard drive." (but note that they've received no funding yet in exploring this further, I presume that's another joke) $\endgroup$ – Maarten Bodewes Aug 15 '15 at 10:44
  • $\begingroup$ Also symmetric algorithm are not based on prime factoring $\endgroup$ – albanx Aug 16 '15 at 9:41
  • $\begingroup$ Although Shor's algorithm is polynomial, I don't know how practical will be. $\endgroup$ – 111 Aug 28 '15 at 12:47
8
$\begingroup$

The statement

a 15360-bit RSA key is the equivalent to a 256-bit symmetric key

does not take into account quantum algorithms. In fact, it is based on a specific computation model.

It is just based on the fact that there exist sub-exponential algorithms for factoring and therefore you need longer keys than when using symmetric-key crypto where it is believed that there is no attack that is more efficient than exhaustive search.

I'm not 100% sure, but I think the NIST standard is based on a paper by Lenstra and Verheul (PDF).

$\endgroup$

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.