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.
>
> 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.
No, adding one round halves the chance (actually, I think it quarters it
with the test OpenSSL uses, but I was hoping to get a change to look
closer at this stuff before I started discussing it :-).
> However I find this odd, because here we have these 1024 bit primes chosen
> 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)
Eh? Why do you say that?
> but OpenSSL only
> uses 50 rounds of primality testing doesn't it? Which means that only 1 in
> 2^78 "primes" actually are primes. Has anyone considered the attacks that
> might be possible due to these non-primes?
What it means is that there's a 1 in 2^50 chance (or perhaps 1 in 2^100)
that any particular prime is actually not prime. If my lifetime
requirement for primes is 2^20 of them (1,000,000 odd) then there's
still a tiny chance that a single one of those will turn out to be
non-prime.
Cheers,
Ben.
--
http://www.apache-ssl.org/ben.html
"My grandfather once told me that there are two kinds of people: those
who work and those who take the credit. He told me to try to be in the
first group; there was less competition there."
- Indira Gandhi
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
