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