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
pgpxwpGf9U9Nm.pgp
Description: PGP signature
