Update Miller–Rabin check numbers.

This imports upstream's be4e1f79f631e49c76d02fe4644b52f907c374b2.

Change-Id: If0c4f066ba0ce540beaddd6a3e2540165d949dd2
Reviewed-on: https://boringssl-review.googlesource.com/31024
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: David Benjamin <davidben@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>

crypto/fipsmodule/bn/prime.c

diff --git a/crypto/fipsmodule/bn/prime.c b/crypto/fipsmodule/bn/prime.c
index 903d6b1..b417d4f 100644
--- a/crypto/fipsmodule/bn/prime.c
+++ b/crypto/fipsmodule/bn/prime.c
@@ -311,11 +311,57 @@
 };
 
 // BN_prime_checks_for_size returns the number of Miller-Rabin iterations
-// necessary for a 'bits'-bit prime, in order to maintain an error rate greater
-// than the security level for an RSA prime of that many bits (calculated using
-// the FIPS SP 800-57 security level and 186-4 Section F.1; original paper:
-// Damgaard, Landrock, Pomerance: Average case error estimates for the strong
-// probable prime test. -- Math. Comp. 61 (1993) 177-194)
+// necessary for a 'bits'-bit prime.
+//
+//
+// This table is generated using the algorithm of FIPS PUB 186-4
+// Digital Signature Standard (DSS), section F.1, page 117.
+// (https://dx.doi.org/10.6028/NIST.FIPS.186-4)
+// The following magma script was used to generate the output:
+// securitybits:=125;
+// k:=1024;
+// for t:=1 to 65 do
+//   for M:=3 to Floor(2*Sqrt(k-1)-1) do
+//     S:=0;
+//     // Sum over m
+//     for m:=3 to M do
+//       s:=0;
+//       // Sum over j
+//       for j:=2 to m do
+//         s+:=(RealField(32)!2)^-(j+(k-1)/j);
+//       end for;
+//       S+:=2^(m-(m-1)*t)*s;
+//     end for;
+//     A:=2^(k-2-M*t);
+//     B:=8*(Pi(RealField(32))^2-6)/3*2^(k-2)*S;
+//     pkt:=2.00743*Log(2)*k*2^-k*(A+B);
+//     seclevel:=Floor(-Log(2,pkt));
+//     if seclevel ge securitybits then
+//       printf "k: %5o, security: %o bits  (t: %o, M: %o)\n",k,seclevel,t,M;
+//       break;
+//     end if;
+//   end for;
+//   if seclevel ge securitybits then break; end if;
+// end for;
+//
+// It can be run online at: http://magma.maths.usyd.edu.au/calc
+// And will output:
+// k:  1024, security: 129 bits  (t: 6, M: 23)
+// k is the number of bits of the prime, securitybits is the level we want to
+// reach.
+// prime length | RSA key size | # MR tests | security level
+// -------------+--------------|------------+---------------
+//  (b) >= 6394 |     >= 12788 |          3 |        256 bit
+//  (b) >= 3747 |     >=  7494 |          3 |        192 bit
+//  (b) >= 1345 |     >=  2690 |          4 |        128 bit
+//  (b) >= 1080 |     >=  2160 |          5 |        128 bit
+//  (b) >=  852 |     >=  1704 |          5 |        112 bit
+//  (b) >=  476 |     >=   952 |          5 |         80 bit
+//  (b) >=  400 |     >=   800 |          6 |         80 bit
+//  (b) >=  347 |     >=   694 |          7 |         80 bit
+//  (b) >=  308 |     >=   616 |          8 |         80 bit
+//  (b) >=   55 |     >=   110 |         27 |         64 bit
+//  (b) >=    6 |     >=    12 |         34 |         64 bit
 static int BN_prime_checks_for_size(int bits) {
   if (bits >= 3747) {
     return 3;
@@ -329,16 +375,16 @@
   if (bits >= 400) {
     return 6;
   }
+  if (bits >= 347) {
+    return 7;
+  }
   if (bits >= 308) {
     return 8;
   }
-  if (bits >= 205) {
-    return 13;
+  if (bits >= 55) {
+    return 27;
   }
-  if (bits >= 155) {
-    return 19;
-  }
-  return 28;
+  return 34;
 }
 
 // num_trial_division_primes returns the number of primes to try with trial