Chinese researchers break RSA encryption with a quantum computer
Chinese researchers break RSA encryption with a quantum computer
The research team, led by Wang Chao from Shanghai University, found that D-Wave’s quantum computers can optimize problem-solving in a way that makes it possible to attack encryption methods such as RSA.
The research team, led by Wang Chao from Shanghai University, found that D-Wave’s quantum computers can optimize problem-solving in a way that makes it possible to attack encryption methods such as RSA.
Paper: http://cjc.ict.ac.cn/online/onlinepaper/wc-202458160402.pdf
Follow up to https://lemmy.ca/post/30853830
There's a lot of misinformation in this thread. Sure, they broke 22-bit RSA encryption. But here's the thing - that's proof that a suitably large quantum computer can break any size RSA encryption in the same amount of time it took to break 22-bit RSA encryption.
Because of the way the annealing process works, it's a known-time process, no matter how many inputs or q-bits are used. We don't have the ability to create a computer with sufficient q-bits to break anything more than 22-bit at the moment, but current estimates are that in 10 - 15 years we will have enough to break 1024-bit.
And it'll take the same amount of time as this 22-bit process took.
And that basically means we need new encryption processes within 10-15 years, that are quantum safe, or all our encryption is belong to whoever has these quantum computers.
1Chinese researchers break 22-bit RSA encryption.
It's still important news but that headline is deliberately missing that crucial little bit of scope.
115Now I can stop following the thread. So much useless information, and now I can search a decent article by the correct title
Thx for saving me a click
11Isnt that something you can break on a raspberry pi in like seconds?
3Much less than seconds. The naive algorithm is a loop to 4096 doing one integer divide on each iteration. I think the limiting factor is going to be the memory access to load the code from main memory, so you can say the whole thing can basically be done within the length of time of one memory fetch.
I still think it’s a significant development. Doing a toy problem on a radically different hardware platform that has the potential to scale up and tackle real-scale problems orders of magnitude more efficiently than the existing architecture is progress. I’m just saying that saying “break RSA” is pure clickbait.
Edit: I got curious whether my intuition about this is right. Reading from main memory on an ARM generally takes 100 ns, and doing an integer modulo takes around 40 cycles apparently. So the total time is way longer than a memory read. If you assume 1 GHz clock speed, and that the memory reads and looping code are dwarfed by the cost of the modulo operation itself, then a Raspberry Pi can factor a 22-bit integer in about 163 microseconds. The memory operation is negligible.
7
Thank you sir
1
I think Schneier wrote this well before quantum computers were a reality - did he miss something fundamental in regards to them? Quantum computers are relatively new but the theory behind them is nearly a century old.
*One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant. (Stick with me; the physics lesson is almost over.) Given that k = 1.38×10-16 erg/°Kelvin, and that the ambient temperature of the universe is 3.2°Kelvin, an ideal computer running at 3.2°K would consume 4.4×10-16 ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump. Now, the annual energy output of our sun is about 1.21×1041 ergs. This is enough to power about 2.7×1056 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2192. Of course, it wouldn't have the energy left over to perform any useful calculations with this counter. But that's just one star, and a measly one at that. A typical supernova releases something like 1051 ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states. These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.*I'm not a physicist but quantum particles were still considered to be matter the last time I checked.
5So two things that are not accounted for here:
- This covers only brute force attacks, meaning you try every different combination. Shor’s Algorithm exploits patterns in RSA keys and is much, much more efficient than brute force.
- There actually is an algorithm (Grover’s search algorithm) that can speed up brute force search. However, this speedup is only quadratic, so brute forcing something like a 256 bit key is still infeasible. The discrepancy is quantum information doesn’t flow the same way that classical information does. A related concept is the idea of reversible classical computing: this derivation relies on the assumption that you change set a bit, thereby erasing the information of what that bit was before. If your operation doesn’t erase that information (e.g. if it’s specifically a bit flip, you know what the original bit was, it’s the opposite), then this argument about the minimum required energy falls apart. Most operations in a quantum computer are inherently reversible.
3The issue here is that Schneier is discussing brute force forward computation of cryptography (IIRC of AES). Quantum computers don't iteratively attack primes by attempting to compute all possible primes. The current conventional computer attacks against RSA also aren't brute force hence why the advised size of an RSA key right now is 4096 bits.
This calculation only holds if there is no faster way than brute force iterating the entire key space.
5Good post, but dear god the text colors make my eyes hurt.
3
Sure they did. Sure sure sure. We totally believe them.
1You probably don't even need quantum for this, one day someone's gonna figure out a clever trick for primes. It's not mathematically provable to be "hard" and if you look on a radial graph there's a visible pattern. I'll worry when people are breaking decent sized elliptic curves.
4Funny, neither the article nor the paper seem to mention Shor's Algorithm. I'm going to read up more on this in the morning.
6This is why perfect forward secrecy is mandatory even if you have quantum encryption on your VPN.
As for file storage, even if it's quantum resistant, we may see a time in the future where you need to periodically re-encrypt your files to keep them a little bit less in danger
1