Hi,
I'm un-CCing Bruce S from this ...
On Mon, 29 Nov 1999, Clifford Heath wrote:
> Mark Shuttleworth wrote:
> > > I don't really understand the math, but it seems to me that it finds
> > > prime candidates then tests them for primeness. Is there a way to make
> > > it test even more rigorously?
>
> And Ben Laurie answered:
> > In short, probably. But that tends to be expensive.
So far so good. However I think I might have either lost my bearings
altogether, or someone else has got their wires a bit crossed. Either way,
this got a bit weird all of a sudden...
With regard to Mark's original question - already with the way OpenSSL
does it's prime number generation, I don't think you really need to get
too worried about "testing it more rigorously". I interpreted your
original question as being about searching for primes more securely (you
mentioned usually using specialised hardware for this?) rather than adding
a couple more zeroes to the chances of getting a false prime.
I don't have any of the oft-quoted stats, but it goes something like this;
if very many people generated very many primes very very quickly, you'd be
extremely unlikely to hit a false prime anytime this century ... er, or
the next one for that matter. Notice the use of actual numbers. :-)
The primality testing used in OpenSSL will be sending your probabilities
up into the kind of numbers astronomers get a kick out of - and if a false
prime *is* generated it would (I think) probably manifest itself by not
working, rather than working insecurely (the existence of inverses and
other mathematical niceties would fall down and who knows what else).
Without any low-prime sieving, the probabilistic tests add about 75% more
certainty with each round. However there are some results available in
"Handbook of Applied Cryptography", and probably Bruce's "Applied
Cryptography" too, to do with how the probabilities work if you rule out
all low prime-factors in a given range. If those low-primes are ruled out
the maths gets a whole lot more powerful. Sufficit to say that with a
low-prime sieve plus 5 rounds of (Miller-Rabin? Fermat?) probabilistic
testing, it would be ... how to make this sound as enormous as it should
... ***unlikely*** ... to have a false-prime slip through the net.
> You simply need to increase the number of rounds of primality testing,
> say, double it. That doubles the cost, and each extra round approximately
> halves the chance of getting a non-prime.
If it gets through the current number of primality tests and still looks
prime, it is *extremely* unlikely it is not a prime ... and as such you
could throw another couple of tests at it because you'll not be needing to
use them on any other candidates. It's not chosen as 5 for performance
reasons, it's chosen because you have to stop somewhere and anything
higher than 4 or 5 is just getting so paranoid as to be ridiculous :-) It
is a rare occurance to get a false-prime slip through the *first*
probabilistic test after passing through the low-prime sieve. The 5 rounds
OpenSSL uses is to try and make sure the sun explodes before it will pass
a false-prime. BTW: I think each round improves certainty by 4 not 2 and
that's if you forget that you did a low-prime sieve. With a low-prime
sieve, the improvement is (I think) much higher.
however, if you want more testing ... specify "checks" in;
crypto/bn/bn_prime.c: line 154;
int BN_is_prime(BIGNUM *a, int checks, void (*callback)(int,int,void *),
BN_CTX *ctx_passed, void *cb_arg)
but if you just want to change the default used in OpenSSL, it's in
crypto/bn/bn.h: line 286;
#define BN_prime_checks (5)
> However I find this odd, because here we have these 1024 bit primes chosen
If you mean for 1024-bit keys then it's two 512-bit primes.
> from what we consider to be a space containing very roughly 2^128 primes
> (i.e. our 1024 bit prime contains ~128 bits of entropy), but OpenSSL only
> uses 50 rounds of primality testing doesn't it? Which means that only 1 in
??? 50 rounds??? I doubt it very much. This doesn't affect the entropy
arguments for how randomly we choose our primes. It affects how
astronomically sure we wish to be that the "prime" we've stumbled onto is
genuinely prime and not just fooling with our primality tests. The entropy
stuff you're talking about has nothing to do with the number of primality
testing rounds, it has to do with the potential key-space we are working
in?!
> 2^78 "primes" actually are primes. Has anyone considered the attacks that
> might be possible due to these non-primes?
I think you might be a little bit confused? Or perhaps you're teasing? :-)
> Cc'd to Bruce Schneier in the hope it might interest him to answer...
Hmm ... I somehow doubt it, although it would amusing to hear his
reaction. Only 1 in 2^78 OpenSSL-generated primes are actually prime ...
that's a very interesting theory ... so the astronomical part now is to
find an RSA key out there that actually has real primes in it. :-)
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]
