[HN Gopher] "This destroys the RSA cryptosystem"
___________________________________________________________________
"This destroys the RSA cryptosystem"
Author : renaudg
Score : 109 points
Date : 2021-03-02 22:29 UTC (31 minutes ago)
(HTM) web link (eprint.iacr.org)
(TXT) w3m dump (eprint.iacr.org)
| jeofken wrote:
| Would someone competent in cryptography please explain this to a
| "regular" programmer?
| lquist wrote:
| Yes and if it is feasible given current computer architectures
| or requires significant advances in quantum
| algorithms/computers?
| pkulak wrote:
| Yeah, if this really is fast prime factoring, we're all in a
| lot of trouble.
| toomuchtodo wrote:
| "No more secrets"
| immigrantsheep wrote:
| Setec Astronomy
| LinuxBender wrote:
| Cocktail party at the lake
| smolder wrote:
| If that's the case it's funny to think... NSA could have sat
| on this for years. Though that would be a really hard secret
| to keep.
| xxpor wrote:
| I'd always figured they'd have a (useful) quantum computer
| sitting in the basement of Ft. Meade at some point, and
| it's existence would be Top Secret with whatever codeword
| means "if this leaks, or we think it'll leak, we just
| assassinate you"
| ncann wrote:
| Obviously this went way over my head, but what is the claimed
| time complexity here?
| ramboldio wrote:
| "This proves the polynomial time bound."
| ncann wrote:
| I would be very skeptical if there is indeed a poly time
| algorithm for integer factorization. If that's actually what
| the paper claims then it's a very big claim.
| azornathogron wrote:
| The PDF has a slightly different abstract and is dated "work in
| progress 31.10.2019". I wonder if there is a more recent version
| available somewhere.
| terramex wrote:
| archive.is link: https://archive.is/BC1UQ
| carlosfvp wrote:
| I did not found the word "This destroyes the RSA cryptosystem"
| in the real PDF https://eprint.iacr.org/2021/232.pdf Is this
| fake news?
| sodality2 wrote:
| >This last sentence of the abstract, "This destroyes the RSA
| cryptosystem", does not appear on the abstract of the actual
| PDF (which also appear to be dated).
|
| https://news.ycombinator.com/item?id=26322289
| celticninja wrote:
| It appears on the linked page only, it is someone's
| assessment of the result. Whether that person is qualified to
| make that assessment is anyone's guess
| marktangotango wrote:
| Well, that's certainly provacative, can the title be updated to
| the title of the paper and year (2019)?
|
| "Factoring Integers by CVP and SVP Algorithms"
| OJFord wrote:
| It is a direct quote from the end of the abstract. The paper
| could hardly be titled that way. It is editorialising and thus
| against the guidelines.. but it's reasonable IMO.
| indiv0 wrote:
| <pedant> not a direct quote since the quote in the paper has
| a typo: "destroyes"
| detaro wrote:
| <pedant> that sentence is not in the paper, only on the
| linked page
|
| Also missing the dash in his name, and apparently title
| from somewhere else?
| (https://news.ycombinator.com/item?id=26322254)
|
| seems somewhat fishy, I'll wait what experts say in the
| next few days...
| ttul wrote:
| That's just the Chaucerian spelling.
| gnulinux wrote:
| Can someone please correct me? We don't know polynomial CVP/SVP
| algorithms correct? In fact, isn't SVP an NP-Hard problem? Why
| would this "destroy" RSA?
| randtrain34 wrote:
| They only tested with numbers size of ~2^800, which is around 240
| digits, but I believe (correct me if I'm wrong) there exists
| usages of RSA with over 600 digits, so it'll still take a
| massively long amount of time to factor those numbers...
| munchbunny wrote:
| Typical key lengths for RSA these days are 2048 and 4096 bits.
|
| I don't know what that means for this paper, just happened to
| have those two key lengths off the top of my head.
| pkulak wrote:
| So, 616 and 1233 digits, respectively.
| ChuckMcM wrote:
| 2048 bits ~ 617 decimal digits, 4096 bits ~ 1234 digits.
| Centigonal wrote:
| The author of this paper is Claus P. Schnorr, of Schnorr
| signature fame.
|
| https://en.wikipedia.org/wiki/Claus_P._Schnorr
|
| The paper has the same title as a 2017 draft paper of his. The
| "This destroyes the RSA cryptosystem" quote is not in the linked
| paper abstract. This seems fishy.
| detaro wrote:
| He also apparently misspelled his own name. It's "Claus-Peter",
| not "Claus Peter". agreed, seems odd.
| aliljet wrote:
| I'm out of my depth. Disclaimer applied, I genuinely wonder how
| fast this "fast factoring" method is in this case?
| elmo2you wrote:
| This last sentence of the abstract, "This destroyes the RSA
| cryptosystem", does not appear on the abstract of the actual PDF
| (which also appears to be dated).
|
| How does it destroy RSA? Under what conditions? That claim sounds
| rather broad and definitely bold, to say the least.
| gpm wrote:
| > work in progress 31.10.2019
|
| ^ Date on the pdf
| BluSyn wrote:
| There's a difference between cryptography broken in "theory" and
| broken in "practice". Couldn't find anything relevant to that
| point in the paper. Who here is qualified to make that
| assessment?
| olliej wrote:
| Given the claims I would have wanted the paper to include
| factoring for some of the known rsa public keys to demonstrate
| feasible time.
| karaterobot wrote:
| The linked page links to the full article as a PDF, though I'll
| be honest and say it still doesn't help me fully understand the
| ramifications of that statement.
|
| https://eprint.iacr.org/2021/232.pdf
| muricula wrote:
| The website is being hugged to death, but archive.org has scraped
| the PDF:
| https://web.archive.org/web/20210302215033/https://eprint.ia...
___________________________________________________________________
(page generated 2021-03-02 23:00 UTC)