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

[Viktor Dukhovni]

On Fri, Jul 31, 2015 at 01:42:01PM -0700, Bill Cox wrote:

> You are correct, or at least very close.  I was testing for GCD(p-1, q-1)
> == 4, when I should have been testing for GCD(p-1, q-1) == 2, since p-1 and
> q-1 are known to be even.  Fixing that, I see that the probability of
> having GCD(p-1, q-1) == 2 for random odd numbers is a bit over 60% in the
> python runs.  This will result most likely in a bit less a 2X runtime
> penalty for determining the primes.

There's no need for that, just a priori force at least one of then
to be 3 mod 4.  Then the largest common even factor is necessarily 2.

I still see little reason to bother though.  My example demostrates
a GCD of 28559 * 2 (almost 16 bits), so we can compute d = 1/e mod
phi(m) modulo an ~31 bit number, but d is a 1024-bit number, knowing
it mod an ~31 bit number does not seem particularly useful.

Common factors with considerably more bits are exponentially (correct
usage for once) rare.  Does this "leak" warrant remediation?

How would the attacker know whether any factors of (n-1) are or
are not in fact common factos of (p-1) and (q-1) if p and q remain
unknown?  Is finding sufficiently large factors a tractable problem?

-- 
	Viktor.