Ah. "In most cases, automatic endorsement is given to authors from known academic institutions and research facilities." So the ancestor's "Anyone can upload those." should have been "Anyone with an academic email address can upload those."
For whatever it's worth, the preprint in question was not on arXiv but on https://eprint.iacr.org/index.html which looks like it's even more laid back regarding submissions.
That isn't as reassuring as it seems. It may be that Schnorr could "destroy RSA", but that the computing requirements are still beyond what a researcher could have access to, but are within the abilities of a large corporation or nation-state. An example is SHA-1. We have known it was broken for some time, but it took Google's massive compute power to actually produce a real world collision.
You are correct, but I think it’s still a valid point. The way to demonstrate to the world that it is broken would have been to break it, and if you even skim over his bonafides it seems like something he is 1) an expert in and 2) would have the resources to demonstrate, even if not programmed by himself (grad students, perhaps?).
He’s also older and retired and could simply have the attitude of “F it, I’ll leave this here, mic drop”, so who the hell really knows.
He could find any number of grad students who would be happy to code up his algorithm for him, so they can be co-authors on the paper that "destroyed RSA".
Or any number of hackers who would be happy to do it so they could be the first to break into people's bank accounts. If RSA were broken as a result of a public announcement with no warning, there would be no doubt in anyone's mind because chaos would ensue in very short order.
I’m not claiming anything about the correctness of this proof, but if it isn’t correct, writing a program that implements the algorithm would be a waste of time.
So, if the proof is hard to follow and describes a complex algorithm, grad students who don’t fully grok the supposed proof might not be that happy to work on that program. They might end up looking for a nonexistent bug in their program for months.
I also think it’s illustrative to mention the Grothendieck prime (https://en.wikipedia.org/wiki/57_(number)) here, as an example of how little concern some mathematicians have for applications of their results. That _could_ explain why Schnorr didn’t bother to even ask his students to write that program.
> Instead of performing 96 lattice reductions with a near guarantee of recovering 96 smooth values, a very rough approximation with the correct determinant indicates that we would need to perform 2^200 reductions of enormous lattices to find enough smooth values.
> This is well beyond any plausible computation. It strongly suggests that this particular approach does not scale to the point of practically breaking RSA.
> However, there are many open questions. Would a different lattice construction avoid this problem? Can the bound be established in another way? What are the concrete performance numbers and asymptotic complexity?
"Schnorr has been making presentations on his concept since at least 2009. In my personal opinion, 11+ years is enough time for a small group to make some kind of significant demonstration software, if people believed that the idea is likely to work.
Because this proposed factoring technique has been public for more than a decade, both specialists in lattice algorithms, and other mathematicians who focus on factoring algorithms in general, have had plenty of opportunity to study Schnorr’s ideas. I don’t see evidence that even one mathematician with relevant expertise has yet been persuaded."
I don't believe it. The state of the art in quantum computing is far from it. In fact, we are not even sure if it is possible at all due to the extremely low temperatures required for a significant number of entangled qubits.
In general, secret tech is only more advanced than what is available in the open when it has no real application outside defense. But a lot of people want quantum computers more simple than the ones that can crack RSA, and they don't have them. So I find it unlikely that any nation state has a quantum computer able to break current crypto.
The focus on post-quantum cryptography is mostly preventive.
NSA used to push pretty hard for moving to elliptic curve from RSA. There was some speculation they already knew better factoring methods that worked for breaking RSA.
But then the Dual_EC_DRBG backdoor came to light, so maybe they were just pushing elliptic curve to get their backdoors out there.
These days NSA pushes for post-quantum crypto, but it's not practical yet.
> NSA used to push pretty hard for moving to elliptic curve from RSA. There was some speculation they already knew better factoring methods that worked for breaking RSA.
Just to add a bit more detail...
NSA was pushing EC pretty hard for a bit. Then, after a while, they switched gears and said (and I'm paraphrasing here, obviously), "Actually, don't worry about it. If you've already switched to EC, that's fine, just stick with it. If you're still on RSA, though, just stick with that. There's no need to switch, both are fine (for the time being)."
So who knows WTF they were thinking. Unfortunately, it's impossible to get any real "signal" from their statements since they can no longer be trusted. They could be legitimately looking out for our best interests or they could be trying to get everyone to use less secure algorithms -- and we have no way to know which it is!
(Personally, I've just carried on normally and pretended like they never said anything at all).
I still need to be convinced that more than 2048 bit RSA keys are required. There seems to be no rational reason to use longer keys.
There have been no real breakthroughs in breaking RSA for 15-20 years. So if you were playing the odds you would actually prefer RSA over systems invented more recently.
You should avoid attempting RSA key exchange because it's too hard to safely do this correctly and even if you do that loses forward secrecy in protocols where that means something.
If you're just doing signatures (so e.g. modern TLS or SSH) then any of the elliptic curve signature schemes are nicer than RSA. However, whether that's practical for you to rely on will depend on whether it's important to let random peers from the public Internet connect with whatever mouldy garbage they're running which may only do RSA.
35 comments
[ 3.2 ms ] story [ 82.5 ms ] threadWeird!
Getting endorsement seems a relatively low bar, but it's still a bar.
> if Schnorr could “destroy RSA”, he would have destroyed one of the RSA Challenge problems to prove it. He did not.
[0] https://www.schneier.com/blog/archives/2021/03/no-rsa-is-not...
He’s also older and retired and could simply have the attitude of “F it, I’ll leave this here, mic drop”, so who the hell really knows.
So, if the proof is hard to follow and describes a complex algorithm, grad students who don’t fully grok the supposed proof might not be that happy to work on that program. They might end up looking for a nonexistent bug in their program for months.
I also think it’s illustrative to mention the Grothendieck prime (https://en.wikipedia.org/wiki/57_(number)) here, as an example of how little concern some mathematicians have for applications of their results. That _could_ explain why Schnorr didn’t bother to even ask his students to write that program.
> This is well beyond any plausible computation. It strongly suggests that this particular approach does not scale to the point of practically breaking RSA.
> However, there are many open questions. Would a different lattice construction avoid this problem? Can the bound be established in another way? What are the concrete performance numbers and asymptotic complexity?
- Keegan Ryan
https://twitter.com/inf_0_/status/1367377462582079489
> Out of 1000 trials, no factoring relations was found.
- Léo Ducas
https://twitter.com/DucasLeo/status/1367367057055109125
Because this proposed factoring technique has been public for more than a decade, both specialists in lattice algorithms, and other mathematicians who focus on factoring algorithms in general, have had plenty of opportunity to study Schnorr’s ideas. I don’t see evidence that even one mathematician with relevant expertise has yet been persuaded."
It's been out there for a long time and...nada.
[0] https://en.wikipedia.org/wiki/Shor%27s_algorithm
In general, secret tech is only more advanced than what is available in the open when it has no real application outside defense. But a lot of people want quantum computers more simple than the ones that can crack RSA, and they don't have them. So I find it unlikely that any nation state has a quantum computer able to break current crypto.
The focus on post-quantum cryptography is mostly preventive.
But then the Dual_EC_DRBG backdoor came to light, so maybe they were just pushing elliptic curve to get their backdoors out there.
These days NSA pushes for post-quantum crypto, but it's not practical yet.
Just to add a bit more detail...
NSA was pushing EC pretty hard for a bit. Then, after a while, they switched gears and said (and I'm paraphrasing here, obviously), "Actually, don't worry about it. If you've already switched to EC, that's fine, just stick with it. If you're still on RSA, though, just stick with that. There's no need to switch, both are fine (for the time being)."
So who knows WTF they were thinking. Unfortunately, it's impossible to get any real "signal" from their statements since they can no longer be trusted. They could be legitimately looking out for our best interests or they could be trying to get everyone to use less secure algorithms -- and we have no way to know which it is!
(Personally, I've just carried on normally and pretended like they never said anything at all).
There have been no real breakthroughs in breaking RSA for 15-20 years. So if you were playing the odds you would actually prefer RSA over systems invented more recently.
If you're just doing signatures (so e.g. modern TLS or SSH) then any of the elliptic curve signature schemes are nicer than RSA. However, whether that's practical for you to rely on will depend on whether it's important to let random peers from the public Internet connect with whatever mouldy garbage they're running which may only do RSA.
Amusingly, at the bottom of the page, it states “Proudly made without PHP, Java, Perl, MySQL and Postgres”.