-   Math (
-   -   RSA-100 factored! (

ewmayer 2003-03-14 23:59

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 [i]sure[/i]?

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

Factors: 40094690950920881030683735292761468389214899724061 *

p-1 = 2.3167.3613.587546788471.3263521422991.

p+1 = 2^3.3.5^2.109.409.20839813.60236089.49147216823.

q-1 = 2^

q+1 =

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.

willmore 2003-05-13 14:48

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. :)

ewmayer 2003-05-13 16:31

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.

pakaran 2003-05-14 07:38

I wouldn't be surprised if NFSnet set a record or two by the end of this summer.

Check out [url][/url]. 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.

smh 2003-05-14 09:37

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!

pakaran 2003-05-14 15:08

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.

All times are UTC. The time now is 16:16.

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