It seems a wrong version was uploaded.
https://twitter.com/FredericJacobs/status/136717279911944601...
Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
41–50 of 81 posts
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#42Earlier quoted context omitted.
Seems like not a fault of the construction of RSA or anything else that relies on the cost of factoring, but a fault of appropriately anticipating the costs to break it. Useable quantum will also make crypto security more expensive and complicated. Another thing that often bothers me are claims and emphasis of how fast constructions are. This just makes it easier to brute force.
> Another thing that often bothers me are claims and emphasis of how fast constructions are. This just makes it easier to brute force. People generally talk about speed of encryption and decryption. You're complaining about time for bruit-force attacks. In general, there's not a linear relation between the two, and the time for initial TLS session setup matters. If it takes a year to hit amazon.com for the first time…
> People generally talk about speed of encryption and decryption. You're complaining about time for bruit-force attacks.
If it takes me k time to decrypt something where there are N key variations and where I can run p attempts in parallel, the maximum runtime for a brute force attack is k*N/p. Perfectly linear relationship.
This is why we want large key spaces, and why algorithms needing offline brute force protection like password hashing algorithms artificially increase execution time and resource requirements to very large numbers.
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#43Without experimental data to back it up (e.g. implementation and benchmarks), I'd consider this claim veeeery dubious - regardless of who it came from. Extraordinary claims need extraordinary evidence, and in this case it would be easy to provide such evidence - by cracking appropriately-sized challenge primes in a transparent way that can be independently verified. On the other hand, the theoretical approach in the…
There are some approaches that seem difficult to implement at first view, but that can be improved when more people work on the difficult pieces. The most important thing in a paper like this is the general strategy. Even if there are small issues or if the implementation is too complex, if the general ideas are right we can find a better way to solve these problems over time.
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#44It doesn't destroy it...at best it weakens the lower RSA bit keys. If it destroys it...why not prove it with a PoC on one of the RSA numbers that hasn't been factored yet. RSA-260 is still open...
On one hand I am skeptical about strong claims especially in the early stage of the claim. On the other hand Schnorr is the person claiming it and no one has refuted it yet. I wonder how long until we will know for certain.
Hironaka has claimed to have a proof of reduction of singularities in positive characteristic for years (he got the Fields Medal for the same result in characteristic 0).
Nobody has read the manuscript though...
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#45Earlier quoted context omitted.
> Another thing that often bothers me are claims and emphasis of how fast constructions are. This just makes it easier to brute force. People generally talk about speed of encryption and decryption. You're complaining about time for bruit-force attacks. In general, there's not a linear relation between the two, and the time for initial TLS session setup matters. If it takes a year to hit amazon.com for the first time…
> People generally talk about speed of encryption and decryption. You're complaining about time for bruit-force attacks. If it takes me k time to decrypt something where there are N key variations and where I can run p attempts in parallel, the maximum runtime for a brute force attack is k*N/p. Perfectly linear relationship. This is why we want large key spaces, and why algorithms needing offline brute force protecti…
> This is why we want large key spaces,
This is a subset of what I'm talking about. Encryption/decryption times aren't linear with key space sizes. Force the number of required parallel instances to exceed the number of atoms on Earth, and bruit force time rapidly diverges from being linear with encryption/decryption time.
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#46[deleted]
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#47Would love a "what's going on here for dummies" summary if possible. From what I gather someone is claiming they broke RSA encryption?
1. Claus-Peter Schnorr, a well-established and reputable cryptographer, publishes a paper and claims he found a new algorithm for integer factorization, which is faster than the best known algorithm today (Number Field Sieve).
2. If it's all the paper says, it probably won't attract that much attention, at best it leads to a new wave of RSA keysize upgrade (or transition to ECC). But today, this paper appeared on the Cryptology ePrint Archive, and its abstract reads "This destroys the RSA cryptosystem", the use of strong language is extraordinary, a reader may interpret it as "the speedup is significant and all RSA keys can be broken." Researchers usually don't make such claims.
3. Meanwhile, it's also very suspicious for two reasons. First, this claim didn't appear in the actual paper, only the ePrint Archive web page, and it also includes an embarrassing typo. Also, the submitted paper wasn't even the latest version, which is available at Schnorr's web page, but an old version from 2019. Many people suspected that the paper was submitted by someone else, who happened to see an earlier version on the web and got too excited about it, and added the "destroys RSA" claim.
4. But now, personal communication with Schnorr confirmed the paper was indeed submitted by him, and he indeed makes the "destroys RSA" claim. Schnorr also said he uploaded the wrong file.
5. About 10 minutes ago, an updated preprint was published, that includes the sentence, "This destroys the RSA cryptosystem".
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#48About 10 minutes ago an updated preprint was published with a much more succinct and understandable abstract, that includes the sentence, "This destroys the RSA cryptosystem".
https://eprint.iacr.org/2021/232.pdf
Version history here: https://eprint.iacr.org/eprint-bin/versions.pl?entry=2021/23...
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#49If my understanding is correct, Schnorr converts the integer factorization problem to lattice problems: SVP and CVP. Then he claims he had an efficient algorithm to solve this particular instance of SVP and CVP, thus RSA is destroyed. But, the hardness assumption of SVP and CVP in general is the very foundation that another branch of public-key cryptosystems - lattice-based cryptography - is built upon. So, if Schnor…
I noticed HN user fractionalhare has made a comprehensive reply to my questions, but it wasn't posted as a reply to me, so now it has fallen to the bottom of the page. You can see it here: https://news.ycombinator.com/item?id=26331747
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#50Earlier quoted context omitted.
If Frederic Jacobs says he communicated with Schnorr, then that's what happened.
If Frederic Jacobs says he communicated with Schnorr, he thinks he communicated with Schnorr. It's possible that someone is impersonating Schnorr.
If only there was some kind of way of proving who you were... possibly using public key cryptography? ;)