diff options
| -rw-r--r-- | src/lib/math/numbertheory/make_prm.cpp | 96 | ||||
| -rwxr-xr-x | src/scripts/test_cli.py | 16 | ||||
| -rw-r--r-- | src/tests/test_bigint.cpp | 10 |
3 files changed, 73 insertions, 49 deletions
diff --git a/src/lib/math/numbertheory/make_prm.cpp b/src/lib/math/numbertheory/make_prm.cpp index 67bdcd678..4a67a1377 100644 --- a/src/lib/math/numbertheory/make_prm.cpp +++ b/src/lib/math/numbertheory/make_prm.cpp @@ -1,6 +1,6 @@ /* * Prime Generation -* (C) 1999-2007,2018 Jack Lloyd +* (C) 1999-2007,2018,2019 Jack Lloyd * * Botan is released under the Simplified BSD License (see license.txt) */ @@ -9,6 +9,8 @@ #include <botan/rng.h> #include <botan/internal/bit_ops.h> #include <botan/loadstor.h> +#include <botan/reducer.h> +#include <botan/internal/primality.h> #include <algorithm> namespace Botan { @@ -92,35 +94,42 @@ BigInt random_prime(RandomNumberGenerator& rng, throw Invalid_Argument("random_prime Invalid value for equiv/modulo"); // Handle small values: - if(bits <= 1) - { - throw Invalid_Argument("random_prime: Can't make a prime of " + - std::to_string(bits) + " bits"); - } - else if(bits == 2) - { - return ((rng.next_byte() % 2) ? 2 : 3); - } - else if(bits == 3) - { - return ((rng.next_byte() % 2) ? 5 : 7); - } - else if(bits == 4) - { - return ((rng.next_byte() % 2) ? 11 : 13); - } - else if(bits <= 16) + + if(bits <= 16) { - for(;;) + if(equiv != 1 || modulo != 2 || coprime != 0) + throw Not_Implemented("random_prime equiv/modulo/coprime options not usable for small primes"); + + if(bits <= 1) { - // This is slightly biased, but for small primes it does not seem to matter - const uint8_t b0 = rng.next_byte(); - const uint8_t b1 = rng.next_byte(); - const size_t idx = make_uint16(b0, b1) % PRIME_TABLE_SIZE; - const uint16_t small_prime = PRIMES[idx]; - - if(high_bit(small_prime) == bits) - return small_prime; + throw Invalid_Argument("random_prime: Can't make a prime of " + + std::to_string(bits) + " bits"); + } + else if(bits == 2) + { + return ((rng.next_byte() % 2) ? 2 : 3); + } + else if(bits == 3) + { + return ((rng.next_byte() % 2) ? 5 : 7); + } + else if(bits == 4) + { + return ((rng.next_byte() % 2) ? 11 : 13); + } + else + { + for(;;) + { + // This is slightly biased, but for small primes it does not seem to matter + const uint8_t b0 = rng.next_byte(); + const uint8_t b1 = rng.next_byte(); + const size_t idx = make_uint16(b0, b1) % PRIME_TABLE_SIZE; + const uint16_t small_prime = PRIMES[idx]; + + if(high_bit(small_prime) == bits) + return small_prime; + } } } @@ -154,7 +163,13 @@ BigInt random_prime(RandomNumberGenerator& rng, sieve.step(modulo); - if(sieve.passes(true) == false) + // p can be even if modulo is odd, continue on in that case + if(p.is_even() || sieve.passes(true) == false) + continue; + + Modular_Reducer mod_p(p); + + if(is_miller_rabin_probable_prime(p, mod_p, rng, 1) == false) continue; if(coprime > 1) @@ -166,13 +181,20 @@ BigInt random_prime(RandomNumberGenerator& rng, * key generation, though RSA keygen should be using generate_rsa_prime. */ if(inverse_mod(p - 1, coprime).is_zero()) + { continue; + } } if(p.bits() > bits) break; - if(is_prime(p, rng, prob, true)) + const size_t t = miller_rabin_test_iterations(bits, prob, true); + + if(is_miller_rabin_probable_prime(p, mod_p, rng, t) == false) + continue; + + if(is_lucas_probable_prime(p, mod_p)) return p; } } @@ -227,6 +249,16 @@ BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng, if(sieve.passes() == false) continue; + Modular_Reducer mod_p(p); + + /* + * Do a single primality test first before checking coprimality, since + * currently a single Miller-Rabin test is faster than computing modular + * inverse, and this eliminates almost all wasted modular inverses. + */ + if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, 1) == false) + continue; + /* * Check if p - 1 and coprime are relatively prime by computing the inverse. * @@ -252,7 +284,9 @@ BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng, if(p.bits() > bits) break; - if(is_prime(p, prime_test_rng, prob, true)) + const size_t t = miller_rabin_test_iterations(bits, prob, true); + + if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, t) == true) return p; } } diff --git a/src/scripts/test_cli.py b/src/scripts/test_cli.py index e449bb74f..ae3ceed18 100755 --- a/src/scripts/test_cli.py +++ b/src/scripts/test_cli.py @@ -251,12 +251,12 @@ def cli_argon2_tests(_tmp_dir): def cli_gen_dl_group_tests(_tmp_dir): pem = """-----BEGIN X9.42 DH PARAMETERS----- -MIIBJAKBgwTw7LQiLkXJsrgMVQxTPlWaQlYz/raZ+5RtIZe4YluQgRQGPFADLZ/t -TOYzuIzZJFOcdKtEtrVkxZRGSkjZwKFKLUD6fzSjoC2M2EHktK/y5HsvxBxL4tKr -q1ffbyPQi+iBLYTZAXygvxj2vWyrvA+/w4nbt1fStCHTDhWjLWqFpV9nAoGDAKzA -HUu/IRl7OiUtW/dz36gzEJnaYtz4ZtJl0FG8RJiOe02lD8myqW2sVzYqMvKD0LGx -x9fdSKC1G+aZ/NWtqrQjb66Daf7b0ddDx+bfWTWJ2dOtZd8IL2rmQQJm+JogDi9i -huVYFicDNQGzi+nEKAzrZ1L/VxtiSiw/qw0IyOuVtz8CFjgPiPatvmWssQw2AuZ9 +MIIBJAKBgwVcMHlFVo64S86Y5KrlClZrIibOQ6iKm8Ih3Eb53XoQiSc33GtilRmP +f7qKIVI86meoJHVU7gtaJk82yAYk6BksmZn0eXvUU7zD8yF/yH3yym0SfI0eH1OC +2+esfGblePpHCtt5uO56pzIqCIpOq+8gTG7JbFHJvTb8nwmAWFLZvjepAoGDBHOP +e5A/RNyeXz+16+7Jjh4QOXWo/c6kM0WrIHgFbaIkupRndG5bcy8aCjsbgiIpeWy1 +aNDURFB3UR3q1Si0gA7cvirDOH7lnN3C9zeohq+VPy5L7S3gKLGB1HXY/r2qLKhM +6ziphMYZxtr+XhsbxbA/+MuNoP/He+kwlGLtDKiBdF4CFjgPiPatvmWssQw2AuZ9 mFvAZ/8wal0= -----END X9.42 DH PARAMETERS-----""" @@ -904,7 +904,7 @@ def cli_pk_encrypt_tests(tmp_dir): test_cli("keygen", ["--algo=RSA", "--provider=base", "--params=2048", "--output=%s" % (rsa_priv_key)], "") - key_hash = "891A3AA179639796B7A6348D2F1C3A8CC7E0FFED38BAE29143DF9B8A55391F28" + key_hash = "72AF3227EF57A728E894D54623EB8E2C0CD11A4A98BF2DF32DB052BF60897873" test_cli("hash", ["--no-fsname", "--algo=SHA-256", rsa_priv_key], key_hash) test_cli("pkcs8", ["--pub-out", "%s/rsa.priv" % (tmp_dir), "--output=%s" % (rsa_pub_key)], "") @@ -914,7 +914,7 @@ def cli_pk_encrypt_tests(tmp_dir): # Because we used a fixed DRBG for each invocation the same ctext is generated each time rng_output_hash = "32F5E7B61357DE8397EFDA1E598379DFD5EE21767BDF4E2A435F05117B836AC6" - ctext_hash = "5F45F360CF431C3E1BC126B1DB20CFE7A869AE7B67484A64F426A6349245EB51" + ctext_hash = "FF1F0EEC2C42DD61D78505C5DF624A19AE6FE2BAB0B8F7D878C7655D54C68FE0" test_cli("hash", ["--no-fsname", "--algo=SHA-256", input_file], rng_output_hash) diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp index 3ea57d584..283b078ff 100644 --- a/src/tests/test_bigint.cpp +++ b/src/tests/test_bigint.cpp @@ -117,16 +117,6 @@ class BigInt_Unit_Tests final : public Test result.test_eq("P is prime", Botan::is_prime(p, Test::rng()), true); } - for(size_t bits = 5; bits <= 32; ++bits) - { - const BigInt last_p = p; - p = Botan::random_prime(Test::rng(), bits, last_p); - - result.test_eq("Relatively prime", Botan::gcd(last_p, p), 1); - result.test_eq("Expected bit size", p.bits(), bits); - result.test_eq("P is prime", Botan::is_prime(p, Test::rng()), true); - } - const size_t safe_prime_bits = 65; const BigInt safe_prime = Botan::random_safe_prime(Test::rng(), safe_prime_bits); result.test_eq("Safe prime size", safe_prime.bits(), safe_prime_bits); |