The death of RSA and elliptic curve cryptography?

[Progman]

Prime-factor mathematical foundations of RSA cryptography ‘broken’, claims cryptographer

https://portswigger.net/daily-swig/amp/prime-factor-mathematical-foundations-of-rsa-cryptography-broken-claims-cryptographer

 

A paper from mathematician and cryptographer Claus Schnorr claims that prime factorization can be reduced to a much less intractable ‘shortest vector’ problem.

The abstract to the paper (PDF), entitled ‘Fast Factoring Integers by SVP Algorithms’, claims that this process “destroys the RSA cryptosystem”.

 

If verified, the technique would work even if longer key values were deployed. Increasing the key length is the standard response to making sure algorithms stay ahead of advances in computing technology.

 

Paper:

https://eprint.iacr.org/2021/232.pdf

Edited March 6, 2021 by Progman

[Kurapica]

very complicated math for the average man, any practical examples or a proof of concept ?

[kao]

@Kurapica: https://crypto.stackexchange.com/questions/88582/does-schnorrs-2021-factoring-method-show-that-the-rsa-cryptosystem-is-not-secur

[Progman]

Yes I agree the algorithm looked difficult and very time consuming to implement to parse through all the math.  But the sage implementation in the stack exchange post is useful!

Time will tell, but I agree if you dont publish working code that can break known challenges, then probably you did not solve anything.

 

Like all the ridiculous papers claiming P=NP.  Nobody wants to read through garbage.  Post your polynomial time SAT solver or go back to school.  You do it right like this and the empirical proof hammer will come down fast.  Even if your proof has mistakes, a working algorithm will inevitably get a valid proof or you just postulate what you cant prove, and it's still a huge accomplishment.

 

But big names manage to get news coverage quite easily even if its vapor.  That's why the question mark

[Progman]

Valid proof that RSA broken: $10000

Code that factors RSA primes in asymptotically better time: $10 mil , gray area, sell key factoring service on the dark web would be legal

Valid proof that P=NP: $1 million

Code that solves SAT in P time: $ billions, Bitcoin, ethereum, darkweb solve service for all crypto algos

[Taitor]

7 hours ago, Progman said:

Prime-factor mathematical foundations of RSA cryptography ‘broken’, claims cryptographer

https://portswigger.net/daily-swig/amp/prime-factor-mathematical-foundations-of-rsa-cryptography-broken-claims-cryptographer

A paper from mathematician and cryptographer Claus Schnorr claims that prime factorization can be reduced to a much less intractable ‘shortest vector’ problem.

The abstract to the paper (PDF), entitled ‘Fast Factoring Integers by SVP Algorithms’, claims that this process “destroys the RSA cryptosystem”.

If verified, the technique would work even if longer key values were deployed. Increasing the key length is the standard response to making sure algorithms stay ahead of advances in computing technology.

Paper:

https://eprint.iacr.org/2021/232.pdf

TL;DR: All unsubstantiated.

The corresponding Twitter thread is here.

<Added on March 3 ~ morning - view my own> I'm also basing my conclusion on the fact that several top experts on SVP and CVP algorithms have looked at the paper and concluded that it is incorrect (I cannot provide names, since it was in the context of anonymous reviews). Of course, the latter should not be treated as clear evidence, since I'm not providing proof of this statement - please treat it simply as it is, a claim I'm making.

Among the potential issues (again to be treated with care, as pointers to help people willing to look further into where the paper might fail):

The proof of (5.8) does only show the existence of many smooth triples, but says nothing about the probability of successfully finding factoring relations.

The paper relies on the Schnorr-Hörner pruning strategy, which is known to be flawed.

No justification is given for the cost indicated for (3.2)

<Added on March 3 ~ evening> The "Added on March 3 ~ morning - view my own" part of the answer above refers to the version of the paper which was initially uploaded, and whose eprint extracted abstract (thanks to fgrieu for pointing it) contained a claim that RSA was "destroyed", together with the sample running times given in OP's question.

Apparently, Schnorr himself still claimed, after being asked by mail about the paper, that the latest version breaks RSA - and so does its abstract; with respect to this claim and given the lack of solved RSA challenge, I stand by my initial statement that it should be regarded as essentially unsubstantiated.

<added March 5, 2pm CET> Forgot to mention, this Twitter thread points to what seems to be a fatal mistake in Schnorr's paper.

[deepzero]

> Like all the ridiculous papers claiming P=NP.  Nobody wants to read through garbage.  Post your polynomial time SAT solver or go back to school. 

lol

Very odd story, guy is a very respected cryptographer and has been working on this since at least before 2014, for that the mistakes mentioned on stack overflow are really basic. I am guessing one doesnt put "this breaks rsa" easily into ones abstract. I wonder if it really was just a cheap call for attention.

[Progman]

So am I right though that if you are intelligent enough to solve prime factoring or P=NP...

Then you are probably intelligent enough to not publish it until you have properly milked the solution for $$$$$$$$...

Essentially these problems are at least initially unpublishable.

That being said if you started breaking RSA for payment or mining every bit coin, all hell would break loose.  You would also be intelligent to use a VPN or just about every intelligence agency, at least ones with resources would attempt to hack or show up at your physical location to retrieve the solve.  Then they may even leak it to one of their own academics if publication looks to be inevitable.

Another reasonable approach would be to quietly mine bitcoins so you deliberately mine only a small % of the time to remain undetected.  Then after making enough profit you seek out connects in an agency willing to protect the solve with big security resources, and make a deal to share some of the future profit.

 

So I'm always extremely skeptical of these types of claims.  It is hard to be so smart and so stupid at the same time.  Yet who knows maybe what I said already could have happened and the tail end where publication is inevitable is reached.  But I feel we would see strong indicators or hear plenty of rumors well in advance if that were so.