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

1160610 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