No, RSA Is Not Broken
schneier.com
schneier.com
> 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
> Out of 1000 trials, no factoring relations was found.
- Léo Ducas
> 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.
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.
Amusingly, at the bottom of the page, it states “Proudly made without PHP, Java, Perl, MySQL and Postgres”.
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).
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.
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.
Weird!
Getting endorsement seems a relatively low bar, but it's still a bar.
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.