| Subject: | Primality testing |
In looking at the key generation, it seems we're using either OpenSSL or using the FIPS 186-3/4 method for generating p and q. I'm going to preface this by saying I'm unclear if we're trying to be compliant or not -- in both cases I think there are improvements possible.
My understanding of OpenSSL is that it does 50 M-R tests, using uniform random bases. This is in theory not enough for FIPS 186-3/4 C.1 when p > 160 bits or p > 1024 bits, but let's pretend we're happy with the results for now.
When Crypt::DSA does not use OpenSSL, it performs 5 to 25 M-R tests using witnesses more or less randomly chosen. This is not enough for FIPS 186-3/4 compliance.
The M-R test wants the bases chosen between 2 and n-2. The isprime_algorithms_with_perl code allows a = 1 and a = n-1. Both should be skipped, although with a large enough n value their chances of occurring are infinitesimal and we effectively perform one fewer test. On the other hand, if witness = n, then it will get passed through and return the wrong answer. The defect is that that we only mod with n if witness > n. This needs to be a >= n or we will indicate composite for primes. This would be completely disastrous if this happened in a real primality test. In our particular usage it's not nearly as bad -- we will just reject a prime and waste time, and like the previous case, the chances are infinitesimal for a 160+ bit number.
One possibility to consider is using Math::Prime::Util, optionally with Math::Prime::Util::GMP for better performance. That contains numerous primality tests. Math::Primality is another option (it requires Math::GMPz). I believe this will be much faster (with Math::Prime::Util::GMP, it's faster than Pari). The point is that not only is this much faster, but it allows us to have strict compliance with fewer tests. When I say "much faster" I mean t/03-keygen.t goes from over 2 minutes to half a second.
Another option if you do not need strict FIPS 186-3 compliance is to use MPU's random_proven_prime, random_maurer_prime, or random_nbit_prime.
- None of these use the FIPS 186-3 Appendix A.1 method of producing the primes.
- The first two are proven prime, the last has passed the extra strong BPSW test for primality.
- They get randomness from Bytes::Random::Secure, which in turn will use Win32, /dev/random, EGD, /dev/urandom, or a userspace method depending on what is available.
- To handle the Seed parameter we'd need to hand in our own random function, which isn't hard.
The proven prime methods don't need extra tests (they give a certificate), but with random_nbit prime we could follow the FIPS 186-3 table C.1 guidelines and add something like:
next unless is_strong_pseudoprime($p, map { irand() } 1 .. $n_extra_tests);
Looking forward, some possibilities include:
- adding the the Shawe-Taylor provable algorithm to MPU. This would make a nice NIST-approved provable prime algorithm.
- Create some code that generates FIPS 186-3 approved random primes using a simple SHA1 or SHA2.
- Would any of the information in Loebenberter and Nüsken 2012 aregarding methods for generating RSA pairs be useful for DSA pairs?