Would love a "what's going on here for dummies" summary if possible. From what I gather someone is claiming they broke RSA encryption?
Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
21–30 of 81 posts
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#22The two links to the paper...had to navigate twitter a bit to find them: https://eprint.iacr.org/2021/232.pdf (older) https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9... (newer) Edit: And the abstract with the "destroyes the RSA..." blurb: https://eprint.iacr.org/2021/232
Quick summary, he's found a faster way to factor numbers. He hasn't found a way to break RSA that isn't equivalent to factoring the modulus. (As far as I know, it's still just a long-standing conjecture that breaking RSA is as difficult as factoring. RSA always uses odd exponents. The Rabin cryptosystem is similar to RSA except that it always uses 2 as the public exponent and is provably as difficult as factoring, bu…
>> As far as I know, it's still just a long-standing conjecture that breaking RSA is as difficult as factoring.
No, that's not a conjecture. If you factor the modulus you can directly calculate the private key from the public one.
Edit: oh maybe you mean that it's possible to break RSA faster without factoring... Its been too long since I looked at that.
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#23If 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…
> Of course, I don't know what I'm talking about.
I would honestly have no way of knowing either way. It is always fun to get a peek into people working out ideas in fields I have no experience in.
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#24It 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...
Agreed. Typical mathematician mentality
People would be more convinced by presenting a factorization of a challenge RSA number
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#25Earlier quoted context omitted.
Quick summary, he's found a faster way to factor numbers. He hasn't found a way to break RSA that isn't equivalent to factoring the modulus. (As far as I know, it's still just a long-standing conjecture that breaking RSA is as difficult as factoring. RSA always uses odd exponents. The Rabin cryptosystem is similar to RSA except that it always uses 2 as the public exponent and is provably as difficult as factoring, bu…
>> As far as I know, it's still just a long-standing conjecture that breaking RSA is as difficult as factoring. No, that's not a conjecture. If you factor the modulus you can directly calculate the private key from the public one. Edit: oh maybe you mean that it's possible to break RSA faster without factoring... Its been too long since I looked at that.
> No, that's not a conjecture. If you factor the modulus you can directly calculate the private key from the public one.
You have misread my post. The conjecture is that the RSA problem is as difficult as the factoring problem. In other words, it's possible that solving the RSA problem isn't as difficult as the factoring problem (but most people doubt it). A This is the inverse of your statement. Factoring breaking RSA doesn't tell us if there's a non-factoring solution to the RSA problem. Everyone knows breaking RSA is no more difficult than factoring, but it may be easier than factoring.
A break in the Rabin cryptosystem would provably break RSA, but it's not necessarily true that a break in RSA would break the Rabin cryptosystem.
Edit: Paragraph 4 of https://en.wikipedia.org/wiki/RSA_problem at least believes it's still a conjecture that RSA is as difficult as the factoring problem.
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#26*according to someone on twitter.
If Frederic Jacobs says he communicated with Schnorr, then that's what happened.
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#27It 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...
From the look of it, he hasn't really claimed this yet in public. This link is someone on twitter saying he did in private. I would just wait
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#28I wrote my thesis on post-quantum public key cryptosystems, though I'm not currently a practitioner and haven't been academically active since ~2017 or so. With those provisos in mind, I'll try to give the summary as I see it. As a basic tl;dr I'm skeptical of the paper. Crypto-twitter is lit up about this right now and as far as I can tell, harbors the same skepticism.
- For context and background: yes, there are well-established links between factoring problems and lattice problems. These links have been known from at least the early 90s. There are many complexity theoretic reductions between specific factoring problems and specific lattice problems, and the approximate variants of the latter. There hasn't been an arbitrary reduction yet, it's mostly on a problem by problem basis.
- That first bullet point means that this research is at least structurally built on, and engages with, prior work in the academic community. Schnorr in particular has been pursuing this since the 90s. Schnorr is an accomplished and established cryptographer.
- I consider the context of that second bullet point unfortunate, because it means the research gets outsized attention even though it is otherwise, as of now, unsubstantiated. It gives the paper a lot more charity than it would ordinarily receive.
- Critically: Schnorr has not empirically demonstrated a break in RSA. He has demonstrated - in theory - faster factoring methods using SVP and CVP solving techniques which rely on a reduction of the factoring problem.
- The paper may not be worthless even if it doesn't break RSA. If he has indeed found a polynomial time way to solve a subset of lattice (and factoring) problems, that will be impressive. I'll have to read the paper a few more times to come to a belief on this point though.
Many comparisons are being drawn online between Schnorr and Atiyah, because the latter kept insisting he found a proof of the Riemann Hypothesis towards the end of his life. It would be sad if this is the case for Schnorr, but it's personally what I believe at this time pending an empirical demonstration of his work and/or critical substantiation from the rest of the academic community. I'm skeptical of this result the same way I'm skeptical when highly established mathematicians publish purported proofs of long standing open problems.
Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#29Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
#30What if it's actually someone else that discovered this and is just publicly posting and acting as Schnorr, in an attempt to prove their point? ;)