Would someone competent in cryptography please explain this to a “regular” programmer?
Yeah, if this really is fast prime factoring, we're all in a lot of trouble.
Semi-prime factoring. Also we have elliptic curves.
“This destroys the RSA cryptosystem”
41–50 of 152 posts
Re: “This destroys the RSA cryptosystem”
#42The 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.
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...
Re: “This destroys the RSA cryptosystem”
#43Earlier quoted context omitted.
Yeah, if this really is fast prime factoring, we're all in a lot of trouble.
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.
Re: “This destroys the RSA cryptosystem”
#44Can 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?
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 whic…
I see, makes sense, thanks.
Re: “This destroys the RSA cryptosystem”
#45Earlier quoted context omitted.
Yeah, if this really is fast prime factoring, we're all in a lot of trouble.
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.
RSA has always been a lot weaker than it seems at first... I mean, people have been moving from 1024 to 2048 bit primes... The biggest number I could conceivably brute force is probably about 2^50. Maybe 2^60 with a big budget, or 2^65 with a team of ASIC designers. The mere fact that 2^1024 is considered risky tells you how far from ideal RSA is!!
Re: “This destroys the RSA cryptosystem”
#46Re: “This destroys the RSA cryptosystem”
#47The 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...
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.
he spells it like that on his published research, though. See here:
https://link.springer.com/chapter/10.1007/978-3-642-42001-6_...
Re: “This destroys the RSA cryptosystem”
#48cstheory stackexchange discussion: https://cstheory.stackexchange.com/questions/1300/integer-fa...
Re: “This destroys the RSA cryptosystem”
#49Earlier quoted context omitted.
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.
he spells it like that on his published research, though. See here: https://link.springer.com/chapter/10.1007/978-3-642-42001-6_...
yep, found that too. disregard that then, just seemed odd on first glance.
Re: “This destroys the RSA cryptosystem”
#50Does this reference the breakthrough that the UKs GCHQ had against RSA supposedly for several decades??