Hi there,
On Sun, 28 Nov 1999, Ben Laurie wrote:
> Geoff Thorpe wrote:
> >
> > I can't recall whether the prime number generation uses sequential
> > candidates or an arithmetic sequence (or even something else) but I don't
> > think that would qualify as a "known problem" either way ...
>
> Sequential candidates or an arithmetic sequence would both effectively
> reduce the randomness of the primes, because they'd both favour primes
> that come after long gaps.
sequential yes, arithmetic not *really*. :-)
The basic idea is to give each prime (in some region of the integers) a
roughly equal shot at being hit by the prime number search. Sequential
searches do not do that - eg the second prime in a prime pair (where two
sequential odd numbers are both prime) has an extremely low chance of
being stumbled across in a sequential search because the search would have
to begin right on top of it. An arithmetic search increases the "fair
play" by skipping across intervals plucking candidates out every 'k' odd
numbers. Provided no ground-breaking maths crops up and you choose good
'k's, I think it pretty much evens the playing field.
However, even with sequential searches - the real problem is not entropy
as someone has shown (I can't recall who, Peter Gutmann showed me a paper
ages back about this - perhaps he can recall - Peter, you there?). There
is a slight reduction in the effective key-space from an entropy point of
view but bounds were given on the loss of entropy due to the bias towards
some primes over others. The scary thing about sequential searches is that
nobody seems to know whether or not heavily favouring primes following
long gaps happens to heavily favour primes with particular numerical or
algebraic properties that may undermine the security of those keys (or
facilitate a much faster factor search that gives preferences to such
primes).
> What OpenSSL does is choose a fresh random number each time. Umm. I
> think (I checked the code a while ago, but not recently).
I don't think this is such a hot idea - for a start you gobble up your
available entropy like crazy zooming about over vast numbers of
candidates, most of which aren't prime. I'd say it was better to use up
good entropy by ("carefully"?) choosing a starting point for the prime
search rather than using it all up on lots of candidates that get thrown
away almost immediately. There are other ways to get round "candidate
bias" after you've got that starting point than purely using up the
entropy pool.
Also, this makes doing low-prime sieves a lot slower as you have to
process them one at a time. When doing sequential (or arithmetic) searches
you can perform low-prime sieves in a large block *much* faster than doing
them individually (I can elaborate if you like) ... as most candidates
sneaking past a low-prime sieve go on to be real primes (using
probabilistic tests) it makes low-prime sieving a major performance
consideration.
As a side note (again, I'll elaborate if anyone gives a hoot) there are
some cool ways to avoid (or lessen) candidate bias whether using
sequential or arithmetic sequences that still allow you to do fast
low-prime sieves on large blocks rather than one at a time. Guess I should
look into the crypto/bn/ code at some point ... something I've done on the
odd occasion when I was left with no alternative, but I try to avoid it as
a rule.
Cheers,
Geoff
----------------------------------------------------------------------
Geoff Thorpe Email: [EMAIL PROTECTED]
Cryptographic Software Engineer, C2Net Europe http://www.int.c2.net
----------------------------------------------------------------------
May I just take this opportunity to say that of all the people I have
EVER emailed, you are definitely one of them.
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
