# What does “a 15360-bit RSA key is the equivalent to a 256-bit symmetric key” mean?

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?

• 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. – WDS Aug 14 '15 at 19:50
• @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 ;) – SEJPM Aug 14 '15 at 19:52
• 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 ﬁts on a hard drive." (but note that they've received no funding yet in exploring this further, I presume that's another joke) – Maarten Bodewes Aug 15 '15 at 10:44
• Also symmetric algorithm are not based on prime factoring – albanx Aug 16 '15 at 9:41
• Although Shor's algorithm is polynomial, I don't know how practical will be. – 111 Aug 28 '15 at 12:47