Hi there,
On Tue, 30 Nov 1999, Ben Laurie wrote:
> Geoff Thorpe wrote:
> > Will post more later when I have a chance.
>
> No need (at least, not for me). I understand. Quite neat, but I still
> have to believe that it doesn't introduce significant bias.
>
> BTW, it occurs to me that one could extend the sieving idea to
> simultaneously sieve (p-1)/2 (or 2p+1) so that safe primes can be
> generated more rapidly...
Good point. OK, I did some examination ... here goes ...
OpenSSL is already using some "fast" low-prime sieving using the algorithm
mentioned in handbook of applied crypto - the source comments suggest he
pinched this off PGP + or - some of his own modifications. Whatever. The
current approach is to run a low prime sieve from a random starting point
(builds up the array of remainders) and use that to scoot along the
sequential odd numbers looking for a "probable prime" that can be handed
back for probabilistic testing. So there's all the bias we discussed about
using sequential searches, but there's all the penalty of having to
restart a low-prime sieve each time a candidate appears from the
probable_prime() function. This varies wildly, and depends on key-size of
course, but it typically requires quite a few candidates before one is
verified to be prime by probabilistic testing. That's a lot of *new* low
prime sieves. hmmm ...
When generating a key (eg. ./openssl genrsa ...) the "." characters
indicate the discovery of a probable prime ("candidate") using the low
prime sieve, a "+" indicates the candidate passing a probabilistic test.
My tests last night generated a *lot* of RSA keys and I never once had a
"+" that did not lead to a prime - so in short, quite a few candidates can
get through the low prime sieve, but generally only true primes make it
through even one probabilistic test. No surprises there.
This led me to some experimentation ... I can send on my hacked apart
bn_prime.c if you want to run some similar tests yourself. I was curious
how much overhead redoing the "random starting point" was, given that a
new low-prime sieve was being started for each candidate, so I modified
BN_generate_prime to not generate *a* candidate, but to generate the first
*400* candidates that pass the low-prime sieve from one random starting
point and then run them through the probabilistic tests. All this really
did was cut the startup cost of a new low-prime sieve. However, on a
Pentium Pro 200, generating 400 candidates (512-bit for a 1024-bit RSA
key) took less than the blink of an eye - (I still had the enter button
down when the probabilistic testing began). Also, because it did not have
to restart low prime sieving for each candidate, I benchmarked with genrsa
to find that key-generation took 80% of the time of the current
implementation. NB: That was after some long-running tests so it's a
reasonably reliable stat. The advantage tapered off to about 92% for
4096-bit RSA keygen (2048-bit primes). The implication, although I haven't
tested this (no time!) is that the improvement is probably more dramatic
with smaller keys, so it may be handy for generating temporary 512-bit RSA
keys on the fly.
Anyway, my quick and hurried conclusions are;
(a) we're already biasing towards sequential searches because whatever
prime makes it through the probabilistic testing was selected using
sequential searching in a low-prime sieve. In fact *all* candidates are
generated in that fashion.
(b) the sequential searching could be modified to use arithmetic sequences
with a much larger period than the current "2" (:-)) to help rectify that
a bit (and the period can be random itself).
(c) we could then make BN_generate_prime generate a bank of a candidates
from the arithmetic search rather than restarting each time. Given "n-bit"
prime searches, the expected number of candidates (and deviation thereof)
before finding a true prime is relatively easy to analyse, so we could
generate a "safe" number of candidates (based on "n") to too many repeat
sievings without going to extremes.
(d) there is nothing at all to prevent the probabilistic testing leaping
around the generated candidates rather than checking them linearly. Given
a bank of 400 candidates, only the first one is significantly "biased" and
that is dubious in an arithmetic search of random period - additionally
checking the sequential candidates (over period "k") in a psuedo-random
order helps further cut the risk of bias.
(e) this would almost certainly be faster, and would address a number of
potential biases in the key-space.
(f) I'd rather see a much large list of low-primes in the initial sieving.
Sequential (or arithmetic) sieving after "startup" is insignificant
compared to the "startup" itself, and that "startup" is small compared to
the probabilistic testing. If we can slim down the number of non-prime
candidates that slip through our (fast) low-prime sieve I think it would
be an improvement. For almost all architectures, BN_ULONG is large enough
to cope with a *lot* of low primes.
Please don't take any of the above as read, anyone who has the time should
really have a crack at this too and check if they get the same results on
this as me.
Cheers,
Geoff
PS: As a side issue, I still think there's the potential to do the
low-prime sieving faster and using less memory, and it could also grow
with lower complexity than the current implementation if the number of
low-primes in the sieve increases. However, it makes little or no
difference to the above arguments - and at 3am one doesn't look for new
distractions if at all possible.
<sigh>
----------------------------------------------------------------------
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]
