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

In summary, the conversation discusses a new factoring method that claims to "destroy the RSA cryptosystem". However, there are doubts about the validity of this claim and the paper has not yet been published. Some experts have tested the method and found that it does not outperform current methods. There is also speculation about the personal motivations of the author and the potential implications for cryptocurrencies.
  • #1
1,014
52
TL;DR Summary
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
  • #2
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.
 
  • #3
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.
 
  • #4
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"
 
  • #5
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 jim mcnamara
  • #6
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.
 
  • #7
An interesting post about how the claimed capabilities of the algorithm described in the paper could be tested:

 
  • Like
Likes Vanadium 50
  • #8
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.
 
  • #9
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 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.
 

1. How does Cryptology work?

Cryptology is the study of codes, ciphers, and other methods of securing information. It involves using mathematical algorithms to encrypt data, making it unreadable to anyone without the proper key. This ensures the confidentiality and integrity of sensitive information.

2. What is RSA?

RSA is a widely used public-key cryptosystem that is based on the difficulty of factoring large integers. It is named after its inventors, Ron Rivest, Adi Shamir, and Leonard Adleman, and is commonly used for secure communication, digital signatures, and authentication.

3. How does fast factoring of integers affect RSA?

Fast factoring of integers refers to the ability to quickly find the prime factors of large numbers. This is significant for RSA because the security of the algorithm relies on the difficulty of factoring large numbers. If fast factoring algorithms are developed, it could potentially make RSA vulnerable to attacks.

4. What is the role of SVP algorithms in cryptology?

SVP (shortest vector problem) algorithms are used in cryptology to solve lattice problems, which are mathematical problems that are difficult to solve using classical computers. These algorithms are important in cryptanalysis, which is the process of breaking codes and ciphers to reveal the hidden information.

5. Can SVP algorithms completely destroy RSA?

At this time, there is no evidence to suggest that SVP algorithms can completely destroy RSA. While these algorithms have the potential to make factoring integers easier, there are still many challenges and limitations to overcome. Additionally, there are other factors, such as key length and implementation, that can affect the security of RSA.

Suggested for: Cryptology - Fast Factoring Integers by SVP Algorithms "destroys RSA"

Replies
3
Views
879
Replies
1
Views
1K
Replies
4
Views
933
Replies
1
Views
696
Replies
1
Views
678
Back
Top