diff options
| -rw-r--r-- | CHANGELOG.txt | 1 | ||||
| -rw-r--r-- | rsa/prime.py | 40 | ||||
| -rw-r--r-- | tests/test_prime.py | 14 |
3 files changed, 47 insertions, 8 deletions
diff --git a/CHANGELOG.txt b/CHANGELOG.txt index 315bb4a..6488615 100644 --- a/CHANGELOG.txt +++ b/CHANGELOG.txt @@ -12,6 +12,7 @@ Version 4.0 - in development - Removed CLI commands that use the VARBLOCK/bigfile format. - Ensured that PublicKey.save_pkcs1() and PrivateKey.save_pkcs1() always return bytes. - Dropped support for Python 2.6 +- Miller-Rabin iterations determined by bitsize of key. Version 3.4.2 - released 2016-03-29 diff --git a/rsa/prime.py b/rsa/prime.py index 94d1ef8..29fa498 100644 --- a/rsa/prime.py +++ b/rsa/prime.py @@ -20,6 +20,7 @@ Implementation based on the book Algorithm Design by Michael T. Goodrich and Roberto Tamassia, 2002. """ +import rsa.common import rsa.randnum __all__ = ['getprime', 'are_relatively_prime'] @@ -37,6 +38,32 @@ def gcd(p, q): return p +def get_primality_testing_rounds(number): + """Returns minimum number of rounds for Miller-Rabing primality testing, + based on number bitsize. + + According to NIST FIPS 186-4, Appendix C, Table C.3, minimum number of + rounds of M-R testing, using an error probability of 2 ** (-100), for + different p, q bitsizes are: + * p, q bitsize: 512; rounds: 7 + * p, q bitsize: 1024; rounds: 4 + * p, q bitsize: 1536; rounds: 3 + See: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf + """ + + # Calculate number bitsize. + bitsize = rsa.common.bit_size(number) + # Set number of rounds. + if bitsize >= 1536: + return 3 + if bitsize >= 1024: + return 4 + if bitsize >= 512: + return 7 + # For smaller bitsizes, set arbitrary number of rounds. + return 10 + + def miller_rabin_primality_testing(n, k): """Calculates whether n is composite (which is always correct) or prime (which theoretically is incorrect with error probability 4**-k), by @@ -109,14 +136,11 @@ def is_prime(number): if not (number & 1): return False - # According to NIST FIPS 186-4, Appendix C, Table C.3, minimum number of - # rounds of M-R testing, using an error probability of 2 ** (-100), for - # different p, q bitsizes are: - # * p, q bitsize: 512; rounds: 7 - # * p, q bitsize: 1024; rounds: 4 - # * p, q bitsize: 1536; rounds: 3 - # See: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf - return miller_rabin_primality_testing(number, 7) + # Calculate minimum number of rounds. + k = get_primality_testing_rounds(number) + + # Run primality testing with (minimum + 1) rounds. + return miller_rabin_primality_testing(number, k + 1) def getprime(nbits): diff --git a/tests/test_prime.py b/tests/test_prime.py index 173c991..44d8d71 100644 --- a/tests/test_prime.py +++ b/tests/test_prime.py @@ -74,3 +74,17 @@ class PrimeTest(unittest.TestCase): self.assertEqual([], randints) finally: rsa.randnum.randint = orig_randint + + def test_get_primality_testing_rounds(self): + """Test round calculation for primality testing.""" + + self.assertEquals(rsa.prime.get_primality_testing_rounds(1 << 63), 10) + self.assertEquals(rsa.prime.get_primality_testing_rounds(1 << 127), 10) + self.assertEquals(rsa.prime.get_primality_testing_rounds(1 << 255), 10) + self.assertEquals(rsa.prime.get_primality_testing_rounds(1 << 511), 7) + self.assertEquals(rsa.prime.get_primality_testing_rounds(1 << 767), 7) + self.assertEquals(rsa.prime.get_primality_testing_rounds(1 << 1023), 4) + self.assertEquals(rsa.prime.get_primality_testing_rounds(1 << 1279), 4) + self.assertEquals(rsa.prime.get_primality_testing_rounds(1 << 1535), 3) + self.assertEquals(rsa.prime.get_primality_testing_rounds(1 << 2047), 3) + self.assertEquals(rsa.prime.get_primality_testing_rounds(1 << 4095), 3) |