Factoring "weak" RSA moduli

[Nooby]

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/

[jasonp]

Your site actually factored 10% of the assumed-secure keys submitted to it?!

[fivemack]

0.1%, I think; still a bit much, but I can imagine that the RNGs in newly-installed virtual machines might not always be very well seeded.

[Nooby]

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 p-1/2 in OpenSSL) may also reduce the entropy somehow but I do not have the knowledge to prove it, or many other conspiracy.

[Gimarel]

See http://www.h-online.com/security/new...e-1435474.html for example.

[prgamma10]

Since p will be 1024 bits or more, what is the probability of p-1 (or p+1) being "smooth" enough for P-1 or P+1? (with B1=1e16, or something...)

[alpertron]

The probability of your number N to be B-smooth is about u^-u where u = ln N / ln B.

So for N = 2¹⁰²⁴, B = 10¹⁶ 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 p-1. In the same time you could complete the 40-digit 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 p-1 and ECM algorithms. When adding step 2 the probabilities are better, but they are harder to compute.

[Nooby]

for the p-1 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 (p-1)/2 is not prime).

[alpertron]

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 p-1.

I think it does not help at all to use "safe" primes for RSA.

[Nooby]

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.

[R.D. Silverman]

Originally Posted by alpertron

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 p-1.

I think it does not help at all to use "safe" primes for RSA.

Sigh. Another complaint from me on a subject I raise repeatedly.

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 1024-bit 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.