Slashdot Mirror
Ask Slashdot: Post-Quantum Asymmetric Key Exchange?
First time accepted submitter LeDopore writes "Quantum computers might be coming. I'd estimate that there's a 10% chance RSA will be useless within 20 years. Whatever the odds, some of the data we send over ssh and ssl today should remain private for a century, and we simply can't guarantee secrecy anymore using the algorithms with which we have become complacent. Are there any alternatives to RSA and ECC that are trustworthy and properly implemented? Why is everyone still happy with SSH and RSA with the specter of a quantum menace lurking just around the corner?"
Quantum entanglement is being studied hard by bright people, who are publishing. I think that the technology is a ways off, and I expect that there are some limitations on entanglement. Being able to collapse 2^2048 super-positions seems a bit preposterous to me. I could be horribly wrong, but I have a feeling that there are going to be limits on how many "entanglements" can be made by a given subatomic particle.
I'm a bit more worried about someone who finally get's a eureka on factoring large numbers. Then the genie is out of the bottle, and no-one knows it. Heck it might already be cracked, and held as a state secret, only makes sense.
What would you do if you had a factoring algorithm that could factor a RSA number as fast as the generator could make them?
What would be the fallout?
Whatever the odds, some of the data we send over ssh and ssl today should remain private for a century, and we simply can't guarantee secrecy anymore using the algorithms with which we have become complacent.
If I may, I would like to quote the MC Frontalot song, "Secrets From The Future":
You can't hide secrets from the future
with math, you can try, but I'll bet that in the future
they laugh at the half-assed schemes and algorithms
amassed to enforce cryptographs in the past.
The rest of the song does a pretty good job of explaining exactly how absurd the entire concept of keeping data private, long-term (like, say, a century as suggested, or even twenty years when RSA is theorized to fall), entirely using encryption algorithms. Brings up points like how nobody's going to care about things like your shopping habits (as embarrassing as they may be), credit card transactions from cards expired twenty years previous, sensitive SSH streams decades old, etc. And that it's a moot point anyway, as it's impossible to predict technology out that far, so it's more than a bit futile to count on math to protect things on a time scale like that.
Best of all, your secret: nothing extant could extract it
By 2025 a children's Speak & Spell could crack it.
Demanding constant attention will only lead to attention.
15 has been factored using NMR machines which have been abandoned for most serious research precisely because they can't be scaled very well. There are other systems which are more scalable in theory but they haven't been successful so far as getting the minimum number of qbits needed to factor 15. (Also this isn't quite accurate in that you need slightly more than log_2 n qbits to factor n in the general case, but the basic point is sound.)
Lockheed installed a 128bit quantum computer this year
http://www.forbes.com/sites/alexknapp/2011/10/31/lockheed-martin-installs-quantum-computer/
I have no idea of the specifics, but it sounds as if they have a working version.