SoylentNews is people
SoylentNews
Math is hard. Indeed, much of the modern infrastructure for secure communication depends heavily on the difficulty of elementary mathematics — of factoring, to be exact. It's easy to reduce a small number like 15 to its prime factors (3 x 5), but factoring numbers with a few hundred digits is still exceedingly difficult. For this reason, the RSA cryptosystem, an encryption scheme that derives its security from the difficulty of integer factorization, remains a popular tool for secure communication.
Research suggests, however, that a quantum computer would be able to factor a large number far more quickly than the best available methods today. If researchers could build a quantum computer that could outperform classical supercomputers, the thinking goes, cryptographers could use a particular algorithm called Shor's algorithm to render the RSA cryptosystem unsalvageable. The deadline to avert this may arrive sooner than we think: Google recently claimed that its quantum computers will be able to perform a calculation that's beyond the reach of any classical computer by the end of the year. In light of this, cryptographers are scrambling to find a new quantum-proof security standard.
Yet perhaps RSA isn't in as much trouble as researchers have assumed. A few weeks ago, a paper surfaced on the Cryptology ePrint Archive that asked: "Is it actually true that quantum computers will kill RSA?" The authors note that even though a quantum computer running Shor's algorithm would be faster than a classical computer, the RSA algorithm is faster than both. And the larger the RSA "key" — the number that must be factored — the greater the speed difference.
-- submitted from IRC
(Score: 4, Insightful) by tangomargarine on Tuesday May 16 2017, @02:56PM (7 children)
"Is it actually true that quantum computers will kill RSA?" The authors note that even though a quantum computer running Shor's algorithm would be faster than a classical computer, the RSA algorithm is faster than both. And the larger the RSA "key" — the number that must be factored — the greater the speed difference.
So decrypting it using the proper technique is faster than brute-forcing it. Duh? How is this supposed to show that quantum computers aren't a problem for cryptography?
The authors of the paper estimate that attacking a terabyte-size key using Shor’s algorithm would require around 2100 operations on a quantum computer, an enormous number comparable to the total number of bacterial cells on Earth. The authors don’t convert this to a concrete time estimate, but current research suggests that a real quantum computer wouldn’t be able to accomplish this in any reasonable amount of time.
And transmitting a fucking terabyte-sized key to protect your data is also not reasonable. When you multiply by infinity, shockingly the answer you get out is infinity?? *facepalm*
Still, a terabyte-size key isn’t exactly easy to work with. (The largest RSA keys right now are a few thousand bits; a terabyte is many trillions of bits.) The authors report that generating a terabyte-size RSA key and carrying out the encryption-decryption process takes about five days. “The encryption and decryption cost is terrible for most applications,”
Oh, so you're aware of this. Alright. *scrolls* Nope, that's the end of the article.
Thanks so much.
"Is that really true?" "I just spent the last hour telling you to think for yourself! Didn't you hear anything I said?"
(Score: 2) by bob_super on Tuesday May 16 2017, @06:14PM
How fast do you blow through your battery and data cap when you encode "grab milk on the way home" with a TB key?
(Score: 2) by VLM on Tuesday May 16 2017, @06:57PM (3 children)
And transmitting a fucking terabyte-sized key to protect your data is also not reasonable
Actually no, you probably shouldn't distribute your private key along with the encrypted message. Also I'm so old people used to whine about 1024 bit keys being too long and SSH is too slow to use securely on a 486 etc etc. A terrabyte, terrabit, whats the difference when thats juuuuuuuuust about cheap SSH range now and has been cheap spinning rust for some years. Another 10,20,30 years and every raspberry pi will come with 16 exabytes of storage for $25 or whatever.
Also you might not be favorably impressed with the sheer size of some post-quantum algos. They're not used TODAY instead of RSA because they're too big. We think we understand RSA and have debugged it so merely using a long key is the way.
Right now crypto is cheap enough that we do dumb paranoid things with it. Its likely that in a post quantum world as long as you spend, I donno, 10x the profit of having your credit card get powned on cracking it, most folks would never crack it (why spend $10000 on electricity to when your average haul per crack will be $1000 or less?). The days of your gmail connection being nation-state proof might be over but as long as your neighbor kid can't read it, thats good enough? So yeah maybe 1 TB key is nation state nuclear launch code secure for a trillion years, but we'll use mere 1 megabit keys that cost $100K and ten years to crack, and that'll be OK because my CC expires in 3 years anyway and my neighbor doesn't have 100 years and $10K or $1M and one year.
(Score: 2) by tangomargarine on Tuesday May 16 2017, @07:04PM (1 child)
Actually no, you probably shouldn't distribute your private key along with the encrypted message.
It may not have to be transmitted in the same session, but the recipient still has to get it *somehow.*
A terrabyte, terrabit, whats the difference when thats juuuuuuuuust about cheap SSH range now and has been cheap spinning rust for some years.
Using half my hard drive to store a single key is super optimal. God forbid I want to communicate with two different people...
The terrabyte thing was just the punchline to an entire article that didn't make sense.
"Is that really true?" "I just spent the last hour telling you to think for yourself! Didn't you hear anything I said?"
(Score: 2) by VLM on Tuesday May 16 2017, @07:40PM
RSA dates back to '77.
In '75 the Altair 8800 was release and S100 memory cards usually only held 8192 bits or 32768 bits (costing $340). Organized as bytes of course.
In about '82 my father paid about a couple hundred bucks for a mere 16K of ram to upgrade one of his machines. I remember being impressed that each 4116 dram was worth like $30 or whatever it was.
Its gonna be OK. Maybe not today. maybe not tomorrow, soon enough sure.
(Score: 2) by stormwyrm on Wednesday May 17 2017, @03:25AM
Numquam ponenda est pluralitas sine necessitate.
(Score: 2) by Azuma Hazuki on Tuesday May 16 2017, @08:32PM (1 child)
Let's say something more reasonable, like a 128-megabyte key. How long would *that* take Shor's Algorithm to crunch? Because if it's anything over 50 years or so that should be plenty.
I am "that girl" your mother warned you about...
(Score: 0) by Anonymous Coward on Monday May 22 2017, @05:46PM
I find your question interesting, and would like to subscribe to your newsletter.