Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
twitter.com
twitter.com
"These new algorithms factor integers N ≈ 2^400 and N ≈ 2^800 using 7x10^10 and 4.3x10^12 arithmetic operations".
He does not specify how many it uses for 2^1024 or 2^2048. This is clearly nonlinear. Assume (nevertheless) that you multiply x100 every 400 binary digits, then for
2^2048, you get
(2048-800) equiv 1200/400 equiv 3, so you would need approx. 10^12*10^6 operations. Assuming you can do 10^6 ops , you need 10^12 seconds (like 30000 years).
BUT those are very very rough assumptions (an "arithmetic op" might probably take more than 1 microsec).
EDIT: sorry, this link is pretty interesting. Factor RSA-260, which only has 862 bits. Should be feasible in about 2 hours. The link: https://crypto.stackexchange.com/questions/88582/does-schnor...
EDIT2: sorry again: Schnorr is 78 years old. I am not gerontophobic (being 50 I am approaching that age) but: Atiyah claimed the Riemann Hypothesis, Hironaka has claimed full resolution of singularities in any characteristic... And I am speaking of Fields medalists.
So: you do really need peer-review for strong arguments.
function test(opp, n) {
const start = Date.now();
let i = 1;
if (opp === '*') {
let prod = 1;
while (i < n) {
i++;
prod *= i;
}
} else if (opp === '/') {
let quot = 100000000000000;
while (i < n) {
i++;
quot /= i;
}
} else if (opp === '+') {
let sum = 0;
while (i < n) {
i++;
sum += i;
}
} else if (opp == '-') {
let sum = 100000000000000;
while (i < n) {
i++;
sum -= i;
}
}
const end = Date.now();
console.log(`${n} ${opp} ops in ${end - start} ms`);
}Or, if we take a GPU, can we split a 4096 bit number into, say, 32-bit fragments, mass-multiply them, and combine the results faster than on a CPU? I suspect pretty common hardware can help speed such things up a lot; isn't crypto mining already using some of these approaches?
Naive multiplication is O(n^2) (where n = number of digits). The fastest algorithms seem to involve either cutting the numbers into pieces and doing multiplies, adds, shifts, and maybe subtracts on the pieces, and doing so recursively, which are O(n^[something slightly greater than 1]); or doing Fourier transforms, which apparently approach O(n log n). I don't know how easy it is to implement pieces of these more advanced approaches in hardware (especially if the size of the numbers isn't pre-chosen).
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
(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, but if the modulus has 2 prime factors p and q, then by the Chinese remainder theorem, the output will always be a quadratic residue modulo p and also a quadratic residue modulo q. In other words, the number of possible plaintexts is 4 times the number of possible ciphertexts, so decryption gives you back 4 possibilities and you need some convention that only one of those was a legal message.)
Unfortunately, this is a faster factoring method, so it also applies to the Rabin cryptosystem, the Blum-Blum-Shub pseudorandom number generator, and Rivest's time lock puzzles (repeated squaring modulo a large composite).
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.
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 <= B. Most people think A == B.
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.
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, how many people are going to visit amazon.com?
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.
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.
Yes, but large key spaces are really easy to have. The size of the key space doesn't cost you anything when you're encrypting or decrypting, but it costs the earth if you're trying to guess the key.
> and why algorithms needing offline brute force protection like password hashing algorithms artificially increase execution time and resource requirements
Ehhhh... this is more of a function of the fact that the password space is much smaller than it looks. Password cracking attempts generally aren't trying to exhaust the space. Instead, they're trying to guess the password based on the known properties of passwords. You start with common passwords and work your way down to iffy ones. You don't bother guessing rare passwords; there are too many of them.
Rainbow tables exist, but they have sharp length limits, precisely because of the explosion-of-the-key-space phenomenon.
This condition is satisfied by ~100% of all communications, including stuff like software downloads. (If I send you a file, then yes, any message is legal, but as soon as you try to do anything with it, you'll know whether the message was correct or not.)
[0] https://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_...
Nobody has read the manuscript though...
Theory is nice but if you can find the solution to something, just do it and then brag once it's done : )
Nobody ever did.
The other guy came back with a program that moved some of the random data into the metadata of the filesystem, in such a way so that the produced files did indeed become small enough.
Don't know if the other guy ever paid out.
I learned a little bit about information theory that day, and my sneakernet bandwidth was saturated for a while afterwards.
That's a cheap trick. You gotta send someone the file, otherwise there's not much of a point.
full story, for the perspective of the metadata guy is here
https://www.patrickcraig.co.uk/other/compression.htm
Excellent computer story, on a par with "We can't send email more than 500 miles" IMO.
People would be more convinced by presenting a factorization of a challenge RSA number
Expecting everybody to have mastery of every specialization that their work touches is toxic and unproductive. I look forward to a team of motivated undergrad number theorists to tear into this and hack up an implementation.
"This destroys the RSA cryptosystem" - Claus Peter Schnorr[0]
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 paper is quite complex and hard to follow - even for professional cryptographers.
Of course, I don't know what I'm talking about.
[0] Factorization had a history of speedups, both theoretical and practical. It doesn't really affect the practical security but always comes at a cost of either decreasing confidence or constantly increasing the keysize, so I won't be too surprised if Schnorr really has new insights to speed it up further. In fact, "We need something with a better security record than RSA" was one of the main arguments for transitioning to ECC - which has already completed at large on today's Internet, RSA is only used for digital signature, almost all key exchanges are ECC now. You can't decrypt post-2016 web traffic by breaking RSA.
The main claim of Schnorr's, as far as I can gather, is that for lattices where the shortest vector(s) are much shorter than the maximum shortest vector(s) for the same dimension, i.e., low-density lattices, those vectors can be found in heuristic polynomial time with his enumeration approach.
Now, low-density lattices are fairly common in cryptographic settings, where the solution, discoverable by finding shortest vectors, is unusually short/close relatively to what one would expect in a random lattice.
As such, if true, I would expect Schnorr's idea to lead to more breaks than just RSA. But I don't personally think it's true. At the same time, I'm not a lattice expert, so make of that what you will.
[1] https://www.math.uni-frankfurt.de/~dmst/research/papers/SVP2...
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.
Phew. I'm not alone.
I understood _some_ of the words used in the HN comments in this thread.
https://eprint.iacr.org/2021/232.pdf
Version history here: https://eprint.iacr.org/eprint-bin/versions.pl?entry=2021/23...
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".
- 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.
Schnorr's main novel claim here seems to be a speedup in finding the SVP and CVP in some cases (he explicitly acknowledges limitations.) A Proof Of Concept seems like it would be great to test for edge cases, and that's where I think the interesting bits are likely to be. Disclaimer: Not a mathematician or complexity theorist. Just here to learn, and glad to be corrected any time.
https://twitter.com/FredericJacobs/status/136717279911944601...