11 ms·
“This destroys the RSA cryptosystem”
- hn_throwaway_99 6y agoIf this did actually "destroy the RSA cryptosystem", seems like a proof of concept would actually be trivial to demonstrate. Given that, my bet is on this (or, rather, at least that particular sentence) being BS.
- stjohnswarts 6y agoYeah I highly doubt the author of the paper would miss out on a chance like that. I think this is probably a lot of pearl clutching.
- DanielMcLaury 6y agoThat's not necessarily the case in general. If you had an algorithm which, given a billion dollars' worth of specialized lattice reduction ASICs, could break 2048-bit RSA in a few months' time, then for all practical purposes this would mean that 2048-bit RSA was broken -- there are plenty of state actors who would drop that kind of money in a heartbeat -- but that doesn't mean that some guy who came up with it would be able to do a demo on his laptop. (Not saying that the above has anything to do with this paper in particular.)
- hn_throwaway_99 6y agoBut still it would be trivial to write a program that could demonstrate this, no? Something that you could show that perhaps broke an unreasonably short RSA key in a shorter time than expected.
- jeofken 6y agoWould someone competent in cryptography please explain this to a “regular” programmer?
- lquist 6y agoYes and if it is feasible given current computer architectures or requires significant advances in quantum algorithms/computers?
- pkulak 6y agoYeah, if this really is fast prime factoring, we're all in a lot of trouble.
- toomuchtodo 6y ago“No more secrets”
- immigrantsheep 6y agoSetec Astronomy
- LinuxBender 6y agoCocktail party at the reservoir
- trav4225 6y agoI'll be there! P.S. Please don't bring Cooty.
- ballballball 6y agoToo many secrets
- smolder 6y agoIf 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 6y ago
- ncann 6y agoObviously this went way over my head, but what is the claimed time complexity here?
- ramboldio 6y ago"This proves the polynomial time bound."
- ncann 6y agoI 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.
- dleslie 6y agoIf true... Hot damn! There's NP-Hard problems that if we had polynomial time solutions for we could vastly improve the quality of life on earth.
- gnulinux 6y agoInteger factorizatiom not proved to be NP-complete. It's been guessed to be "hard" for a while.
- LeegleechN 6y agoInteger factoring is in a fairly sparse in-between zone between polynomial and NP Hard problems. This is why quantum computers can have a near exponential speedup from them (disregarding this claimed result) and only a polynomial speedup for NP Hard problems. So even if this result holds it can't be converted into a fast solution for all NP Hard problems.
- dleslie 6y agoAh, bummer. For some reason I thought it was NP-hard; thank-you for the correction.
- 6y ago
- azornathogron 6y agoThe 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.
- cameronperot 6y agoThe latest I was able to find was this draft from 04.03.2020 [1]. [1] https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9.pdf https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9...
- terramex 6y agoarchive.is link: https://archive.is/BC1UQ https://archive.is/BC1UQ
- carlosfvp 6y agoI did not found the sentence "This destroyes the RSA cryptosystem" in the real PDF https://eprint.iacr.org/2021/232.pdf https://eprint.iacr.org/2021/232.pdf Is this fake news?
- sodality2 6y ago>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 https://news.ycombinator.com/item?id=26322289
- celticninja 6y agoIt 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 6y agoWell, 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 6y agoIt 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. It would hardly be getting such attention with the original title, and that attention is either what it needs, or what it needs to promptly dispell it.
- indiv0 6y ago<pedant> not a direct quote since the quote in the paper has a typo: “destroyes”
- baby 6y agoCan we not do this, your suggestion prevents anyone from understanding what is at play here.
- gnulinux 6y agoCan 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?
- dleslie 6y agoI'm not sure if this is the claim in the paper; but I'll try to explain in plain terms. Let's say you have an algorithm that can solve NP-hard problems in polynomial time with an N% success rate. What value of N makes the algorithm useful in practice depends on the practicality of its use as an attack against the NP-hard problem; there is an inflection point whereat the speed of the attack outstrips the speed at which the cypher can change secrets.
- gnulinux 6y agoI see, makes sense, thanks.
- randtrain34 6y agoThey 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 6y agoTypical 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.
- paconbork 6y agoIt's worth noting that numbers of this size are already being factored with existing techniques. RSA-250, a 250 digit (829 binary digit) product of two primes was factored pretty recently: https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/202... Moreover, a 768 bit product was factored over 11 years ago, though it took two years to compute! https://en.wikipedia.org/wiki/RSA_Factoring_Challenge https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
- Centigonal 6y agoThe author of this paper is Claus P. Schnorr[1], of Schnorr signature fame. The paper has almost the same title as a 2017 draft paper[2] of his. The “This destroyes the RSA cryptosystem” quote is not in the linked paper abstract. This seems fishy. [1] https://en.wikipedia.org/wiki/Claus_P._Schnorr https://en.wikipedia.org/wiki/Claus_P._Schnorr [2] https://www.math.uni-frankfurt.de/~dmst/research/papers/SVP9.pdf https://www.math.uni-frankfurt.de/~dmst/research/papers/SVP9...
- detaro 6y agoEDIT: that draft appears in clearer sources with the same spelling, disregard below... He also apparently misspelled(?) his own name. It's "Claus-Peter" (also on other publications), not "Claus Peter". agreed, seems odd.
- gpm 6y agoClaus Peter is the name on the actual (2019 draft) paper too? https://eprint.iacr.org/2021/232.pdf https://eprint.iacr.org/2021/232.pdf
- monocasa 6y agoI wouldn't necessarily consider that a misspelling.
- Centigonal 6y agohe spells it like that on his published research, though. See here: https://link.springer.com/chapter/10.1007/978-3-642-42001-6_6 https://link.springer.com/chapter/10.1007/978-3-642-42001-6_...
- detaro 6y agoyep, found that too. disregard that then, just seemed odd on first glance.
- Centigonal 6y ago
- aliljet 6y agoI'm out of my depth. Disclaimer applied, I genuinely wonder how fast this "fast factoring" method is in this case?
- elmo2you 6y agoThis 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 6y ago> work in progress 31.10.2019 ^ Date on the pdf
- elmo2you 6y agoYes, that's what I meant with dated. So the linked paper is a work in progress from half a year ago, but presented today on ePrint and with an abstract that has extra text added. I can not determine if this "discovery" could actually break any practically operating RSA systems. Considering how that is probably true for most people, that could even be the intent here. The claim that this will destroy RSA cryptosystems, so all of them categorically, just feels like a big red flag to me. If it said it could break RSA under certain circumstances .. then maybe. Don't get me wrong, I think there are plenty of things wrong with RSA. Not least of all that determining if a key pair has a backdoor (when only having access to a public key), is essentially just as hard as deriving a private key from a public key (both require you to factor the product of two primes). It still puzzles me that apparently only cryptographic strength has been an argument for the adoption of RSA, but not the ability to detect any (trivially simple to add) backdoor. Apparently we are all supposed to trust whoever generated an RSA key pair (and only supplies a public key). Something I'd rather not do in this day and age.
- phkahler 6y agoYou're supposed to generate your own key pair. Keep the private one and publish the public one.
- jfrunyon 6y agoWhy would someone backdoor their own key when they could instead just mirror the data or something? Yes, the person you are encrypting something towards is responsible for ensuring that encryption is secure. No matter how secure you make the cryptography, the other party could still just leak the key...
- BluSyn 6y agoThere'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 6y agoGiven the claims I would have wanted the paper to include factoring for some of the known rsa public keys to demonstrate feasible time.
- intunderflow 6y agoI agree, at this point I'm way out of my depth so I'm waiting for folks who know cryptography inside and out to give their comment
- karaterobot 6y agoThe 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 https://eprint.iacr.org/2021/232.pdf
- muricula 6y agoThe website is being hugged to death, but archive.org has scraped the PDF: https://web.archive.org/web/20210302215033/https://eprint.iacr.org/2021/232.pdf https://web.archive.org/web/20210302215033/https://eprint.ia...
- eternalny1 6y agoThis is a different paper. The linked one is: received 1 Mar 2021 The PDF is: work in progress 31.10.2019
- rincebrain 6y agoNo, that archive.org link is a valid link for the PDF of the linked paper - if you click through to the PDF from the HN link, it's identical, including the "work in progress 31.10.2019" stamp on the first page. Why "work in progress 31.10.2019" appears on something supposedly submitted 1 Mar 2021 is an open question, but they do point to the same thing.
- strictfp 6y agocstheory stackexchange discussion: https://cstheory.stackexchange.com/questions/1300/integer-factoring-via-lattice-reduction https://cstheory.stackexchange.com/questions/1300/integer-fa...
- nanis 6y ago> cstheory stackexchange discussion That discussion is from 2010. The download link for the paper does not seem to work.
- throwawaymanbot 6y agoDoes this reference the breakthrough that the UKs GCHQ had against RSA supposedly for several decades??
- Geee 6y agoGPT-3?
- nanis 6y agoIt looks like someone read the paper and came to the conclusion that this shortens the expected lifespan of RSA and submitted the paper to IACR. I doubt it was Schnorr himself who decided to make the sensationalist claim. The final theorem in the paper is where the polynomial time claim is states. Can't quote it here because it would make no sense in isolation, but the math is readable and the claims should be independently verifiable.
- sjwalter 6y agoIf you've been following Schnorr's work, his pathway for the last decade can be summed up as thus: * 2011, retires from work at RSA foundation * 2015, publishes first version of this paper, stating, "This is a WIP". * 2017, 2018, 2019: Publishes updates of this paper, still stating "This is a WIP". Paper mostly ignorred. * 2021: Publishes this final update. Removes "WIP" marking. Adds sentence (verifiable in original paper), "This destroys RSA cryptosystems". Whether or not it's true, the level of dismissal here is kinda insane. This guy has credibility up the wazoo. The paper is dense and beyond my understanding. But this guy ain't some crackpot, this isn't some out-of-nowhere change: He's been clear about his intent and goals for nearly a decade, and now he says it's achieved.
- annoyingnoob 6y agoIs it just me or is that really hard to read?
- deleted 6y ago[deleted]
- hyper_reality 6y agoThis is being discussed in CryptoHack Discord. We are struggling to understand the paper, it is written in a very dense style and the difficulty is compounded by the fact that lattice problems can be a challenging topic even for cryptographers. Either way, we think that the title "this destroys the RSA cryptosystem" is sensationalistic and probably incorrect. It is presumably based on the fact that the paper claims to reduce some forms of integer factorisation to a lattice problem which can be solved in polynomial time. However, whether this technique applies in the general case to RSA moduli is not argued here and the claim seems to be premature.
- 7800 6y agoIt actually states, “This destroyes the RSA cryptosystem.” Seems a bit like the way an old pirate might speak, or at least someone hundreds of years old.
- sundbry 6y agoIts a meme. "This kills the crab."
- balupton 6y agoCryptoHack discord invite: https://discord.com/invite/eJaJ3xC https://discord.com/invite/eJaJ3xC
- bjeds 6y ago? This is discussed here, at Hacker News. It's also discussed at many other places on the internet. :-) Why is this chat room you mention relevant? And who are "we" you speak of? You are presenting yourself as some kind of authority, but you need to back that claim up.
- zenexer 6y agoI assume “we” refers to the aforementioned community on Discord. I would hardly call that a claim to authority; it’s closer to, “my friends and I think this is bunk.” That’s not to be dismissive of their opinion, but I don’t think it’s accurate to call it a claim to authority. It’s the same as saying “a channel on IRC” or “a group on WhatsApp.”
- kaishiro 6y agoMan, this is one of those HN pieces I open and immediately think "I'm not smart enough to understand any of this."
- yuhong 6y agoTIL https://cryptologie.net/article/222/implementation-of-coppersmith-attack-rsa-attack-using-lattice-reductions/ https://cryptologie.net/article/222/implementation-of-copper... There is also: https://simons.berkeley.edu/sites/default/files/docs/14975/cryptanalysis.pdf https://simons.berkeley.edu/sites/default/files/docs/14975/c...
- balupton 6y agoI've gone ahead and updated the following wiki pages to get the right eyeballs on this: https://en.wikipedia.org/wiki/Integer_factorization https://en.wikipedia.org/wiki/Integer_factorization https://en.wikipedia.org/wiki/RSA_(cryptosystem) https://en.wikipedia.org/wiki/RSA_(cryptosystem) https://en.wikipedia.org/wiki/Claus_P._Schnorr https://en.wikipedia.org/wiki/Claus_P._Schnorr Also cross-shared with Cloudflare's forum, as I believe they would be interested: https://community.cloudflare.com/t/this-destroys-the-rsa-cryptosystem-iacr-org/248941?u=balupton https://community.cloudflare.com/t/this-destroys-the-rsa-cry...
- earonesty 6y ago....and someone rolled back your edits. because it's not peer reviewed.
- deleted 6y ago[deleted]
- Rounin 6y agoApparently a newer version of the PDF can be found on the university's website, and the "destroys RSA" phrase isn't found there either: https://twitter.com/ManishEarth/status/1366906561486983171 https://twitter.com/ManishEarth/status/1366906561486983171 https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9.pdf https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9...
- aceon48 6y agoQuantum computers already destroy RSA. most likely already in thdhands of a nationstate
- PhantomGremlin 6y agoIf RSA is truly destroyed, then, as a demonstration, please answer a simple question: What is the factorization of RSA-1024? https://en.wikipedia.org/wiki/RSA_numbers https://en.wikipedia.org/wiki/RSA_numbers Extra credit: What is the factorization of RSA-2048?
- CryptoLeo 6y agodebunked: https://github.com/lducas/SchnorrGate https://github.com/lducas/SchnorrGate
- foobarmanman 6y agoTwo questions: 1. Is the 'n' small enough in the SVP problems to pay out the transform? 2. Is there inverse for this transform? It would be the way to solve NP-hard problems with a quantum computer.