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

[mancha]

On Fri, Jul 31, 2015 at 11:31:08PM +0000, paul at securecottage.com wrote:
> Hi Mancha,
> 
> Since p*q-1==(p-1)*(q-1)+(p-1)+q-1) any prime that divides (p-1) and
> (q-1) will divide all 4 of the terms in the definition of p*q-1.  Thus
> it will be a common factor in the totient.

Hi Paul, many thanks for your reply.

Yes, it's clear any f that divides both (p-1) and (q-1) also divides
(pq-1), (p-1)(q-1), and p-q.

In another email in this thread, I mention one concern regarding having
p-1 and q-1 share a large factor is that searching for a private
exponent d becomes easier as lcm((p-1),(q-1)) decreases.  However,
approximations for the distribution of g=gcd((p-1),(q-1)) for randomly
chosen 1024-bit primes p,q estimate P(g<=20)=91% and P(g<=100)=98% and
that largely allays this concern because it can be expected with high
probability lcm((p-1),(q-1)) and (p-1)(q-1) will be close in size.  

That said, I am certainly supportive of your suggestion to use safe
primes, thereby ensuring gcd((p-1),(q-1))=2, as long as it's not overly
costly.

Your concerns appear different, however. Please correct me if I
misunderstood but it seems you require Mallory (who only has access to
{n,e}) discover a factor f common to (p-1) and (q-1). My question was on
the mechanics of how this discovery occurs assuming Mallory is able to
fully factor pq-1 (ie. n-1).

Thanks.

--mancha

> I have checked through the key generation code of the openssl ssl
> code. I hacked it to report the greatest common divisor of p-1 and
> q-1. I then ran 100 key generations. It only had greatest common
> divisors of 2, 4 , 8, and 16. There were no other primes reported
> besides small powers of 2.
> 
> So there doesn't seem to be a practical problem with common divisors
> in the openssl code.
> 
> Still, I think this is a theoretical problem.  There should be a
> gcd(p-1,q-1)>16 check for the two primes in key generation.
> 
> Paul
> 
> 
> Quoting mancha <mancha1 at zoho.com>:
> 
> >On Fri, Jul 31, 2015 at 02:36:03AM +0000, paul at securecottage.com
> >wrote:
> >>
> >>Hi there,
> >>
> >>I have looked at the RSA protocol a bit and have concluded that
> >>
> >>1) common factors in (p-1) and (q-1) are also in the factorisation
> >>of (p*q-1).  2) by factoring (p*q-1) you can come up with candidates
> >>for squares in the totient.  3) you can also come up with d mod
> >>commonfactor^2 if there is a common factor.
> >>
> >>the math is shown in my wikipedia users page math blog at:
> >>
> >>https://en.wikipedia.org/wiki/User:Endo999#The_Bad_Stuff_That_Happens_When_There_Are_Common_Factors_Between_.28P-1.29_and_.28Q-1.29
> >
> >[SNIP]
> >
> >Hi. How are you finding a common factor f such that f|(p-1) and
> >f|(q-1)?
> >
> >Thanks.
> >
> >--mancha
> >
> >-- https://twitter.com/mancha140
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL: <http://mta.openssl.org/pipermail/openssl-dev/attachments/20150801/a1359ab3/attachment.sig>