On Mon, 3 Aug 2015 at 14:09:33 +0000 Viktor Dukhovni wrote: > On Mon, Aug 03, 2015 at 12:07:18AM -0600, Hilarie Orman wrote:
> > > > 1. Use strong primes as in Rivest/Silverman. Simply described, > > > > choose large primes r and s. Choose small factors i and j, gcd(i, j) > > > > = 1. Find p such that 1+2*i*r is prime and q such that 1+2*j*s is > > > > prime. > > > > > That's expensive to do. > > > > Twice as expensive. Is that really expensive? > Perhaps the algorithm used to generate strong (Sophie Germain) > primes in OpenSSL is not optimal, but it is noticeably slow. > The probability that both p and 2*p+1 are prime (taking p=11 mod > 12 to avoid obvious problems mod 2 and 3) is I would guess the > square of the probability that p alone is prime. For P around 1024 > bits, 1 in ~350 odd numbers of that size is prime, so only 1 in > ~350^2 candidates will be a strong prime. > Now, you've relaxed the conditions to admit i!=1 and j!=1, by what > algorithm does one quickly find i so that 1 + 2ir is also prime. Because you can search through many 1+2*i*r combinations without the need to generate a new base prime, the search is much faster than for Sophie Germain primes. > It seems to be me, and just finding p = 3 mod 4 some prime, and q > any other prime with gcd(p-1, q-1) = 2 is a lot faster. For each > of p,q we already ensure that the residue modulo each of the first > 2047 odd primes is neither 0 nor 1, so exceptions will be very > rare. About one time in 20K. For running time comparisons to strong primes, the devil is in the details. > > > > 2. Find large primes p and q such that gcd(p^2-1, q^2-1) < 10^6. > > > > > This is much cheaper, but why (p^2-1, q^2-1), rather than just > > > (p-1, q-1). What use is a common factor (other than 2) of (p+1, > > > q-1) or (p+1, q+1)? > > > > Rules out Lucas sequences. > What problem does that avoid for RSA? Common factors in p+-1, q+-1 can be exploited to use Lucas sequences to factor pq. 10^6 is a heuristic. It will be about a million times as hard get a Lucas attack rolling if small factors are eliminated. Hilarie _______________________________________________ openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev