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