On Mon, May 26, 2014 at 08:49:03PM +0000, Viktor Dukhovni wrote: > On Mon, May 26, 2014 at 08:20:43PM +0000, mancha wrote: > > > 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). > > The maximum gap between primes of size $n$ is conjectured to be around > $log(n)^2$. If $n$ is $2^k$, the gap is at most $k^2$, with an > average value of $k$. Thus the most probable primes are most $k$ > times more probable than is typical, and we lose at most $log(k)$ bits > of entropy. This is not a problem.
One consequence of the k-tuple conjecture (generally believed to be true) is that the size of gaps between primes is distributed poisson. You're right when you say the entropy loss between a uniform distribution to OpenSSL's biased one is small. In that sense there is not much to be gained entropy-wise from using a process that gives uniformly distributed primes over what OpenSSL does. However, if a way exists to exploit the OpenSSL distribution bias, it can be modified to be used against uniformly distributed primes with only minimal algorithmic complexity increases. In other words, the gold standard here isn't a uniform distribution. --mancha
pgpkQPBWaNcH0.pgp
Description: PGP signature
