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

[mancha]

On Fri, Jul 31, 2015 at 11:19:39AM -0700, Bill Cox wrote:
> Cool observation.  From running a bit of Python code, it looks like
> the probability that GCD(p-1, p-q) == 4 is a bit higher than 15%, at
> least for random numbers between 2048 and 4096 bits long.  It looks
> like putting in a GCD(p-1, q-1) check will slow down finding suitable
> p and q by around a factor of 6.5.
> 
> I am not saying OpenSSL should or should not do this check, but
> hopefully making that decision is easier knowing the runtime penalty.

To clarify, the worry is that lcm((p-1),(q-1)) << (p-1)(q-1) thus making
the computation of d=1/e (mod lcm((p-1),(q-1))) comparatively easier?

If so, here's my quick & dirty back-of-envelope calculation (mod bound)
for the probability the gcd of two randomly chosen integers x,y is at
most k:

k	p(gcd(x,y)<=k)
-       --------------
1	60.79%
2	75.99%
3	82.75%
4	86.55%
5	88.98%
6	90.67%
7	91.91%
8	92.86%
9	93.61%
10	94.21%

As can be seen, the probability is quite high the gcd will be small so
(p-1)(q-1) ~ lcm((p-1)(q-1)) removing the above benefit.

But it's the end of the week and the neurons need respite so please let
me know if I'm missing something.

--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/20150731/8a8899fd/attachment.sig>