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

[Hilarie Orman]

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