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.
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.
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.
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.
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.
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.
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.)
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.
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.
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...
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...
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?
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.
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?
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.
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.
[+] [-] Centigonal|5 years ago|reply
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...
[+] [-] yesenadam|5 years ago|reply
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
[+] [-] tveita|5 years ago|reply
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
[+] [-] detaro|5 years ago|reply
He also apparently misspelled(?) his own name. It's "Claus-Peter" (also on other publications), not "Claus Peter". agreed, seems odd.
[+] [-] unknown|5 years ago|reply
[deleted]
[+] [-] cnlp100|5 years ago|reply
[+] [-] Rounin|5 years ago|reply
https://twitter.com/ManishEarth/status/1366906561486983171 https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9...
[+] [-] hyper_reality|5 years ago|reply
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.
[+] [-] balupton|5 years ago|reply
[+] [-] 7800|5 years ago|reply
Seems a bit like the way an old pirate might speak, or at least someone hundreds of years old.
[+] [-] bjeds|5 years ago|reply
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.
[+] [-] marktangotango|5 years ago|reply
"Factoring Integers by CVP and SVP Algorithms"
[+] [-] OJFord|5 years ago|reply
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.
[+] [-] baby|5 years ago|reply
[+] [-] elmo2you|5 years ago|reply
How does it destroy RSA? Under what conditions? That claim sounds rather broad and definitely bold, to say the least.
[+] [-] gpm|5 years ago|reply
^ Date on the pdf
[+] [-] jeofken|5 years ago|reply
[+] [-] dfabulich|5 years ago|reply
(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.)
[+] [-] pkulak|5 years ago|reply
[+] [-] lquist|5 years ago|reply
[+] [-] nanis|5 years ago|reply
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|reply
* 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.
[+] [-] muricula|5 years ago|reply
[+] [-] eternalny1|5 years ago|reply
The linked one is: received 1 Mar 2021
The PDF is: work in progress 31.10.2019
[+] [-] randtrain34|5 years ago|reply
[+] [-] paconbork|5 years ago|reply
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
[+] [-] munchbunny|5 years ago|reply
I don't know what that means for this paper, just happened to have those two key lengths off the top of my head.
[+] [-] kaishiro|5 years ago|reply
[+] [-] strictfp|5 years ago|reply
[+] [-] nanis|5 years ago|reply
That discussion is from 2010. The download link for the paper does not seem to work.
[+] [-] azornathogron|5 years ago|reply
[+] [-] cameronperot|5 years ago|reply
[1] https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9...
[+] [-] gnulinux|5 years ago|reply
[+] [-] dleslie|5 years ago|reply
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.
[+] [-] BluSyn|5 years ago|reply
[+] [-] balupton|5 years ago|reply
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|reply
[+] [-] ncann|5 years ago|reply
[+] [-] ramboldio|5 years ago|reply
[+] [-] thomasahle|5 years ago|reply
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.
[+] [-] terramex|5 years ago|reply
[+] [-] carlosfvp|5 years ago|reply
[+] [-] olliej|5 years ago|reply
[+] [-] intunderflow|5 years ago|reply
[+] [-] unknown|5 years ago|reply
[deleted]
[+] [-] karaterobot|5 years ago|reply
https://eprint.iacr.org/2021/232.pdf