On Tue, May 27, 2014 at 08:23:29AM +0200, Otto Moerbeek wrote: > On Tue, May 27, 2014 at 05:23:45AM +0000, mancha wrote: > > > On Mon, May 26, 2014 at 09:01:53PM +0000, mancha wrote: > > > 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 > > > > This is probably more wonkish than Ben intended with his question but > > for those interested, the Poisson result I alluded to is due to > > Gallagher [1]. > > > > [1] Gallagher, On the distribution of primes in short intervals, > > Mathematika, 1976 > > Would this work: if you are worried the algorithm will never pick the > highest of a prime pair, just make it search backward half of the time?
(unless it hits it right on of course) > > But I understand it has no real security implications. > > -Otto > > ______________________________________________________________________ > OpenSSL Project http://www.openssl.org > Development Mailing List openssl-dev@openssl.org > Automated List Manager majord...@openssl.org ______________________________________________________________________ OpenSSL Project http://www.openssl.org Development Mailing List openssl-dev@openssl.org Automated List Manager majord...@openssl.org
