[openssl-dev] common factors in (p-1) and (q-1)

[Viktor Dukhovni]

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.

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.

> >  > 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?

-- 
	Viktor.