bug in probably_prime; probably harmless

bug in probably_prime; probably harmless

[Russ Cox]

Andrey pointed out a bug in libsec's probably_prime.
Essentially, probably_prime uses only a single
repetition of the Miller-Rabin test even when nrep > 1.
Typically people try to run with nrep = 20 or so.
Doing just one test is, at the least, disobeying the
intent of the call.  (By the way, it's very easy to
see how one would make this mistake trying to translate
Knuth's inimitable English text pseudocode.)

I've just checked a fixed version into plan9port,
and the fixed version went into Plan 9 and Inferno
over the weekend.

In theory this bug could result in false positives, claiming
a number is prime when in fact it is not.  In practice,
the smallprimetest eliminates obvious mistakes without
any repetitions, and for random inputs of the size we use
in cryptographic keys, the probability of a single Miller-Rabin
round being wrong is actually more like 1 in 10^80 than
like 1 in 4.  Empirically, I've ran both old and new
code side by side for a few million random inputs and
never saw the two differ.  Even though we typically try
to use 20 or so rounds for cryptographic keys, that's
intentional overkill.  Some texts (e.g., CLR) argue that
three rounds is enough, and some papers suggest that
only the first round has any value.

Regardless, the bug is fixed.  I've changed the plan9port
factotum to double-check that any DSA and RSA private
keys it loads are actually using prime numbers, so if your
key file still loads into the plan9port factotum, you're not
affected.  (If you are affected, I've be very interested to
hear about it, since that would either make you very very
(un)lucky or make the papers I read over the weekend wrong.)

Russ

Re: [9fans] bug in probably_prime; probably harmless

[Anh Hai Trinh]

On Fri, Mar 12, 2010 at 9:13 AM, Russ Cox <rsc@swtch.com> wrote:
>
> In theory this bug could result in false positives, claiming
> a number is prime when in fact it is not.  In practice,
> the smallprimetest eliminates obvious mistakes without
> any repetitions, and for random inputs of the size we use
> in cryptographic keys, the probability of a single Miller-Rabin
> round being wrong is actually more like 1 in 10^80 than
> like 1 in 4.  Empirically, I've ran both old and new
> code side by side for a few million random inputs and
> never saw the two differ.  Even though we typically try
> to use 20 or so rounds for cryptographic keys, that's
> intentional overkill.  Some texts (e.g., CLR) argue that
> three rounds is enough, and some papers suggest that
> only the first round has any value.
>

This paper has a definitive table of upper bounds for the probability
of a k-bit random odd number from a uniformly distribution to pass t
iterations of the test:

Damgård, I.; Landrock, P.; and Pomerance, C. "Average Case Error
Estimates for the Strong Probably Prime Test." Math. Comput. 61,
177-194, 1993.

For instance:
P(600-bit, 1-iteration) <= 2^-75, which is good, but
P(100-bit, 1-iteration) <= 2^-5, so more iterations are really needed here as
P(100-bit, 10-iteration) <= 2^-44

As for the code, since you are already doing a Fermat test, you might
as well do an iteration with base 2, which takes the same time and
gives much stronger result.

Also if you do that, you can reduce the (boy, really really long) list
of smallprimes to this
<http://www.research.att.com/~njas/sequences/A001262>, as the base 2
strong-pseudoprime test will really weeds out composites in a few
instructions anyway.

-- 
// aht