mersenneforum.org > Math RSA-100 factored!
 Register FAQ Search Today's Posts Mark Forums Read

 2003-03-14, 23:59 #1 ewmayer ∂2ω=0     Sep 2002 República de California 3×53×31 Posts RSA-100 factored! The RSA challenge numbers have long served as a useful yardstick for our ability to factor generic integers (i.e. those having no special algebraic form.) I remember once asking Bob Silverman (of RSA Labs) whether, when they chose the similar-sized primes p and q which are multiplied together to form each RSA number, they checked to make sure that none of p+-1 or q+-1 was sufficiently smooth so as to make the number vulnerable to the humble p-1 or p+1 methods of factorization. He pretty much laughed that one off, saying that for sufficiently large p and q, the odds of p+-1 or q+-1 being smooth were essentially negligible. True, as the numbers get large the odds of a generically chosen integer being K-smooth (K some smoothness bound) tend toward zero, but my reasoning was: since it's not difficult to check smoothness of p+-1 and q+-1, given the importance of the supposed hard-to-factor property of the product, why not check and be sure? Today I was looking at the list of RSA challenge numbers which have been factored, ranging from 100 to 155 digits (the largest of these, the 155-digit, 512-bit RSA-155, was cracked just last year using GNFS), and for nearly all of these, it is indeed true that the p-1 or p+1 method would have no chance of factoring the number. Note I said "nearly all." In fact, the smallest RSA challenge number I'm aware of, RSA-100, which was cracked in 1991 using the then-new quadratic sieve algorithm, has the factorization RSA-100 Factors: 40094690950920881030683735292761468389214899724061 * 37975227936943673922808872755445627854565536638199 p-1 = 2.3167.3613.587546788471.3263521422991. 865417043661324529. p+1 = 2^3.3.5^2.109.409.20839813.60236089.49147216823. 23011759155976667. q-1 = 2^2.5.41.2119363.602799725049211. 38273186726790856290328531. q+1 = 2.3.11.59. 10296530804037206222569012658644444886804031773. Here, p denotes the smaller of the 2 factors and q the larger. Note how smooth p+1 is. That means that the p-1 method with (luckily chosen) bounds B1 = 5e10 and B2 = 2.5e16 would find this factorization. To see roughly how long such a p-1 run would take, I ran GMP-ECM in p-1 mode to the smaller bounds 5e7 and 2.5e10. Each of these needed slightly less than 2 minutes on a 1GHz Alpha ev6, so to run to the above large bounds would need around 1 CPU-day for stage 1 and around 3 CPU-years for stage 2. With a distributed stage 2 (note that stage 2 is perfectly distributable, i.e. each of N machines can work on its own interval with no interprocessor communication needed), the factorization time could be brought down to ~1000/N days. Of course MPQS and NFS could do it much quicker still, but I still found it interesting how much our conception of "impossible" tasks can change in just a decade.
 2003-05-13, 14:48 #2 willmore     Aug 2002 22×3×5 Posts Hey, Ernst, is there much work being done on factoring the (if any) remaining RSA challenge numbers? I was at ISU when the RSA-129 team was doing its work. That's when I met Bob and got interested in MPQS and NFS, and eventually the Cunningham Project, which lead me here, to Mersenne's. :) So, I'm sort of curious if that kind of stuff is still alive. I guess it's nice to have going as it sets a good esitmate of the casual lower bound for key sizes used in RSA. Basically, if a bunch of nuts on the Internet can crack a key that size *for fun*, you probably want to use something bigger for anything more important than your instant messenger traffic. :)
 2003-05-13, 16:31 #3 ewmayer ∂2ω=0     Sep 2002 República de California 3×53×31 Posts Hi, Dave: yes, various collaborations like NFSNet continually work on a variety of NFS factoring challenges (Sam Wagstaff of Purdue U. maintains the NFS "most-wanted" lists). Every few years, their horsepower gets to the point where they try the next-larger RSA challenge number as a test for their latest algorithms and hardware. Peter Montgomery and Paul Leyland would be the guys to talk to about this, I believe.
 2003-05-14, 07:38 #4 pakaran     Aug 2002 3·83 Posts I wouldn't be surprised if NFSnet set a record or two by the end of this summer. Check out http://www.nfsnet.org/. Its their official site, and they just posted a public release candidate the other day. I see a few issues in it with seeing if the client is running or not on a Windows gui client, while the client window is hidden. If I set the client window to visible, there's no probs, though.
 2003-05-14, 09:37 #5 smh     "Sander" Oct 2002 52.345322,5.52471 29·41 Posts Currentely they are doing the remaining C212 of 10^227-1 but i've understood there's plenty of room for larger composites when more people help with the sieving. There isn't really a problem when the client window is not vissible, you only have to be careful when you stop the client. When i want to stop the client, i always make the window vissible, press the stop button and wait until the window disappears. BTW, after Ernst wrote the original message, RSA 160 was cracked!
 2003-05-14, 15:08 #6 pakaran     Aug 2002 3×83 Posts Yeah, the client always stops within maybe ten or fifteen seconds on my 2000+, after finishing the current line. I can't imagine how long it would take on say a P3.

 Similar Threads Thread Thread Starter Forum Replies Last Post ixfd64 Factoring 2 2016-05-24 16:01 ryanp Factoring 6 2013-11-26 09:33 aketilander Factoring 4 2012-08-08 18:09 unconnected Factoring 31 2010-06-26 04:07 Raman Factoring 4 2010-04-01 13:57

All times are UTC. The time now is 22:53.

Mon Apr 12 22:53:53 UTC 2021 up 4 days, 17:34, 1 user, load averages: 2.76, 2.83, 2.88