[HN Gopher] No, RSA Is Not Broken
___________________________________________________________________
No, RSA Is Not Broken
Author : LinuxBender
Score : 115 points
Date : 2021-03-09 15:32 UTC (7 hours ago)
(HTM) web link (www.schneier.com)
(TXT) w3m dump (www.schneier.com)
| MaxBarraclough wrote:
| An interesting point at [0]:
|
| > if Schnorr could "destroy RSA", he would have destroyed one of
| the RSA Challenge problems to prove it. He did not.
|
| [0] https://www.schneier.com/blog/archives/2021/03/no-rsa-is-
| not...
| RcouF1uZ4gsC wrote:
| That isn't as reassuring as it seems. It may be that Schnorr
| could "destroy RSA", but that the computing requirements are
| still beyond what a researcher could have access to, but are
| within the abilities of a large corporation or nation-state. An
| example is SHA-1. We have known it was broken for some time,
| but it took Google's massive compute power to actually produce
| a real world collision.
| amelius wrote:
| What kind of reasoning is this? Not all mathematicians are
| interested in or capable of computer programming.
| chrismeller wrote:
| You are correct, but I think it's still a valid point. The
| way to demonstrate to the world that it is broken would have
| been to break it, and if you even skim over his bonafides it
| seems like something he is 1) an expert in and 2) would have
| the resources to demonstrate, even if not programmed by
| himself (grad students, perhaps?).
|
| He's also older and retired and could simply have the
| attitude of "F it, I'll leave this here, mic drop", so who
| the hell really knows.
| not2b wrote:
| He could find any number of grad students who would be
| happy to code up his algorithm for him, so they can be co-
| authors on the paper that "destroyed RSA".
| lisper wrote:
| Or any number of hackers who would be happy to do it so
| they could be the first to break into people's bank
| accounts. If RSA were broken as a result of a public
| announcement with no warning, there would be no doubt in
| anyone's mind because chaos would ensue in very short
| order.
| Someone wrote:
| I'm not claiming anything about the correctness of this
| proof, but if it isn't correct, writing a program that
| implements the algorithm would be a waste of time.
|
| So, if the proof is hard to follow and describes a
| complex algorithm, grad students who don't fully grok the
| supposed proof might not be that happy to work on that
| program. They might end up looking for a nonexistent bug
| in their program for months.
|
| I also think it's illustrative to mention the
| Grothendieck prime
| (https://en.wikipedia.org/wiki/57_(number)) here, as an
| example of how little concern some mathematicians have
| for applications of their results. That _could_ explain
| why Schnorr didn't bother to even ask his students to
| write that program.
| darig wrote:
| When the "computer programming" in question is pure
| mathematics, the reasoning is called "logic".
| kzrdude wrote:
| What's the consensus on RSA, that it's fine to use still with
| 4096-bit keys? Why are we not moving off of it?
| upofadown wrote:
| I still need to be convinced that more than 2048 bit RSA keys
| are required. There seems to be no rational reason to use
| longer keys.
|
| There have been no real breakthroughs in breaking RSA for 15-20
| years. So if you were playing the odds you would actually
| prefer RSA over systems invented more recently.
| ralph84 wrote:
| NSA used to push pretty hard for moving to elliptic curve from
| RSA. There was some speculation they already knew better
| factoring methods that worked for breaking RSA.
|
| But then the Dual_EC_DRBG backdoor came to light, so maybe they
| were just pushing elliptic curve to get their backdoors out
| there.
|
| These days NSA pushes for post-quantum crypto, but it's not
| practical yet.
| theandrewbailey wrote:
| We've already used and proven Shor's algorithm[0]; we just need a
| machine with enough quantum bits to defeat conventional
| encryption.
|
| [0] https://en.wikipedia.org/wiki/Shor%27s_algorithm
| mzs wrote:
| > Instead of performing 96 lattice reductions with a near
| guarantee of recovering 96 smooth values, a very rough
| approximation with the correct determinant indicates that we
| would need to perform 2^200 reductions of enormous lattices to
| find enough smooth values.
|
| > This is well beyond any plausible computation. It strongly
| suggests that this particular approach does not scale to the
| point of practically breaking RSA.
|
| > However, there are many open questions. Would a different
| lattice construction avoid this problem? Can the bound be
| established in another way? What are the concrete performance
| numbers and asymptotic complexity?
|
| - Keegan Ryan
|
| https://twitter.com/inf_0_/status/1367377462582079489
| mzs wrote:
| > update: the new version of March 3rd is much easier to test,
| requiring SVP in dimension as low as 47 (down from 1800 !).
|
| > Out of 1000 trials, no factoring relations was found.
|
| - Leo Ducas
|
| https://twitter.com/DucasLeo/status/1367367057055109125
| aceon48 wrote:
| RSA is broken, but likely from Quantum computers held by a nation
| state
| GuB-42 wrote:
| I don't believe it. The state of the art in quantum computing
| is far from it. In fact, we are not even sure if it is possible
| at all due to the extremely low temperatures required for a
| significant number of entangled qubits.
|
| In general, secret tech is only more advanced than what is
| available in the open when it has no real application outside
| defense. But a lot of people want quantum computers more simple
| than the ones that can crack RSA, and they don't have them. So
| I find it unlikely that any nation state has a quantum computer
| able to break current crypto.
|
| The focus on post-quantum cryptography is mostly preventive.
| waynesonfire wrote:
| Are you referring to this
| https://www.wired.com/story/microsoft-retracts-disputed-quan...
| quantum computer whose breakthrough was retracted?
| aborsy wrote:
| How could someone write in the abstract of a supposedly
| scientific paper, "This destroys RSA cryptosystem"?
|
| Weird!
| eru wrote:
| It's a pre-print. Anyone can upload those.
| iso8859-1 wrote:
| It's not anyone though, it is a renowned professor called
| Claus Peter Schnorr. And he has claimed through other
| channels that it is his paper.
| anoonmoose wrote:
| ok then reformulate that to "even renowned professors can
| occasionally get high on their own supply and make wild
| claims"
| est31 wrote:
| Not anyone. For untrusted people, arxiv needs someone trusted
| to vouch for you.
| tom_mellior wrote:
| Huh? The way I remember it, registering at arXiv is the
| same as registering anywhere else. I certainly don't recall
| needing someone to vouch for me.
| est31 wrote:
| https://arxiv.org/help/endorsement
| tom_mellior wrote:
| Ah. "In most cases, automatic endorsement is given to
| authors from known academic institutions and research
| facilities." So the ancestor's "Anyone can upload those."
| should have been "Anyone with an academic email address
| can upload those."
| vlovich123 wrote:
| The crypto stackexchange post leads to this Twitter thread
| discussing some of the math details:
| https://twitter.com/inf_0_/status/1367376959055962112
| aarchi wrote:
| Here are some notes on the paper's authenticity (in German):
| https://blog.fefe.de/?ts=9ec00c82
|
| Amusingly, at the bottom of the page, it states "Proudly made
| without PHP, Java, Perl, MySQL and Postgres".
| muizelaar wrote:
| See also: https://github.com/lducas/SchnorrGate an implementation
| in Sage Math.
| sigzero wrote:
| "Schnorr has been making presentations on his concept since at
| least 2009. In my personal opinion, 11+ years is enough time for
| a small group to make some kind of significant demonstration
| software, if people believed that the idea is likely to work.
|
| Because this proposed factoring technique has been public for
| more than a decade, both specialists in lattice algorithms, and
| other mathematicians who focus on factoring algorithms in
| general, have had plenty of opportunity to study Schnorr's ideas.
| I don't see evidence that even one mathematician with relevant
| expertise has yet been persuaded."
|
| It's been out there for a long time and...nada.
| tom_mellior wrote:
| Where is this quote from?
___________________________________________________________________
(page generated 2021-03-09 23:03 UTC)