from Hacker News

Did Schnorr destroy RSA? Show me the factors

by sweis on 3/3/21, 8:38 PM with 207 comments

by tyingq on 3/3/21, 9:17 PM
Isn't it typical to release the paper first, for peer vetting, ahead of any actual working proof?
It seems like the only reason for the "put up or shut up" reactions is that "destroys RSA" comment in the submitted abstract...which isn't in the actual paper.
by paob on 3/4/21, 12:09 PM
Here we have Léo Ducas testing Schnorr's new method in Sage: https://github.com/lducas/SchnorrGate
Apparently, "[t]his suggest that the approach may be sensible, but that not all short vectors give rise to factoring relations, and that obtaining a sufficient success rate requires much larger lattice dimension than claimed in [Sch21]."
by NoKnowledge on 3/3/21, 9:34 PM
This take is rather naive. Those RSA factoring records were done by a large international team of researchers, using well established algorithms and decades of work on implementing those methods as fast as possible.
The blog post says the paper mentions 8.4e10 operations for factoring, but I can't find that number in the paper anywhere. The post then states: "The 800-bit claims would be 36 bits of work." I don't know what that means.
[edit]: the numbers are in the new version (https://eprint.iacr.org/2021/232). I was looking at the old version uploaded yesterday.
by chrisco255 on 3/3/21, 9:20 PM
For those of us less familiar with cryptography and RSA in general: what are the implications if RSA is broken? What are the mitigations that would need to occur in its place?
by abetusk on 3/3/21, 10:30 PM
OK, here is a brief overview for people:
To factor a number N (assumed to essentially be the product of two very large primes), find a 'short' lattice vector [0] using LLL [1] (and BKZ reduction? [2]) that finds many relations of the form:
```
    (u_i) = p_i,0 * p_{i,1} * ... * p_{i,n-1}
    (u_i - v_i * N) = q_{i,0} * q_{i,1} * ... * q_{i,n-1}
```
where p,q are small primes.
Numbers that have all their factors less than some prime, B, are said to be "B-smooth". In the above, both (u_i) and (u_i - v_i * N) are p_{i,n-1}-smooth and q_{i,n-1}-smooth, respectively.
Construct many u_i and (u_i - v_i * N), so much so that you can create a product of primes, r_i, of the form:
```
    r_0^{2 b_0} * r_1^{2 b_1} * ... * r_{n-1}^{2 b_{n-1}} = 1 mod N
```
where each b_i are integers.
Since all exponents (2b_i) are even, we have the potential to find the square root of 1 which has the potential to resolve to two different numbers since N is composite. One of those is the product of r_i^{b_i} and the other is -1. Since y^2 = 1 mod N, we get (y-1)(y+1) = 0 mod N. If (y-1) or (y+1) are not 0, then then must share a factor of N and we've successfully factored.
The trick is, of course, finding the smooth numbers. To do this, a lattice basis is made such that you find a short integer relation of the form
```
    a_0 ln(p_0) + a_1 ln(p_1) + ... + a_{n-1} ln(p_{n-1}) ~= ln(N)
```
where ~= means "approximately equal to".
u is chosen as the product of primes of all a_i > 0 and v is chosen to be the product of all primes where a_i < 0. The hope is that (u - v*N) is also p_{n-1}-smooth, which, as far as I understand, most of the math in the paper is trying to justify.
The main innovation here, as far as I can tell, is that Schnorr is fiddling with the 'weighting' of the main diagonal when constructing the lattice basis. I interpret this as basically trying to randomize the initial lattice basis so that the chances of getting a different integer relation (for eventual construction of u,v) is more probable.
I've been confused about this for over a decade as variants of this algorithm, and Schnorr's work in general, have been well published. For example, there's a paper from 2010 on "A Note on Integer Factorization Using Lattices" by Antonio Vera which discusses Schnorr's [3] construction.
Is Schnorr trying to shout louder so people will listen or is there something else fundamentally flawed with this type of algorithm?
Just a word of warning, LLL solves polynomial factorization in polynomial time (given a polynomial with integer coefficients, find it's factor polynomials also with integer coefficients) [4] and has been used to break other (now very old) cryptosystems [5]. If there's a candidate algorithm to solve integer factoring, lattice reduction (LLL, PSLQ, etc.) are it.
I know of fplll that's a stand alone (FOSS) implementation of LLL and some extensions (BKZ, etc.) [6].
[0] https://en.wikipedia.org/wiki/Lattice_reduction
[1] https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%...
[2] https://www.newton.ac.uk/files/seminar/20140509093009501-202...
[3] https://arxiv.org/pdf/1003.5461.pdf
[4] https://en.wikipedia.org/wiki/Factorization_of_polynomials#F...
[5] https://web.eecs.umich.edu/~cpeikert/lic13/lec05.pdf
[6] https://github.com/fplll/fplll
by hertzrat on 3/4/21, 1:22 AM
If someone wasn’t a cryptographer, but does occasional security tasks at work, what is the takeaway? RSA needs to be 4096 or higher now, or that similar techniques in the future might make RSA a bad choice altogether?
by tgsovlerkhgsel on 3/3/21, 9:29 PM
Devil's advocate: Posting the factors requires implementation work, then optimization, then a manageable but possibly still not trivial amount of resources and time - and likely a lot of trial and error. It is perfectly conceivable that a paper would be published before the implementation is actually better than a slower but heavily optimized approach. (I don't even try to understand the paper, but I've seen a mention that it's a storage tradeoff, which may make it a very different kind of optimization problem.)
Do we know that the paper is definitely from Schnorr? (Edit: The article claims its provenance is confirmed). The "destroys the RSA cryptosystem" claim is now part of the paper. While anyone can make mistakes, I would expect such claims to be at least somewhat carefully checked before releasing them.
Either way, I expect that we'll see either a retraction/correction or factors within weeks.
by hn_throwaway_99 on 3/3/21, 9:37 PM
This was my exact argument: https://news.ycombinator.com/item?id=26323951
Should be trivial to show a working proof on a smaller-than-usual RSA number if "this really destroys RSA".
by gojomo on 3/3/21, 9:50 PM
I can imagine a certain pure-theorist mindset being confident enough in their reasoning, but not yet their coding, to report this first. Or, strategically holding definitive proof back as a hammer to deploy once the doubters reveal themselves.
Why not let others do the rote reduction-to-practice?
Why not create an example where your theory was correct, & your reputation was on the line, that took a little while to resolve – but when it does, it does so definitively in your favor, so you are more trusted in future pre-definitive-verification pronouncements?
(I don't know enough about Schnorr-the-person to know if this fits his personality, but I can imagine such personalities.)
by dang on 3/3/21, 10:12 PM
This was heavily discussed yesterday. (Edit: this next bit was out of date:) It seems the provenance of the paper and the 'destroy' claim are unclear.
“This destroys the RSA cryptosystem” - https://news.ycombinator.com/item?id=26321962 - March 2021 (140 comments)
by unnouinceput on 3/4/21, 10:44 AM
An example, by hand, from the paper author, where he is using this algorithm to factor a number would be great. Even a small number that's easy to factor by brute force would be enough to actually proof that his claims are true. We'll do code implementation and run it against RSA challenge numbers, and see if this is a prank or the real deal.
by yipbub on 3/4/21, 11:51 AM
Crypto noob question: Wouldn't it be prudent to switch to something like ECDSA(heardsay that it is stronger) if there was even a hint that it was possible?
If a major government got wind that such work was going on, wouldn't it be prudent to publish before you are disappeared? I assume high-profile crypto research people are spied on.
by racecar789 on 3/3/21, 9:37 PM
I know a lot of programming languages, but I have never wrapped my head around math notation.
Question for someone who is familiar math notation...was the abstract of this article easy to understand?
For me, the abstract seems like code but no commentary explaining what each bloc does. But I could be mistaken.
by natch on 3/3/21, 9:14 PM
> the provenance of the paper has been confirmed: it is indeed Schnorr.
What I read is that someone contacted Schnorr over email to get this confirmation.
I’m not saying the confirmation is wrong. And I’m not saying email cannot convey information.
by tandr on 3/3/21, 9:25 PM
What does "36 bits of work" mean, sorry?
by sodality2 on 3/3/21, 9:15 PM
Factors or gtfo
by shashasha2 on 3/4/21, 9:46 AM
Is prime factorisation used in SHA256 ? Would I be able to solo mine from my CPU again ?
by jagger27 on 3/3/21, 9:14 PM
That's really all there is to it. Pudding, proof, etc.
by TacticalCoder on 3/3/21, 10:44 PM
I am no cryptographer. I did implement, from the paper, Yao's "socialist millionaire" cryptographic protocol but... It was only a few lines of code and a very simple (to understand, not to come up with) paper.
Now I just looked at that Schnorr paper and, well, I can tell you that I'm not going to be the one implementing it : (
by senderista on 3/4/21, 4:30 AM
I wonder if Schnorr is going senile like Atiyah.
by anonisko on 3/3/21, 9:22 PM
Reminiscent of Craig Wright's claim to be Satoshi.
It doesn't matter what you claim with words if you can't back it up with cryptographic evidence.
Shut up and prove you've done (or can do) the work.
by bhouston on 3/3/21, 10:52 PM
The first thing this will be used for is stealing Bitcoin and other cryptocurrency I predict. So watch out for your wallets.
by jMyles on 3/3/21, 9:30 PM
I'm skeptical. The paper is too tough for me to digest without spending days/weeks/lifetimes focusing on it (and there are many who can do it much faster obviously). But I think that if RSA is materially broken, we'll know it from movements in the ground (eg, sudden mysterious forged signatures) by the time a paper is published.
I don't think that such a secret can be kept for more than a few minutes with immediately proceeding to runtime weaponization.