external/boringssl: Sync to a7a75f208caea8a303615724d4cc5f4e8dfb9695.

This includes the following changes:

https://boringssl.googlesource.com/boringssl/+log/4ca15d5dcbe6e8051a4654df7c971ea8307abfe0..a7a75f208caea8a303615724d4cc5f4e8dfb9695

Test: atest CtsLibcoreTestCases
Change-Id: Ie997cc5a7f8f03b271d58b5d89d43f67e4df68b0

25 files changed, 920 insertions, 297 deletions

diff --git a/src/crypto/CMakeLists.txt b/src/crypto/CMakeLists.txt
index b874c621..d84e5457 100644
--- a/src/crypto/CMakeLists.txt
+++ b/src/crypto/CMakeLists.txt
@@ -268,6 +268,7 @@ add_library(
   ecdh_extra/ecdh_extra.c
   ecdsa_extra/ecdsa_asn1.c
   ec_extra/ec_asn1.c
+  ec_extra/ec_derive.c
   err/err.c
   err_data.c
   engine/engine.c
diff --git a/src/crypto/curve25519/asm/x25519-asm-arm.S b/src/crypto/curve25519/asm/x25519-asm-arm.S
index 9a26adda..41bc0c6e 100644
--- a/src/crypto/curve25519/asm/x25519-asm-arm.S
+++ b/src/crypto/curve25519/asm/x25519-asm-arm.S
@@ -2129,8 +2129,8 @@ mov sp,r12
 vpop {q4,q5,q6,q7}
 bx lr
 
+#endif  /* !OPENSSL_NO_ASM && __arm__ && !__APPLE__ */
+
 #if defined(__ELF__)
 .section	.note.GNU-stack,"",%progbits
 #endif
-
-#endif  /* !OPENSSL_NO_ASM && __arm__ && !__APPLE__ */
diff --git a/src/crypto/ec_extra/ec_derive.c b/src/crypto/ec_extra/ec_derive.c
new file mode 100644
index 00000000..ca1dc442
--- /dev/null
+++ b/src/crypto/ec_extra/ec_derive.c
@@ -0,0 +1,96 @@
+/* Copyright (c) 2019, Google Inc.
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
+
+#include <openssl/ec_key.h>
+
+#include <string.h>
+
+#include <openssl/buf.h>
+#include <openssl/ec.h>
+#include <openssl/err.h>
+#include <openssl/digest.h>
+#include <openssl/hkdf.h>
+#include <openssl/mem.h>
+
+#include "../fipsmodule/ec/internal.h"
+
+
+EC_KEY *EC_KEY_derive_from_secret(const EC_GROUP *group, const uint8_t *secret,
+                                  size_t secret_len) {
+#define EC_KEY_DERIVE_MAX_NAME_LEN 16
+  const char *name = EC_curve_nid2nist(EC_GROUP_get_curve_name(group));
+  if (name == NULL || strlen(name) > EC_KEY_DERIVE_MAX_NAME_LEN) {
+    OPENSSL_PUT_ERROR(EC, EC_R_UNKNOWN_GROUP);
+    return NULL;
+  }
+
+  // Assemble a label string to provide some key separation in case |secret| is
+  // misused, but ultimately it's on the caller to ensure |secret| is suitably
+  // separated.
+  static const char kLabel[] = "derive EC key ";
+  char info[sizeof(kLabel) + EC_KEY_DERIVE_MAX_NAME_LEN];
+  BUF_strlcpy(info, kLabel, sizeof(info));
+  BUF_strlcat(info, name, sizeof(info));
+
+  // Generate 128 bits beyond the group order so the bias is at most 2^-128.
+#define EC_KEY_DERIVE_EXTRA_BITS 128
+#define EC_KEY_DERIVE_EXTRA_BYTES (EC_KEY_DERIVE_EXTRA_BITS / 8)
+
+  if (EC_GROUP_order_bits(group) <= EC_KEY_DERIVE_EXTRA_BITS + 8) {
+    // The reduction strategy below requires the group order be large enough.
+    // (The actual bound is a bit tighter, but our curves are much larger than
+    // 128-bit.)
+    OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
+    return NULL;
+  }
+
+  uint8_t derived[EC_KEY_DERIVE_EXTRA_BYTES + EC_MAX_BYTES];
+  size_t derived_len = BN_num_bytes(&group->order) + EC_KEY_DERIVE_EXTRA_BYTES;
+  assert(derived_len <= sizeof(derived));
+  if (!HKDF(derived, derived_len, EVP_sha256(), secret, secret_len,
+            /*salt=*/NULL, /*salt_len=*/0, (const uint8_t *)info,
+            strlen(info))) {
+    return NULL;
+  }
+
+  EC_KEY *key = EC_KEY_new();
+  BN_CTX *ctx = BN_CTX_new();
+  BIGNUM *priv = BN_bin2bn(derived, derived_len, NULL);
+  EC_POINT *pub = EC_POINT_new(group);
+  if (key == NULL || ctx == NULL || priv == NULL || pub == NULL ||
+      // Reduce |priv| with Montgomery reduction. First, convert "from"
+      // Montgomery form to compute |priv| * R^-1 mod |order|. This requires
+      // |priv| be under order * R, which is true if the group order is large
+      // enough. 2^(num_bytes(order)) < 2^8 * order, so:
+      //
+      //    priv < 2^8 * order * 2^128 < order * order < order * R
+      !BN_from_montgomery(priv, priv, group->order_mont, ctx) ||
+      // Multiply by R^2 and do another Montgomery reduction to compute
+      // priv * R^-1 * R^2 * R^-1 = priv mod order.
+      !BN_to_montgomery(priv, priv, group->order_mont, ctx) ||
+      !EC_POINT_mul(group, pub, priv, NULL, NULL, ctx) ||
+      !EC_KEY_set_group(key, group) || !EC_KEY_set_public_key(key, pub) ||
+      !EC_KEY_set_private_key(key, priv)) {
+    EC_KEY_free(key);
+    key = NULL;
+    goto err;
+  }
+
+err:
+  OPENSSL_cleanse(derived, sizeof(derived));
+  BN_CTX_free(ctx);
+  BN_free(priv);
+  EC_POINT_free(pub);
+  return key;
+}
diff --git a/src/crypto/fipsmodule/FIPS.md b/src/crypto/fipsmodule/FIPS.md
index 69719b66..5d742dd4 100644
--- a/src/crypto/fipsmodule/FIPS.md
+++ b/src/crypto/fipsmodule/FIPS.md
@@ -46,6 +46,10 @@ The DRBG state is kept in a thread-local structure and is seeded from one of the
 
 In FIPS mode, each of those entropy sources is subject to a 10× overread. That is, when *n* bytes of entropy are needed, *10n* bytes will be read from the entropy source and XORed down to *n* bytes. Reads from the entropy source are also processed in blocks of 16 bytes and if two consecutive chunks are equal the process will abort.
 
+In the case that the seed is taken from RDRAND, getrandom will also be queried with `GRND_NONBLOCK` to attempt to obtain additional entropy from the operating system. If available, that extra entropy will be XORed into the whitened seed.
+
+On Android, only `getrandom` is supported and, when seeding for the first time, the system property `ro.boringcrypto.hwrand` is queried. If set to `true` then `getrandom` will be called with the `GRND_RANDOM` flag. Only entropy draws destined for DRBG seeds are affected by this. We are not suggesting that there is any security advantage at all to doing this, and thus recommend that Android vendors do _not_ set this flag.
+
 The CTR-DRBG is reseeded every 4096 calls to `RAND_bytes`. Thus the process will randomly crash about every 2¹³⁵ calls.
 
 The FIPS PRNGs allow “additional input” to be fed into a given call. We use this feature to be as robust as possible to state duplication from process forks and VM copies: for every call we read 32 bytes of “additional data” from the entropy source (without overread) which means that cloned states will diverge at the next call to `RAND_bytes`. This is called “prediction resistance” by FIPS, but we do *not* claim this property in a FIPS context because we don't implement it the way they want.
@@ -54,6 +58,12 @@ There is a second interface to the RNG which allows the caller to supply bytes t
 
 FIPS requires that RNG state be zeroed when the process exits. In order to implement this, all per-thread RNG states are tracked in a linked list and a destructor function is included which clears them. In order for this to be safe in the presence of threads, a lock is used to stop all other threads from using the RNG once this process has begun. Thus the main thread exiting may cause other threads to deadlock, and drawing on entropy in a destructor function may also deadlock.
 
+## Self-test optimisation
+
+On Android, the self-tests are optimised in line with [IG](https://csrc.nist.gov/csrc/media/projects/cryptographic-module-validation-program/documents/fips140-2/fips1402ig.pdf) section 9.11. The module will always perform the integrity test at power-on, but the self-tests will test for the presence of a file named after the hex encoded, HMAC-SHA-256 hash of the module in `/dev/boringssl/selftest/`. If such a file is found then the self-tests are skipped. Otherwise, after the self-tests complete successfully, that file will be written. Any I/O errors are ignored and, if they occur when testing for the presence of the file, the module acts as if it's not present.
+
+It is intended that a `tmpfs` be mounted at that location in order to skip running the self tests for every process once they have already passed in a given instance of the operating system.
+
 ## Integrity Test
 
 FIPS-140 mandates that a module calculate an HMAC of its own code in a constructor function and compare the result to a known-good value. Typical code produced by a C compiler includes large numbers of relocations: places in the machine code where the linker needs to resolve and inject the final value of a symbolic expression. These relocations mean that the bytes that make up any specific bit of code generally aren't known until the final link has completed.
diff --git a/src/crypto/fipsmodule/bn/bn_test.cc b/src/crypto/fipsmodule/bn/bn_test.cc
index 0be83969..ea3967b5 100644
--- a/src/crypto/fipsmodule/bn/bn_test.cc
+++ b/src/crypto/fipsmodule/bn/bn_test.cc
@@ -2279,6 +2279,32 @@ TEST_F(BNTest, PrimeChecking) {
   EXPECT_EQ(1, is_probably_prime_1);
 }
 
+TEST_F(BNTest, MillerRabinIteration) {
+  FileTestGTest(
+      "crypto/fipsmodule/bn/miller_rabin_tests.txt", [&](FileTest *t) {
+        BIGNUMFileTest bn_test(t, /*large_mask=*/0);
+
+        bssl::UniquePtr<BIGNUM> w = bn_test.GetBIGNUM("W");
+        ASSERT_TRUE(w);
+        bssl::UniquePtr<BIGNUM> b = bn_test.GetBIGNUM("B");
+        ASSERT_TRUE(b);
+        bssl::UniquePtr<BN_MONT_CTX> mont(
+            BN_MONT_CTX_new_consttime(w.get(), ctx()));
+        ASSERT_TRUE(mont);
+
+        bssl::BN_CTXScope scope(ctx());
+        BN_MILLER_RABIN miller_rabin;
+        ASSERT_TRUE(bn_miller_rabin_init(&miller_rabin, mont.get(), ctx()));
+        int possibly_prime;
+        ASSERT_TRUE(bn_miller_rabin_iteration(&miller_rabin, &possibly_prime,
+                                              b.get(), mont.get(), ctx()));
+
+        std::string result;
+        ASSERT_TRUE(t->GetAttribute(&result, "Result"));
+        EXPECT_EQ(result, possibly_prime ? "PossiblyPrime" : "Composite");
+      });
+}
+
 TEST_F(BNTest, NumBitsWord) {
   constexpr BN_ULONG kOne = 1;
 
diff --git a/src/crypto/fipsmodule/bn/internal.h b/src/crypto/fipsmodule/bn/internal.h
index c1e60fe5..d58a2acc 100644
--- a/src/crypto/fipsmodule/bn/internal.h
+++ b/src/crypto/fipsmodule/bn/internal.h
@@ -437,6 +437,40 @@ OPENSSL_EXPORT uint16_t bn_mod_u16_consttime(const BIGNUM *bn, uint16_t d);
 // of the first several odd primes and zero otherwise.
 int bn_odd_number_is_obviously_composite(const BIGNUM *bn);
 
+// A BN_MILLER_RABIN stores state common to each Miller-Rabin iteration. It is
+// initialized within an existing |BN_CTX| scope and may not be used after
+// that scope is released with |BN_CTX_end|. Field names match those in FIPS
+// 186-4, section C.3.1.
+typedef struct {
+  // w1 is w-1.
+  BIGNUM *w1;
+  // m is (w-1)/2^a.
+  BIGNUM *m;
+  // one_mont is 1 (mod w) in Montgomery form.
+  BIGNUM *one_mont;
+  // w1_mont is w-1 (mod w) in Montgomery form.
+  BIGNUM *w1_mont;
+  // w_bits is BN_num_bits(w).
+  int w_bits;
+  // a is the largest integer such that 2^a divides w-1.
+  int a;
+} BN_MILLER_RABIN;
+
+// bn_miller_rabin_init initializes |miller_rabin| for testing if |mont->N| is
+// prime. It returns one on success and zero on error.
+OPENSSL_EXPORT int bn_miller_rabin_init(BN_MILLER_RABIN *miller_rabin,
+                                        const BN_MONT_CTX *mont, BN_CTX *ctx);
+
+// bn_miller_rabin_iteration performs one Miller-Rabin iteration, checking if
+// |b| is a composite witness for |mont->N|. |miller_rabin| must have been
+// initialized with |bn_miller_rabin_setup|. On success, it returns one and sets
+// |*out_is_possibly_prime| to one if |mont->N| may still be prime or zero if
+// |b| shows it is composite. On allocation or internal failure, it returns
+// zero.
+OPENSSL_EXPORT int bn_miller_rabin_iteration(
+    const BN_MILLER_RABIN *miller_rabin, int *out_is_possibly_prime,
+    const BIGNUM *b, const BN_MONT_CTX *mont, BN_CTX *ctx);
+
 // bn_rshift1_words sets |r| to |a| >> 1, where both arrays are |num| bits wide.
 void bn_rshift1_words(BN_ULONG *r, const BN_ULONG *a, size_t num);
 
diff --git a/src/crypto/fipsmodule/bn/miller_rabin_tests.txt b/src/crypto/fipsmodule/bn/miller_rabin_tests.txt
new file mode 100644
index 00000000..437d0f97
--- /dev/null
+++ b/src/crypto/fipsmodule/bn/miller_rabin_tests.txt
@@ -0,0 +1,322 @@
+# This file contains test vectors for whether B is a Miller-Rabin composite
+# witness for W. W must be odd and B must satisfy 1 <= B <= W-1.
+#
+# The following Python function may be used to check values.
+#
+#  def is_miller_rabin_witness(w, b):
+#      # Variable names taken from FIPS 186-4 C.3.1 but the algorithm skips a
+#      # couple of optimizations in the FIPS formulation.
+#      m = w - 1
+#      a = 0
+#      while m&1 == 0:
+#          a += 1
+#          m //= 2
+#      # b is a composite witness for w iff the following are true:
+#      # - b^m != 1 (mod w)
+#      # - b^(m*2^j) != -1 (mod w), for 0 <= j < a
+#      z = pow(b, m, w)
+#      if z == 1:
+#         # b^m = 1 (mod w)
+#         return False
+#      for j in range(a):
+#         if z == w-1:
+#             # b^(m*2^j) = -1 (mod w)
+#             return False
+#         z = (z * z) % w
+#      # At this point, z is b^(w-1) (mod w). If z is not 1, w has failed the
+#      # Fermat test and is composite. If z is 1, the value of z immediately
+#      # before it became 1 is a non-trivial root of unity and w is composite.
+#      return True
+
+# Exhaustively test a small prime.
+
+Result = PossiblyPrime
+W = 7
+B = 1
+
+Result = PossiblyPrime
+W = 7
+B = 2
+
+Result = PossiblyPrime
+W = 7
+B = 3
+
+Result = PossiblyPrime
+W = 7
+B = 4
+
+Result = PossiblyPrime
+W = 7
+B = 5
+
+Result = PossiblyPrime
+W = 7
+B = 6
+
+
+# Random large inputs which try to cover a few cases. The nontrivial square root
+# case appears to be difficult to hit randomly.
+
+# b^m = w-1
+Result = PossiblyPrime
+W = d6b4ffc7cf70b2a2fc5d6023015875504d40e3dcce7c2e6b762c3de7bb806a5074144e7054198dabf53d23108679ccc541d5a99efeb1d1abaf89e0dbcead2a8b
+B = fabbafdbec6494ddb5ea4bf458536e87082369b0e53a200ed413f3e64b2fddc7c57c565710fbe73fae5b188fce97d8dcca74c2b5d90906c96d3c2c358a735cd
+
+# b^m = w-1
+Result = PossiblyPrime
+W = 52cc61c42b341ad56dc11495e7cb2fe31e506b9e99522efbf44cd7c28468d3833c5e360f3c77b0aa43c0495c4e14665ab0d7cee9294c722f0de47d4401828401
+B = 3bdc9639c0fc2e77ab48d46e0b4ac6529c11c900e8fe4d82d75767c0556feb23d3f42d4924d16876a743feb386b7b84c7fd16a6c252f662faf0024d19972e62f
+
+# b^m = w-1
+Result = PossiblyPrime
+W = cff9897aa7dce0f2afad262b2de57d301305de717f3539c537c4ce062f8cb70df13fbc1eb4a3b9f0958a8810d1ca9042b4f23334b285a15fee3fc66498761d4b
+B = 9ceb43132fddf9ee4104ea1cb3eb2253c1d7f803f05f0305de9e31a17dd75832f47b8bf189a9b7ca0905f2a7470d9c6349080f481ff1708696fa12d972e7d7ba
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 67d1825dad5344170e65247a87aef1634a1b32bdc22f2f04d9d2959767bb5a27610fba55cd607e0f9fdd9fbb0f7f98e40d5e1eb2f52318fb5be4dbfd30d38861
+B = 260fb14724ff80984736859d8755ee98b25bcb56db9fde1db001a1e1273374034c5b75fd60b3710c7a08ce7d390776f010f384d4e32943cf0c477497d53e9e05
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = ad0bc85b58aaa204177aa9431a40929beb1cbea2dd6f66a25cc54600013213b225ba881805661df43f4208965ada7aacc8095d07d3cbef1a7bbfaae8b745f731
+B = 3d9310f20e9c80269fa6830c7e1a6f02fc5c58646001a9ef6b8b3e496602ff22c3dcb2ddb6a221723fc1722ce237fb46f7a7bb2945e415c8839b15a972f076c9
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = b25c917f55f6c7b596921daba919f35039e5d805119c1587e99849dd7104460c86214f162a6f17aea847bc7f3859e59f2991d457059511972ef373d4bc75e309
+B = a1f10b261dee84619b0423201d46af19eef9ec0612cf947c4d5c36c0c4b28207f75967e69452eabad0a5dcd28f27f7a8a7ed9c8b3e5026c6e0ba5634d94c2d44
+
+# b^m = 1
+Result = PossiblyPrime
+W = d3eeb0eff05b6992e9fa61b02755e155f4aae28c6e45ddb874edd86acdd2d83d18a20e0e00d8b8bc94b92d14fc3f41ced6ababe8ac98c7730c075dbe0f699369
+B = 6b7717269c6225203681a1cacec87cacd83003ec6e9e3f04effcc4f86634770c0860e1f2770b8f303719a44949664a1094205a99d95a0856758fed66d690105e
+
+# b^m = 1
+Result = PossiblyPrime
+W = 64561b8d9aa50340c3a01ccb3e6e17f5023513661c012be288f3900a3ca76890e67290b9560fa1d480f9d2aacccca581b5690636665f243fa13aff5d0bff12d3
+B = 1f5ff70d3d60671ebc5fbfca731898a04438053dbc3c841e6335f487e457d92d9efb5d506d5bef6872d58d12b9a41c950bfc38d12ed977c90eacdd6535b811a0
+
+# b^m = 1
+Result = PossiblyPrime
+W = 69c63fbf44df21b0ed0ee929a740c12d1f3f064da0dcd9d509f31fa45fa27d1a759ab5a9f6f1040d7ee90a0b1e68f779273c41ea1c1198fd547ff6bd70c7e787
+B = 5f7996a9bbfd8fd88e472220b70077bfdacdd63d88885134431f024c2acb7126827b174eb093eb5313f07bb5461de9b0feb7d77ca2c39c2a323a150f33ea525f
+
+# End of iteration
+Result = Composite
+W = 28cc3e08c44571c6dcb98a9ab8b4f3e2b16e1f884997d94a3188bcbb7f1b7cdaecdae8329c013ec8f75dc00004da0039943e4262cd080b16a42910102e00dddb
+B = 512061ab1c69931c2fa0bb89d8d09f3c9209230bf927ddd6fb6a72075f967ed3c4dbb5f437bf4d31ca7344782b22011ad56609dc19aed65319bababfc13dd7
+
+# End of iteration
+Result = Composite
+W = 4eeb7b4d371c45fe8586fee3b1efd792176b70f6cc2698dfa1dd028366626febe0199c3c5f77a5c3cad0057a04767383051d41965255d03681b2a37edad34a9b
+B = 4afc2e85f84017b3fd6967a227eb74c8297b40ea02733d9513bff9b3f01081963f25872f4254afc4e9321eea35b2a1e42eadb186fcc84f2f30f4a994350b93b8
+
+# End of iteration
+Result = Composite
+W = 8e35a959555dd2eb66c65cee3c264071d20671f159e1f9896f1d0ceb041905fcf053eacc189de317c3ee6f93901223cbf30d5b7ddbbdab981790e2f6397e6803
+B = 44c0153759309ec4e5b1e59d57c1b126545ef7ea302b6e43561df4d16068b922389d6924f01c945d9080d1f93a0732599bdedae72d6d590839dc0884dd860441
+
+
+# 0x6c1 = 1729 = 7 * 13 * 19 is a Fermat pseudoprime.
+
+# Found non-trivial square root
+Result = Composite
+W = 6c1
+B = b8
+
+# End of iteration
+Result = Composite
+W = 6c1
+B = 111
+
+# End of iteration
+Result = Composite
+W = 6c1
+B = 11d
+
+# Found non-trivial square root
+Result = Composite
+W = 6c1
+B = 19c
+
+# Found non-trivial square root
+Result = Composite
+W = 6c1
+B = 223
+
+# End of iteration
+Result = Composite
+W = 6c1
+B = 3aa
+
+# Found non-trivial square root
+Result = Composite
+W = 6c1
+B = 653
+
+
+# 1729 has a number of false witnesses.
+
+# b^m = 1
+Result = PossiblyPrime
+W = 6c1
+B = 78
+
+# b^m = 1
+Result = PossiblyPrime
+W = 6c1
+B = eb
+
+# b^m = w-1
+Result = PossiblyPrime
+W = 6c1
+B = 178
+
+# b^m = w-1
+Result = PossiblyPrime
+W = 6c1
+B = 178
+
+# b^m = w-1
+Result = PossiblyPrime
+W = 6c1
+B = 1aa
+
+# b^m = 1
+Result = PossiblyPrime
+W = 6c1
+B = 271
+
+# b^m = 1
+Result = PossiblyPrime
+W = 6c1
+B = 2b2
+
+
+# 1 and W-1 are always nonwitnesses.
+Result = PossiblyPrime
+W = 6c1
+B = 1
+
+Result = PossiblyPrime
+W = 6c1
+B = 6c0
+
+
+# https://kconrad.math.uconn.edu/blurbs/ugradnumthy/millerrabin.pdf, examples
+# 3.1 and 3.2 has a complete list of false witnesses for 65 = 0x41 and
+# 85 = 0x55.
+
+# b^m = 1
+Result = PossiblyPrime
+W = 41
+B = 1
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 41
+B = 8
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 41
+B = 12
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 41
+B = 2f
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 41
+B = 39
+
+# b^m = w-1
+Result = PossiblyPrime
+W = 41
+B = 40
+
+# b^m = 1
+Result = PossiblyPrime
+W = 55
+B = 1
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 55
+B = d
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 55
+B = 26
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 55
+B = 2f
+
+# Some b^(m*2^j) = w-1
+Result = PossiblyPrime
+W = 55
+B = 48
+
+# b^m = w-1
+Result = PossiblyPrime
+W = 55
+B = 54
+
+# Other witnesses for 65 and 85 will report composite:
+
+# Found non-trivial square root
+Result = Composite
+W = 41
+B = 2c
+
+# End of iteration
+Result = Composite
+W = 41
+B = 16
+
+# End of iteration
+Result = Composite
+W = 41
+B = 14
+
+# End of iteration
+Result = Composite
+W = 41
+B = 2
+
+# End of iteration
+Result = Composite
+W = 41
+B = 3a
+
+# End of iteration
+Result = Composite
+W = 55
+B = 40
+
+# End of iteration
+Result = Composite
+W = 55
+B = 7
+
+# End of iteration
+Result = Composite
+W = 55
+B = 23
+
+# End of iteration
+Result = Composite
+W = 55
+B = 2e
+
+# End of iteration
+Result = Composite
+W = 55
+B = 2a
diff --git a/src/crypto/fipsmodule/bn/prime.c b/src/crypto/fipsmodule/bn/prime.c
index c030c9ee..9df4f95c 100644
--- a/src/crypto/fipsmodule/bn/prime.c
+++ b/src/crypto/fipsmodule/bn/prime.c
@@ -119,195 +119,94 @@
 // Zimmermann's, as implemented in PGP.  I have had a read of his comments and
 // implemented my own version.
 
-// kPrimes contains the first 2048 primes.
+// kPrimes contains the first 1024 primes.
 static const uint16_t kPrimes[] = {
-    2,     3,     5,     7,     11,    13,    17,    19,    23,    29,    31,
-    37,    41,    43,    47,    53,    59,    61,    67,    71,    73,    79,
-    83,    89,    97,    101,   103,   107,   109,   113,   127,   131,   137,
-    139,   149,   151,   157,   163,   167,   173,   179,   181,   191,   193,
-    197,   199,   211,   223,   227,   229,   233,   239,   241,   251,   257,
-    263,   269,   271,   277,   281,   283,   293,   307,   311,   313,   317,
-    331,   337,   347,   349,   353,   359,   367,   373,   379,   383,   389,
-    397,   401,   409,   419,   421,   431,   433,   439,   443,   449,   457,
-    461,   463,   467,   479,   487,   491,   499,   503,   509,   521,   523,
-    541,   547,   557,   563,   569,   571,   577,   587,   593,   599,   601,
-    607,   613,   617,   619,   631,   641,   643,   647,   653,   659,   661,
-    673,   677,   683,   691,   701,   709,   719,   727,   733,   739,   743,
-    751,   757,   761,   769,   773,   787,   797,   809,   811,   821,   823,
-    827,   829,   839,   853,   857,   859,   863,   877,   881,   883,   887,
-    907,   911,   919,   929,   937,   941,   947,   953,   967,   971,   977,
-    983,   991,   997,   1009,  1013,  1019,  1021,  1031,  1033,  1039,  1049,
-    1051,  1061,  1063,  1069,  1087,  1091,  1093,  1097,  1103,  1109,  1117,
-    1123,  1129,  1151,  1153,  1163,  1171,  1181,  1187,  1193,  1201,  1213,
-    1217,  1223,  1229,  1231,  1237,  1249,  1259,  1277,  1279,  1283,  1289,
-    1291,  1297,  1301,  1303,  1307,  1319,  1321,  1327,  1361,  1367,  1373,
-    1381,  1399,  1409,  1423,  1427,  1429,  1433,  1439,  1447,  1451,  1453,
-    1459,  1471,  1481,  1483,  1487,  1489,  1493,  1499,  1511,  1523,  1531,
-    1543,  1549,  1553,  1559,  1567,  1571,  1579,  1583,  1597,  1601,  1607,
-    1609,  1613,  1619,  1621,  1627,  1637,  1657,  1663,  1667,  1669,  1693,
-    1697,  1699,  1709,  1721,  1723,  1733,  1741,  1747,  1753,  1759,  1777,
-    1783,  1787,  1789,  1801,  1811,  1823,  1831,  1847,  1861,  1867,  1871,
-    1873,  1877,  1879,  1889,  1901,  1907,  1913,  1931,  1933,  1949,  1951,
-    1973,  1979,  1987,  1993,  1997,  1999,  2003,  2011,  2017,  2027,  2029,
-    2039,  2053,  2063,  2069,  2081,  2083,  2087,  2089,  2099,  2111,  2113,
-    2129,  2131,  2137,  2141,  2143,  2153,  2161,  2179,  2203,  2207,  2213,
-    2221,  2237,  2239,  2243,  2251,  2267,  2269,  2273,  2281,  2287,  2293,
-    2297,  2309,  2311,  2333,  2339,  2341,  2347,  2351,  2357,  2371,  2377,
-    2381,  2383,  2389,  2393,  2399,  2411,  2417,  2423,  2437,  2441,  2447,
-    2459,  2467,  2473,  2477,  2503,  2521,  2531,  2539,  2543,  2549,  2551,
-    2557,  2579,  2591,  2593,  2609,  2617,  2621,  2633,  2647,  2657,  2659,
-    2663,  2671,  2677,  2683,  2687,  2689,  2693,  2699,  2707,  2711,  2713,
-    2719,  2729,  2731,  2741,  2749,  2753,  2767,  2777,  2789,  2791,  2797,
-    2801,  2803,  2819,  2833,  2837,  2843,  2851,  2857,  2861,  2879,  2887,
-    2897,  2903,  2909,  2917,  2927,  2939,  2953,  2957,  2963,  2969,  2971,
-    2999,  3001,  3011,  3019,  3023,  3037,  3041,  3049,  3061,  3067,  3079,
-    3083,  3089,  3109,  3119,  3121,  3137,  3163,  3167,  3169,  3181,  3187,
-    3191,  3203,  3209,  3217,  3221,  3229,  3251,  3253,  3257,  3259,  3271,
-    3299,  3301,  3307,  3313,  3319,  3323,  3329,  3331,  3343,  3347,  3359,
-    3361,  3371,  3373,  3389,  3391,  3407,  3413,  3433,  3449,  3457,  3461,
-    3463,  3467,  3469,  3491,  3499,  3511,  3517,  3527,  3529,  3533,  3539,
-    3541,  3547,  3557,  3559,  3571,  3581,  3583,  3593,  3607,  3613,  3617,
-    3623,  3631,  3637,  3643,  3659,  3671,  3673,  3677,  3691,  3697,  3701,
-    3709,  3719,  3727,  3733,  3739,  3761,  3767,  3769,  3779,  3793,  3797,
-    3803,  3821,  3823,  3833,  3847,  3851,  3853,  3863,  3877,  3881,  3889,
-    3907,  3911,  3917,  3919,  3923,  3929,  3931,  3943,  3947,  3967,  3989,
-    4001,  4003,  4007,  4013,  4019,  4021,  4027,  4049,  4051,  4057,  4073,
-    4079,  4091,  4093,  4099,  4111,  4127,  4129,  4133,  4139,  4153,  4157,
-    4159,  4177,  4201,  4211,  4217,  4219,  4229,  4231,  4241,  4243,  4253,
-    4259,  4261,  4271,  4273,  4283,  4289,  4297,  4327,  4337,  4339,  4349,
-    4357,  4363,  4373,  4391,  4397,  4409,  4421,  4423,  4441,  4447,  4451,
-    4457,  4463,  4481,  4483,  4493,  4507,  4513,  4517,  4519,  4523,  4547,
-    4549,  4561,  4567,  4583,  4591,  4597,  4603,  4621,  4637,  4639,  4643,
-    4649,  4651,  4657,  4663,  4673,  4679,  4691,  4703,  4721,  4723,  4729,
-    4733,  4751,  4759,  4783,  4787,  4789,  4793,  4799,  4801,  4813,  4817,
-    4831,  4861,  4871,  4877,  4889,  4903,  4909,  4919,  4931,  4933,  4937,
-    4943,  4951,  4957,  4967,  4969,  4973,  4987,  4993,  4999,  5003,  5009,
-    5011,  5021,  5023,  5039,  5051,  5059,  5077,  5081,  5087,  5099,  5101,
-    5107,  5113,  5119,  5147,  5153,  5167,  5171,  5179,  5189,  5197,  5209,
-    5227,  5231,  5233,  5237,  5261,  5273,  5279,  5281,  5297,  5303,  5309,
-    5323,  5333,  5347,  5351,  5381,  5387,  5393,  5399,  5407,  5413,  5417,
-    5419,  5431,  5437,  5441,  5443,  5449,  5471,  5477,  5479,  5483,  5501,
-    5503,  5507,  5519,  5521,  5527,  5531,  5557,  5563,  5569,  5573,  5581,
-    5591,  5623,  5639,  5641,  5647,  5651,  5653,  5657,  5659,  5669,  5683,
-    5689,  5693,  5701,  5711,  5717,  5737,  5741,  5743,  5749,  5779,  5783,
-    5791,  5801,  5807,  5813,  5821,  5827,  5839,  5843,  5849,  5851,  5857,
-    5861,  5867,  5869,  5879,  5881,  5897,  5903,  5923,  5927,  5939,  5953,
-    5981,  5987,  6007,  6011,  6029,  6037,  6043,  6047,  6053,  6067,  6073,
-    6079,  6089,  6091,  6101,  6113,  6121,  6131,  6133,  6143,  6151,  6163,
-    6173,  6197,  6199,  6203,  6211,  6217,  6221,  6229,  6247,  6257,  6263,
-    6269,  6271,  6277,  6287,  6299,  6301,  6311,  6317,  6323,  6329,  6337,
-    6343,  6353,  6359,  6361,  6367,  6373,  6379,  6389,  6397,  6421,  6427,
-    6449,  6451,  6469,  6473,  6481,  6491,  6521,  6529,  6547,  6551,  6553,
-    6563,  6569,  6571,  6577,  6581,  6599,  6607,  6619,  6637,  6653,  6659,
-    6661,  6673,  6679,  6689,  6691,  6701,  6703,  6709,  6719,  6733,  6737,
-    6761,  6763,  6779,  6781,  6791,  6793,  6803,  6823,  6827,  6829,  6833,
-    6841,  6857,  6863,  6869,  6871,  6883,  6899,  6907,  6911,  6917,  6947,
-    6949,  6959,  6961,  6967,  6971,  6977,  6983,  6991,  6997,  7001,  7013,
-    7019,  7027,  7039,  7043,  7057,  7069,  7079,  7103,  7109,  7121,  7127,
-    7129,  7151,  7159,  7177,  7187,  7193,  7207,  7211,  7213,  7219,  7229,
-    7237,  7243,  7247,  7253,  7283,  7297,  7307,  7309,  7321,  7331,  7333,
-    7349,  7351,  7369,  7393,  7411,  7417,  7433,  7451,  7457,  7459,  7477,
-    7481,  7487,  7489,  7499,  7507,  7517,  7523,  7529,  7537,  7541,  7547,
-    7549,  7559,  7561,  7573,  7577,  7583,  7589,  7591,  7603,  7607,  7621,
-    7639,  7643,  7649,  7669,  7673,  7681,  7687,  7691,  7699,  7703,  7717,
-    7723,  7727,  7741,  7753,  7757,  7759,  7789,  7793,  7817,  7823,  7829,
-    7841,  7853,  7867,  7873,  7877,  7879,  7883,  7901,  7907,  7919,  7927,
-    7933,  7937,  7949,  7951,  7963,  7993,  8009,  8011,  8017,  8039,  8053,
-    8059,  8069,  8081,  8087,  8089,  8093,  8101,  8111,  8117,  8123,  8147,
-    8161,  8167,  8171,  8179,  8191,  8209,  8219,  8221,  8231,  8233,  8237,
-    8243,  8263,  8269,  8273,  8287,  8291,  8293,  8297,  8311,  8317,  8329,
-    8353,  8363,  8369,  8377,  8387,  8389,  8419,  8423,  8429,  8431,  8443,
-    8447,  8461,  8467,  8501,  8513,  8521,  8527,  8537,  8539,  8543,  8563,
-    8573,  8581,  8597,  8599,  8609,  8623,  8627,  8629,  8641,  8647,  8663,
-    8669,  8677,  8681,  8689,  8693,  8699,  8707,  8713,  8719,  8731,  8737,
-    8741,  8747,  8753,  8761,  8779,  8783,  8803,  8807,  8819,  8821,  8831,
-    8837,  8839,  8849,  8861,  8863,  8867,  8887,  8893,  8923,  8929,  8933,
-    8941,  8951,  8963,  8969,  8971,  8999,  9001,  9007,  9011,  9013,  9029,
-    9041,  9043,  9049,  9059,  9067,  9091,  9103,  9109,  9127,  9133,  9137,
-    9151,  9157,  9161,  9173,  9181,  9187,  9199,  9203,  9209,  9221,  9227,
-    9239,  9241,  9257,  9277,  9281,  9283,  9293,  9311,  9319,  9323,  9337,
-    9341,  9343,  9349,  9371,  9377,  9391,  9397,  9403,  9413,  9419,  9421,
-    9431,  9433,  9437,  9439,  9461,  9463,  9467,  9473,  9479,  9491,  9497,
-    9511,  9521,  9533,  9539,  9547,  9551,  9587,  9601,  9613,  9619,  9623,
-    9629,  9631,  9643,  9649,  9661,  9677,  9679,  9689,  9697,  9719,  9721,
-    9733,  9739,  9743,  9749,  9767,  9769,  9781,  9787,  9791,  9803,  9811,
-    9817,  9829,  9833,  9839,  9851,  9857,  9859,  9871,  9883,  9887,  9901,
-    9907,  9923,  9929,  9931,  9941,  9949,  9967,  9973,  10007, 10009, 10037,
-    10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111, 10133,
-    10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223,
-    10243, 10247, 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313,
-    10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429,
-    10433, 10453, 10457, 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529,
-    10531, 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639,
-    10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733,
-    10739, 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859,
-    10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949, 10957,
-    10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059, 11069, 11071,
-    11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161, 11171,
-    11173, 11177, 11197, 11213, 11239, 11243, 11251, 11257, 11261, 11273, 11279,
-    11287, 11299, 11311, 11317, 11321, 11329, 11351, 11353, 11369, 11383, 11393,
-    11399, 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483, 11489, 11491,
-    11497, 11503, 11519, 11527, 11549, 11551, 11579, 11587, 11593, 11597, 11617,
-    11621, 11633, 11657, 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731,
-    11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831,
-    11833, 11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933,
-    11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037,
-    12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109, 12113, 12119,
-    12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211, 12227, 12239, 12241,
-    12251, 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323, 12329, 12343,
-    12347, 12373, 12377, 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437,
-    12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527,
-    12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611, 12613,
-    12619, 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713,
-    12721, 12739, 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823,
-    12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923,
-    12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 13009,
-    13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121, 13127,
-    13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187, 13217, 13219, 13229,
-    13241, 13249, 13259, 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337,
-    13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441, 13451, 13457,
-    13463, 13469, 13477, 13487, 13499, 13513, 13523, 13537, 13553, 13567, 13577,
-    13591, 13597, 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681, 13687,
-    13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759,
-    13763, 13781, 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877,
-    13879, 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967,
-    13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081, 14083,
-    14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221,
-    14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323, 14327, 14341, 14347,
-    14369, 14387, 14389, 14401, 14407, 14411, 14419, 14423, 14431, 14437, 14447,
-    14449, 14461, 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549, 14551,
-    14557, 14561, 14563, 14591, 14593, 14621, 14627, 14629, 14633, 14639, 14653,
-    14657, 14669, 14683, 14699, 14713, 14717, 14723, 14731, 14737, 14741, 14747,
-    14753, 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831,
-    14843, 14851, 14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939,
-    14947, 14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073,
-    15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149, 15161,
-    15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259, 15263, 15269,
-    15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331, 15349,
-    15359, 15361, 15373, 15377, 15383, 15391, 15401, 15413, 15427, 15439, 15443,
-    15451, 15461, 15467, 15473, 15493, 15497, 15511, 15527, 15541, 15551, 15559,
-    15569, 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643, 15647, 15649,
-    15661, 15667, 15671, 15679, 15683, 15727, 15731, 15733, 15737, 15739, 15749,
-    15761, 15767, 15773, 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859,
-    15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959,
-    15971, 15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069,
-    16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183, 16187,
-    16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267, 16273, 16301,
-    16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381, 16411, 16417, 16421,
-    16427, 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493, 16519, 16529,
-    16547, 16553, 16561, 16567, 16573, 16603, 16607, 16619, 16631, 16633, 16649,
-    16651, 16657, 16661, 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747,
-    16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843, 16871, 16879, 16883,
-    16889, 16901, 16903, 16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981,
-    16987, 16993, 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077,
-    17093, 17099, 17107, 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191,
-    17203, 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317, 17321,
-    17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389, 17393, 17401,
-    17417, 17419, 17431, 17443, 17449, 17467, 17471, 17477, 17483, 17489, 17491,
-    17497, 17509, 17519, 17539, 17551, 17569, 17573, 17579, 17581, 17597, 17599,
-    17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683, 17707, 17713, 17729,
-    17737, 17747, 17749, 17761, 17783, 17789, 17791, 17807, 17827, 17837, 17839,
-    17851, 17863,
+    2,    3,    5,    7,    11,   13,   17,   19,   23,   29,   31,   37,
+    41,   43,   47,   53,   59,   61,   67,   71,   73,   79,   83,   89,
+    97,   101,  103,  107,  109,  113,  127,  131,  137,  139,  149,  151,
+    157,  163,  167,  173,  179,  181,  191,  193,  197,  199,  211,  223,
+    227,  229,  233,  239,  241,  251,  257,  263,  269,  271,  277,  281,
+    283,  293,  307,  311,  313,  317,  331,  337,  347,  349,  353,  359,
+    367,  373,  379,  383,  389,  397,  401,  409,  419,  421,  431,  433,
+    439,  443,  449,  457,  461,  463,  467,  479,  487,  491,  499,  503,
+    509,  521,  523,  541,  547,  557,  563,  569,  571,  577,  587,  593,
+    599,  601,  607,  613,  617,  619,  631,  641,  643,  647,  653,  659,
+    661,  673,  677,  683,  691,  701,  709,  719,  727,  733,  739,  743,
+    751,  757,  761,  769,  773,  787,  797,  809,  811,  821,  823,  827,
+    829,  839,  853,  857,  859,  863,  877,  881,  883,  887,  907,  911,
+    919,  929,  937,  941,  947,  953,  967,  971,  977,  983,  991,  997,
+    1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
+    1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163,
+    1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249,
+    1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321,
+    1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439,
+    1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
+    1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601,
+    1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693,
+    1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783,
+    1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877,
+    1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987,
+    1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069,
+    2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143,
+    2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267,
+    2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347,
+    2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
+    2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543,
+    2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657,
+    2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713,
+    2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801,
+    2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903,
+    2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011,
+    3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119,
+    3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221,
+    3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323,
+    3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
+    3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527,
+    3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607,
+    3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697,
+    3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797,
+    3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907,
+    3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003,
+    4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093,
+    4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211,
+    4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283,
+    4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,
+    4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513,
+    4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621,
+    4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721,
+    4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813,
+    4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937,
+    4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011,
+    5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113,
+    5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233,
+    5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351,
+    5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443,
+    5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531,
+    5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653,
+    5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743,
+    5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849,
+    5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939,
+    5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073,
+    6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173,
+    6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271,
+    6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359,
+    6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473,
+    6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581,
+    6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701,
+    6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803,
+    6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907,
+    6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997,
+    7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121,
+    7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229,
+    7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349,
+    7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487,
+    7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561,
+    7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669,
+    7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757,
+    7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879,
+    7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009,
+    8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111,
+    8117, 8123, 8147, 8161,
 };
 
 // BN_prime_checks_for_size returns the number of Miller-Rabin iterations
@@ -394,7 +293,7 @@ static size_t num_trial_division_primes(const BIGNUM *n) {
   if (n->width * BN_BITS2 > 1024) {
     return OPENSSL_ARRAY_SIZE(kPrimes);
   }
-  return OPENSSL_ARRAY_SIZE(kPrimes) / 4;
+  return OPENSSL_ARRAY_SIZE(kPrimes) / 2;
 }
 
 // BN_PRIME_CHECKS_BLINDED is the iteration count for blinding the constant-time
@@ -594,14 +493,158 @@ int bn_odd_number_is_obviously_composite(const BIGNUM *bn) {
   return bn_trial_division(&prime, bn) && !BN_is_word(bn, prime);
 }
 
+int bn_miller_rabin_init(BN_MILLER_RABIN *miller_rabin, const BN_MONT_CTX *mont,
+                         BN_CTX *ctx) {
+  // This function corresponds to steps 1 through 3 of FIPS 186-4, C.3.1.
+  const BIGNUM *w = &mont->N;
+  // Note we do not call |BN_CTX_start| in this function. We intentionally
+  // allocate values in the containing scope so they outlive this function.
+  miller_rabin->w1 = BN_CTX_get(ctx);
+  miller_rabin->m = BN_CTX_get(ctx);
+  miller_rabin->one_mont = BN_CTX_get(ctx);
+  miller_rabin->w1_mont = BN_CTX_get(ctx);
+  if (miller_rabin->w1 == NULL ||
+      miller_rabin->m == NULL ||
+      miller_rabin->one_mont == NULL ||
+      miller_rabin->w1_mont == NULL) {
+    return 0;
+  }
+
+  // See FIPS 186-4, C.3.1, steps 1 through 3.
+  if (!bn_usub_consttime(miller_rabin->w1, w, BN_value_one())) {
+    return 0;
+  }
+  miller_rabin->a = BN_count_low_zero_bits(miller_rabin->w1);
+  if (!bn_rshift_secret_shift(miller_rabin->m, miller_rabin->w1,
+                              miller_rabin->a, ctx)) {
+    return 0;
+  }
+  miller_rabin->w_bits = BN_num_bits(w);
+
+  // Precompute some values in Montgomery form.
+  if (!bn_one_to_montgomery(miller_rabin->one_mont, mont, ctx) ||
+      // w - 1 is -1 mod w, so we can compute it in the Montgomery domain, -R,
+      // with a subtraction. (|one_mont| cannot be zero.)
+      !bn_usub_consttime(miller_rabin->w1_mont, w, miller_rabin->one_mont)) {
+    return 0;
+  }
+
+  return 1;
+}
+
+int bn_miller_rabin_iteration(const BN_MILLER_RABIN *miller_rabin,
+                              int *out_is_possibly_prime, const BIGNUM *b,
+                              const BN_MONT_CTX *mont, BN_CTX *ctx) {
+  // This function corresponds to steps 4.3 through 4.5 of FIPS 186-4, C.3.1.
+  int ret = 0;
+  BN_CTX_start(ctx);
+
+  // Step 4.3. We use Montgomery-encoding for better performance and to avoid
+  // timing leaks.
+  const BIGNUM *w = &mont->N;
+  BIGNUM *z = BN_CTX_get(ctx);
+  if (z == NULL ||
+      !BN_mod_exp_mont_consttime(z, b, miller_rabin->m, w, ctx, mont) ||
+      !BN_to_montgomery(z, z, mont, ctx)) {
+    goto err;
+  }
+
+  // is_possibly_prime is all ones if we have determined |b| is not a composite
+  // witness for |w|. This is equivalent to going to step 4.7 in the original
+  // algorithm. To avoid timing leaks, we run the algorithm to the end for prime
+  // inputs.
+  crypto_word_t is_possibly_prime = 0;
+
+  // Step 4.4. If z = 1 or z = w-1, b is not a composite witness and w is still
+  // possibly prime.
+  is_possibly_prime = BN_equal_consttime(z, miller_rabin->one_mont) |
+                      BN_equal_consttime(z, miller_rabin->w1_mont);
+  is_possibly_prime = 0 - is_possibly_prime;  // Make it all zeros or all ones.
+
+  // Step 4.5.
+  //
+  // To avoid leaking |a|, we run the loop to |w_bits| and mask off all
+  // iterations once |j| = |a|.
+  for (int j = 1; j < miller_rabin->w_bits; j++) {
+    if (constant_time_eq_int(j, miller_rabin->a) & ~is_possibly_prime) {
+      // If the loop is done and we haven't seen z = 1 or z = w-1 yet, the
+      // value is composite and we can break in variable time.
+      break;
+    }
+
+    // Step 4.5.1.
+    if (!BN_mod_mul_montgomery(z, z, z, mont, ctx)) {
+      goto err;
+    }
+
+    // Step 4.5.2. If z = w-1 and the loop is not done, this is not a composite
+    // witness.
+    crypto_word_t z_is_w1_mont = BN_equal_consttime(z, miller_rabin->w1_mont);
+    z_is_w1_mont = 0 - z_is_w1_mont;    // Make it all zeros or all ones.
+    is_possibly_prime |= z_is_w1_mont;  // Go to step 4.7 if |z_is_w1_mont|.
+
+    // Step 4.5.3. If z = 1 and the loop is not done, the previous value of z
+    // was not -1. There are no non-trivial square roots of 1 modulo a prime, so
+    // w is composite and we may exit in variable time.
+    if (BN_equal_consttime(z, miller_rabin->one_mont) & ~is_possibly_prime) {
+      break;
+    }
+  }
+
+  *out_is_possibly_prime = is_possibly_prime & 1;
+  ret = 1;
+
+err:
+  BN_CTX_end(ctx);
+  return ret;
+}
+
 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;
@@ -646,36 +689,13 @@ int BN_primality_test(int *out_is_probably_prime, const BIGNUM *w,
 
   // See C.3.1 from FIPS 186-4.
   int ret = 0;
-  BN_MONT_CTX *mont = NULL;
   BN_CTX_start(ctx);
-  BIGNUM *w1 = BN_CTX_get(ctx);
-  if (w1 == NULL ||
-      !bn_usub_consttime(w1, w, BN_value_one())) {
-    goto err;
-  }
-
-  // Write w1 as m * 2^a (Steps 1 and 2).
-  int w_len = BN_num_bits(w);
-  int a = BN_count_low_zero_bits(w1);
-  BIGNUM *m = BN_CTX_get(ctx);
-  if (m == NULL ||
-      !bn_rshift_secret_shift(m, w1, a, ctx)) {
-    goto err;
-  }
-
-  // Montgomery setup for computations mod w. Additionally, compute 1 and w - 1
-  // in the Montgomery domain for later comparisons.
   BIGNUM *b = BN_CTX_get(ctx);
-  BIGNUM *z = BN_CTX_get(ctx);
-  BIGNUM *one_mont = BN_CTX_get(ctx);
-  BIGNUM *w1_mont = BN_CTX_get(ctx);
-  mont = BN_MONT_CTX_new_consttime(w, ctx);
-  if (b == NULL || z == NULL || one_mont == NULL || w1_mont == NULL ||
-      mont == NULL ||
-      !bn_one_to_montgomery(one_mont, mont, ctx) ||
-      // w - 1 is -1 mod w, so we can compute it in the Montgomery domain, -R,
-      // with a subtraction. (|one_mont| cannot be zero.)
-      !bn_usub_consttime(w1_mont, w, one_mont)) {
+  BN_MONT_CTX *mont = BN_MONT_CTX_new_consttime(w, ctx);
+  BN_MILLER_RABIN miller_rabin;
+  if (b == NULL || mont == NULL ||
+      // Steps 1-3.
+      !bn_miller_rabin_init(&miller_rabin, mont, ctx)) {
     goto err;
   }
 
@@ -713,64 +733,22 @@ int BN_primality_test(int *out_is_probably_prime, const BIGNUM *w,
   for (int i = 1; (i <= BN_PRIME_CHECKS_BLINDED) |
                   constant_time_lt_w(uniform_iterations, iterations);
        i++) {
+    // Step 4.1-4.2
     int is_uniform;
-    if (// Step 4.1-4.2
-        !bn_rand_secret_range(b, &is_uniform, 2, w1) ||
-        // Step 4.3
-        !BN_mod_exp_mont_consttime(z, b, m, w, ctx, mont)) {
-      goto err;
+    if (!bn_rand_secret_range(b, &is_uniform, 2, miller_rabin.w1)) {
+        goto err;
     }
     uniform_iterations += is_uniform;
 
-    // loop_done is all ones if the loop has completed and all zeros otherwise.
-    crypto_word_t loop_done = 0;
-    // next_iteration is all ones if we should continue to the next iteration
-    // (|b| is not a composite witness for |w|). This is equivalent to going to
-    // step 4.7 in the original algorithm.
-    crypto_word_t next_iteration = 0;
-
-    // Step 4.4. If z = 1 or z = w-1, mask off the loop and continue to the next
-    // iteration (go to step 4.7).
-    loop_done = BN_equal_consttime(z, BN_value_one()) |
-                BN_equal_consttime(z, w1);
-    loop_done = 0 - loop_done;   // Make it all zeros or all ones.
-    next_iteration = loop_done;  // Go to step 4.7 if |loop_done|.
-
-    // Step 4.5. We use Montgomery-encoding for better performance and to avoid
-    // timing leaks.
-    if (!BN_to_montgomery(z, z, mont, ctx)) {
+    // Steps 4.3-4.5
+    int is_possibly_prime = 0;
+    if (!bn_miller_rabin_iteration(&miller_rabin, &is_possibly_prime, b, mont,
+                                   ctx)) {
       goto err;
     }
 
-    // To avoid leaking |a|, we run the loop to |w_len| and mask off all
-    // iterations once |j| = |a|.
-    for (int j = 1; j < w_len; j++) {
-      loop_done |= constant_time_eq_int(j, a);
-
-      // Step 4.5.1.
-      if (!BN_mod_mul_montgomery(z, z, z, mont, ctx)) {
-        goto err;
-      }
-
-      // Step 4.5.2. If z = w-1 and the loop is not done, run through the next
-      // iteration.
-      crypto_word_t z_is_w1_mont = BN_equal_consttime(z, w1_mont) & ~loop_done;
-      z_is_w1_mont = 0 - z_is_w1_mont;  // Make it all zeros or all ones.
-      loop_done |= z_is_w1_mont;
-      next_iteration |= z_is_w1_mont;  // Go to step 4.7 if |z_is_w1_mont|.
-
-      // Step 4.5.3. If z = 1 and the loop is not done, w is composite and we
-      // may exit in variable time.
-      if (BN_equal_consttime(z, one_mont) & ~loop_done) {
-        assert(!next_iteration);
-        break;
-      }
-    }
-
-    if (!next_iteration) {
+    if (!is_possibly_prime) {
       // Step 4.6. We did not see z = w-1 before z = 1, so w must be composite.
-      // (For any prime, the value of z immediately preceding 1 must be -1.
-      // There are no non-trivial square roots of 1 modulo a prime.)
       *out_is_probably_prime = 0;
       ret = 1;
       goto err;
diff --git a/src/crypto/fipsmodule/ec/ec_test.cc b/src/crypto/fipsmodule/ec/ec_test.cc
index 9737d310..07638cd4 100644
--- a/src/crypto/fipsmodule/ec/ec_test.cc
+++ b/src/crypto/fipsmodule/ec/ec_test.cc
@@ -912,3 +912,87 @@ TEST(ECTest, ScalarBaseMultVectors) {
 #endif
   });
 }
+
+static uint8_t FromHexChar(char c) {
+  if ('0' <= c && c <= '9') {
+    return c - '0';
+  }
+  if ('a' <= c && c <= 'f') {
+    return c - 'a' + 10;
+  }
+  abort();
+}
+
+static std::vector<uint8_t> HexToBytes(const char *str) {
+  std::vector<uint8_t> ret;
+  while (str[0] != '\0') {
+    ret.push_back((FromHexChar(str[0]) << 4) | FromHexChar(str[1]));
+    str += 2;
+  }
+  return ret;
+}
+
+TEST(ECTest, DeriveFromSecret) {
+  struct DeriveTest {
+    int curve;
+    std::vector<uint8_t> secret;
+    std::vector<uint8_t> expected_priv;
+    std::vector<uint8_t> expected_pub;
+  };
+  const DeriveTest kDeriveTests[] = {
+      {NID_X9_62_prime256v1, HexToBytes(""),
+       HexToBytes(
+           "b98a86a71efb51ebdac4759937b977e9b0c05224675bb2b6a58ba306e237f4b8"),
+       HexToBytes(
+           "04fbe6cab439918e00231a2ff073cdc25823998864a9eb36f809095a1a919ece875"
+           "a145803fbe89a6cde53936e3c6d9c253ed3d38f5f58cae455c27e95645ceda9")},
+      {NID_X9_62_prime256v1, HexToBytes("123456"),
+       HexToBytes(
+           "44a72bc62087b88e5ab7126766177ed0d8f1ed09ad066cd746527fc201105a7e"),
+       HexToBytes(
+           "04ec0555cd76e991fef7f5504343937d0f38696db3360a4854052cb0d84a377a5a0"
+           "ff64c352755c28692b4ae085c2b817db9a1eddbd22e9cf39c12751e0870791b")},
+      {NID_X9_62_prime256v1, HexToBytes("00000000000000000000000000000000"),
+       HexToBytes(
+           "7ca1e2c83e6a5f2c1b3e7d58180226f269930c4b9fbe2a275096079630b7c57d"),
+       HexToBytes(
+           "0442ef70c8fc0fbe383ed0a0da36f39f9a590f3feebc07863cc858c9a8ef0465731"
+           "0408c249bd4d61929c54b71ffe056e6b4fa1eb537039b43d1c175f0ceab0f89")},
+      {NID_X9_62_prime256v1,
+       HexToBytes(
+           "de9c9b35543aaa0fba039e34e8ca9695da3225c7161c9e3a8c70356cac28c780"),
+       HexToBytes(
+           "659f5abf3b62b9931c29d6ed0722efd2349fa56f54e708cf3272f620f1bc44d0"),
+       HexToBytes(
+           "046741f806b593bf3a3d4a9d76bdcb9b0d7874633cbea8f42c05e78561f7e8ec362"
+           "b9b6f1913ded796fbdafe7f210cea897ac22a4e580c06a60f2659fd09f1830f")},
+      {NID_secp384r1, HexToBytes("123456"),
+       HexToBytes("95cd90d548997de090c7622708eccb7edc1b1bd78d2422235ad97406dada"
+                  "076555309da200096f6e4b36c46002beee89"),
+       HexToBytes(
+           "04007b2d026aa7636fa912c3f970d62bb6c10fa81c8f3290ed90b2d701696d1c6b9"
+           "5af88ce13e962996a7ac37e16527cb5d69bd081b8641d07634cf84b438600ec9434"
+           "15ac6bd7a0236f7ab0ea31ece67df03fa11646ea2b75e73d1b5e45b75c18")},
+  };
+
+  for (const auto &test : kDeriveTests) {
+    SCOPED_TRACE(Bytes(test.secret));
+    bssl::UniquePtr<EC_GROUP> group(EC_GROUP_new_by_curve_name(test.curve));
+    ASSERT_TRUE(group);
+    bssl::UniquePtr<EC_KEY> key(EC_KEY_derive_from_secret(
+        group.get(), test.secret.data(), test.secret.size()));
+    ASSERT_TRUE(key);
+
+    std::vector<uint8_t> priv(BN_num_bytes(EC_GROUP_get0_order(group.get())));
+    ASSERT_TRUE(BN_bn2bin_padded(priv.data(), priv.size(),
+                                 EC_KEY_get0_private_key(key.get())));
+    EXPECT_EQ(Bytes(priv), Bytes(test.expected_priv));
+
+    uint8_t *pub = nullptr;
+    size_t pub_len =
+        EC_KEY_key2buf(key.get(), POINT_CONVERSION_UNCOMPRESSED, &pub, nullptr);
+    bssl::UniquePtr<uint8_t> free_pub(pub);
+    EXPECT_NE(pub_len, 0u);
+    EXPECT_EQ(Bytes(pub, pub_len), Bytes(test.expected_pub));
+  }
+}
diff --git a/src/crypto/fipsmodule/rand/internal.h b/src/crypto/fipsmodule/rand/internal.h
index 07563b7f..280aae42 100644
--- a/src/crypto/fipsmodule/rand/internal.h
+++ b/src/crypto/fipsmodule/rand/internal.h
@@ -40,7 +40,7 @@ void RAND_bytes_with_additional_data(uint8_t *out, size_t out_len,
 // system.
 void CRYPTO_sysrand(uint8_t *buf, size_t len);
 
-#if defined(OPENSSL_URANDOM) && defined(BORINGSSL_FIPS)
+#if defined(OPENSSL_URANDOM) || defined(BORINGSSL_UNSAFE_DETERMINISTIC_MODE)
 // CRYPTO_sysrand_for_seed fills |len| bytes at |buf| with entropy from the
 // operating system. It may draw from the |GRND_RANDOM| pool on Android,
 // depending on the vendor's configuration.
diff --git a/src/crypto/fipsmodule/rand/urandom.c b/src/crypto/fipsmodule/rand/urandom.c
index 33c0b031..4a60eb2f 100644
--- a/src/crypto/fipsmodule/rand/urandom.c
+++ b/src/crypto/fipsmodule/rand/urandom.c
@@ -389,7 +389,7 @@ static int fill_with_entropy(uint8_t *out, size_t len, int block, int seed) {
 
 #if defined(USE_NR_getrandom)
   int getrandom_flags = 0;
-  if (block) {
+  if (!block) {
     getrandom_flags |= GRND_NONBLOCK;
   }
   if (seed) {
diff --git a/src/crypto/hrss/asm/poly_rq_mul.S b/src/crypto/hrss/asm/poly_rq_mul.S
index 0b684c38..d3846279 100644
--- a/src/crypto/hrss/asm/poly_rq_mul.S
+++ b/src/crypto/hrss/asm/poly_rq_mul.S
@@ -8460,8 +8460,8 @@ ret
 .cfi_endproc
 .size poly_Rq_mul,.-poly_Rq_mul
 
-#if defined(__ELF__)
-.section	.note.GNU-stack,"",@progbits
 #endif
 
+#if defined(__ELF__)
+.section	.note.GNU-stack,"",@progbits
 #endif
diff --git a/src/crypto/perlasm/arm-xlate.pl b/src/crypto/perlasm/arm-xlate.pl
index adbd239e..58904d08 100755
--- a/src/crypto/perlasm/arm-xlate.pl
+++ b/src/crypto/perlasm/arm-xlate.pl
@@ -228,10 +228,10 @@ while(my $line=<>) {
     print "\n";
 }
 
-# See https://www.airs.com/blog/archives/518.
-print ".section\t.note.GNU-stack,\"\",\%progbits\n" if ($flavour =~ /linux/);
-
 print "#endif\n" if ($flavour eq "linux32" || $flavour eq "linux64");
 print "#endif  // !OPENSSL_NO_ASM\n";
 
+# See https://www.airs.com/blog/archives/518.
+print ".section\t.note.GNU-stack,\"\",\%progbits\n" if ($flavour =~ /linux/);
+
 close STDOUT;
diff --git a/src/crypto/perlasm/ppc-xlate.pl b/src/crypto/perlasm/ppc-xlate.pl
index f8e42a22..4f22c36d 100644
--- a/src/crypto/perlasm/ppc-xlate.pl
+++ b/src/crypto/perlasm/ppc-xlate.pl
@@ -309,9 +309,9 @@ while($line=<>) {
     print "\n";
 }
 
+print "#endif  // !OPENSSL_NO_ASM && __powerpc64__\n";
+
 # See https://www.airs.com/blog/archives/518.
 print ".section\t.note.GNU-stack,\"\",\@progbits\n" if ($flavour =~ /linux/);
 
-print "#endif  // !OPENSSL_NO_ASM && __powerpc64__\n";
-
 close STDOUT;
diff --git a/src/crypto/perlasm/x86_64-xlate.pl b/src/crypto/perlasm/x86_64-xlate.pl
index d2854cf4..4a41a241 100755
--- a/src/crypto/perlasm/x86_64-xlate.pl
+++ b/src/crypto/perlasm/x86_64-xlate.pl
@@ -1260,10 +1260,9 @@ while(defined(my $line=<>)) {
 
 print "\n$current_segment\tENDS\n"	if ($current_segment && $masm);
 print "END\n"				if ($masm);
+print "#endif\n"			if ($gas);
 # See https://www.airs.com/blog/archives/518.
 print ".section\t.note.GNU-stack,\"\",\@progbits\n" if ($elf);
-print "#endif\n"			if ($gas);
-
 
 close STDOUT;
 
diff --git a/src/crypto/perlasm/x86asm.pl b/src/crypto/perlasm/x86asm.pl
index b331cd4f..2d19425f 100644
--- a/src/crypto/perlasm/x86asm.pl
+++ b/src/crypto/perlasm/x86asm.pl
@@ -297,9 +297,9 @@ ___
 ___
     }
     print @out;
+    print "#endif\n" unless ($win32 || $netware);
     # See https://www.airs.com/blog/archives/518.
     print ".section\t.note.GNU-stack,\"\",\@progbits\n" if ($elf);
-    print "#endif\n" unless ($win32 || $netware);
 }
 
 sub ::asm_init
diff --git a/src/crypto/poly1305/poly1305_arm_asm.S b/src/crypto/poly1305/poly1305_arm_asm.S
index 77b3c48e..80a4b31f 100644
--- a/src/crypto/poly1305/poly1305_arm_asm.S
+++ b/src/crypto/poly1305/poly1305_arm_asm.S
@@ -2022,8 +2022,8 @@ vst1.8 d4,[r0,: 64]
 add sp,sp,#0
 bx lr
 
+#endif  /* __arm__ && !OPENSSL_NO_ASM && !__APPLE__ */
+
 #if defined(__ELF__)
 .section	.note.GNU-stack,"",%progbits
 #endif
-
-#endif  /* __arm__ && !OPENSSL_NO_ASM && !__APPLE__ */
diff --git a/src/crypto/rand_extra/deterministic.c b/src/crypto/rand_extra/deterministic.c
index 17fa71e6..34547ea5 100644
--- a/src/crypto/rand_extra/deterministic.c
+++ b/src/crypto/rand_extra/deterministic.c
@@ -45,4 +45,12 @@ void CRYPTO_sysrand(uint8_t *out, size_t requested) {
   g_num_calls++;
 }
 
+void CRYPTO_sysrand_for_seed(uint8_t *out, size_t requested) {
+  CRYPTO_sysrand(out, requested);
+}
+
+void CRYPTO_sysrand_if_available(uint8_t *out, size_t requested) {
+  CRYPTO_sysrand(out, requested);
+}
+
 #endif  // BORINGSSL_UNSAFE_DETERMINISTIC_MODE
diff --git a/src/include/openssl/bn.h b/src/include/openssl/bn.h
index b6b7e9ab..0ca9ad5a 100644
--- a/src/include/openssl/bn.h
+++ b/src/include/openssl/bn.h
@@ -846,8 +846,9 @@ OPENSSL_EXPORT int BN_to_montgomery(BIGNUM *ret, const BIGNUM *a,
                                     const BN_MONT_CTX *mont, BN_CTX *ctx);
 
 // BN_from_montgomery sets |ret| equal to |a| * R^-1, i.e. translates values out
-// of the Montgomery domain. |a| is assumed to be in the range [0, n), where |n|
-// is the Montgomery modulus. It returns one on success or zero on error.
+// of the Montgomery domain. |a| is assumed to be in the range [0, n*R), where
+// |n| is the Montgomery modulus. Note n < R, so inputs in the range [0, n*n)
+// are valid. This function returns one on success or zero on error.
 OPENSSL_EXPORT int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a,
                                       const BN_MONT_CTX *mont, BN_CTX *ctx);
 
diff --git a/src/include/openssl/ec_key.h b/src/include/openssl/ec_key.h
index be0faaf8..1bc6d30c 100644
--- a/src/include/openssl/ec_key.h
+++ b/src/include/openssl/ec_key.h
@@ -130,7 +130,7 @@ OPENSSL_EXPORT const BIGNUM *EC_KEY_get0_private_key(const EC_KEY *key);
 // EC_KEY_set_private_key sets the private key of |key| to |priv|. It returns
 // one on success and zero otherwise. |key| must already have had a group
 // configured (see |EC_KEY_set_group| and |EC_KEY_new_by_curve_name|).
-OPENSSL_EXPORT int EC_KEY_set_private_key(EC_KEY *key, const BIGNUM *prv);
+OPENSSL_EXPORT int EC_KEY_set_private_key(EC_KEY *key, const BIGNUM *priv);
 
 // EC_KEY_get0_public_key returns a pointer to the public key point inside
 // |key|.
@@ -195,6 +195,20 @@ OPENSSL_EXPORT int EC_KEY_generate_key(EC_KEY *key);
 // additional checks for FIPS compliance.
 OPENSSL_EXPORT int EC_KEY_generate_key_fips(EC_KEY *key);
 
+// EC_KEY_derive_from_secret deterministically derives a private key for |group|
+// from an input secret using HKDF-SHA256. It returns a newly-allocated |EC_KEY|
+// on success or NULL on error. |secret| must not be used in any other
+// algorithm. If using a base secret for multiple operations, derive separate
+// values with a KDF such as HKDF first.
+//
+// Note this function implements an arbitrary derivation scheme, rather than any
+// particular standard one. New protocols are recommended to use X25519 and
+// Ed25519, which have standard byte import functions. See
+// |X25519_public_from_private| and |ED25519_keypair_from_seed|.
+OPENSSL_EXPORT EC_KEY *EC_KEY_derive_from_secret(const EC_GROUP *group,
+                                                 const uint8_t *secret,
+                                                 size_t secret_len);
+
 
 // Serialisation.
 
diff --git a/src/include/openssl/ssl.h b/src/include/openssl/ssl.h
index 8cd03be8..f12cacce 100644
--- a/src/include/openssl/ssl.h
+++ b/src/include/openssl/ssl.h
@@ -644,10 +644,10 @@ OPENSSL_EXPORT int SSL_CTX_set_max_proto_version(SSL_CTX *ctx,
                                                  uint16_t version);
 
 // SSL_CTX_get_min_proto_version returns the minimum protocol version for |ctx|
-OPENSSL_EXPORT uint16_t SSL_CTX_get_min_proto_version(SSL_CTX *ctx);
+OPENSSL_EXPORT uint16_t SSL_CTX_get_min_proto_version(const SSL_CTX *ctx);
 
 // SSL_CTX_get_max_proto_version returns the maximum protocol version for |ctx|
-OPENSSL_EXPORT uint16_t SSL_CTX_get_max_proto_version(SSL_CTX *ctx);
+OPENSSL_EXPORT uint16_t SSL_CTX_get_max_proto_version(const SSL_CTX *ctx);
 
 // SSL_set_min_proto_version sets the minimum protocol version for |ssl| to
 // |version|. If |version| is zero, the default minimum version is used. It
@@ -659,6 +659,14 @@ OPENSSL_EXPORT int SSL_set_min_proto_version(SSL *ssl, uint16_t version);
 // returns one on success and zero if |version| is invalid.
 OPENSSL_EXPORT int SSL_set_max_proto_version(SSL *ssl, uint16_t version);
 
+// SSL_get_min_proto_version returns the minimum protocol version for |ssl|. If
+// the connection's configuration has been shed, 0 is returned.
+OPENSSL_EXPORT uint16_t SSL_get_min_proto_version(const SSL *ssl);
+
+// SSL_get_max_proto_version returns the maximum protocol version for |ssl|. If
+// the connection's configuration has been shed, 0 is returned.
+OPENSSL_EXPORT uint16_t SSL_get_max_proto_version(const SSL *ssl);
+
 // SSL_version returns the TLS or DTLS protocol version used by |ssl|, which is
 // one of the |*_VERSION| values. (E.g. |TLS1_2_VERSION|.) Before the version
 // is negotiated, the result is undefined.
diff --git a/src/sources.cmake b/src/sources.cmake
index 8dc65e64..db144562 100644
--- a/src/sources.cmake
+++ b/src/sources.cmake
@@ -47,6 +47,7 @@ set(
   crypto/evp/scrypt_tests.txt
   crypto/fipsmodule/aes/aes_tests.txt
   crypto/fipsmodule/bn/bn_tests.txt
+  crypto/fipsmodule/bn/miller_rabin_tests.txt
   crypto/fipsmodule/ec/ec_scalar_base_mult_tests.txt
   crypto/fipsmodule/ec/p256-x86_64_tests.txt
   crypto/fipsmodule/ecdsa/ecdsa_sign_tests.txt
diff --git a/src/ssl/ssl_versions.cc b/src/ssl/ssl_versions.cc
index df5ffd26..e63a1896 100644
--- a/src/ssl/ssl_versions.cc
+++ b/src/ssl/ssl_versions.cc
@@ -335,11 +335,11 @@ int SSL_CTX_set_max_proto_version(SSL_CTX *ctx, uint16_t version) {
   return set_max_version(ctx->method, &ctx->conf_max_version, version);
 }
 
-uint16_t SSL_CTX_get_min_proto_version(SSL_CTX *ctx) {
+uint16_t SSL_CTX_get_min_proto_version(const SSL_CTX *ctx) {
   return ctx->conf_min_version;
 }
 
-uint16_t SSL_CTX_get_max_proto_version(SSL_CTX *ctx) {
+uint16_t SSL_CTX_get_max_proto_version(const SSL_CTX *ctx) {
   return ctx->conf_max_version;
 }
 
@@ -357,6 +357,20 @@ int SSL_set_max_proto_version(SSL *ssl, uint16_t version) {
   return set_max_version(ssl->method, &ssl->config->conf_max_version, version);
 }
 
+uint16_t SSL_get_min_proto_version(const SSL *ssl) {
+  if (!ssl->config) {
+    return 0;
+  }
+  return ssl->config->conf_min_version;
+}
+
+uint16_t SSL_get_max_proto_version(const SSL *ssl) {
+  if (!ssl->config) {
+    return 0;
+  }
+  return ssl->config->conf_max_version;
+}
+
 int SSL_version(const SSL *ssl) {
   return wire_version_to_api(ssl_version(ssl));
 }
diff --git a/src/util/run_android_tests.go b/src/util/run_android_tests.go
index 115c3da0..c5abdcb3 100644
--- a/src/util/run_android_tests.go
+++ b/src/util/run_android_tests.go
@@ -268,6 +268,19 @@ func main() {
 		}
 	}
 
+	var libraries []string
+	if _, err := os.Stat(filepath.Join(*buildDir, "crypto/libcrypto.so")); err == nil {
+		libraries = []string{
+			"libboringssl_gtest.so",
+			"crypto/libcrypto.so",
+			"decrepit/libdecrepit.so",
+			"ssl/libssl.so",
+		}
+	} else if !os.IsNotExist(err) {
+		fmt.Printf("Failed to stat crypto/libcrypto.so: %s\n", err)
+		os.Exit(1)
+	}
+
 	fmt.Printf("Copying test binaries...\n")
 	for _, binary := range binaries {
 		if err := copyFile(filepath.Join(tmpDir, "build", binary), filepath.Join(*buildDir, binary)); err != nil {
@@ -276,6 +289,20 @@ func main() {
 		}
 	}
 
+	var envPrefix string
+	if len(libraries) > 0 {
+		fmt.Printf("Copying libraries...\n")
+		for _, library := range libraries {
+			// Place all the libraries in a common directory so they
+			// can be passed to LD_LIBRARY_PATH once.
+			if err := copyFile(filepath.Join(tmpDir, "build", "lib", filepath.Base(library)), filepath.Join(*buildDir, library)); err != nil {
+				fmt.Printf("Failed to copy %s: %s\n", library, err)
+				os.Exit(1)
+			}
+		}
+		envPrefix = "env LD_LIBRARY_PATH=/data/local/tmp/boringssl-tmp/build/lib "
+	}
+
 	fmt.Printf("Copying data files...\n")
 	for _, file := range files {
 		if err := copyFile(filepath.Join(tmpDir, file), file); err != nil {
@@ -293,7 +320,7 @@ func main() {
 	var unitTestExit int
 	if enableUnitTests() {
 		fmt.Printf("Running unit tests...\n")
-		unitTestExit, err = adbShell(fmt.Sprintf("cd /data/local/tmp/boringssl-tmp && ./util/all_tests -json-output results.json %s", *allTestsArgs))
+		unitTestExit, err = adbShell(fmt.Sprintf("cd /data/local/tmp/boringssl-tmp && %s./util/all_tests -json-output results.json %s", envPrefix, *allTestsArgs))
 		if err != nil {
 			fmt.Printf("Failed to run unit tests: %s\n", err)
 			os.Exit(1)
@@ -303,7 +330,7 @@ func main() {
 	var sslTestExit int
 	if enableSSLTests() {
 		fmt.Printf("Running SSL tests...\n")
-		sslTestExit, err = adbShell(fmt.Sprintf("cd /data/local/tmp/boringssl-tmp/ssl/test/runner && ./runner -json-output ../../../results.json %s", *runnerArgs))
+		sslTestExit, err = adbShell(fmt.Sprintf("cd /data/local/tmp/boringssl-tmp/ssl/test/runner && %s./runner -json-output ../../../results.json %s", envPrefix, *runnerArgs))
 		if err != nil {
 			fmt.Printf("Failed to run SSL tests: %s\n", err)
 			os.Exit(1)
diff --git a/src/util/whitespace.txt b/src/util/whitespace.txt
index c311da36..08ccc0a1 100644
--- a/src/util/whitespace.txt
+++ b/src/util/whitespace.txt
@@ -1 +1 @@
-This file is ignored.  It exists to make no-op commits to trigger new builds.
+This file is ignored. It exists to make no-op commits to trigger new builds.