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: -1, Offtopic) by Anonymous Coward on Tuesday May 16 2017, @12:06PM (1 child)
DON'T YOU, PRECIOUS!
NOW GIVE ME THAT FUCKING BUCKET BACK
(Score: 0) by Anonymous Coward on Tuesday May 16 2017, @07:09PM
go ask alice when she's ten feet tall
(Score: 4, Interesting) by VLM on Tuesday May 16 2017, @12:47PM (6 children)
That's an interesting alternate strategy, simply using a RSA key too large for even Shor's algo to crack in a reasonable length of time.
WRT "cryptographers are scrambling to find a new quantum-proof security standard.", about a decade ago there was a major book in the field on post quantum crypto and it was an interesting read. In my infinite spare time I intended to implement some of the algos to fool around with them, you can guess how much I got done. There's quite a bit of cryptographically useful math that is thus far quantum-proof. Some of the key lengths were pretty icky.
I'm not going to bother with an Amazon link but given "Post-Quantum Cryptography 2009th Edition by Daniel J. Bernstein (Editor), Johannes Buchmann (Editor), Erik Dahmen " Yeah, that DJB.
I wonder how much has changed in the last decade. I wonder if the 2009 edition is newer than the one I have. I need to search my bookshelves and find this dusty tome.
One big problem is scientists use quantum in a technical sense whereas the general public uses it exclusively in terms of magic and crystal healing power and new age magick and druidry and therefore you can have totally bizarre conversations where one side is talking about real math and physics and the other is talking about Hollywood technobabble.
(Score: 3, Insightful) by driverless on Tuesday May 16 2017, @01:35PM (4 children)
one side is talking about real math and physics and the other is talking about Hollywood technobabble.
Some of the cryptographers who are discussing post-quantum crypto are definitely on the Hollywood technobabble side. For others, it's just a new gravy train to hook up to for funding for playing with math once their existing grants run out. We can't even get single-sign-on, browser PKI, alternatives to passwords, or malware-proof binaries right, and they're off playing with imaginary ways to deal with science-fiction-movie-plot threats.
(Score: 2) by sgleysti on Tuesday May 16 2017, @06:22PM (3 children)
"Some of the cryptographers who are discussing post-quantum crypto are definitely on the Hollywood technobabble side."
I doubt this.
You seemed to be confused about the nature of research. Looking into threats that are decades away is exactly the kind of thing that researchers are supposed to do. The other things that you are asking for are implementation-related. Cryptographic researchers may be investigating algorithms that enable those things, but you'll need software engineers and developers to make them reality.
(Score: 0) by Anonymous Coward on Tuesday May 16 2017, @09:53PM (2 children)
It's why I sell flying-car insurance.
(Score: 2) by J053 on Wednesday May 17 2017, @12:05AM (1 child)
(Score: 0) by Anonymous Coward on Wednesday May 17 2017, @02:04PM
I was going to sell you handsome cream, but it looks like you already bought out the store [youtube.com].
(Score: 2) by sgleysti on Tuesday May 16 2017, @06:19PM
This technique from 2011 has more reasonable key lengths
https://en.wikipedia.org/wiki/Supersingular_isogeny_key_exchange [wikipedia.org]
(Score: 0) by Anonymous Coward on Tuesday May 16 2017, @02:21PM (1 child)
Not exactly. It remains an open problem whether or not RSA's security actually depends on the difficulty of integer factorization.
The security of RSA encryption depends on the difficulty of the so-called RSA Problem [wikipedia.org]: Given integers C, N, e, (plus a bunch of extra constraints) compute P where C ≡ Pe (mod N).
Factoring N is the most efficient currently-known method to solve the RSA problem. But there is no proof that the RSA problem is necessarily as hard as factoring N: it is possible that breaking RSA could actually be easier than factoring N.
(Score: 0, Touché) by Anonymous Coward on Tuesday May 16 2017, @02:26PM
Prove it.
(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.
(Score: 2) by dak664 on Tuesday May 16 2017, @07:21PM (2 children)
It strikes me that nuclei undergoing beta decay are quantum computers solving the problem of energy release. Some of them get it right away, others take a very long time. Wonder what the "half life" of Shor's algorithm is?
(Score: 2) by maxwell demon on Wednesday May 17 2017, @08:50PM (1 child)
But beta decay is exponential, and thus non-polynomial. We already have a non-polynomial solution to integer factorization even on a classical computer. Shor's algorithm doesn't have a half-life because it's not an exponential-time algorithm, but a polynomial-time one.
The Tao of math: The numbers you can count are not the real numbers.
(Score: 2) by dak664 on Thursday May 18 2017, @12:14AM
So no exponential time? Expected time then, they have no understanding of the statistics.