On Mon, May 26, 2014 at 08:23:07PM +0100, Ben Laurie wrote: > On 26 May 2014 19:52, Viktor Dukhovni <openssl-us...@dukhovni.org> > wrote: > > On Mon, May 26, 2014 at 07:24:54PM +0100, Ben Laurie wrote: > > > >> Finally, all of them have a bias: they're much more likely to pick > >> a prime with a long run of non-primes before it than one that > >> hasn't (in the case of the DH ones, the condition is slightly more > >> subtle, depending on parameters, but its there nevertheless). Is > >> this wise? > > > > Where do you see the bias? > > They all work by picking a random number and then stepping upwards > from that number until a probable prime is found. Clearly, that is > more likely to find primes with a long run of non-primes before than > primes with a short run.
To put this another way, take OpenSSL's probable_prime(). It finds "probable primes" by searching arithmetic progressions (common difference of 2) with random start points. The starting point is more likely to be chosen from within long runs of composites thus biasing prime selection to ones at tail ends of longer sequences of composites. For our purposes, the operative question is whether the distribution bias created can be leveraged in any way to attack factoring (RSA) or dlog (DH). --mancha
pgp8Sh6nO8iDZ.pgp
Description: PGP signature
