Cryptology - Fast Factoring Integers by SVP Algorithms "destroys RSA"

Click For Summary

Discussion Overview

The discussion centers around the implications of a new factoring algorithm proposed by Schnorr, which some participants claim could potentially undermine the RSA cryptosystem. The conversation explores the validity of these claims, the methodology of the algorithm, and the lack of practical demonstrations to support the assertions made in the paper.

Discussion Character

  • Debate/contested
  • Technical explanation
  • Exploratory

Main Points Raised

  • Some participants express skepticism about the claim that Schnorr's algorithm "destroys the RSA cryptosystem," noting the need for practical demonstrations to validate such a revolutionary assertion.
  • Others highlight discrepancies in the dates of the abstracts associated with the paper, suggesting potential issues with the claims made.
  • A few participants propose that while the algorithm may show significant speed improvements for smaller bit lengths, it remains uncertain whether these improvements apply to larger RSA key sizes, such as 2048-bit or 4096-bit numbers.
  • There is mention of the possibility of a flaw in the claims rather than in the mathematics of the algorithm itself, with some participants emphasizing their personal biases in their assessments.
  • Discussion includes references to testing the algorithm on commodity hardware and the potential for practical evaluations to emerge soon.
  • One participant notes that preliminary evaluations of the algorithm in Sage suggest it may not outperform existing methods, raising questions about the reliability of the approach.
  • The implications of a fast factoring algorithm on cryptocurrencies are also considered, with some participants suggesting it may not affect Bitcoin directly but could impact other cryptocurrencies reliant on hard factoring.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the validity of Schnorr's claims. Multiple competing views remain regarding the algorithm's effectiveness and implications for RSA, with ongoing skepticism about the lack of practical demonstrations.

Contextual Notes

Participants note limitations in the claims made about the algorithm, particularly regarding its performance across different bit lengths and the absence of empirical testing results to support the assertions. The discussion reflects a range of assumptions and uncertainties about the algorithm's capabilities.

Who May Find This Useful

Readers interested in cryptography, particularly those focused on RSA security, factoring algorithms, and their implications for modern cryptographic systems, may find this discussion relevant.

bahamagreen
Messages
1,015
Reaction score
52
TL;DR
Claus Peter Schnorr paper
Secret-key cryptography / Primal-dual reduction, SVP, fac-relation
Claims this destroys the RSA cryptosystem
The summary abstract (describes the method) and full paper are linked.

Summary abstract

https://eprint.iacr.org/2021/232.pdf
 
Mathematics news on Phys.org
Big claims. I'm not knowledgeable enough to know if this really "destroys the RSA cryptosystem", but I'm sure there are people on this forum who can comment. I'm interested to hear what they think.
 
If N. Gama and P.Q. Nguyen, Predicting lattice reduction, in Proc. EUROCRYPT 2008, LNCS 4965, Springer-Verlag, pp. 31–51, 2008 did the job and only needed an improvement, then we would have heard about it earlier.

So my personal bet is a flaw, possibly one which isn't easy to find.
 
Me, too.
The abstracts are not just different in what is written... they have different dates.
The linked abstract alone is "Date: received 1 Mar 2021, last revised 3 Mar 2021"
The PDF linked paper with the different abstract is "work in progress 31.10.2019"
 
fresh_42 said:
my personal bet is a flaw

I'm not sure there is necessarily a flaw in the actual math, just in the claim that this result "destroys the RSA cryptosystem". The paper is claiming much shorter times for factoring 400-bit and 800-bit numbers than current methods (looks like about 8 orders of magnitude speed-up), but it doesn't appear to give a general result for the time complexity of the algorithm, so we don't know if the same speed-up will hold for 2048-bit or 4096-bit numbers, which are the current bit lengths normally used for RSA.
 
  • Like
Likes   Reactions: jim mcnamara
PeterDonis said:
I'm not sure there is necessarily a flaw in the actual math, just in the claim that this result "destroys the RSA cryptosystem".
This doesn't rule out the other possibility. However, I have to admit that I'm biased, which is why I said personal opinion.
 
An interesting post about how the claimed capabilities of the algorithm described in the paper could be tested:

 
  • Like
Likes   Reactions: Vanadium 50
bahamagreen said:
The linked abstract alone is "Date: received 1 Mar 2021, last revised 3 Mar 2021"
The PDF linked paper with the different abstract is "work in progress 31.10.2019"
PeterDonis said:
An interesting post about how the claimed capabilities of the algorithm described in the paper could be tested:
I think we will have to take his age into account. This could explain the differences on the time table as well as the missing capability to test the algorithm. Of course this is speculative, and I'm not saying we have a similar case as Atiyah and RH here. But the parallels come to mind.
 
fresh_42 said:
the missing capability to test the algorithm

If the article I linked to is correct that the testing can be done on commodity hardware, I don't think it will be long before somebody tries it, even if Schnorr himself doesn't.
 
  • #10
How can you declare "destroys RSA" without a practical demonstration?
If you make a revolutionary claim that would be easy to demonstrate - and then you don't... it's pretty clear the claim is wrong.
 
  • #12
There is another strange fact: Schnorr and Shamir know each other personally, so I would have expected something more than "This destroys the RSA cryptosystem." in the abstract of an unpublished paper.
 
  • #13
I like "Show me the factors" from the Medium article title. And we already know Shor's Algorithm destroys RSA. Why not Schnorr's?

But anyway, there are plenty of RSA challenges out there. I'd find it more convincing if we had a demonstration.
 
  • Like
Likes   Reactions: jim mcnamara
  • #14
Here's the Cryptography Stack Exchange link about testing the method in "Sage":

Does Schnorr's factoring method work:

Leo Ducas, one of the top experts in lattice-based cryptography (and especially in its cryptanalysis) has implemented the March 3 version of the paper (in Sage). The preliminary experimental evaluations seem to indicate that the method cannot outperform the state of the art (quoted from Sage code to test algorithm):

However, further:

This 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

Would anyone be interested in downloading the Sage code and running it for say ##N=7919*7727## and reporting the results here or just explaining what the output below means? I would do so myself if I knew how to interpret the results.

Results of running the Sage code:

Running b=10, n=47, t=1000, we obtained 353 Factoring Relation found out of 1000 trials.
Running b=20, n=47, t=1000, we obtained 65 Factoring Relation found out of 1000 trials.
Running b=40, n=47, t=1000, we obtained 0 Factoring Relation found out of 1000 trials.
 
Last edited:
  • #15
Would a practical fast factoring algorithm have implications for cryptocurrencies?
 
  • #16
From my understanding this would not affect bitcoin, but there might be some crypto currency relying on hard factoring in some way.
 

Similar threads

Computation for nuclear reactor systems
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad Progress In Calculating The HLbL Contribution To Muon g-2
  • · Replies 0 ·
Replies
0
Views
3K
Undergrad New Hubble Paper On Lensing In Galactic Clusters
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad What Key Issues Should Cosmologists Address in the ΛCDM Model?
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad B -> s µµ decays: Current status
  • · Replies 49 ·
2
Replies
49
Views
13K
Undergrad How Does Beta Decay Relate to the Role of W Bosons in Weak Nuclear Force?
  • · Replies 4 ·
Replies
4
Views
5K
Programs Math minor, double major, and elective classes advice
  • · Replies 4 ·
Replies
4
Views
3K
Requesting suggestions for languages, libraries, and architectures for parallel (and sometimes non parallel) numerical and scientific computations
  • · Replies 8 ·
Replies
8
Views
4K
Undergrad Is there new LHC data on coupling constant running?
  • · Replies 1 ·
Replies
1
Views
3K
Mathematica This Week's Finds in Mathematical Physics (Week 226)
  • · Replies 7 ·
Replies
7
Views
3K