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
