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.
https://twitter.com/robinhouston/status/1169877007045296128
Its easier to drum up support for your paper when you have a quick way to prove to the community of mathematicians that your results are golden.
EDIT: The original webpage: http://math.mit.edu/~drew/sumsofcubes.html
As you can see, the sum-of-cubes announcements are very terse. Ultimately pointing to the following link: https://share.cocalc.com/share/900eec7e-0710-4e2f-a03a-dba01...
That kind of website / tweet is a "drop the mic" moment. It really makes people pay attention.
In particular, I think the right process would be:
1. Give some brief description of the result (eg factoring numbers in O(...)), and some proof (eg a factorisation of the next rsa semiprime, possibly more) that convinces people that your claims are true
2. Wait a while for people to have the chance to not be burned
3. Publish the paper
Instead, the authors seem to be going for:
1. Publish the paper with a provocative abstract.
2. Wait to see who implements the algorithm first.
It doesn’t seem the best idea to me, but what do I know?
As it is, if the algorithm presented is valid then this potentially compromises currently operating systems.
There are so many devices and pieces of software that are stuck on RSA, a headsup of say 5 years would still result in a clossal mess; may as well have the mess now.
I think it is - https://eprint.iacr.org/2021/232.pdf
The latter is much more important.
For an algorithm, asking for results is not that weird. It certainly fits within the purview of a paper. Moreover, it would be really strong evidence for the claims made in the paper. It is much easier to check than the proofs.
I wouldn't be surprised if a demonstration that pushes the current publicly known record for largest factored RSA modulus costs hundreds of thousands or millions of dollars even with this new algorithm, and the algorithm is also slower than other methods for, say 384-bit RSA.
It may be difficult even for Peter Schnorr to get that kind of budget for a demonstration before his paper gets traction.
I believe that this breakthrough could be quite a bit bigger because it's changing the costs from exponential to polynomial and so speedup is likely a much bigger change.
That's for previous algorithms, not the one described in the paper.
Also, without that sentence nobody would be trying to read the paper, so props to Schnorr who understands how to create the buzz :P
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]."
Yes, claiming that "this breaks RSA" is bold, but this implementation shows that there is some advance in doing so in the paper.
Therefore signaling that this is a "scandal" via the postfix "gate" seems just inappropriate.
Apart from that kudos for the implementation to Ducas!
Calling it the "Schnorr attack" would imply that the outcome of it is still uncertain. And it also would sound way cooler ;)
Just to make sure you get Ducas's main argument, I quote him here again: "Personal study (unfortunately, never written down cleanly) of this approach suggested me that this approach requires solving SVP in dimensions beyond reasonable, leading to a factorization algorithm much slower than the state of the art. My impression is that this is the consensus among experts having spent some time on it as well."
So it seems like the conclusion is clear-cut contrary to what you were suggesting.
Also wouldn't the name "Schnorr attack" lead to people thinking of attacks on Schnorr signatures instead?
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.
From the article: "Schnorr’s paper claims to factor ... 800-bit moduli in 8.4·10¹⁰ operations"
2^36 ~= 8.4·10¹⁰, so I guess "36 bits of work" means 2^36 operations. Analogous to how a password with 36 bits of entropy would require 2^36 guesses. My first time encountering the phrase "bits of work" as well, though.
>Our accelerated strongprimal-dual reduction of [GN08] factors integers N≈2^400 and N≈2^800 by 4.2·10^9 and 8.4·10^10 arithmetic operations.
It took me 3.3 years of actual computation time to do about 2^46 multiplication+modulo of two 2048 bit numbers on a Core i7. 2^36 of 2048 bit numbers should be doable in a day on an eight years old CPU.
P.S: that was on a single core, for the problem I solved was explicitly created as to not be parallelizable.
The public web and code signing PKIs collapse overnight. Most certificate authorities use RSA-2048 either for the roots or intermediates. The HN site not only uses a RSA-2048 key in its own certificate, the CA issuing that certificate and the root CA issuing the intermediate also do.
All data transmitted without forward secrecy on most web sites is compromised. Most websites nowadays use forward secrecy and/or ECDSA, but data sent years ago may still be of value (e.g. passwords) and become decryptable now.
Any data (e.g. backups, past e-mails) encrypted using RSA keys is at risk.
Any authentication system relying on RSA keys has a problem. This can include systems like smartcards or HSMs that are hard to update, software or firmware updates, etc. Banking too.
Edit to add - if RSA-1024 is practically breakable but RSA-2048 is not: some systems that relied on RSA-1024 have a problem. These should be rare, but sometimes legacy doesn't get updated until it becomes an absolute emergency. Everyone realizes that RSA-2048 is only a matter of time, that time is running out quicker than expected, and starts upgrading to ECDSA with more urgency. This will likely take a long time due to legacy hardware.
Forward secrecy does not protect against broken cryptography, so this is more about what methods were used and how much an new technique like this affects them.
It's a continuum from "impossible to do with all the time and energy of the universe and the most advanced computers we have" to "my commodity hardware can crack it in a few minutes".
The same goes for fears of quantum computing breaking current cryptography. It goes from effectively impossible to "yeah, we could break it with a few years of constant computation, which is plenty of time to switch to quantum resistant schemes".
If there were, for example, a way to glean a private key without factoring the modulus, I think we'd all agree that this amounts to "breaking" the system insofar as that it changes the applicability of the hardness assumption.
On the other hand, simply achieving a faster way to factor the modulus is, at best, part of a continuum as you say.
That's not how you treat broken cryptography. If your data is already collected and stored encrypted by a third party which still holds value after several years, you're already in bad shape.
2. Major issue is going to be webpki and replaying govt captured encrypted communications.
3. There are a lot of abandoned servers out there that use RSA. There is a lot of code signing that uses RSA. There is just a lot of identity proven on the web that uses RSA to prove the identity. It's going to be a clusterfuck of identity. Again, assuming the paper means RSA is just completely broken.
Only if you somehow "know" quantum computing is ever going to be practically realized. It may never be.
1024-bit and higher RSA is still unfactorable, so I don't think anyone will be attacking RSA directly any time soon.
Also, that whole thing about lots of computer encryption tech suddenly being effectively insecure.
But then there's that line: "This destroys the RSA cryptosystem" in the abstract of the paper.
The mitigation would be to move to experimental post-quantum crypto systems immediately (quantum computers have all the fuss because they can break rsa).
This is basically an unbelievable result. Without actually providing some factored numbers i am very doubtful.
[I have not read paper]
Edit: as pointed out below, i may have gotten overexcited. Still an incredible result if true.
"A bit"? A lot more than a bit. A world.
And on the surface, since it appears to be a factoring system, rather than a general purpose discrete log solver, the consequences, while incredible, are far more limited than the picture you paint. If this is even true; a matter over which I'm skeptical.
It does not extend to breaking eliptic-curve cryptography, for the same reason that the Quadratic Sieve does not extend to eliptic-curve crypto: the underling math problem is different (factorisation vs discrete logarithm).
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}
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
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)
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...
https://twitter.com/SchmiegSophie/status/1367197172664389635
They mostly mirror the article this post is under, namely "show me the factors". Schnorr claims spectacular run times but it isn't clear he provides actual data from runs he's done. Schnorr also doesn't discuss complexity considerations in the detail they would deserve while focusing on basic details that I suppose wouldn't show up in a paper like this normally.
In the paper Schnorr suggests that this algorithm factors 800-bit integers in ~10^11 operations [36 bits], whereas the Number Field Sieve uses ~10^23 [76 bits]. Does that 76-bit figure represent the current state of the art, more or less?
Also, since the paper talks only in terms of specific sizes of integers, I assume there's no claimed asymptotic speedup over existing methods?
The runtime depends on the frequency of primes, which is how you know you can run the algorithm and have a good chance of finding a "B-smooth" number. So that frequency might decrease too fast as to make it not a polynomial time or quasi-polynomial time algorithm.
In terms of my own opinion, in general practical large exponent runtime algorithms have a way of becoming increasingly more efficient so this isn't usually a big blocking point, especially not for long. For example the interior point method eventually lent itself to faster implementations. In terms of frequency of primes, I suspect this is also not a big slowdown factor.
Anyway, like I said, I've been confused about this point for a long time. It seems like this method is providing effectively a polynomial time algorithm for integer factoring. I read this paper and others by Schnorr as "this is 'efficient' in the theoretical sense but the polynomial exponent is so large as to make it computationally infeasible right now" but then I don't know why this hasn't been bigger news. Maybe because the algorithm has a randomness component to it?
I don't know. If anyone is wiser than me, I would appreciate some enlightenment.
But there’s no real current takeaway until we know if this approach works, and if so how extensible it is to RSA, especially 2048 bit RSA.
If you are going with it anyway, yeah, 4k bits is a safe choice for making it reasonably secure right now (2k being a bare minimum), but remember, attacks always get better, never worse, and RSA has a fair share of possible attacks.
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.
Should be trivial to show a working proof on a smaller-than-usual RSA number if "this really destroys RSA".
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.)
“This destroys the RSA cryptosystem” - https://news.ycombinator.com/item?id=26321962 - March 2021 (140 comments)
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.
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.
The notation is easy to understand (and as far as mathematical notation goes, really quite tame). I don't know what a nearly shortest vector of a lattice is in this context, but I do understand everything else. Note that means I have no idea how the actual method works, but I can understand what's being claimed.
You can have a "good basis" where the norms for b are low, or an equivalent "bad basis" with the same lattice points but with high norms. That's one hard problem (lattice reduction), but there are polynomial-time approximations.
The shortest vector problem, iirc, is to find the vector with the smallest norm in the best possible basis of that lattice.
You are mistaken. (Pretty much) all of mathematics is written as natural language, and those symbols are just abbreviations for stuff that could also be written as words. If I read those sentences out loud, another could write them back down and arrive at something that looks the same.
That's why all of mathematical notation is embedded in sentences - they are part of the sentence and can be read as such.
Further that is really basic notation a first semester student of any STEM discipline should be able to read, though I wouldn't expect them to know what a lattice and some of the other terminology is.
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.
You seem to mean something different from what your words say...
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 : (
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.
More drawing attention to the wider theme that we generally should not take people at their word when we have the option to demand proof of work that can't be faked or mistaken.
Don't trust. Verify.
I don't know why people don't bring this up more often. It will likely happen long before quantum computers make it possible.
I don't think that such a secret can be kept for more than a few minutes with immediately proceeding to runtime weaponization.