Repository: randombit/botan
Pull request #2298 (2020-03-06 13:06:46)

Clean up prime generation logic slightly
We were trying to generate safe primes using a weak check on q but actually this was rounded up to 128 bit probability check anyway. So just do that from the start then check p=2*q+1


Patch:
diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index e876b7205..eb5d88069 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -1596,26 +1596,37 @@ class Speed final : public Command
          {
          const size_t coprime = 65537; // simulates RSA key gen
 
-         for(size_t bits : { 1024, 1536 })
+         for(size_t bits : { 256, 384, 512, 768, 1024, 1536 })
             {
             std::unique_ptr<Timer> genprime_timer = make_timer("random_prime " + std::to_string(bits));
+            std::unique_ptr<Timer> gensafe_timer = make_timer("random_safe_prime " + std::to_string(bits));
             std::unique_ptr<Timer> is_prime_timer = make_timer("is_prime " + std::to_string(bits));
 
-            while(genprime_timer->under(runtime) && is_prime_timer->under(runtime))
+            while(gensafe_timer->under(runtime))
                {
                const Botan::BigInt p = genprime_timer->run([&]
                   {
                   return Botan::random_prime(rng(), bits, coprime);
                   });
 
-               const bool ok = is_prime_timer->run([&]
+               if(!is_prime_timer->run([&] { return Botan::is_prime(p, rng(), 64, true); }))
                   {
-                  return Botan::is_prime(p, rng(), 64, true);
+                  error_output() << "Generated prime " << p << " which failed a primality test";
+                  }
+
+               const Botan::BigInt sg = gensafe_timer->run([&]
+                  {
+                  return Botan::random_safe_prime(rng(), bits);
                   });
 
-               if(!ok)
+               if(!is_prime_timer->run([&] { return Botan::is_prime(sg, rng(), 64, true); }))
                   {
-                  error_output() << "Generated prime " << p << " which failed a primality test";
+                  error_output() << "Generated safe prime " << sg << " which failed a primality test";
+                  }
+
+               if(!is_prime_timer->run([&] { return Botan::is_prime(sg / 2, rng(), 64, true); }))
+                  {
+                  error_output() << "Generated prime " << sg/2 << " which failed a primality test";
                   }
 
                // Now test p+2, p+4, ... which may or may not be prime
@@ -1626,6 +1637,7 @@ class Speed final : public Command
                }
 
             record_result(genprime_timer);
+            record_result(gensafe_timer);
             record_result(is_prime_timer);
             }
          }
diff --git a/src/lib/math/numbertheory/make_prm.cpp b/src/lib/math/numbertheory/make_prm.cpp
index 6c2c20718..404e30104 100644
--- a/src/lib/math/numbertheory/make_prm.cpp
+++ b/src/lib/math/numbertheory/make_prm.cpp
@@ -122,9 +122,9 @@ BigInt random_prime(RandomNumberGenerator& rng,
          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;
+            uint8_t b[4];
+            rng.randomize(b, 4);
+            const size_t idx = load_le<uint32_t>(b, 0) % PRIME_TABLE_SIZE;
             const uint16_t small_prime = PRIMES[idx];
 
             if(high_bit(small_prime) == bits)
@@ -135,6 +135,8 @@ BigInt random_prime(RandomNumberGenerator& rng,
 
    const size_t MAX_ATTEMPTS = 32*1024;
 
+   const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);
+
    while(true)
       {
       BigInt p(rng, bits);
@@ -161,15 +163,15 @@ BigInt random_prime(RandomNumberGenerator& rng,
 
          Modular_Reducer mod_p(p);
 
-         /*
-         First do a single M-R iteration to quickly elimate most non-primes,
-         before doing the coprimality check which is expensive
-         */
-         if(is_miller_rabin_probable_prime(p, mod_p, rng, 1) == false)
-            continue;
-
          if(coprime > 1)
             {
+            /*
+            First do a single M-R iteration to quickly elimate most non-primes,
+            before doing the coprimality check which is expensive
+            */
+            if(is_miller_rabin_probable_prime(p, mod_p, rng, 1) == false)
+               continue;
+
             /*
             * Check if p - 1 and coprime are relatively prime, using gcd.
             * The gcd computation is const-time
@@ -181,9 +183,7 @@ BigInt random_prime(RandomNumberGenerator& rng,
          if(p.bits() > bits)
             break;
 
-         const size_t t = miller_rabin_test_iterations(bits, prob, true);
-
-         if(is_miller_rabin_probable_prime(p, mod_p, rng, t) == false)
+         if(is_miller_rabin_probable_prime(p, mod_p, rng, mr_trials) == false)
             continue;
 
          if(prob > 32 && !is_lucas_probable_prime(p, mod_p))
@@ -213,19 +213,21 @@ BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng,
 
    const size_t MAX_ATTEMPTS = 32*1024;
 
+   const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);
+
    while(true)
       {
       BigInt p(keygen_rng, bits);
 
-      // Force lowest and two top bits on
+      // Force high two bits so multiplication always results in expected n bit integer
       p.set_bit(bits - 1);
       p.set_bit(bits - 2);
       p.set_bit(0);
 
-      Prime_Sieve sieve(p, bits);
-
       const word step = 2;
 
+      Prime_Sieve sieve(p, bits);
+
       for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt)
          {
          p += step;
@@ -239,8 +241,8 @@ BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng,
 
          /*
          * 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.
+         * currently a single Miller-Rabin test is faster than computing gcd,
+         * and this eliminates almost all wasted gcd computations.
          */
          if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, 1) == false)
             continue;
@@ -254,9 +256,7 @@ BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng,
          if(p.bits() > bits)
             break;
 
-         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)
+         if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, mr_trials) == true)
             return p;
          }
       }
@@ -271,25 +271,21 @@ BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits)
       throw Invalid_Argument("random_safe_prime: Can't make a prime of " +
                              std::to_string(bits) + " bits");
 
+   const size_t error_bound = 128;
+
    BigInt q, p;
    for(;;)
       {
       /*
-      Generate q == 2 (mod 3)
-
-      Otherwise [q == 1 (mod 3) case], 2*q+1 == 3 (mod 3) and not prime.
-
-      Initially allow a very high error prob (1/2**8) to allow for fast checks,
-      then if 2*q+1 turns out to be a prime go back and strongly check q.
+      Generate q == 2 (mod 3), since otherwise [in the case of q == 1 (mod 3)],
+      2*q+1 == 3 (mod 3) and so certainly not prime.
       */
-      q = random_prime(rng, bits - 1, 0, 2, 3, 8);
+      q = random_prime(rng, bits - 1, 0, 2, 3, error_bound);
       p = (q << 1) + 1;
 
-      if(is_prime(p, rng, 128, true))
+      if(is_prime(p, rng, error_bound, true))
          {
-         // We did only a weak check before, go back and verify q before returning
-         if(is_prime(q, rng, 128, true))
-            return p;
+         return p;
          }
       }
    }


Test patch:
diff --git a/src/scripts/test_cli.py b/src/scripts/test_cli.py
index cafab6a09..4e0f8ab83 100755
--- a/src/scripts/test_cli.py
+++ b/src/scripts/test_cli.py
@@ -269,12 +269,12 @@ def cli_argon2_tests(_tmp_dir):
 def cli_gen_dl_group_tests(_tmp_dir):
 
     pem = """-----BEGIN X9.42 DH PARAMETERS-----
-MIIBJAKBgwVcMHlFVo64S86Y5KrlClZrIibOQ6iKm8Ih3Eb53XoQiSc33GtilRmP
-f7qKIVI86meoJHVU7gtaJk82yAYk6BksmZn0eXvUU7zD8yF/yH3yym0SfI0eH1OC
-2+esfGblePpHCtt5uO56pzIqCIpOq+8gTG7JbFHJvTb8nwmAWFLZvjepAoGDBHOP
-e5A/RNyeXz+16+7Jjh4QOXWo/c6kM0WrIHgFbaIkupRndG5bcy8aCjsbgiIpeWy1
-aNDURFB3UR3q1Si0gA7cvirDOH7lnN3C9zeohq+VPy5L7S3gKLGB1HXY/r2qLKhM
-6ziphMYZxtr+XhsbxbA/+MuNoP/He+kwlGLtDKiBdF4CFjgPiPatvmWssQw2AuZ9
+MIIBJAKBgwTw7LQiLkXJsrgMVQxTPlWaQlYz/raZ+5RtIZe4YluQgRQGPFADLZ/t
+TOYzuIzZJFOcdKtEtrVkxZRGSkjZwKFKLUD6fzSjoC2M2EHktK/y5HsvxBxL4tKr
+q1ffbyPQi+iBLYTZAXygvxj2vWyrvA+/w4nbt1fStCHTDhWjLWqFpV9nAoGDAKzA
+HUu/IRl7OiUtW/dz36gzEJnaYtz4ZtJl0FG8RJiOe02lD8myqW2sVzYqMvKD0LGx
+x9fdSKC1G+aZ/NWtqrQjb66Daf7b0ddDx+bfWTWJ2dOtZd8IL2rmQQJm+JogDi9i
+huVYFicDNQGzi+nEKAzrZ1L/VxtiSiw/qw0IyOuVtz8CFjgPiPatvmWssQw2AuZ9
 mFvAZ/8wal0=
 -----END X9.42 DH PARAMETERS-----"""