20140606, 05:41  #1 
Apr 2014
47_{8} Posts 
Factoring "weak" RSA moduli
Out of great curiosity after reading some papers on this topic, I made a site sharing the results.
I'm also looking for other sources of inputs, and a way to remove the cask effect in the cluster if it is ever possible. Here is the link: http://www.rsahunt.com/ 
20140606, 15:20  #2 
Tribal Bullet
Oct 2004
2·3·19·31 Posts 
Your site actually factored 10% of the assumedsecure keys submitted to it?!

20140606, 15:25  #3 
(loop (#_fork))
Feb 2006
Cambridge, England
2×3,191 Posts 
0.1%, I think; still a bit much, but I can imagine that the RNGs in newlyinstalled virtual machines might not always be very well seeded.

20140606, 16:11  #4 
Apr 2014
47_{8} Posts 
Surprisingly true about the ratio as all moduli are unique. At first I thought most of the factored keys came from the "Debian weak key", but it turned out that most of the factored moduli are not in the blacklist.
Most of them came from embedded devices such as routers, firewalls, etc. The ratio will continue to grow, because each worker in the cluster holds a local "pool" of primes/moduli, new inputs will be assigned to a random worker for the initial pass, then every other worker will try to factor it. This is the cask effect I'm talking about. Currently there are 16 such workers and it is only a half way into the initial pass. My guess the final ratio may be around 0.5%. Some people suggested that the fast "probable prime" selection and the extra requirement for "strong primes"(primality of p1/2 in OpenSSL) may also reduce the entropy somehow but I do not have the knowledge to prove it, or many other conspiracy. Last fiddled with by Nooby on 20140606 at 16:18 Reason: grammar 
20140606, 16:14  #5 
Apr 2010
2·79 Posts 
See http://www.honline.com/security/new...e1435474.html for example.

20140606, 19:38  #6 
Jan 2013
1101101_{2} Posts 
Since p will be 1024 bits or more, what is the probability of p1 (or p+1) being "smooth" enough for P1 or P+1? (with B1=1e16, or something...)

20140606, 20:10  #7 
Aug 2002
Buenos Aires, Argentina
2·11·61 Posts 
The probability of your number N to be Bsmooth is about u^{u} where u = ln N / ln B.
So for N = 2^{1024}, B = 10^{16} you get u = 19.26592, so the probability is 1.7674*10^{25}. It is far better to use that time to compute ECM instead of p1. In the same time you could complete the 40digit level in ECM so you get: u = 7.706368, so the probability is 1.4642*10^{7}. Notice that in both cases I used only step 1 for both p1 and ECM algorithms. When adding step 2 the probabilities are better, but they are harder to compute. 
20140606, 21:35  #8 
Apr 2014
27_{16} Posts 
for the p1 thing, I was talking about the function "BN_generate_prime_ex" in OpenSSL, when choosing "safe primes" it does an extra sieve which will reduce the range of primes being chosen(eg. primes like 17 will never be used since (p1)/2 is not prime).

20140606, 21:58  #9 
Aug 2002
Buenos Aires, Argentina
2476_{8} Posts 
From my previous post, you can see that the "safe primes" are as safe as other primes in that range, because it is far easier to factor the RSA modulus using ECM than using p1.
I think it does not help at all to use "safe" primes for RSA. 
20140606, 22:21  #10 
Apr 2014
3·13 Posts 
Yes, doing so does not improve security, on the contrary, it narrows the range of possible primes that OpenSSL uses, thus increses the chance of collisions.

20140607, 02:20  #11  
Nov 2003
2^{2}×5×373 Posts 
Quote:
Noone reads. I wrote a joint paper with Ron Rivest about whether strong primes are needed for RSA. But of course, noone (or almost) here has read it. BTW, factoring a 1024bit RSA key by ECM is hopeless. Each prime is almost twice the size of the largest ECM factor ever found. It would be far far faster to use GNFS. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
"factoring" vs "factorizing"  ixfd64  Factoring  4  20121016 04:07 
DJB paper "Factoring into coprimes in essentially linear time"  Chris Card  Factoring  6  20050625 19:41 
request: always include "from" in trialfactoring results  James Heinrich  Software  1  20050410 02:44 
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?  nitai1999  Software  7  20040826 18:12 
"Factoring only" results / stats in account details page  schneelocke  PrimeNet  3  20040107 22:12 