Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

“This destroys the RSA cryptosystem”

eprint.iacr.org

Post reply on HN
Print view View original

71–80 of 152 posts

Re: “This destroys the RSA cryptosystem”

#71

Post by dleslie »

LeegleechN wrote: post #69
dleslie wrote: post #52

Earlier quoted context omitted.

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.

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

Ah, bummer. For some reason I thought it was NP-hard; thank-you for the correction.

Re: “This destroys the RSA cryptosystem”

#72

Post by elmo2you »

gpm wrote: post #33
elmo2you wrote: post #20

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.

> work in progress 31.10.2019 ^ Date on the pdf

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.

Re: “This destroys the RSA cryptosystem”

#73

Post by Centigonal »

yesenadam wrote: post #54
Centigonal wrote: post #13

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

> 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

For sure -- and I appreciate the clarification.

Re: “This destroys the RSA cryptosystem”

#74

Post by sudosysgen »

dleslie wrote: post #52
ramboldio wrote: post #9

Earlier quoted context omitted.

"This proves the polynomial time bound."

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.

Which ones?

Re: “This destroys the RSA cryptosystem”

#75

Post by ChuckMcM »

pkulak wrote: post #31
munchbunny wrote: post #15

Earlier quoted context omitted.

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.

So, 616 and 1233 digits, respectively.

Jinx! :-)

Re: “This destroys the RSA cryptosystem”

#77

Post by hyper_reality »

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.

Re: “This destroys the RSA cryptosystem”

#79

Post by rasz »

hardwaregeek wrote: post #43
smolder wrote: post #18

Earlier quoted context omitted.

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.

I've held the theory that if anybody found something like fast prime factoring or a P = NP proof, they'd get assassinated pretty quickly. It'd be in basically every government's interest to get the knowledge, then make sure nobody else has it.

Travelling Salesman (2012) movie is about exactly this.

Re: “This destroys the RSA cryptosystem”

#80

Post by xxpor »

Lammy wrote: post #70
xxpor wrote: post #35

Earlier quoted context omitted.

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"

Why not just put it somewhere far away instead? You could even double up the benefits by picking a cold place to help keep your equipment temps down https://commons.wikimedia.org/wiki/File:Xkeyscore-worldmap.j...

Because that's not as fun to think about when you drive past the Ft. Meade exit and it's scary signs on the Baltimore-Washington Parkway ;)
Post reply on HN