mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-03-03, 06:44   #1
kubus
 
kubus's Avatar
 
May 2003
Warsaw

3×5 Posts
Default 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
kubus is offline   Reply With Quote
Old 2021-03-03, 15:00   #2
ccorn
 
ccorn's Avatar
 
Apr 2010

2·3·52 Posts
Default

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.
ccorn is offline   Reply With Quote
Old 2021-03-03, 15:21   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·36 Posts
Default

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/
R. Gerbicz is offline   Reply With Quote
Old 2021-03-03, 17:25   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

101001100101102 Posts
Default

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?
xilman is offline   Reply With Quote
Old 2021-03-03, 17:29   #5
ccorn
 
ccorn's Avatar
 
Apr 2010

9616 Posts
Default

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).
ccorn is offline   Reply With Quote
Old 2021-03-03, 19:08   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

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
CRGreathouse is offline   Reply With Quote
Old 2021-03-03, 21:15   #7
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101Γ—103 Posts

949110 Posts
Default

Quote:
Originally Posted by xilman View Post
Someone whom I respect greatly
Agsapiens?
Uncwilly is offline   Reply With Quote
Old 2021-03-04, 15:20   #8
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

There is a german statement on heise.de

https://www.heise.de/news/RSA-zersto...t-5071387.html
ThiloHarich is offline   Reply With Quote
Old 2021-03-05, 00:00   #9
jwaltos
 
jwaltos's Avatar
 
Apr 2012
Brady

18116 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
.. 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.

Good thread with good links!

Last fiddled with by jwaltos on 2021-03-05 at 00:01
jwaltos is offline   Reply With Quote
Old 2021-03-05, 07:10   #10
jwaltos
 
jwaltos's Avatar
 
Apr 2012
Brady

5×7×11 Posts
Default

Quote:
Originally Posted by jwaltos View Post
Links
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
jwaltos is offline   Reply With Quote
Old 2021-03-05, 09:46   #11
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

Somebody tried to implement it

https://github.com/lducas/SchnorrGate
ThiloHarich is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
AMD hardware level debugger cracked dans Hardware 3 2010-12-02 02:23
EFF claim(s) bearnol Miscellaneous Math 58 2010-09-05 17:48
GIMPS may not claim $100,000 Mindnar Lounge 28 2008-08-27 16:22
ECDLP cracked mathematically acc. Bearnol bearnol Miscellaneous Math 2 2006-08-12 09:17
Ramanujan math puzzle cracked at last Jeff Gilchrist Math 1 2005-03-24 02:31

All times are UTC. The time now is 09:35.

Mon Apr 19 09:35:10 UTC 2021 up 11 days, 4:16, 0 users, load averages: 1.65, 1.74, 1.58

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.