Repository: randombit/botan
Pull request #2148 (2019-10-12 07:54:01)

Improve speed of prime generation especially for RSA keygen
In RSA keygen we have to verify that p-1 and e are coprime. But this is expensive to compute. So first do a single round of Miller-Rabin primality test; only if that passes do we test coprimality. Improves RSA keygen times notably as it means (almost always) only a single modular inverse must be computed. All times averaged over many keygens:

1024-bit  21.7 ms ->  10.8 ms
2048-bit  92.2 ms ->  57.1 ms
3072-bit 307.6 ms -> 176.9 ms
4096-bit 738.1 ms -> 499.1 ms

Omits Lucas test when generating RSA - Lucas test is slow, and we are never testing adversarial inputs in this case so just M-R seems ok.

Fix random_prime which previously ignored equiv/modulo/coprime arguments when bits <= 16. Instead reject.


Patch:
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;
          }
       }


Test patch:
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);