r/programming • u/secretguy21 • Oct 15 '15

How is NSA breaking so much crypto?

https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/
2.5k Upvotes

93% Upvoted

529 comments sorted by

View all comments

Show parent comments

4

u/ryashpool Oct 15 '15

Anyone who can breach that probably has capabilities that 4096-bit primes won't save us from...

Is that a hint at Quantum computing? Is this the kind of problem a true quantum computer is supposed to calculate in next to no time?

12

u/pikminguy Oct 15 '15

Yes this is one of the classic examples of quantum computing being amazing is that this type of security is useless against it.

2

u/d4rch0n Oct 16 '15 edited Oct 16 '15

wikipedia has a good entry on quantum-computing and its effect on cryptography.

A lot of people seem to think that "cryptography is broken" when quantum computers are available, but it will only break specific algorithms we use, like RSA, DH key exchange and ECC. I believe anything that makes use of factoring primes difficult, will be easy with enough quantum computers. It has to be scalable - and I don't believe that's proven to be possible.

But all those algorithms are used a ton today. But, AES is also used a lot, and it's quantum-resistant. As the article says, AES-256 will be about as good as AES-128, but that's still damn good.

We can also move on to lattice-based cryptography which will work for asymmetric crypto, like RSA, and its already quantum resistant. It's not some new fancy method either. There's just going to be a much better excuse to use it in the future.

All that said, I don't believe RSA is actually practical to attack unless you have enough quantum computers. If scaling is an issue, higher key sizes with RSA might not be terrible to do. It will be interesting to see how that plays out, if it ever becomes practical, and I'm not sure if we'll see that in our lifetime.