mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2014-06-06, 05:41   #1
Nooby
 
Apr 2014

478 Posts
Default 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/
Nooby is offline   Reply With Quote
Old 2014-06-06, 15:20   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

Your site actually factored 10% of the assumed-secure keys submitted to it?!
jasonp is offline   Reply With Quote
Old 2014-06-06, 15:25   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×3,191 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2014-06-06, 16:11   #4
Nooby
 
Apr 2014

478 Posts
Default

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.

Last fiddled with by Nooby on 2014-06-06 at 16:18 Reason: grammar
Nooby is offline   Reply With Quote
Old 2014-06-06, 16:14   #5
Gimarel
 
Apr 2010

2·79 Posts
Default

See http://www.h-online.com/security/new...e-1435474.html for example.
Gimarel is offline   Reply With Quote
Old 2014-06-06, 19:38   #6
prgamma10
 
prgamma10's Avatar
 
Jan 2013

11011012 Posts
Default

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...)
prgamma10 is offline   Reply With Quote
Old 2014-06-06, 20:10   #7
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2·11·61 Posts
Default

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

So for N = 21024, B = 1016 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.
alpertron is offline   Reply With Quote
Old 2014-06-06, 21:35   #8
Nooby
 
Apr 2014

2716 Posts
Default

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).
Nooby is offline   Reply With Quote
Old 2014-06-06, 21:58   #9
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

24768 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2014-06-06, 22:21   #10
Nooby
 
Apr 2014

3·13 Posts
Default

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.
Nooby is offline   Reply With Quote
Old 2014-06-07, 02:20   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by alpertron View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
"factoring" vs "factorizing" ixfd64 Factoring 4 2012-10-16 04:07
DJB paper "Factoring into coprimes in essentially linear time" Chris Card Factoring 6 2005-06-25 19:41
request: always include "from" in trial-factoring results James Heinrich Software 1 2005-04-10 02:44
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12
"Factoring only" results / stats in account details page schneelocke PrimeNet 3 2004-01-07 22:12

All times are UTC. The time now is 19:27.

Fri Feb 26 19:27:06 UTC 2021 up 85 days, 15:38, 0 users, load averages: 2.90, 2.23, 2.15

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