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?
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
