mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2003-03-14, 23:59   #1
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

983210 Posts
Default 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.
ewmayer is offline   Reply With Quote
Old 2003-05-13, 14:48   #2
willmore
 
willmore's Avatar
 
Aug 2002

22·3·5 Posts
Default

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. :)
willmore is offline   Reply With Quote
Old 2003-05-13, 16:31   #3
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

23·1,229 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2003-05-14, 07:38   #4
pakaran
 
pakaran's Avatar
 
Aug 2002

3718 Posts
Default

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.
pakaran is offline   Reply With Quote
Old 2003-05-14, 09:37   #5
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

4A516 Posts
Default

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!
smh is offline   Reply With Quote
Old 2003-05-14, 15:08   #6
pakaran
 
pakaran's Avatar
 
Aug 2002

3·83 Posts
Default

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.
pakaran is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
RSA-220 factored ixfd64 Factoring 2 2016-05-24 16:01
RSA-210 factored ryanp Factoring 6 2013-11-26 09:33
Factored vs. Completely factored aketilander Factoring 4 2012-08-08 18:09
F22 factored! unconnected Factoring 31 2010-06-26 04:07
F33 is factored !! Raman Factoring 4 2010-04-01 13:57

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

Fri Nov 27 09:26:07 UTC 2020 up 78 days, 6:37, 4 users, load averages: 0.95, 1.12, 1.19

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.