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. _______________________________________________ openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev