Add some notes on RSA key generation performance.

Change-Id: I8c0cadddcfc7d8b14adbc3ed3b75332859deea42
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/38166
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Adam Langley <agl@google.com>

crypto/fipsmodule/bn/prime.c

diff --git a/crypto/fipsmodule/bn/prime.c b/crypto/fipsmodule/bn/prime.c
index 404139e..37a73bf 100644
--- a/crypto/fipsmodule/bn/prime.c
+++ b/crypto/fipsmodule/bn/prime.c
@@ -709,11 +709,49 @@
 int BN_primality_test(int *out_is_probably_prime, const BIGNUM *w,
                       int iterations, BN_CTX *ctx, int do_trial_division,
                       BN_GENCB *cb) {
-  *out_is_probably_prime = 0;
+  // This function's secrecy and performance requirements come from RSA key
+  // generation. We generate RSA keys by selecting two large, secret primes with
+  // rejection sampling.
+  //
+  // We thus treat |w| as secret if turns out to be a large prime. However, if
+  // |w| is composite, we treat this and |w| itself as public. (Conversely, if
+  // |w| is prime, that it is prime is public. Only the value is secret.) This
+  // is fine for RSA key generation, but note it is important that we use
+  // rejection sampling, with each candidate prime chosen independently. This
+  // would not work for, e.g., an algorithm which looked for primes in
+  // consecutive integers. These assumptions allow us to discard composites
+  // quickly. We additionally treat |w| as public when it is a small prime to
+  // simplify trial decryption and some edge cases.
+  //
+  // One RSA key generation will call this function on exactly two primes and
+  // many more composites. The overall cost is a combination of several factors:
+  //
+  // 1. Checking if |w| is divisible by a small prime is much faster than
+  //    learning it is composite by Miller-Rabin (see below for details on that
+  //    cost). Trial division by p saves 1/p of Miller-Rabin calls, so this is
+  //    worthwhile until p exceeds the ratio of the two costs.
+  //
+  // 2. For a random (i.e. non-adversarial) candidate large prime and candidate
+  //    witness, the probability of false witness is very low. (This is why FIPS
+  //    186-4 only requires a few iterations.) Thus composites not discarded by
+  //    trial decryption, in practice, cost one Miller-Rabin iteration. Only the
+  //    two actual primes cost the full iteration count.
+  //
+  // 3. A Miller-Rabin iteration is a modular exponentiation plus |a| additional
+  //    modular squares, where |a| is the number of factors of two in |w-1|. |a|
+  //    is likely small (the distribution falls exponentially), but it is also
+  //    potentially secret, so we loop up to its log(w) upper bound when |w| is
+  //    prime. When |w| is composite, we break early, so only two calls pay this
+  //    cost. (Note that all calls pay the modular exponentiation which is,
+  //    itself, log(w) modular multiplications and squares.)
+  //
+  // 4. While there are only two prime calls, they multiplicatively pay the full
+  //    costs of (2) and (3).
+  //
+  // 5. After the primes are chosen, RSA keys derive some values from the
+  //    primes, but this cost is negligible in comparison.
 
-  // To support RSA key generation, this function should treat |w| as secret if
-  // it is a large prime. Composite numbers are discarded, so they may return
-  // early.
+  *out_is_probably_prime = 0;
 
   if (BN_cmp(w, BN_value_one()) <= 0) {
     return 1;