“This destroys the RSA cryptosystem”

https://eprint.iacr.org/2021/232

by renaudg • 5 years ago

279 146 5 years ago

eprint.iacr.org

jeofken• 5 years ago

Would someone competent in cryptography please explain this to a “regular” programmer?

lquist• 5 years ago

Yes and if it is feasible given current computer architectures or requires significant advances in quantum algorithms/computers?

pkulak3• 5 years ago

Yeah, if this really is fast prime factoring, we're all in a lot of trouble.

toomuchtodo• 5 years ago

“No more secrets”

smolder• 5 years ago

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.

muricula2• 5 years ago

Dunno we have post quantum algorithms which don't rely on factoring prime numbers like RSA does, but it will be a lot of systems administration type work to make sure that nobody is using RSA keys anymore.

john_alan2• 5 years ago

Semi-prime factoring. Also we have elliptic curves.

dfabulich• 5 years ago

RSA is a "public key" cryptography system, where you have a public key that everyone's allowed to know, and a private key that you keep secret. Anyone can use the public key to encrypt messages, but you need the private key to decrypt messages.

(You can also use it for digital signatures, where you provide a copy of the message and also "encrypt" the message with the private key; anyone can publicly decrypt it. If the "decrypted" message matches the original, then the signature proves that the message was signed by someone who has the private key.)

RSA works by starting with two large random prime numbers P and Q. You multiply P and Q to get a number M, and that number becomes part of the public key. An attacker who knows P and Q can compute your private key and decrypt your messages.

RSA assumes that it's computationally infeasible to factor M back into P and Q. It's supposed to be something like O(2^n), where n is the length of M.

A fast factorization algorithm breaks that assumption, allowing attackers to decrypt messages and forge digital signatures.

If Schorr has found an algorithm that does this, I would say it "destroyes the RSA cryptosystem."

(My guess: it probably doesn't work, because drafts of this paper have been out for a few years and the sky hasn't fallen yet.)

ncann2• 5 years ago

Obviously this went way over my head, but what is the claimed time complexity here?

ramboldio• 5 years ago

"This proves the polynomial time bound."

ncann2• 5 years ago

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.

dleslie7• 5 years ago

If 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.

thomasahle• 5 years ago

It's hard to figure out what they are claiming, which makes the whole paper seem fishy.

On page 14 they seem to claim a factor 2 improvement in the exponent of the quadratic number field sieve, which might be better that the general sieve for some N, but is still worse asymptotically.

azornathogron• 5 years ago

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.

cameronperot• 5 years ago

The 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...

terramex• 5 years ago

archive.is link: https://archive.is/BC1UQ

carlosfvp• 5 years ago

I did not found the sentence "This destroyes the RSA cryptosystem" in the real PDF https://eprint.iacr.org/2021/232.pdf Is this fake news?

sodality2• 5 years 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

celticninja• 5 years ago

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• 5 years ago

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• 5 years ago

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.

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• 5 years ago

<pedant> not a direct quote since the quote in the paper has a typo: “destroyes”

baby• 5 years ago

Can we not do this, your suggestion prevents anyone from understanding what is at play here.

gnulinux3• 5 years ago

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?

dleslie7• 5 years ago

I'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.

gnulinux3• 5 years ago

I see, makes sense, thanks.

randtrain34• 5 years ago

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...

munchbunny2• 5 years ago

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.

pkulak3• 5 years ago

So, 616 and 1233 digits, respectively.

ChuckMcM2• 5 years ago

2048 bits ~ 617 decimal digits, 4096 bits ~ 1234 digits.

paconbork• 5 years ago

It'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/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

Centigonal4• 5 years ago

The 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

[2] https://www.math.uni-frankfurt.de/~dmst/research/papers/SVP9...

detaro3• 5 years ago

EDIT: 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.

gpm2• 5 years ago

Claus Peter is the name on the actual (2019 draft) paper too?

https://eprint.iacr.org/2021/232.pdf

monocasa• 5 years ago

I wouldn't necessarily consider that a misspelling.

Centigonal4• 5 years ago

he spells it like that on his published research, though. See here:

https://link.springer.com/chapter/10.1007/978-3-642-42001-6_...

yesenadam3• 5 years ago

The paper has the same title as a 2017 draft paper

Not quite the same title. He has papers with similar titles since at least 2010.

I wanted to say thanks - this document linked to on his wikipedia page was unexpectedly fascinating! NSA, patents, conspiracies..

https://marc.info/?l=cypherpunks&m=95280154624588&w=2

dleslie7• 5 years ago

Be careful, cypherpunks is a fascinating rabit hole; you can easily fall in and forever alter your perspective.

Centigonal4• 5 years ago

For sure -- and I appreciate the clarification.

aarchi• 5 years ago

I was surprised to see, in the 1999 email you linked, that NSA mass surveillance was already widely known, before the NSA ramp up from 9/11 and before the Snowden disclosures.

Actually, I don't think of the NSA's plots to deny everyone but themselves (and those they dub worthy) access to strong un-GAKed commercial cryptography as a conspiracy, per se. NSA officials acted upon a fairly open if Byzantine strategy. It was hatched by men who obviously believe that Western liberal society is best safeguarded if the US can continue to gleen the benefits of the huge passive eavesdropping net that has for decades sustained America's geo-political dominance.

cnlp100• 5 years ago

It is strange, perhaps a pdf reader exploit?

tveita• 5 years ago

So are you saying I shouldn't run out and short the RSA stock? :)

I was curious about the submission process for ePrint, it looks like there is supposed to be some vetting, even though it is explicitly not fact checked or peer reviewed. You do get papers from cranks and blockchainers but presumably Schnorr doesn't fall into those categories.

https://eprint.iacr.org/about.html

ralph84• 5 years ago

RSA is owned by private equity so there's nothing to short. In any case, the patent on RSA is long-expired and OpenSSL drove the price of crypto libraries to $0, so any revenue RSA the company gets from RSA the cryptosystem is negligible.

aliljet• 5 years ago

I'm out of my depth. Disclaimer applied, I genuinely wonder how fast this "fast factoring" method is in this case?

elmo2you5• 5 years ago

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.

gpm2• 5 years ago

work in progress 31.10.2019

^ Date on the pdf

elmo2you5• 5 years ago

Yes, 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.

BluSyn• 5 years ago

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• 5 years ago

Given the claims I would have wanted the paper to include factoring for some of the known rsa public keys to demonstrate feasible time.

intunderflow• 5 years ago

I 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• 5 years ago

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

muricula2• 5 years ago

The website is being hugged to death, but archive.org has scraped the PDF: https://web.archive.org/web/20210302215033/https://eprint.ia...

eternalny1• 5 years ago

This is a different paper.

The linked one is: received 1 Mar 2021

The PDF is: work in progress 31.10.2019

rincebrain• 5 years ago

No, 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• 5 years ago

cstheory stackexchange discussion: https://cstheory.stackexchange.com/questions/1300/integer-fa...

nanis2• 5 years ago

cstheory stackexchange discussion

That discussion is from 2010. The download link for the paper does not seem to work.

Geee• 5 years ago

GPT-3?

nanis2• 5 years ago

It 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• 5 years ago

If 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• 5 years ago

Is it just me or is that really hard to read?

hyper_reality• 5 years ago

This 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• 5 years ago

It 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• 5 years ago

Its a meme. "This kills the crab."

balupton2• 5 years ago

CryptoHack discord invite: https://discord.com/invite/eJaJ3xC

bjeds• 5 years 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• 5 years ago

I 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• 5 years ago

Man, this is one of those HN pieces I open and immediately think "I'm not smart enough to understand any of this."

yuhong• 5 years ago

TIL https://cryptologie.net/article/222/implementation-of-copper...

There is also: https://simons.berkeley.edu/sites/default/files/docs/14975/c...

balupton2• 5 years ago

I'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/RSA_(cryptosystem) 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-cry...

earonesty• 5 years ago

....and someone rolled back your edits. because it's not peer reviewed.

hn_throwaway_992• 5 years ago

If 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• 5 years ago

Yeah 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• 5 years ago

That'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_992• 5 years ago

But 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.

Rounin• 5 years ago

Apparently 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://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9...

PhantomGremlin• 5 years ago

If 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

Extra credit:

   What is the factorization of RSA-2048?

aceon48• 5 years ago

Quantum computers already destroy RSA. most likely already in thdhands of a nationstate

CryptoLeo• 5 years ago

debunked: https://github.com/lducas/SchnorrGate

foobarmanman• 5 years ago

Two 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.

“This destroys the RSA cryptosystem”

Related Stories