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

[mancha]

On Sun, Aug 02, 2015 at 08:08:52PM -0600, Hilarie Orman wrote:
> For primes p and q for which p-1 and q-1 have no common factor <= n,
> probability of gcd(p, q) > 1 is very roughly 1/n.

Hi

There's a typo or two here. Assuming p!=q, we always have gcd(p,q)=1.
> 
> Therefore, 1.  Use strong primes as in Rivest/Silverman.  Simply
> described, choose large primes r and s.  Choose small factors i and j,
> gcd(i, j) = 1.  Find p such that 1+2*i*r is prime and q such that
> 1+2*j*s is prime.

This appears a generalization of safe primes (i=j=1) which aren't overly
costly to generate. In fact, OpenSSL surely uses them already for
Diffie-Hellman MODPs. If they don't I'd be surprised (and alarmed). An
added small benefit is they mitigate Pollard's 'p-1' (only a concern
should p-1 or q-1 happen to be extremely smooth).

Strong primes have a bit more structure and afford protection against
repeated encryption attacks. If, as sometimes required of strong primes
p, p+1 must have a large prime factor, they also mitigate Williams'
'p+1' algo.

> 
> Or
> 
> 2.  Find large primes p and q such that gcd(p^2-1, q^2-1) < 10^6.

That's an interesting formulation. What's the importance of 10^6?

Thanks.

--mancha (https://twitter.com/mancha140)

> 
> Hilarie
-------------- 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/20150803/885612f6/attachment.sig>