jktdev
Martijn GrootenA group of Chinese researchers claims it can break 2048-bit RSA using a quantum-ish computer and it's worth reading Schneier's comments https://www.schneier.com/blog/archives/2023/01/breaking-rsa-with-a-quantum-computer.html
leE Brotherston@martijn_grooten I have yet to encounter "quantum-ish" computers đ
John Gordon@martijn_grooten Mostly a nothing but remarkable how Schorâs algorithm fails in weird ways
Justin Derrick@martijn_grooten This is why I've *always* used the maximum key length offered by any particular system. Yeah, it's great to get logged into that remote server 0.14 seconds faster by choosing a 2048 RSA key instead of a 8192 bit key, but spending all that time re-keying servers is way worse.
@martijn_grooten And to follow that up, creating a 16384-bit RSA key only takes about 45 seconds on my laptop. :) Haven't tested login speeds... yet. :)
amarioguy@martijn_grooten definitely worth expressing skepticism here especially given what happened with the Schnorr paper
just a side note - maybe this is just me but yes I do see a lot of absolutely justifiable skepticism i also feel that there's been a sort of... inherent avoidance towards work on factoring and related problems? (best way i can put it really)
like it could be that people are afraid of the implications (justifiably so! again not saying it's wrong) of solving problems like factoring that it's easy to just brush aside things as practically unsolvable even when they haven't mathematically proven to be unsolvable in practice.
idk that's just my stance, i've been looking at the academic material on factoring and such but i'm definitely not an expert nor am i a cryptographer, i'm just interested in the field generally.
Wladimir Palant@martijn_grooten Well, they donât actually claim that they *can* break 2048-bit RSA, they rather say that they *could* break it on future quantum computers. So far they only managed to factorize a 48 bit integer and extrapolate the results.
Also, in my understanding this sentence means that it isnât clear whether cracking an RSA key will happen in a reasonable time:
> It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA
Not that I understand the terminology, but presumably there are unknowns related to the characteristics of these future quantum computers.
Even so, these results are quite remarkable of course.
SeĂĄn FenianSchneier says,
"One of the issues with the algorithm is that it relies on a recent factoring paper by Peter Schnorr. Itâs a controversial paper; and despite the âthis destroys the RSA cryptosystemâ claim in the abstract, it does nothing of the sort. Schnorrâs algorithm works well with smaller moduliâaround the same order as ones the Chinese group has testedâbut falls apart at larger sizes. At this point, nobody understands why. The Chinese paper claims that their quantum techniques get around this limitation (I think thatâs whatâs behind Grimesâs comment) but donât give any detailsâand they havenât tested it with larger moduli. So if itâs true that the Chinese paper depends on this Schnorr technique that doesnât scale, the techniques in this Chinese paper wonât scale, either. (On the other hand, if it does scale then I think it also breaks a bunch of lattice-based public-key cryptosystems.)"
So, the odds are this almost certainly DOES NOT, in fact, break RSA at any practical working key size.
"One of the issues with the algorithm is that it relies on a recent factoring paper by Peter Schnorr. Itâs a controversial paper; and despite the âthis destroys the RSA cryptosystemâ claim in the abstract, it does nothing of the sort. Schnorrâs algorithm works well with smaller moduliâaround the same order as ones the Chinese group has testedâbut falls apart at larger sizes. At this point, nobody understands why. The Chinese paper claims that their quantum techniques get around this limitation (I think thatâs whatâs behind Grimesâs comment) but donât give any detailsâand they havenât tested it with larger moduli. So if itâs true that the Chinese paper depends on this Schnorr technique that doesnât scale, the techniques in this Chinese paper wonât scale, either. (On the other hand, if it does scale then I think it also breaks a bunch of lattice-based public-key cryptosystems.)"
So, the odds are this almost certainly DOES NOT, in fact, break RSA at any practical working key size.
ecsdA story emerged perhaps a decade ago that NSA had been able to "crack RSA", but in reading the article, it turned out that they only did it by brute force, so the obvious answer is: use longer keys. I use 4096 bits routinely, and will use 8192 and even 16384 when I can.
The "obvious" solution is to weaponize QC for defense as well as offense; we'll wait for new algorithms.
Long live RSA and Zimmerman.
Phillip Hallam-Baker@martijn_grooten Oh boyâŚ
One of the underlying problems here is that breaking RSA has become a measure of excellence for quantum computers. And that leads to some pretty shoddy and at times outright duplicitous work.
For example, there are ways you can significantly reduce the number of gates needed to implement Shorrâs algorithm. But they kinda depend on using information that you need to know the factors to derive. So yes, here you are doing Shorrâs but you donât have a system that can factor numbers.
This looks to be very much more of the same.