Damn, forgot to make one of the points I thought was most relevant in all
that!
On Tue, 30 Nov 1999, Geoff Thorpe wrote:
> 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.
I wish I had my favourite references handy but alas they're 10000 miles
away. Anyhow, I think it would be worth investigating some of the cheaper
probabilistic tests as a "first shot" test on candidates before running
them through the 4 or 5 current (slower) tests. Keygen can require the
testing of quite a few candidates before hitting a prime and we are using
a strong test that very rarely lets a non-prime get through even *1*
iteration. I can't off the top of my head recall which tests are which,
but one or two are "less strong" but faster, particularly with
pre-determined "witness" values (I think "3" was mentioned in one case),
and if a faster test were doing most of the grunt work until a candidate
slips through to get the full treatment from BN_is_prime() I think it
could make some improvement.
Just a thought.
----------------------------------------------------------------------
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]
