mersenneforum.org RSA cracked by SVP algorithms? (claim is disputed)
 Register FAQ Search Today's Posts Mark Forums Read

 2021-03-03, 06:44 #1 kubus     May 2003 Warsaw 3×5 Posts RSA cracked by SVP algorithms? (claim is disputed) Claus Peter Schnorr just posted a paper in which he claims to have broken RSA. Has anyone looked into it? Fast Factoring Integers by SVP Algorithms
 2021-03-03, 15:00 #2 ccorn     Apr 2010 15110 Posts Better look at the more recent draft. I do not consider it likely that Schnorr himself would have posted such an outdated (and apparently haphazardly edited) version.
 2021-03-03, 15:21 #3 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 7·223 Posts An early slide from him: https://eurocrypt2009rump.cr.yp.to/e...a7ba36cf73.pdf Forums about these claims: https://crypto.stackexchange.com/que...m-is-not-secur https://www.reddit.com/r/math/commen...ithms/gphobll/
 2021-03-03, 17:25 #4 xilman Bamboozled!     "𒉺𒌌𒇷𒆷𒀭" May 2003 Down not across 22·3·941 Posts Someone whom I respect greatly told me that he had received that information from several others to whom it was new, including me. His view is that it is unlikely to pan out in reality any time soon, being yet another elaboration of one of Schnorr's ideas. But who knows?
 2021-03-03, 17:29 #5 ccorn     Apr 2010 151 Posts Here is my superficial impression, gathered from the PDFs linked at the university's lattice algorithms course page. I might be wrong. Better consult the linked resources directly. There is a known construction of a close-enough-lattice-vector problem that helps generate smooth integers $$u$$ and $$v$$ such that $$u/v$$ is close to the to-be-factored integer $$N$$. Then $$|u-vN|$$ is (relatively) small and, if smooth, gives rise to a relation mod $$N$$. Enough such relations can be combined in the usual way, using linear algebra over GF(2) on the exponent vectors, to construct congruent squares mod $$N$$, which are then used to find a (probably nontrivial) factor of $$N$$. I find it worth remarking that the method does not require proven shortest or closest lattice vectors to be found; in fact it needs to find and examine several close-enough lattice vectors in order to gather enough relations. It does so by looking at many (but not too many) enumerated lattice vectors and by tweaking the lattice. Thus, keywords like SVP or CVP are a bit misleading; their presence is justified merely by the fact that algorithms for those problems have been adapted to solve a related problem. Anyway, the factor base size and thus the number of relations needed are claimed to be far lower than for typical NFS scenarios. The crux is then to do the close-vectors search efficiently. Over the last decade, progress has been made in the lattice methods used, reducing the computational effort per relation found. The latest version of the method is claimed to use far less arithmetic operations than QS or NFS for 400-bit and 800-bit numbers. The abstract says that that means "much faster", but the body text cautions that the bit length of the operands is much larger. If I interpret that correctly, this means that the number of machine-word arithmetic operations is not something to brag about yet. In any case, I'd like to see the method demonstrated with a solution to some $$n$$-bit factorization challenge with $$n$$ between 400 and 800. There is also a polynomial-complexity claim, but that seems to refer to the part that finds close-enough lattice vectors, subject to some assumptions. If I am not mistaken, that estimate does not cover the smoothness filter that produces relations, so there might still be a more-than-polynomial slowdown (which I consider likely as Dickman's rho function will have a say there).
2021-03-03, 19:08   #6
CRGreathouse

Aug 2006

3×1,993 Posts

I think it's really exciting to see someone trying (slightly) new things in this space -- since the 90s all we've been doing is tweaking the number field sieve. But he's pretty straightforward about the benefits, as corn points put above:

Quote:
 The number of arithmetic steps of our factorisation is quite small compared with QS and NFS factorisation but the bit length of integers is large.
That is, there's no claim that the number of bit operations stays the same let alone decreases. So I think this is better thought of as a jumping-off point for research than as a useable method. But who knows, I could be wrong! Maybe a careful implementation could beat other algorithms in some ranges, perhaps even in a neighborhood including \infty.

Last fiddled with by CRGreathouse on 2021-03-03 at 19:09

2021-03-03, 21:15   #7
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

2·5·1,051 Posts

Quote:
 Originally Posted by xilman Someone whom I respect greatly
Agsapiens?

 2021-03-04, 15:20 #8 ThiloHarich     Nov 2005 103 Posts There is a german statement on heise.de https://www.heise.de/news/RSA-zersto...t-5071387.html
2021-03-05, 00:00   #9
jwaltos

Apr 2012
Oh oh.

2×32×52 Posts

Quote:
 Originally Posted by CRGreathouse .. since the 90s all we've been doing is tweaking the number field sieve..
No. We've not all been doing that, tweaking a sieving a process then "black-boxing" it..focusing on and optimizing black box processes.

Last fiddled with by jwaltos on 2021-03-05 at 00:01

2021-03-05, 07:10   #10
jwaltos

Apr 2012
Oh oh.

2·32·52 Posts

Quote:
https://www.math.uni-frankfurt.de/~d...ch/papers.html
Here's a link to some older papers. Perhaps some of these may help in correlating past results within the present paper. I'm trying to understand what the breakthrough is. I have some familiarity with
the subset sum problem, LLL and variants and computational complexity. Instead of clarity I'm navigating inscrutability. This paper and its antecedents remind me of some papers regarding the resolution of the abc conjecture by another distinguished professional, Shinichi Mochizuki.

Last fiddled with by jwaltos on 2021-03-05 at 07:22

 2021-03-05, 09:46 #11 ThiloHarich     Nov 2005 10310 Posts Somebody tried to implement it https://github.com/lducas/SchnorrGate

 Similar Threads Thread Thread Starter Forum Replies Last Post dans Hardware 3 2010-12-02 02:23 bearnol Miscellaneous Math 58 2010-09-05 17:48 Mindnar Lounge 28 2008-08-27 16:22 bearnol Miscellaneous Math 2 2006-08-12 09:17 Jeff Gilchrist Math 1 2005-03-24 02:31

All times are UTC. The time now is 11:54.

Tue May 17 11:54:41 UTC 2022 up 33 days, 9:56, 0 users, load averages: 1.73, 1.51, 1.25