FIPS 186-4 RSA Generation & Validation

Reviewed-by: Paul Dale <paul.dale@oracle.com>
Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/6652)

17 files changed, 2163 insertions, 87 deletions

diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c
index c4ab8693fc..7a87b97db3 100644
--- a/crypto/bn/bn_prime.c
+++ b/crypto/bn/bn_prime.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the Apache License 2.0 (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -19,14 +19,49 @@
  */
 #include "bn_prime.h"
 
-static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
-                   const BIGNUM *a1_odd, int k, BN_CTX *ctx,
-                   BN_MONT_CTX *mont);
 static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods);
 static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
                                   const BIGNUM *add, const BIGNUM *rem,
                                   BN_CTX *ctx);
 
+#if BN_BITS2 == 64
+# define BN_DEF(lo, hi) (BN_ULONG)hi<<32|lo
+#else
+# define BN_DEF(lo, hi) lo, hi
+#endif
+
+/*
+ * See SP800 89 5.3.3 (Step f)
+ * The product of the set of primes ranging from 3 to 751
+ * Generated using process in test/bn_internal_test.c test_bn_small_factors().
+ * This includes 751 (which is not currently included in SP 800-89).
+ */
+static const BN_ULONG small_prime_factors[] = {
+    BN_DEF(0x3ef4e3e1, 0xc4309333), BN_DEF(0xcd2d655f, 0x71161eb6),
+    BN_DEF(0x0bf94862, 0x95e2238c), BN_DEF(0x24f7912b, 0x3eb233d3),
+    BN_DEF(0xbf26c483, 0x6b55514b), BN_DEF(0x5a144871, 0x0a84d817),
+    BN_DEF(0x9b82210a, 0x77d12fee), BN_DEF(0x97f050b3, 0xdb5b93c2),
+    BN_DEF(0x4d6c026b, 0x4acad6b9), BN_DEF(0x54aec893, 0xeb7751f3),
+    BN_DEF(0x36bc85c4, 0xdba53368), BN_DEF(0x7f5ec78e, 0xd85a1b28),
+    BN_DEF(0x6b322244, 0x2eb072d8), BN_DEF(0x5e2b3aea, 0xbba51112),
+    BN_DEF(0x0e2486bf, 0x36ed1a6c), BN_DEF(0xec0c5727, 0x5f270460),
+    (BN_ULONG)0x000017b1
+};
+
+#define BN_SMALL_PRIME_FACTORS_TOP OSSL_NELEM(small_prime_factors)
+static const BIGNUM _bignum_small_prime_factors = {
+    (BN_ULONG *)small_prime_factors,
+    BN_SMALL_PRIME_FACTORS_TOP,
+    BN_SMALL_PRIME_FACTORS_TOP,
+    0,
+    BN_FLG_STATIC_DATA
+};
+
+const BIGNUM *bn_get0_small_factors(void)
+{
+    return &_bignum_small_prime_factors;
+}
+
 int BN_GENCB_call(BN_GENCB *cb, int a, int b)
 {
     /* No callback means continue */
@@ -148,127 +183,199 @@ int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
     return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
 }
 
-int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
+/* See FIPS 186-4 C.3.1 Miller Rabin Probabilistic Primality Test. */
+int BN_is_prime_fasttest_ex(const BIGNUM *w, int checks, BN_CTX *ctx_passed,
                             int do_trial_division, BN_GENCB *cb)
 {
-    int i, j, ret = -1;
-    int k;
+    int i, status, ret = -1;
     BN_CTX *ctx = NULL;
-    BIGNUM *A1, *A1_odd, *A3, *check; /* taken from ctx */
-    BN_MONT_CTX *mont = NULL;
 
-    /* Take care of the really small primes 2 & 3 */
-    if (BN_is_word(a, 2) || BN_is_word(a, 3))
-        return 1;
-
-    /* Check odd and bigger than 1 */
-    if (!BN_is_odd(a) || BN_cmp(a, BN_value_one()) <= 0)
+    /* w must be bigger than 1 */
+    if (BN_cmp(w, BN_value_one()) <= 0)
         return 0;
 
-    if (checks == BN_prime_checks)
-        checks = BN_prime_checks_for_size(BN_num_bits(a));
+    /* w must be odd */
+    if (BN_is_odd(w)) {
+        /* Take care of the really small prime 3 */
+        if (BN_is_word(w, 3))
+            return 1;
+    } else {
+        /* 2 is the only even prime */
+        return BN_is_word(w, 2);
+    }
 
     /* first look for small factors */
     if (do_trial_division) {
         for (i = 1; i < NUMPRIMES; i++) {
-            BN_ULONG mod = BN_mod_word(a, primes[i]);
+            BN_ULONG mod = BN_mod_word(w, primes[i]);
             if (mod == (BN_ULONG)-1)
-                goto err;
+                return -1;
             if (mod == 0)
-                return BN_is_word(a, primes[i]);
+                return BN_is_word(w, primes[i]);
         }
         if (!BN_GENCB_call(cb, 1, -1))
-            goto err;
+            return -1;
     }
-
     if (ctx_passed != NULL)
         ctx = ctx_passed;
     else if ((ctx = BN_CTX_new()) == NULL)
         goto err;
-    BN_CTX_start(ctx);
 
-    A1 = BN_CTX_get(ctx);
-    A3 = BN_CTX_get(ctx);
-    A1_odd = BN_CTX_get(ctx);
-    check = BN_CTX_get(ctx);
-    if (check == NULL)
+    ret = bn_miller_rabin_is_prime(w, checks, ctx, cb, 0, &status);
+    if (!ret)
         goto err;
+    ret = (status == BN_PRIMETEST_PROBABLY_PRIME);
+err:
+    if (ctx_passed == NULL)
+        BN_CTX_free(ctx);
+    return ret;
+}
+
+/*
+ * Refer to FIPS 186-4 C.3.2 Enhanced Miller-Rabin Probabilistic Primality Test.
+ * OR C.3.1 Miller-Rabin Probabilistic Primality Test (if enhanced is zero).
+ * The Step numbers listed in the code refer to the enhanced case.
+ *
+ * if enhanced is set, then status returns one of the following:
+ *     BN_PRIMETEST_PROBABLY_PRIME
+ *     BN_PRIMETEST_COMPOSITE_WITH_FACTOR
+ *     BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME
+ * if enhanced is zero, then status returns either
+ *     BN_PRIMETEST_PROBABLY_PRIME or
+ *     BN_PRIMETEST_COMPOSITE
+ *
+ * returns 0 if there was an error, otherwise it returns 1.
+ */
+int bn_miller_rabin_is_prime(const BIGNUM *w, int iterations, BN_CTX *ctx,
+                             BN_GENCB *cb, int enhanced, int *status)
+{
+    int i, j, a, ret = 0;
+    BIGNUM *g, *w1, *w3, *x, *m, *z, *b;
+    BN_MONT_CTX *mont = NULL;
 
-    /* compute A1 := a - 1 */
-    if (!BN_copy(A1, a) || !BN_sub_word(A1, 1))
+    /* w must be odd */
+    if (!BN_is_odd(w))
+        return 0;
+
+    BN_CTX_start(ctx);
+    g = BN_CTX_get(ctx);
+    w1 = BN_CTX_get(ctx);
+    w3 = BN_CTX_get(ctx);
+    x = BN_CTX_get(ctx);
+    m = BN_CTX_get(ctx);
+    z = BN_CTX_get(ctx);
+    b = BN_CTX_get(ctx);
+
+    if (!(b != NULL
+            /* w1 := w - 1 */
+            && BN_copy(w1, w)
+            && BN_sub_word(w1, 1)
+            /* w3 := w - 3 */
+            && BN_copy(w3, w)
+            && BN_sub_word(w3, 3)))
         goto err;
-    /* compute A3 := a - 3 */
-    if (!BN_copy(A3, a) || !BN_sub_word(A3, 3))
+
+    /* check w is larger than 3, otherwise the random b will be too small */
+    if (BN_is_zero(w3) || BN_is_negative(w3))
         goto err;
 
-    /* write  A1  as  A1_odd * 2^k */
-    k = 1;
-    while (!BN_is_bit_set(A1, k))
-        k++;
-    if (!BN_rshift(A1_odd, A1, k))
+    /* (Step 1) Calculate largest integer 'a' such that 2^a divides w-1 */
+    a = 1;
+    while (!BN_is_bit_set(w1, a))
+        a++;
+    /* (Step 2) m = (w-1) / 2^a */
+    if (!BN_rshift(m, w1, a))
         goto err;
 
     /* Montgomery setup for computations mod a */
     mont = BN_MONT_CTX_new();
-    if (mont == NULL)
-        goto err;
-    if (!BN_MONT_CTX_set(mont, a, ctx))
+    if (mont == NULL || !BN_MONT_CTX_set(mont, w, ctx))
         goto err;
 
-    for (i = 0; i < checks; i++) {
-        /* 1 < check < a-1 */
-        if (!BN_priv_rand_range(check, A3) || !BN_add_word(check, 2))
-            goto err;
+    if (iterations == BN_prime_checks)
+        iterations = BN_prime_checks_for_size(BN_num_bits(w));
 
-        j = witness(check, a, A1, A1_odd, k, ctx, mont);
-        if (j == -1)
+    /* (Step 4) */
+    for (i = 0; i < iterations; ++i) {
+        /* (Step 4.1) obtain a Random string of bits b where 1 < b < w-1 */
+        if (!BN_priv_rand_range(b, w3) || !BN_add_word(b, 2)) /* 1 < b < w-1 */
             goto err;
-        if (j) {
-            ret = 0;
+
+        if (enhanced) {
+            /* (Step 4.3) */
+            if (!BN_gcd(g, b, w, ctx))
+                goto err;
+            /* (Step 4.4) */
+            if (!BN_is_one(g)) {
+                *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR;
+                ret = 1;
+                goto err;
+            }
+        }
+        /* (Step 4.5) z = b^m mod w */
+        if (!BN_mod_exp_mont(z, b, m, w, ctx, mont))
             goto err;
+        /* (Step 4.6) if (z = 1 or z = w-1) */
+        if (BN_is_one(z) || BN_cmp(z, w1) == 0)
+            goto outer_loop;
+        /* (Step 4.7) for j = 1 to a-1 */
+        for (j = 1; j < a ; ++j) {
+            /* (Step 4.7.1 - 4.7.2) x = z. z = x^2 mod w */
+            if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx))
+                goto err;
+            /* (Step 4.7.3) */
+            if (BN_cmp(z, w1) == 0)
+                goto outer_loop;
+            /* (Step 4.7.4) */
+            if (BN_is_one(z))
+                goto composite;
         }
         if (!BN_GENCB_call(cb, 1, i))
             goto err;
+        /* At this point z = b^((w-1)/2) mod w */
+        /* (Steps 4.8 - 4.9) x = z, z = x^2 mod w */
+        if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx))
+            goto err;
+        /* (Step 4.10) */
+        if (BN_is_one(z))
+            goto composite;
+        /* (Step 4.11) x = b^(w-1) mod w */
+        if (!BN_copy(x, z))
+            goto err;
+composite:
+        if (enhanced) {
+            /* (Step 4.1.2) g = GCD(x-1, w) */
+            if (!BN_sub_word(x, 1) || !BN_gcd(g, x, w, ctx))
+                goto err;
+            /* (Steps 4.1.3 - 4.1.4) */
+            if (BN_is_one(g))
+                *status = BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME;
+            else
+                *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR;
+        } else {
+            *status = BN_PRIMETEST_COMPOSITE;
+        }
+        ret = 1;
+        goto err;
+outer_loop: ;
+        /* (Step 4.1.5) */
     }
+    /* (Step 5) */
+    *status = BN_PRIMETEST_PROBABLY_PRIME;
     ret = 1;
- err:
-    if (ctx != NULL) {
-        BN_CTX_end(ctx);
-        if (ctx_passed == NULL)
-            BN_CTX_free(ctx);
-    }
+err:
+    BN_clear(g);
+    BN_clear(w1);
+    BN_clear(w3);
+    BN_clear(x);
+    BN_clear(m);
+    BN_clear(z);
+    BN_clear(b);
+    BN_CTX_end(ctx);
     BN_MONT_CTX_free(mont);
-
     return ret;
 }
 
-static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
-                   const BIGNUM *a1_odd, int k, BN_CTX *ctx,
-                   BN_MONT_CTX *mont)
-{
-    if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */
-        return -1;
-    if (BN_is_one(w))
-        return 0;               /* probably prime */
-    if (BN_cmp(w, a1) == 0)
-        return 0;               /* w == -1 (mod a), 'a' is probably prime */
-    while (--k) {
-        if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
-            return -1;
-        if (BN_is_one(w))
-            return 1;           /* 'a' is composite, otherwise a previous 'w'
-                                 * would have been == -1 (mod 'a') */
-        if (BN_cmp(w, a1) == 0)
-            return 0;           /* w == -1 (mod a), 'a' is probably prime */
-    }
-    /*
-     * If we get here, 'w' is the (a-1)/2-th power of the original 'w', and
-     * it is neither -1 nor +1 -- so 'a' cannot be prime
-     */
-    bn_check_top(w);
-    return 1;
-}
-
 static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods)
 {
     int i;
diff --git a/crypto/bn/bn_rsa_fips186_4.c b/crypto/bn/bn_rsa_fips186_4.c
new file mode 100644
index 0000000000..261669d0d0
--- /dev/null
+++ b/crypto/bn/bn_rsa_fips186_4.c
@@ -0,0 +1,346 @@
+/*
+ * Copyright 2018-2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright (c) 2018-2019, Oracle and/or its affiliates.  All rights reserved.
+ *
+ * Licensed under the OpenSSL license (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+/*
+ * According to NIST SP800-131A "Transitioning the use of cryptographic
+ * algorithms and key lengths" Generation of 1024 bit RSA keys are no longer
+ * allowed for signatures (Table 2) or key transport (Table 5). In the code
+ * below any attempt to generate 1024 bit RSA keys will result in an error (Note
+ * that digital signature verification can still use deprecated 1024 bit keys).
+ *
+ * Also see FIPS1402IG A.14
+ * FIPS 186-4 relies on the use of the auxiliary primes p1, p2, q1 and q2 that
+ * must be generated before the module generates the RSA primes p and q.
+ * Table B.1 in FIPS 186-4 specifies, for RSA modulus lengths of 2048 and
+ * 3072 bits only, the min/max total length of the auxiliary primes.
+ * When implementing the RSA signature generation algorithm
+ * with other approved RSA modulus sizes, the vendor shall use the limitations
+ * from Table B.1 that apply to the longest RSA modulus shown in Table B.1 of
+ * FIPS 186-4 whose length does not exceed that of the implementation's RSA
+ * modulus. In particular, when generating the primes for the 4096-bit RSA
+ * modulus the limitations stated for the 3072-bit modulus shall apply.
+ */
+#include <stdio.h>
+#include <openssl/bn.h>
+#include "bn_lcl.h"
+#include "internal/bn_int.h"
+
+/*
+ * FIPS 186-4 Table B.1. "Min length of auxiliary primes p1, p2, q1, q2".
+ *
+ * Params:
+ *     nbits The key size in bits.
+ * Returns:
+ *     The minimum size of the auxiliary primes or 0 if nbits is invalid.
+ */
+static int bn_rsa_fips186_4_aux_prime_min_size(int nbits)
+{
+    if (nbits >= 3072)
+        return 171;
+    if (nbits == 2048)
+        return 141;
+    return 0;
+}
+
+/*
+ * FIPS 186-4 Table B.1 "Maximum length of len(p1) + len(p2) and
+ * len(q1) + len(q2) for p,q Probable Primes".
+ *
+ * Params:
+ *     nbits The key size in bits.
+ * Returns:
+ *     The maximum length or 0 if nbits is invalid.
+ */
+static int bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(int nbits)
+{
+    if (nbits >= 3072)
+        return 1518;
+    if (nbits == 2048)
+        return 1007;
+    return 0;
+}
+
+/*
+ * FIPS 186-4 Table C.3 for error probability of 2^-100
+ * Minimum number of Miller Rabin Rounds for p1, p2, q1 & q2.
+ *
+ * Params:
+ *     aux_prime_bits The auxiliary prime size in bits.
+ * Returns:
+ *     The minimum number of Miller Rabin Rounds for an auxiliary prime, or
+ *     0 if aux_prime_bits is invalid.
+ */
+static int bn_rsa_fips186_4_aux_prime_MR_min_checks(int aux_prime_bits)
+{
+    if (aux_prime_bits > 170)
+        return 27;
+    if (aux_prime_bits > 140)
+        return 32;
+    return 0; /* Error case */
+}
+
+/*
+ * FIPS 186-4 Table C.3 for error probability of 2^-100
+ * Minimum number of Miller Rabin Rounds for p, q.
+ *
+ * Params:
+ *     nbits The key size in bits.
+ * Returns:
+ *     The minimum number of Miller Rabin Rounds required,
+ *     or 0 if nbits is invalid.
+ */
+int bn_rsa_fips186_4_prime_MR_min_checks(int nbits)
+{
+    if (nbits >= 3072) /* > 170 */
+        return 3;
+    if (nbits == 2048) /* > 140 */
+        return 4;
+    return 0; /* Error case */
+}
+
+/*
+ * Find the first odd integer that is a probable prime.
+ *
+ * See section FIPS 186-4 B.3.6 (Steps 4.2/5.2).
+ *
+ * Params:
+ *     Xp1 The passed in starting point to find a probably prime.
+ *     p1 The returned probable prime (first odd integer >= Xp1)
+ *     ctx A BN_CTX object.
+ *     cb An optional BIGNUM callback.
+ * Returns: 1 on success otherwise it returns 0.
+ */
+static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1,
+                                                BIGNUM *p1, BN_CTX *ctx,
+                                                BN_GENCB *cb)
+{
+    int ret = 0;
+    int i = 0;
+    int checks = bn_rsa_fips186_4_aux_prime_MR_min_checks(BN_num_bits(Xp1));
+
+    if (checks == 0 || BN_copy(p1, Xp1) == NULL)
+        return 0;
+
+    /* Find the first odd number >= Xp1 that is probably prime */
+    for(;;) {
+        i++;
+        BN_GENCB_call(cb, 0, i);
+        /* MR test with trial division */
+        if (BN_is_prime_fasttest_ex(p1, checks, ctx, 1, cb))
+            break;
+        /* Get next odd number */
+        if (!BN_add_word(p1, 2))
+            goto err;
+    }
+    BN_GENCB_call(cb, 2, i);
+    ret = 1;
+err:
+    return ret;
+}
+
+/*
+ * Generate a probable prime (p or q).
+ *
+ * See FIPS 186-4 B.3.6 (Steps 4 & 5)
+ *
+ * Params:
+ *     p The returned probable prime.
+ *     Xpout An optionally returned random number used during generation of p.
+ *     p1, p2 The returned auxiliary primes. If NULL they are not returned.
+ *     Xp An optional passed in value (that is random number used during
+ *        generation of p).
+ *     Xp1, Xp2 Optional passed in values that are normally generated
+ *              internally. Used to find p1, p2.
+ *     nlen The bit length of the modulus (the key size).
+ *     e The public exponent.
+ *     ctx A BN_CTX object.
+ *     cb An optional BIGNUM callback.
+ * Returns: 1 on success otherwise it returns 0.
+ */
+int bn_rsa_fips186_4_gen_prob_primes(BIGNUM *p, BIGNUM *Xpout,
+                                     BIGNUM *p1, BIGNUM *p2,
+                                     const BIGNUM *Xp, const BIGNUM *Xp1,
+                                     const BIGNUM *Xp2, int nlen,
+                                     const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
+{
+    int ret = 0;
+    BIGNUM *p1i = NULL, *p2i = NULL, *Xp1i = NULL, *Xp2i = NULL;
+    int bitlen;
+
+    if (p == NULL || Xpout == NULL)
+        return 0;
+
+    BN_CTX_start(ctx);
+
+    p1i = (p1 != NULL) ? p1 : BN_CTX_get(ctx);
+    p2i = (p2 != NULL) ? p2 : BN_CTX_get(ctx);
+    Xp1i = (Xp1 != NULL) ? (BIGNUM *)Xp1 : BN_CTX_get(ctx);
+    Xp2i = (Xp2 != NULL) ? (BIGNUM *)Xp2 : BN_CTX_get(ctx);
+    if (p1i == NULL || p2i == NULL || Xp1i == NULL || Xp2i == NULL)
+        goto err;
+
+    bitlen = bn_rsa_fips186_4_aux_prime_min_size(nlen);
+    if (bitlen == 0)
+        goto err;
+
+    /* (Steps 4.1/5.1): Randomly generate Xp1 if it is not passed in */
+    if (Xp1 == NULL) {
+        /* Set the top and bottom bits to make it odd and the correct size */
+        if (!BN_priv_rand(Xp1i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD))
+            goto err;
+    }
+    /* (Steps 4.1/5.1): Randomly generate Xp2 if it is not passed in */
+    if (Xp2 == NULL) {
+        /* Set the top and bottom bits to make it odd and the correct size */
+        if (!BN_priv_rand(Xp2i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD))
+            goto err;
+    }
+
+    /* (Steps 4.2/5.2) - find first auxiliary probable primes */
+    if (!bn_rsa_fips186_4_find_aux_prob_prime(Xp1i, p1i, ctx, cb)
+            || !bn_rsa_fips186_4_find_aux_prob_prime(Xp2i, p2i, ctx, cb))
+        goto err;
+    /* (Table B.1) auxiliary prime Max length check */
+    if ((BN_num_bits(p1i) + BN_num_bits(p2i)) >=
+            bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(nlen))
+        goto err;
+    /* (Steps 4.3/5.3) - generate prime */
+    if (!bn_rsa_fips186_4_derive_prime(p, Xpout, Xp, p1i, p2i, nlen, e, ctx, cb))
+        goto err;
+    ret = 1;
+err:
+    /* Zeroize any internally generated values that are not returned */
+    if (p1 == NULL)
+        BN_clear(p1i);
+    if (p2 == NULL)
+        BN_clear(p2i);
+    if (Xp1 == NULL)
+        BN_clear(Xp1i);
+    if (Xp2 == NULL)
+        BN_clear(Xp2i);
+    BN_CTX_end(ctx);
+    return ret;
+}
+
+/*
+ * Constructs a probable prime (a candidate for p or q) using 2 auxiliary
+ * prime numbers and the Chinese Remainder Theorem.
+ *
+ * See FIPS 186-4 C.9 "Compute a Probable Prime Factor Based on Auxiliary
+ * Primes". Used by FIPS 186-4 B.3.6 Section (4.3) for p and Section (5.3) for q.
+ *
+ * Params:
+ *     Y The returned prime factor (private_prime_factor) of the modulus n.
+ *     X The returned random number used during generation of the prime factor.
+ *     Xin An optional passed in value for X used for testing purposes.
+ *     r1 An auxiliary prime.
+ *     r2 An auxiliary prime.
+ *     nlen The desired length of n (the RSA modulus).
+ *     e The public exponent.
+ *     ctx A BN_CTX object.
+ *     cb An optional BIGNUM callback object.
+ * Returns: 1 on success otherwise it returns 0.
+ * Assumptions:
+ *     Y, X, r1, r2, e are not NULL.
+ */
+int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
+                                  const BIGNUM *r1, const BIGNUM *r2, int nlen,
+                                  const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
+{
+    int ret = 0;
+    int i, imax;
+    int bits = nlen >> 1;
+    int checks = bn_rsa_fips186_4_prime_MR_min_checks(nlen);
+    BIGNUM *tmp, *R, *r1r2x2, *y1, *r1x2;
+
+    if (checks == 0)
+        return 0;
+    BN_CTX_start(ctx);
+
+    R = BN_CTX_get(ctx);
+    tmp = BN_CTX_get(ctx);
+    r1r2x2 = BN_CTX_get(ctx);
+    y1 = BN_CTX_get(ctx);
+    r1x2 = BN_CTX_get(ctx);
+    if (r1x2 == NULL)
+        goto err;
+
+    if (Xin != NULL && BN_copy(X, Xin) == NULL)
+        goto err;
+
+    if (!(BN_lshift1(r1x2, r1)
+            /* (Step 1) GCD(2r1, r2) = 1 */
+            && BN_gcd(tmp, r1x2, r2, ctx)
+            && BN_is_one(tmp)
+            /* (Step 2) R = ((r2^-1 mod 2r1) * r2) - ((2r1^-1 mod r2)*2r1) */
+            && BN_mod_inverse(R, r2, r1x2, ctx)
+            && BN_mul(R, R, r2, ctx) /* R = (r2^-1 mod 2r1) * r2 */
+            && BN_mod_inverse(tmp, r1x2, r2, ctx)
+            && BN_mul(tmp, tmp, r1x2, ctx) /* tmp = (2r1^-1 mod r2)*2r1 */
+            && BN_sub(R, R, tmp)
+            /* Calculate 2r1r2 */
+            && BN_mul(r1r2x2, r1x2, r2, ctx)))
+        goto err;
+    /* Make positive by adding the modulus */
+    if (BN_is_negative(R) && !BN_add(R, R, r1r2x2))
+        goto err;
+
+    imax = 5 * bits; /* max = 5/2 * nbits */
+    for (;;) {
+        if (Xin == NULL) {
+            /*
+             * (Step 3) Choose Random X such that
+             *    sqrt(2) * 2^(nlen/2-1) < Random X < (2^(nlen/2)) - 1.
+             *
+             * For the lower bound:
+             *   sqrt(2) * 2^(nlen/2 - 1) == sqrt(2)/2 * 2^(nlen/2)
+             *   where sqrt(2)/2 = 0.70710678.. = 0.B504FC33F9DE...
+             *   so largest number will have B5... as the top byte
+             *   Setting the top 2 bits gives 0xC0.
+             */
+            if (!BN_priv_rand(X, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ANY))
+                goto end;
+        }
+        /* (Step 4) Y = X + ((R - X) mod 2r1r2) */
+        if (!BN_mod_sub(Y, R, X, r1r2x2, ctx) || !BN_add(Y, Y, X))
+            goto err;
+        /* (Step 5) */
+        i = 0;
+        for (;;) {
+            /* (Step 6) */
+            if (BN_num_bits(Y) > bits) {
+                if (Xin == NULL)
+                    break; /* Randomly Generated X so Go back to Step 3 */
+                else
+                    goto err; /* X is not random so it will always fail */
+            }
+            BN_GENCB_call(cb, 0, 2);
+
+            /* (Step 7) If GCD(Y-1) == 1 & Y is probably prime then return Y */
+            if (BN_copy(y1, Y) == NULL
+                    || !BN_sub_word(y1, 1)
+                    || !BN_gcd(tmp, y1, e, ctx))
+                goto err;
+            if (BN_is_one(tmp)
+                    && BN_is_prime_fasttest_ex(Y, checks, ctx, 1, cb))
+                goto end;
+            /* (Step 8-10) */
+            if (++i >= imax || !BN_add(Y, Y, r1r2x2))
+                goto err;
+        }
+    }
+end:
+    ret = 1;
+    BN_GENCB_call(cb, 3, 0);
+err:
+    BN_clear(y1);
+    BN_CTX_end(ctx);
+    return ret;
+}
diff --git a/crypto/bn/build.info b/crypto/bn/build.info
index a463eddabb..7e34ce41b3 100644
--- a/crypto/bn/build.info
+++ b/crypto/bn/build.info
@@ -5,7 +5,8 @@ SOURCE[../../libcrypto]=\
         bn_kron.c bn_sqrt.c bn_gcd.c bn_prime.c bn_err.c bn_sqr.c \
         {- $target{bn_asm_src} -} \
         bn_recp.c bn_mont.c bn_mpi.c bn_exp2.c bn_gf2m.c bn_nist.c \
-        bn_depr.c bn_const.c bn_x931p.c bn_intern.c bn_dh.c bn_srp.c
+        bn_depr.c bn_const.c bn_x931p.c bn_intern.c bn_dh.c bn_srp.c \
+        bn_rsa_fips186_4.c
 INCLUDE[../../libcrypto]=../../crypto/include
 
 INCLUDE[bn_exp.o]=..
diff --git a/crypto/include/internal/bn_int.h b/crypto/include/internal/bn_int.h
index 66e34ec5b8..514eaeeb90 100644
--- a/crypto/include/internal/bn_int.h
+++ b/crypto/include/internal/bn_int.h
@@ -87,4 +87,31 @@ int bn_rshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n);
 int bn_div_fixed_top(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m,
                      const BIGNUM *d, BN_CTX *ctx);
 
+#define BN_PRIMETEST_COMPOSITE                    0
+#define BN_PRIMETEST_COMPOSITE_WITH_FACTOR        1
+#define BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME 2
+#define BN_PRIMETEST_PROBABLY_PRIME               3
+
+int bn_miller_rabin_is_prime(const BIGNUM *w, int iterations, BN_CTX *ctx,
+                             BN_GENCB *cb, int enhanced, int *status);
+
+const BIGNUM *bn_get0_small_factors(void);
+
+int bn_rsa_fips186_4_prime_MR_min_checks(int nbits);
+
+int bn_rsa_fips186_4_gen_prob_primes(BIGNUM *p, BIGNUM *Xpout,
+                                     BIGNUM *p1, BIGNUM *p2,
+                                     const BIGNUM *Xp, const BIGNUM *Xp1,
+                                     const BIGNUM *Xp2, int nlen,
+                                     const BIGNUM *e, BN_CTX *ctx,
+                                     BN_GENCB *cb);
+
+int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
+                                  const BIGNUM *r1, const BIGNUM *r2, int nlen,
+                                  const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb);
+
+#ifdef  __cplusplus
+}
+#endif
+
 #endif
diff --git a/crypto/rsa/build.info b/crypto/rsa/build.info
index 87f924922f..70864170ed 100644
--- a/crypto/rsa/build.info
+++ b/crypto/rsa/build.info
@@ -3,4 +3,5 @@ SOURCE[../../libcrypto]=\
         rsa_ossl.c rsa_gen.c rsa_lib.c rsa_sign.c rsa_saos.c rsa_err.c \
         rsa_pk1.c rsa_ssl.c rsa_none.c rsa_oaep.c rsa_chk.c \
         rsa_pss.c rsa_x931.c rsa_asn1.c rsa_depr.c rsa_ameth.c rsa_prn.c \
-        rsa_pmeth.c rsa_crpt.c rsa_x931g.c rsa_meth.c rsa_mp.c
+        rsa_pmeth.c rsa_crpt.c rsa_x931g.c rsa_meth.c rsa_mp.c \
+        rsa_sp800_56b_gen.c rsa_sp800_56b_check.c
diff --git a/crypto/rsa/rsa_chk.c b/crypto/rsa/rsa_chk.c
index 805f998ff2..4f65dfa64b 100644
--- a/crypto/rsa/rsa_chk.c
+++ b/crypto/rsa/rsa_chk.c
@@ -16,8 +16,21 @@ int RSA_check_key(const RSA *key)
     return RSA_check_key_ex(key, NULL);
 }
 
+/*
+ * NOTE: Key validation requires separate checks to be able to be accessed
+ *  individually. These should be visible from the PKEY API..
+ *  See rsa_sp800_56b_check_public, rsa_sp800_56b_check_private and
+ *      rsa_sp800_56b_check_keypair.
+ */
 int RSA_check_key_ex(const RSA *key, BN_GENCB *cb)
 {
+#ifdef FIPS_MODE
+    if (!(rsa_sp800_56b_check_public(key)
+            && rsa_sp800_56b_check_private(key)
+            && rsa_sp800_56b_check_keypair(key, NULL, -1, RSA_bits(key))
+        return 0;
+
+#else
     BIGNUM *i, *j, *k, *l, *m;
     BN_CTX *ctx;
     int ret = 1, ex_primes = 0, idx;
@@ -225,4 +238,5 @@ int RSA_check_key_ex(const RSA *key, BN_GENCB *cb)
     BN_free(m);
     BN_CTX_free(ctx);
     return ret;
+#endif /* FIPS_MODE */
 }
diff --git a/crypto/rsa/rsa_gen.c b/crypto/rsa/rsa_gen.c
index 1d38ec993a..4bfe3c3a96 100644
--- a/crypto/rsa/rsa_gen.c
+++ b/crypto/rsa/rsa_gen.c
@@ -41,6 +41,7 @@ int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
 int RSA_generate_multi_prime_key(RSA *rsa, int bits, int primes,
                                  BIGNUM *e_value, BN_GENCB *cb)
 {
+#ifndef FIPS_MODE
     /* multi-prime is only supported with the builtin key generation */
     if (rsa->meth->rsa_multi_prime_keygen != NULL) {
         return rsa->meth->rsa_multi_prime_keygen(rsa, bits, primes,
@@ -57,13 +58,18 @@ int RSA_generate_multi_prime_key(RSA *rsa, int bits, int primes,
         else
             return 0;
     }
-
+#endif /* FIPS_MODE */
     return rsa_builtin_keygen(rsa, bits, primes, e_value, cb);
 }
 
 static int rsa_builtin_keygen(RSA *rsa, int bits, int primes, BIGNUM *e_value,
                               BN_GENCB *cb)
 {
+#ifdef FIPS_MODE
+    if (primes != 2)
+        return 0;
+    return rsa_sp800_56b_generate_key(rsa, bits, e_value, cb);
+#else
     BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *tmp, *prime;
     int ok = -1, n = 0, bitsr[RSA_MAX_PRIME_NUM], bitse = 0;
     int i = 0, quo = 0, rmd = 0, adj = 0, retries = 0;
@@ -391,4 +397,5 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, int primes, BIGNUM *e_value,
         BN_CTX_end(ctx);
     BN_CTX_free(ctx);
     return ok;
+#endif /* FIPS_MODE */
 }
diff --git a/crypto/rsa/rsa_lib.c b/crypto/rsa/rsa_lib.c
index 0848936b2d..f337a0df08 100644
--- a/crypto/rsa/rsa_lib.c
+++ b/crypto/rsa/rsa_lib.c
@@ -253,7 +253,7 @@ static uint32_t ilog_e(uint64_t v)
  *           \cdot(log_e(nBits \cdot log_e(2))^{2/3} - 4.69}{log_e(2)}
  * The two cube roots are merged together here.
  */
-static uint16_t rsa_compute_security_bits(int n)
+uint16_t rsa_compute_security_bits(int n)
 {
     uint64_t x;
     uint32_t lx;
diff --git a/crypto/rsa/rsa_locl.h b/crypto/rsa/rsa_locl.h
index 44a2a2df39..5dcd6eab7b 100644
--- a/crypto/rsa/rsa_locl.h
+++ b/crypto/rsa/rsa_locl.h
@@ -7,6 +7,9 @@
  * https://www.openssl.org/source/license.html
  */
 
+#ifndef RSA_LOCAL_HEADER_H
+#define RSA_LOCAL_HEADER_H
+
 #include <openssl/rsa.h>
 #include "internal/refcount.h"
 
@@ -130,3 +133,38 @@ void rsa_multip_info_free(RSA_PRIME_INFO *pinfo);
 RSA_PRIME_INFO *rsa_multip_info_new(void);
 int rsa_multip_calc_product(RSA *rsa);
 int rsa_multip_cap(int bits);
+
+uint16_t rsa_compute_security_bits(int n);
+
+int rsa_sp800_56b_validate_strength(int nbits, int strength);
+int rsa_check_pminusq_diff(BIGNUM *diff, const BIGNUM *p, const BIGNUM *q,
+                           int nbits);
+int rsa_get_lcm(BN_CTX *ctx, const BIGNUM *p, const BIGNUM *q,
+                BIGNUM *lcm, BIGNUM *gcd, BIGNUM *p1, BIGNUM *q1,
+                BIGNUM *p1q1);
+
+int rsa_check_public_exponent(const BIGNUM *e);
+int rsa_check_private_exponent(const RSA *rsa, int nbits, BN_CTX *ctx);
+int rsa_check_prime_factor(BIGNUM *p, BIGNUM *e, int nbits, BN_CTX *ctx);
+int rsa_check_prime_factor_range(const BIGNUM *p, int nbits, BN_CTX *ctx);
+int rsa_check_crt_components(const RSA *rsa, BN_CTX *ctx);
+
+int rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx);
+int rsa_sp800_56b_check_public(const RSA *rsa);
+int rsa_sp800_56b_check_private(const RSA *rsa);
+int rsa_sp800_56b_check_keypair(const RSA *rsa, const BIGNUM *efixed,
+                                int strength, int nbits);
+int rsa_sp800_56b_generate_key(RSA *rsa, int nbits, const BIGNUM *efixed,
+                               BN_GENCB *cb);
+
+int rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
+                                        const BIGNUM *e, BN_CTX *ctx);
+int rsa_fips186_4_gen_prob_primes(RSA *rsa, BIGNUM *p1, BIGNUM *p2,
+                                  BIGNUM *Xpout, const BIGNUM *Xp,
+                                  const BIGNUM *Xp1, const BIGNUM *Xp2,
+                                  BIGNUM *q1, BIGNUM *q2, BIGNUM *Xqout,
+                                  const BIGNUM *Xq, const BIGNUM *Xq1,
+                                  const BIGNUM *Xq2, int nbits,
+                                  const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb);
+
+#endif /* RSA_LOCAL_HEADER_H */
diff --git a/crypto/rsa/rsa_sp800_56b_check.c b/crypto/rsa/rsa_sp800_56b_check.c
new file mode 100644
index 0000000000..10e264e591
--- /dev/null
+++ b/crypto/rsa/rsa_sp800_56b_check.c
@@ -0,0 +1,386 @@
+/*
+ * Copyright 2018-2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright (c) 2018-2019, Oracle and/or its affiliates.  All rights reserved.
+ *
+ * Licensed under the OpenSSL license (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#include <openssl/err.h>
+#include <openssl/bn.h>
+#include "internal/bn_int.h"
+#include "rsa_locl.h"
+
+/*
+ * Part of the RSA keypair test.
+ * Check the Chinese Remainder Theorem components are valid.
+ *
+ * See SP800-5bBr1
+ *   6.4.1.2.3: rsakpv1-crt Step 7
+ *   6.4.1.3.3: rsakpv2-crt Step 7
+ */
+int rsa_check_crt_components(const RSA *rsa, BN_CTX *ctx)
+{
+    int ret = 0;
+    BIGNUM *r = NULL, *p1 = NULL, *q1 = NULL;
+
+    /* check if only some of the crt components are set */
+    if (rsa->dmp1 == NULL || rsa->dmq1 == NULL || rsa->iqmp == NULL) {
+        if (rsa->dmp1 != NULL || rsa->dmq1 != NULL || rsa->iqmp != NULL)
+            return 0;
+        return 1; /* return ok if all components are NULL */
+    }
+
+    BN_CTX_start(ctx);
+    r = BN_CTX_get(ctx);
+    p1 = BN_CTX_get(ctx);
+    q1 = BN_CTX_get(ctx);
+    ret = (q1 != NULL)
+          /* p1 = p -1 */
+          && (BN_copy(p1, rsa->p) != NULL)
+          && BN_sub_word(p1, 1)
+          /* q1 = q - 1 */
+          && (BN_copy(q1, rsa->q) != NULL)
+          && BN_sub_word(q1, 1)
+          /* (a) 1 < dP < (p – 1). */
+          && (BN_cmp(rsa->dmp1, BN_value_one()) > 0)
+          && (BN_cmp(rsa->dmp1, p1) < 0)
+          /* (b) 1 < dQ < (q - 1). */
+          && (BN_cmp(rsa->dmq1, BN_value_one()) > 0)
+          && (BN_cmp(rsa->dmq1, q1) < 0)
+          /* (c) 1 < qInv < p */
+          && (BN_cmp(rsa->iqmp, BN_value_one()) > 0)
+          && (BN_cmp(rsa->iqmp, rsa->p) < 0)
+          /* (d) 1 = (dP . e) mod (p - 1)*/
+          && BN_mod_mul(r, rsa->dmp1, rsa->e, p1, ctx)
+          && BN_is_one(r)
+          /* (e) 1 = (dQ . e) mod (q - 1) */
+          && BN_mod_mul(r, rsa->dmq1, rsa->e, q1, ctx)
+          && BN_is_one(r)
+          /* (f) 1 = (qInv . q) mod p */
+          && BN_mod_mul(r, rsa->iqmp, rsa->q, rsa->p, ctx)
+          && BN_is_one(r);
+    BN_clear(p1);
+    BN_clear(q1);
+    BN_CTX_end(ctx);
+    return ret;
+}
+
+/*
+ * Part of the RSA keypair test.
+ * Check that (√2)(2^(nbits/2 - 1) <= p <= 2^(nbits/2) - 1
+ *
+ * See SP800-5bBr1 6.4.1.2.1 Part 5 (c) & (g) - used for both p and q.
+ *
+ * (√2)(2^(nbits/2 - 1) = (√2/2)(2^(nbits/2))
+ * √2/2 = 0.707106781186547524400 = 0.B504F333F9DE6484597D8
+ * 0.B504F334 gives an approximation to 11 decimal places.
+ * The range is then from
+ *   0xB504F334_0000.......................000 to
+ *   0xFFFFFFFF_FFFF.......................FFF
+ */
+int rsa_check_prime_factor_range(const BIGNUM *p, int nbits, BN_CTX *ctx)
+{
+    int ret = 0;
+    BIGNUM *tmp, *low;
+
+    nbits >>= 1;
+
+    /* Upper bound check */
+    if (BN_num_bits(p) != nbits)
+        return 0;
+
+    BN_CTX_start(ctx);
+    tmp = BN_CTX_get(ctx);
+    low = BN_CTX_get(ctx);
+
+    /* set low = (√2)(2^(nbits/2 - 1) */
+    if (low == NULL || !BN_set_word(tmp, 0xB504F334))
+        goto err;
+
+    if (nbits >= 32) {
+        if (!BN_lshift(low, tmp, nbits - 32))
+            goto err;
+    } else if (!BN_rshift(low, tmp, 32 - nbits)) {
+        goto err;
+    }
+    if (BN_cmp(p, low) < 0)
+        goto err;
+    ret = 1;
+err:
+    BN_CTX_end(ctx);
+    return ret;
+}
+
+/*
+ * Part of the RSA keypair test.
+ * Check the prime factor (for either p or q)
+ * i.e: p is prime AND GCD(p - 1, e) = 1
+ *
+ * See SP800-5bBr1 6.4.1.2.3 Step 5 (a to d) & (e to h).
+ */
+int rsa_check_prime_factor(BIGNUM *p, BIGNUM *e, int nbits, BN_CTX *ctx)
+{
+    int checks = bn_rsa_fips186_4_prime_MR_min_checks(nbits);
+    int ret = 0;
+    BIGNUM *p1 = NULL, *gcd = NULL;
+
+    /* (Steps 5 a-b) prime test */
+    if (BN_is_prime_fasttest_ex(p, checks, ctx, 1, NULL) != 1
+            /* (Step 5c) (√2)(2^(nbits/2 - 1) <= p <= 2^(nbits/2 - 1) */
+            || rsa_check_prime_factor_range(p, nbits, ctx) != 1)
+        return 0;
+
+    BN_CTX_start(ctx);
+    p1 = BN_CTX_get(ctx);
+    gcd = BN_CTX_get(ctx);
+    ret = (gcd != NULL)
+          /* (Step 5d) GCD(p-1, e) = 1 */
+          && (BN_copy(p1, p) != NULL)
+          && BN_sub_word(p1, 1)
+          && BN_gcd(gcd, p1, e, ctx)
+          && BN_is_one(gcd);
+
+    BN_clear(p1);
+    BN_CTX_end(ctx);
+    return ret;
+}
+
+/*
+ * See SP800-56Br1 6.4.1.2.3 Part 6(a-b) Check the private exponent d
+ * satisfies:
+ *     (Step 6a) 2^(nBit/2) < d < LCM(p–1, q–1).
+ *     (Step 6b) 1 = (d*e) mod LCM(p–1, q–1)
+ */
+int rsa_check_private_exponent(const RSA *rsa, int nbits, BN_CTX *ctx)
+{
+    int ret;
+    BIGNUM *r, *p1, *q1, *lcm, *p1q1, *gcd;
+
+    /* (Step 6a) 2^(nbits/2) < d */
+    if (BN_num_bits(rsa->d) <= (nbits >> 1))
+        return 0;
+
+    BN_CTX_start(ctx);
+    r = BN_CTX_get(ctx);
+    p1 = BN_CTX_get(ctx);
+    q1 = BN_CTX_get(ctx);
+    lcm = BN_CTX_get(ctx);
+    p1q1 = BN_CTX_get(ctx);
+    gcd = BN_CTX_get(ctx);
+    ret = (gcd != NULL
+          /* LCM(p - 1, q - 1) */
+          && (rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) == 1)
+          /* (Step 6a) d < LCM(p - 1, q - 1) */
+          && (BN_cmp(rsa->d, lcm) < 0)
+          /* (Step 6b) 1 = (e . d) mod LCM(p - 1, q - 1) */
+          && BN_mod_mul(r, rsa->e, rsa->d, lcm, ctx)
+          && BN_is_one(r));
+
+    BN_clear(p1);
+    BN_clear(q1);
+    BN_clear(lcm);
+    BN_clear(gcd);
+    BN_CTX_end(ctx);
+    return ret;
+}
+
+/* Check exponent is odd, and has a bitlen ranging from [17..256] */
+int rsa_check_public_exponent(const BIGNUM *e)
+{
+    int bitlen = BN_num_bits(e);
+
+    return (BN_is_odd(e) &&  bitlen > 16 && bitlen < 257);
+}
+
+/*
+ * SP800-56Br1 6.4.1.2.1 (Step 5i): |p - q| > 2^(nbits/2 - 100)
+ * i.e- numbits(p-q-1) > (nbits/2 -100)
+ */
+int rsa_check_pminusq_diff(BIGNUM *diff, const BIGNUM *p, const BIGNUM *q,
+                           int nbits)
+{
+    int bitlen = (nbits >> 1) - 100;
+
+    if (!BN_sub(diff, p, q))
+        return -1;
+    BN_set_negative(diff, 0);
+
+    if (BN_is_zero(diff))
+        return 0;
+
+    if (!BN_sub_word(diff, 1))
+        return -1;
+    return (BN_num_bits(diff) > bitlen);
+}
+
+/* return LCM(p-1, q-1) */
+int rsa_get_lcm(BN_CTX *ctx, const BIGNUM *p, const BIGNUM *q,
+                BIGNUM *lcm, BIGNUM *gcd, BIGNUM *p1, BIGNUM *q1,
+                BIGNUM *p1q1)
+{
+    return BN_sub(p1, p, BN_value_one())    /* p-1 */
+           && BN_sub(q1, q, BN_value_one()) /* q-1 */
+           && BN_mul(p1q1, p1, q1, ctx)     /* (p-1)(q-1) */
+           && BN_gcd(gcd, p1, q1, ctx)
+           && BN_div(lcm, NULL, p1q1, gcd, ctx); /* LCM((p-1, q-1)) */
+}
+
+/*
+ * SP800-56Br1 6.4.2.2 Partial Public Key Validation for RSA refers to
+ * SP800-89 5.3.3 (Explicit) Partial Public Key Validation for RSA
+ * caveat is that the modulus must be as specified in SP800-56Br1
+ */
+int rsa_sp800_56b_check_public(const RSA *rsa)
+{
+    int ret = 0, nbits, iterations, status;
+    BN_CTX *ctx = NULL;
+    BIGNUM *gcd = NULL;
+
+    if (rsa->n == NULL || rsa->e == NULL)
+        return 0;
+
+    /*
+     * (Step a): modulus must be 2048 or 3072 (caveat from SP800-56Br1)
+     * NOTE: changed to allow keys >= 2048
+     */
+    nbits = BN_num_bits(rsa->n);
+    if (!rsa_sp800_56b_validate_strength(nbits, -1)) {
+        RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_KEY_LENGTH);
+        return 0;
+    }
+    if (!BN_is_odd(rsa->n)) {
+        RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS);
+        return 0;
+    }
+
+    /* (Steps b-c): 2^16 < e < 2^256, n and e must be odd */
+    if (!rsa_check_public_exponent(rsa->e)) {
+        RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC,
+               RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
+        return 0;
+    }
+
+    ctx = BN_CTX_new();
+    gcd = BN_new();
+    if (ctx == NULL || gcd == NULL)
+        goto err;
+
+    iterations = bn_rsa_fips186_4_prime_MR_min_checks(nbits);
+    /* (Steps d-f):
+     * The modulus is composite, but not a power of a prime.
+     * The modulus has no factors smaller than 752.
+     */
+    if (!BN_gcd(gcd, rsa->n, bn_get0_small_factors(), ctx) || !BN_is_one(gcd)) {
+        RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS);
+        goto err;
+    }
+
+    ret = bn_miller_rabin_is_prime(rsa->n, iterations, ctx, NULL, 1, &status);
+    if (ret != 1 || status != BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME) {
+        RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS);
+        ret = 0;
+        goto err;
+    }
+
+    ret = 1;
+err:
+    BN_free(gcd);
+    BN_CTX_free(ctx);
+    return ret;
+}
+
+/*
+ * Perform validation of the RSA private key to check that 0 < D < N.
+ */
+int rsa_sp800_56b_check_private(const RSA *rsa)
+{
+    if (rsa->d == NULL || rsa->n == NULL)
+        return 0;
+    return BN_cmp(rsa->d, BN_value_one()) >= 0 && BN_cmp(rsa->d, rsa->n) < 0;
+}
+
+/*
+ * RSA key pair validation.
+ *
+ * SP800-56Br1.
+ *    6.4.1.2 "RSAKPV1 Family: RSA Key - Pair Validation with a Fixed Exponent"
+ *    6.4.1.3 "RSAKPV2 Family: RSA Key - Pair Validation with a Random Exponent"
+ *
+ * It uses:
+ *     6.4.1.2.3 "rsakpv1 - crt"
+ *     6.4.1.3.3 "rsakpv2 - crt"
+ */
+int rsa_sp800_56b_check_keypair(const RSA *rsa, const BIGNUM *efixed,
+                                int strength, int nbits)
+{
+    int ret = 0;
+    BN_CTX *ctx = NULL;
+    BIGNUM *r = NULL;
+
+    if (rsa->p == NULL
+            || rsa->q == NULL
+            || rsa->e == NULL
+            || rsa->d == NULL
+            || rsa->n == NULL) {
+        RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_REQUEST);
+        return 0;
+    }
+    /* (Step 1): Check Ranges */
+    if (!rsa_sp800_56b_validate_strength(nbits, strength))
+        return 0;
+
+    /* If the exponent is known */
+    if (efixed != NULL) {
+        /* (2): Check fixed exponent matches public exponent. */
+        if (BN_cmp(efixed, rsa->e) != 0) {
+            RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_REQUEST);
+            return 0;
+        }
+    }
+    /* (Step 1.c): e is odd integer 65537 <= e < 2^256 */
+    if (!rsa_check_public_exponent(rsa->e)) {
+        /* exponent out of range */
+        RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR,
+               RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
+        return 0;
+    }
+    /* (Step 3.b): check the modulus */
+    if (nbits != BN_num_bits(rsa->n)) {
+        RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_KEYPAIR);
+        return 0;
+    }
+
+    ctx = BN_CTX_new();
+    if (ctx == NULL)
+        return 0;
+
+    BN_CTX_start(ctx);
+    r = BN_CTX_get(ctx);
+    if (r == NULL || !BN_mul(r, rsa->p, rsa->q, ctx))
+        goto err;
+    /* (Step 4.c): Check n = pq */
+    if (BN_cmp(rsa->n, r) != 0) {
+        RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_REQUEST);
+        goto err;
+    }
+
+    /* (Step 5): check prime factors p & q */
+    ret = rsa_check_prime_factor(rsa->p, rsa->e, nbits, ctx)
+          && rsa_check_prime_factor(rsa->q, rsa->e, nbits, ctx)
+          && (rsa_check_pminusq_diff(r, rsa->p, rsa->q, nbits) > 0)
+          /* (Step 6): Check the private exponent d */
+          && rsa_check_private_exponent(rsa, nbits, ctx)
+          /* 6.4.1.2.3 (Step 7): Check the CRT components */
+          && rsa_check_crt_components(rsa, ctx);
+    if (ret != 1)
+        RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_KEYPAIR);
+
+err:
+    BN_clear(r);
+    BN_CTX_end(ctx);
+    BN_CTX_free(ctx);
+    return ret;
+}
diff --git a/crypto/rsa/rsa_sp800_56b_gen.c b/crypto/rsa/rsa_sp800_56b_gen.c
new file mode 100644
index 0000000000..221136bd0c
--- /dev/null
+++ b/crypto/rsa/rsa_sp800_56b_gen.c
@@ -0,0 +1,362 @@
+/*
+ * Copyright 2018-2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright (c) 2018-2019, Oracle and/or its affiliates.  All rights reserved.
+ *
+ * Licensed under the OpenSSL license (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#include <openssl/err.h>
+#include <openssl/bn.h>
+#include "internal/bn_int.h"
+#include "rsa_locl.h"
+
+#define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048
+#define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112
+#define RSA_FIPS1864_MAX_KEYGEN_STRENGTH 256
+
+/*
+ * Generate probable primes 'p' & 'q'. See FIPS 186-4 Section B.3.6
+ * "Generation of Probable Primes with Conditions Based on Auxiliary Probable
+ * Primes".
+ *
+ * Params:
+ *     rsa  Object used to store primes p & q.
+ *     p1, p2 The returned auxiliary primes for p. If NULL they are not returned.
+ *     Xpout An optionally returned random number used during generation of p.
+ *     Xp An optional passed in value (that is random number used during
+ *        generation of p).
+ *     Xp1, Xp2 Optionally passed in randomly generated numbers from which
+ *              auxiliary primes p1 & p2 are calculated. If NULL these values
+ *              are generated internally.
+ *     q1, q2 The returned auxiliary primes for q. If NULL they are not returned.
+ *     Xqout An optionally returned random number used during generation of q.
+ *     Xq An optional passed in value (that is random number used during
+ *        generation of q).
+ *     Xq1, Xq2 Optionally passed in randomly generated numbers from which
+ *              auxiliary primes q1 & q2 are calculated. If NULL these values
+ *              are generated internally.
+ *     nbits The key size in bits (The size of the modulus n).
+ *     e The public exponent.
+ *     ctx A BN_CTX object.
+ *     cb An optional BIGNUM callback.
+ * Returns: 1 if successful, or  0 otherwise.
+ * Notes:
+ *     p1, p2, q1, q2, Xpout, Xqout are returned if they are not NULL.
+ *     Xp, Xp1, Xp2, Xq, Xq1, Xq2 are optionally passed in.
+ *     (Required for CAVS testing).
+ */
+int rsa_fips186_4_gen_prob_primes(RSA *rsa, BIGNUM *p1, BIGNUM *p2,
+                                  BIGNUM *Xpout, const BIGNUM *Xp,
+                                  const BIGNUM *Xp1, const BIGNUM *Xp2,
+                                  BIGNUM *q1, BIGNUM *q2, BIGNUM *Xqout,
+                                  const BIGNUM *Xq, const BIGNUM *Xq1,
+                                  const BIGNUM *Xq2, int nbits,
+                                  const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
+{
+    int ret = 0, ok;
+    BIGNUM *Xpo = NULL, *Xqo = NULL, *tmp = NULL;
+
+    /* (Step 1) Check key length
+     * NOTE: SP800-131A Rev1 Disallows key lengths of < 2048 bits for RSA
+     * Signature Generation and Key Agree/Transport.
+     */
+    if (nbits < RSA_FIPS1864_MIN_KEYGEN_KEYSIZE) {
+        RSAerr(RSA_F_RSA_FIPS186_4_GEN_PROB_PRIMES, RSA_R_INVALID_KEY_LENGTH);
+        return 0;
+    }
+
+    if (!rsa_check_public_exponent(e)) {
+        RSAerr(RSA_F_RSA_FIPS186_4_GEN_PROB_PRIMES,
+               RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
+        goto err;
+    }
+
+    /* (Step 3) Determine strength and check rand generator strength is ok -
+     * this step is redundant because the generator always returns a higher
+     * strength than is required.
+     */
+
+    BN_CTX_start(ctx);
+    tmp = BN_CTX_get(ctx);
+    Xpo = (Xpout != NULL) ? Xpout : BN_CTX_get(ctx);
+    Xqo = (Xqout != NULL) ? Xqout : BN_CTX_get(ctx);
+    if (tmp == NULL || Xpo == NULL || Xqo == NULL)
+        goto err;
+
+    if (rsa->p == NULL)
+        rsa->p = BN_secure_new();
+    if (rsa->q == NULL)
+        rsa->q = BN_secure_new();
+    if (rsa->p == NULL || rsa->q == NULL)
+        goto err;
+
+    /* (Step 4) Generate p, Xp */
+    if (!bn_rsa_fips186_4_gen_prob_primes(rsa->p, Xpo, p1, p2, Xp, Xp1, Xp2,
+                                          nbits, e, ctx, cb))
+        goto err;
+    for(;;) {
+        /* (Step 5) Generate q, Xq*/
+        if (!bn_rsa_fips186_4_gen_prob_primes(rsa->q, Xqo, q1, q2, Xq, Xq1,
+                                              Xq2, nbits, e, ctx, cb))
+            goto err;
+
+        /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */
+        ok = rsa_check_pminusq_diff(tmp, Xpo, Xqo, nbits);
+        if (ok < 0)
+            goto err;
+        if (ok == 0)
+            continue;
+
+        /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */
+        ok = rsa_check_pminusq_diff(tmp, rsa->p, rsa->q, nbits);
+        if (ok < 0)
+            goto err;
+        if (ok == 0)
+            continue;
+        break; /* successfully finished */
+    }
+    ret = 1;
+err:
+    /* Zeroize any internally generated values that are not returned */
+    if (Xpo != Xpout)
+        BN_clear(Xpo);
+    if (Xqo != Xqout)
+        BN_clear(Xqo);
+    BN_clear(tmp);
+
+    BN_CTX_end(ctx);
+    return ret;
+}
+
+/*
+ * Validates the RSA key size based on the target strength.
+ * See SP800-56Br1 6.3.1.1 (Steps 1a-1b)
+ *
+ * Params:
+ *     nbits The key size in bits.
+ *     strength The target strength in bits. -1 means the target
+ *              strength is unknown.
+ * Returns: 1 if the key size matches the target strength, or 0 otherwise.
+ */
+int rsa_sp800_56b_validate_strength(int nbits, int strength)
+{
+    int s = (int)rsa_compute_security_bits(nbits);
+
+    if (s < RSA_FIPS1864_MIN_KEYGEN_STRENGTH
+            || s > RSA_FIPS1864_MAX_KEYGEN_STRENGTH) {
+        RSAerr(RSA_F_RSA_SP800_56B_VALIDATE_STRENGTH, RSA_R_INVALID_MODULUS);
+        return 0;
+    }
+    if (strength != -1 && s != strength) {
+        RSAerr(RSA_F_RSA_SP800_56B_VALIDATE_STRENGTH, RSA_R_INVALID_STRENGTH);
+        return 0;
+    }
+    return 1;
+}
+
+/*
+ *
+ * Using p & q, calculate other required parameters such as n, d.
+ * as well as the CRT parameters dP, dQ, qInv.
+ *
+ * See SP800-56Br1
+ *   6.3.1.1 rsakpg1 - basic (Steps 3-4)
+ *   6.3.1.3 rsakpg1 - crt   (Step 5)
+ *
+ * Params:
+ *     rsa An rsa object.
+ *     nbits The key size.
+ *     e The public exponent.
+ *     ctx A BN_CTX object.
+ * Notes:
+ *   There is a small chance that the generated d will be too small.
+ * Returns: -1 = error,
+ *           0 = d is too small,
+ *           1 = success.
+ */
+int rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
+                                        const BIGNUM *e, BN_CTX *ctx)
+{
+    int ret = -1;
+    BIGNUM *p1, *q1, *lcm, *p1q1, *gcd;
+
+    BN_CTX_start(ctx);
+    p1 = BN_CTX_get(ctx);
+    q1 = BN_CTX_get(ctx);
+    lcm = BN_CTX_get(ctx);
+    p1q1 = BN_CTX_get(ctx);
+    gcd = BN_CTX_get(ctx);
+    if (gcd == NULL)
+        goto err;
+
+    /* LCM((p-1, q-1)) */
+    if (rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1)
+        goto err;
+
+    /* copy e */
+    BN_free(rsa->e);
+    rsa->e = BN_dup(e);
+    if (rsa->e == NULL)
+        goto err;
+
+    BN_clear_free(rsa->d);
+    /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
+    rsa->d = BN_secure_new();
+    if (rsa->d == NULL || BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL)
+        goto err;
+
+    /* (Step 3) return an error if d is too small */
+    if (BN_num_bits(rsa->d) <= (nbits >> 1)) {
+        ret = 0;
+        goto err;
+    }
+
+    /* (Step 4) n = pq */
+    if (rsa->n == NULL)
+        rsa->n = BN_new();
+    if (rsa->n == NULL || !BN_mul(rsa->n, rsa->p, rsa->q, ctx))
+        goto err;
+
+    /* (Step 5a) dP = d mod (p-1) */
+    if (rsa->dmp1 == NULL)
+        rsa->dmp1 = BN_new();
+    if (rsa->dmp1 == NULL || !BN_mod(rsa->dmp1, rsa->d, p1, ctx))
+        goto err;
+
+    /* (Step 5b) dQ = d mod (q-1) */
+    if (rsa->dmq1 == NULL)
+        rsa->dmq1 = BN_secure_new();
+    if (rsa->dmq1 == NULL || !BN_mod(rsa->dmq1, rsa->d, q1, ctx))
+        goto err;
+
+    /* (Step 5c) qInv = (inverse of q) mod p */
+    BN_free(rsa->iqmp);
+    rsa->iqmp = BN_secure_new();
+    if (rsa->iqmp == NULL
+            || BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL)
+        goto err;
+
+    ret = 1;
+err:
+    if (ret != 1) {
+        BN_free(rsa->e);
+        rsa->e = NULL;
+        BN_free(rsa->d);
+        rsa->d = NULL;
+        BN_free(rsa->n);
+        rsa->n = NULL;
+        BN_free(rsa->iqmp);
+        rsa->iqmp = NULL;
+        BN_free(rsa->dmq1);
+        rsa->dmq1 = NULL;
+        BN_free(rsa->dmp1);
+        rsa->dmp1 = NULL;
+    }
+    BN_clear(p1);
+    BN_clear(q1);
+    BN_clear(lcm);
+    BN_clear(p1q1);
+    BN_clear(gcd);
+
+    BN_CTX_end(ctx);
+    return ret;
+}
+
+/*
+ * Generate a SP800-56B RSA key.
+ *
+ * See SP800-56Br1 6.3.1 "RSA Key-Pair Generation with a Fixed Public Exponent"
+ *    6.3.1.1 rsakpg1 - basic
+ *    6.3.1.3 rsakpg1 - crt
+ *
+ * See also FIPS 186-4 Section B.3.6
+ * "Generation of Probable Primes with Conditions Based on Auxiliary
+ * Probable Primes."
+ *
+ * Params:
+ *     rsa The rsa object.
+ *     nbits The intended key size in bits.
+ *     efixed The public exponent. If NULL a default of 65537 is used.
+ *     cb An optional BIGNUM callback.
+ * Returns: 1 if successfully generated otherwise it returns 0.
+ */
+int rsa_sp800_56b_generate_key(RSA *rsa, int nbits, const BIGNUM *efixed,
+                               BN_GENCB *cb)
+{
+    int ret = 0;
+    int ok;
+    BN_CTX *ctx = NULL;
+    BIGNUM *e = NULL;
+
+    /* (Steps 1a-1b) : Currently ignores the strength check */
+    if (!rsa_sp800_56b_validate_strength(nbits, -1))
+        return 0;
+
+    ctx = BN_CTX_new();
+    if (ctx == NULL)
+        return 0;
+
+    /* Set default if e is not passed in */
+    if (efixed == NULL) {
+        e = BN_new();
+        if (e == NULL || !BN_set_word(e, 65537))
+            goto err;
+    } else {
+        e = (BIGNUM *)efixed;
+    }
+    /* (Step 1c) fixed exponent is checked later . */
+
+    for (;;) {
+        /* (Step 2) Generate prime factors */
+        if (!rsa_fips186_4_gen_prob_primes(rsa, NULL, NULL, NULL, NULL, NULL,
+                                           NULL, NULL, NULL, NULL, NULL, NULL,
+                                           NULL, nbits, e, ctx, cb))
+            goto err;
+        /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */
+        ok = rsa_sp800_56b_derive_params_from_pq(rsa, nbits, e, ctx);
+        if (ok < 0)
+            goto err;
+        if (ok > 0)
+            break;
+        /* Gets here if computed d is too small - so try again */
+    }
+
+    /* (Step 6) Do pairwise test - optional validity test has been omitted */
+    ret = rsa_sp800_56b_pairwise_test(rsa, ctx);
+err:
+    if (efixed == NULL)
+        BN_free(e);
+    BN_CTX_free(ctx);
+    return ret;
+}
+
+/*
+ * See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by
+ * verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1.
+ *
+ * Returns 1 if the RSA key passes the pairwise test or 0 it it fails.
+ */
+int rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx)
+{
+    int ret = 0;
+    BIGNUM *k, *tmp;
+
+    BN_CTX_start(ctx);
+    tmp = BN_CTX_get(ctx);
+    k = BN_CTX_get(ctx);
+    if (k == NULL)
+        goto err;
+
+    ret = (BN_set_word(k, 2)
+          && BN_mod_exp(tmp, k, rsa->e, rsa->n, ctx)
+          && BN_mod_exp(tmp, tmp, rsa->d, rsa->n, ctx)
+          && BN_cmp(k, tmp) == 0);
+    if (ret == 0)
+        RSAerr(RSA_F_RSA_SP800_56B_PAIRWISE_TEST, RSA_R_PAIRWISE_TEST_FAILURE);
+err:
+    BN_CTX_end(ctx);
+    return ret;
+}
diff --git a/test/bn_internal_test.c b/test/bn_internal_test.c
new file mode 100644
index 0000000000..eabeaf8b9f
--- /dev/null
+++ b/test/bn_internal_test.c
@@ -0,0 +1,103 @@
+/*
+ * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
+ *
+ * Licensed under the OpenSSL license (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+#include <assert.h>
+#include <errno.h>
+#include <stdio.h>
+#include <string.h>
+#include <ctype.h>
+
+#include <openssl/bn.h>
+#include <openssl/crypto.h>
+#include <openssl/err.h>
+#include <openssl/rand.h>
+#include "internal/nelem.h"
+#include "internal/numbers.h"
+#include "testutil.h"
+#include "bn_prime.h"
+#include "internal/bn_int.h"
+
+static BN_CTX *ctx;
+
+static int test_is_prime_enhanced(void)
+{
+    int ret;
+    int status = 0;
+    BIGNUM *bn = NULL;
+
+    ret = TEST_ptr(bn = BN_new())
+          /* test passing a prime returns the correct status */
+          && TEST_true(BN_set_word(bn, 11))
+          /* return extra parameters related to composite */
+          && TEST_true(bn_miller_rabin_is_prime(bn, 10, ctx, NULL, 1, &status))
+          && TEST_int_eq(status, BN_PRIMETEST_PROBABLY_PRIME);
+    BN_free(bn);
+    return ret;
+}
+
+static int composites[] = {
+    9, 21, 77, 81, 265
+};
+
+static int test_is_composite_enhanced(int id)
+{
+    int ret;
+    int status = 0;
+    BIGNUM *bn = NULL;
+
+    ret = TEST_ptr(bn = BN_new())
+          /* negative tests for different composite numbers */
+          && TEST_true(BN_set_word(bn, composites[id]))
+          && TEST_true(bn_miller_rabin_is_prime(bn, 10, ctx, NULL, 1, &status))
+          && TEST_int_ne(status, BN_PRIMETEST_PROBABLY_PRIME);
+
+    BN_free(bn);
+    return ret;
+}
+
+/* Test that multiplying all the small primes from 3 to 751 equals a constant.
+ * This test is mainly used to test that both 32 and 64 bit are correct.
+ */
+static int test_bn_small_factors(void)
+{
+    int ret = 0, i;
+    BIGNUM *b = NULL;
+
+    if (!(TEST_ptr(b = BN_new()) && TEST_true(BN_set_word(b, 3))))
+        goto err;
+
+    for (i = 1; i < NUMPRIMES; i++) {
+        prime_t p = primes[i];
+        if (p > 3 && p <= 751)
+            BN_mul_word(b, p);
+        if (p > 751)
+            break;
+    }
+    ret = TEST_BN_eq(bn_get0_small_factors(), b);
+err:
+    BN_free(b);
+    return ret;
+}
+
+int setup_tests(void)
+{
+    if (!TEST_ptr(ctx = BN_CTX_new()))
+        return 0;
+
+    ADD_TEST(test_is_prime_enhanced);
+    ADD_ALL_TESTS(test_is_composite_enhanced, (int)OSSL_NELEM(composites));
+    ADD_TEST(test_bn_small_factors);
+
+    return 1;
+}
+
+void cleanup_tests(void)
+{
+    BN_CTX_free(ctx);
+}
+
diff --git a/test/build.info b/test/build.info
index f7ec8a27db..9c721a5a2a 100644
--- a/test/build.info
+++ b/test/build.info
@@ -445,7 +445,9 @@ IF[{- !$disabled{tests} -}]
   IF[1]
     PROGRAMS{noinst}=asn1_internal_test modes_internal_test x509_internal_test \
                      tls13encryptiontest wpackettest ctype_internal_test \
-                     rdrand_sanitytest property_test
+                     rdrand_sanitytest property_test \
+                     rsa_sp800_56b_test bn_internal_test
+
     IF[{- !$disabled{poly1305} -}]
       PROGRAMS{noinst}=poly1305_internal_test
     ENDIF
@@ -528,6 +530,14 @@ IF[{- !$disabled{tests} -}]
     SOURCE[rdrand_sanitytest]=rdrand_sanitytest.c
     INCLUDE[rdrand_sanitytest]=../include ../apps/include
     DEPEND[rdrand_sanitytest]=../libcrypto.a libtestutil.a
+
+    SOURCE[rsa_sp800_56b_test]=rsa_sp800_56b_test.c
+    INCLUDE[rsa_sp800_56b_test]=.. ../include ../crypto/include ../crypto/rsa ../apps/include
+    DEPEND[rsa_sp800_56b_test]=../libcrypto.a libtestutil.a
+
+    SOURCE[bn_internal_test]=bn_internal_test.c
+    INCLUDE[bn_internal_test]=.. ../include ../crypto/include ../crypto/bn ../apps/include
+    DEPEND[bn_internal_test]=../libcrypto.a libtestutil.a
   ENDIF
 
   IF[{- !$disabled{mdc2} -}]
diff --git a/test/recipes/03-test_internal_bn.t b/test/recipes/03-test_internal_bn.t
new file mode 100644
index 0000000000..8aed18ac30
--- /dev/null
+++ b/test/recipes/03-test_internal_bn.t
@@ -0,0 +1,19 @@
+#! /usr/bin/env perl
+# Copyright 2018 The OpenSSL Project Authors. All Rights Reserved.
+#
+# Licensed under the OpenSSL license (the "License").  You may not use
+# this file except in compliance with the License.  You can obtain a copy
+# in the file LICENSE in the source distribution or at
+# https://www.openssl.org/source/license.html
+
+use strict;
+use OpenSSL::Test;              # get 'plan'
+use OpenSSL::Test::Simple;
+use OpenSSL::Test::Utils;
+
+setup("test_internal_bn");
+
+plan skip_all => "This test is unsupported in a shared library build on Windows"
+    if $^O eq 'MSWin32' && !disabled("shared");
+
+simple_test("test_internal_bn", "bn_internal_test");
diff --git a/test/recipes/03-test_internal_rsa_sp800_56b.t b/test/recipes/03-test_internal_rsa_sp800_56b.t
new file mode 100644
index 0000000000..2f5e003492
--- /dev/null
+++ b/test/recipes/03-test_internal_rsa_sp800_56b.t
@@ -0,0 +1,19 @@
+#! /usr/bin/env perl
+# Copyright 2018 The OpenSSL Project Authors. All Rights Reserved.
+#
+# Licensed under the OpenSSL license (the "License").  You may not use
+# this file except in compliance with the License.  You can obtain a copy
+# in the file LICENSE in the source distribution or at
+# https://www.openssl.org/source/license.html
+
+use strict;
+use OpenSSL::Test;              # get 'plan'
+use OpenSSL::Test::Simple;
+use OpenSSL::Test::Utils;
+
+setup("test_internal_rsa_sp800_56b");
+
+plan skip_all => "This test is unsupported in a shared library build on Windows"
+    if $^O eq 'MSWin32' && !disabled("shared");
+
+simple_test("test_internal_rsa_sp800_56b", "rsa_sp800_56b_test");
diff --git a/test/rsa_sp800_56b_test.c b/test/rsa_sp800_56b_test.c
new file mode 100644
index 0000000000..a64f9f2c1f
--- /dev/null
+++ b/test/rsa_sp800_56b_test.c
@@ -0,0 +1,634 @@
+/*
+ * Copyright 2018-2019 The OpenSSL Project Authors. All Rights Reserved.
+ *
+ * Licensed under the OpenSSL license (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#include <stdio.h>
+#include <string.h>
+
+#include "internal/nelem.h"
+
+#include <openssl/crypto.h>
+#include <openssl/err.h>
+#include <openssl/rand.h>
+#include <openssl/bn.h>
+
+#include "testutil.h"
+
+#ifdef OPENSSL_NO_RSA
+int setup_tests(void)
+{
+    /* No tests */
+    return 1;
+}
+#else
+# include "rsa_locl.h"
+# include <openssl/rsa.h>
+
+/* taken from RSA2 cavs data */
+static const unsigned char cav_e[] = {
+    0x01,0x00,0x01
+};
+static const unsigned char cav_Xp[] = {
+    0xcf,0x72,0x1b,0x9a,0xfd,0x0d,0x22,0x1a,0x74,0x50,0x97,0x22,0x76,0xd8,0xc0,
+    0xc2,0xfd,0x08,0x81,0x05,0xdd,0x18,0x21,0x99,0x96,0xd6,0x5c,0x79,0xe3,0x02,
+    0x81,0xd7,0x0e,0x3f,0x3b,0x34,0xda,0x61,0xc9,0x2d,0x84,0x86,0x62,0x1e,0x3d,
+    0x5d,0xbf,0x92,0x2e,0xcd,0x35,0x3d,0x6e,0xb9,0x59,0x16,0xc9,0x82,0x50,0x41,
+    0x30,0x45,0x67,0xaa,0xb7,0xbe,0xec,0xea,0x4b,0x9e,0xa0,0xc3,0x05,0xb3,0x88,
+    0xd4,0x4c,0xac,0xeb,0xe4,0x03,0xc6,0xca,0xcb,0xd9,0xd3,0x4e,0xf6,0x7f,0x2c,
+    0x27,0x1e,0x08,0x6c,0xc2,0xd6,0x45,0x1f,0x84,0xe4,0x3c,0x97,0x19,0xde,0xb8,
+    0x55,0xaf,0x0e,0xcf,0x9e,0xb0,0x9c,0x20,0xd3,0x1f,0xa8,0xd7,0x52,0xc2,0x95,
+    0x1c,0x80,0x15,0x42,0x4d,0x4f,0x19,0x16
+};
+static const unsigned char cav_Xp1[] = {
+    0xac,0x5f,0x7f,0x6e,0x33,0x3e,0x97,0x3a,0xb3,0x17,0x44,0xa9,0x0f,0x7a,0x54,
+    0x70,0x27,0x06,0x93,0xd5,0x49,0xde,0x91,0x83,0xbc,0x8a,0x7b,0x95
+};
+static const unsigned char cav_Xp2[] = {
+    0x0b,0xf6,0xe8,0x79,0x5a,0x81,0xae,0x90,0x1d,0xa4,0x38,0x74,0x9c,0x0e,0x6f,
+    0xe0,0x03,0xcf,0xc4,0x53,0x16,0x32,0x17,0xf7,0x09,0x5f,0xd9
+};
+static const unsigned char cav_Xq[] = {
+    0xfe,0xab,0xf2,0x7c,0x16,0x4a,0xf0,0x8d,0x31,0xc6,0x0a,0x82,0xe2,0xae,0xbb,
+    0x03,0x7e,0x7b,0x20,0x4e,0x64,0xb0,0x16,0xad,0x3c,0x01,0x1a,0xd3,0x54,0xbf,
+    0x2b,0xa4,0x02,0x9e,0xc3,0x0d,0x60,0x3d,0x1f,0xb9,0xc0,0x0d,0xe6,0x97,0x68,
+    0xbb,0x8c,0x81,0xd5,0xc1,0x54,0x96,0x0f,0x99,0xf0,0xa8,0xa2,0xf3,0xc6,0x8e,
+    0xec,0xbc,0x31,0x17,0x70,0x98,0x24,0xa3,0x36,0x51,0xa8,0x54,0xbd,0x9a,0x89,
+    0x99,0x6e,0x57,0x5e,0xd0,0x39,0x86,0xc3,0xa3,0x1b,0xc7,0xcf,0xc4,0x4f,0x47,
+    0x25,0x9e,0x2c,0x79,0xe1,0x2c,0xcc,0xe4,0x63,0xf4,0x02,0x84,0xf8,0xf6,0xa1,
+    0x5c,0x93,0x14,0xf2,0x68,0x5f,0x3a,0x90,0x2f,0x4e,0x5e,0xf9,0x16,0x05,0xcf,
+    0x21,0x63,0xca,0xfa,0xb0,0x08,0x02,0xc0
+};
+static const unsigned char cav_Xq1[] = {
+    0x9b,0x02,0xd4,0xba,0xf0,0xaa,0x14,0x99,0x6d,0xc0,0xb7,0xa5,0xe1,0xd3,0x70,
+    0xb6,0x5a,0xa2,0x9b,0x59,0xd5,0x8c,0x1e,0x9f,0x3f,0x9a,0xde,0xeb,0x9e,0x9c,
+    0x61,0xd6,0x5a,0xe1
+};
+static const unsigned char cav_Xq2[] = {
+    0x06,0x81,0x53,0xfd,0xa8,0x7b,0xa3,0x85,0x90,0x15,0x2c,0x97,0xb2,0xa0,0x17,
+    0x48,0xb0,0x7f,0x0a,0x01,0x6d
+};
+/* expected values */
+static const unsigned char cav_p1[] = {
+    0xac,0x5f,0x7f,0x6e,0x33,0x3e,0x97,0x3a,0xb3,0x17,0x44,0xa9,0x0f,0x7a,0x54,
+    0x70,0x27,0x06,0x93,0xd5,0x49,0xde,0x91,0x83,0xbc,0x8a,0x7b,0xc3
+};
+static const unsigned char cav_p2[] = {
+    0x0b,0xf6,0xe8,0x79,0x5a,0x81,0xae,0x90,0x1d,0xa4,0x38,0x74,0x9c,0x0e,0x6f,
+    0xe0,0x03,0xcf,0xc4,0x53,0x16,0x32,0x17,0xf7,0x09,0x5f,0xd9
+};
+static const unsigned char cav_q1[] = {
+    0x9b,0x02,0xd4,0xba,0xf0,0xaa,0x14,0x99,0x6d,0xc0,0xb7,0xa5,0xe1,0xd3,0x70,
+    0xb6,0x5a,0xa2,0x9b,0x59,0xd5,0x8c,0x1e,0x9f,0x3f,0x9a,0xde,0xeb,0x9e,0x9c,
+    0x61,0xd6,0x5d,0x47
+};
+static const unsigned char cav_q2[] = {
+    0x06,0x81,0x53,0xfd,0xa8,0x7b,0xa3,0x85,0x90,0x15,0x2c,0x97,0xb2,0xa0,0x17,
+    0x48,0xb0,0x7f,0x0a,0x01,0x8f
+};
+static const unsigned char cav_p[] = {
+    0xcf,0x72,0x1b,0x9a,0xfd,0x0d,0x22,0x1a,0x74,0x50,0x97,0x22,0x76,0xd8,0xc0,
+    0xc2,0xfd,0x08,0x81,0x05,0xdd,0x18,0x21,0x99,0x96,0xd6,0x5c,0x79,0xe3,0x02,
+    0x81,0xd7,0x0e,0x3f,0x3b,0x34,0xda,0x61,0xc9,0x2d,0x84,0x86,0x62,0x1e,0x3d,
+    0x5d,0xbf,0x92,0x2e,0xcd,0x35,0x3d,0x6e,0xb9,0x59,0x16,0xc9,0x82,0x50,0x41,
+    0x30,0x45,0x67,0xaa,0xb7,0xbe,0xec,0xea,0x4b,0x9e,0xa0,0xc3,0x05,0xbc,0x4c,
+    0x01,0xa5,0x4b,0xbd,0xa4,0x20,0xb5,0x20,0xd5,0x59,0x6f,0x82,0x5c,0x8f,0x4f,
+    0xe0,0x3a,0x4e,0x7e,0xfe,0x44,0xf3,0x3c,0xc0,0x0e,0x14,0x2b,0x32,0xe6,0x28,
+    0x8b,0x63,0x87,0x00,0xc3,0x53,0x4a,0x5b,0x71,0x7a,0x5b,0x28,0x40,0xc4,0x18,
+    0xb6,0x77,0x0b,0xab,0x59,0xa4,0x96,0x7d
+};
+static const unsigned char cav_q[] = {
+    0xfe,0xab,0xf2,0x7c,0x16,0x4a,0xf0,0x8d,0x31,0xc6,0x0a,0x82,0xe2,0xae,0xbb,
+    0x03,0x7e,0x7b,0x20,0x4e,0x64,0xb0,0x16,0xad,0x3c,0x01,0x1a,0xd3,0x54,0xbf,
+    0x2b,0xa4,0x02,0x9e,0xc3,0x0d,0x60,0x3d,0x1f,0xb9,0xc0,0x0d,0xe6,0x97,0x68,
+    0xbb,0x8c,0x81,0xd5,0xc1,0x54,0x96,0x0f,0x99,0xf0,0xa8,0xa2,0xf3,0xc6,0x8e,
+    0xec,0xbc,0x31,0x17,0x70,0x98,0x24,0xa3,0x36,0x51,0xa8,0x54,0xc4,0x44,0xdd,
+    0xf7,0x7e,0xda,0x47,0x4a,0x67,0x44,0x5d,0x4e,0x75,0xf0,0x4d,0x00,0x68,0xe1,
+    0x4a,0xec,0x1f,0x45,0xf9,0xe6,0xca,0x38,0x95,0x48,0x6f,0xdc,0x9d,0x1b,0xa3,
+    0x4b,0xfd,0x08,0x4b,0x54,0xcd,0xeb,0x3d,0xef,0x33,0x11,0x6e,0xce,0xe4,0x5d,
+    0xef,0xa9,0x58,0x5c,0x87,0x4d,0xc8,0xcf
+};
+static const unsigned char cav_n[] = {
+    0xce,0x5e,0x8d,0x1a,0xa3,0x08,0x7a,0x2d,0xb4,0x49,0x48,0xf0,0x06,0xb6,0xfe,
+    0xba,0x2f,0x39,0x7c,0x7b,0xe0,0x5d,0x09,0x2d,0x57,0x4e,0x54,0x60,0x9c,0xe5,
+    0x08,0x4b,0xe1,0x1a,0x73,0xc1,0x5e,0x2f,0xb6,0x46,0xd7,0x81,0xca,0xbc,0x98,
+    0xd2,0xf9,0xef,0x1c,0x92,0x8c,0x8d,0x99,0x85,0x28,0x52,0xd6,0xd5,0xab,0x70,
+    0x7e,0x9e,0xa9,0x87,0x82,0xc8,0x95,0x64,0xeb,0xf0,0x6c,0x0f,0x3f,0xe9,0x02,
+    0x29,0x2e,0x6d,0xa1,0xec,0xbf,0xdc,0x23,0xdf,0x82,0x4f,0xab,0x39,0x8d,0xcc,
+    0xac,0x21,0x51,0x14,0xf8,0xef,0xec,0x73,0x80,0x86,0xa3,0xcf,0x8f,0xd5,0xcf,
+    0x22,0x1f,0xcc,0x23,0x2f,0xba,0xcb,0xf6,0x17,0xcd,0x3a,0x1f,0xd9,0x84,0xb9,
+    0x88,0xa7,0x78,0x0f,0xaa,0xc9,0x04,0x01,0x20,0x72,0x5d,0x2a,0xfe,0x5b,0xdd,
+    0x16,0x5a,0xed,0x83,0x02,0x96,0x39,0x46,0x37,0x30,0xc1,0x0d,0x87,0xc2,0xc8,
+    0x33,0x38,0xed,0x35,0x72,0xe5,0x29,0xf8,0x1f,0x23,0x60,0xe1,0x2a,0x5b,0x1d,
+    0x6b,0x53,0x3f,0x07,0xc4,0xd9,0xbb,0x04,0x0c,0x5c,0x3f,0x0b,0xc4,0xd4,0x61,
+    0x96,0x94,0xf1,0x0f,0x4a,0x49,0xac,0xde,0xd2,0xe8,0x42,0xb3,0x4a,0x0b,0x64,
+    0x7a,0x32,0x5f,0x2b,0x5b,0x0f,0x8b,0x8b,0xe0,0x33,0x23,0x34,0x64,0xf8,0xb5,
+    0x7f,0x69,0x60,0xb8,0x71,0xe9,0xff,0x92,0x42,0xb1,0xf7,0x23,0xa8,0xa7,0x92,
+    0x04,0x3d,0x6b,0xff,0xf7,0xab,0xbb,0x14,0x1f,0x4c,0x10,0x97,0xd5,0x6b,0x71,
+    0x12,0xfd,0x93,0xa0,0x4a,0x3b,0x75,0x72,0x40,0x96,0x1c,0x5f,0x40,0x40,0x57,
+    0x13
+};
+static const unsigned char cav_d[] = {
+    0x47,0x47,0x49,0x1d,0x66,0x2a,0x4b,0x68,0xf5,0xd8,0x4a,0x24,0xfd,0x6c,0xbf,
+    0x56,0xb7,0x70,0xf7,0x9a,0x21,0xc8,0x80,0x9e,0xf4,0x84,0xcd,0x88,0x01,0x28,
+    0xea,0x50,0xab,0x13,0x63,0xdf,0xea,0x14,0x38,0xb5,0x07,0x42,0x81,0x2f,0xda,
+    0xe9,0x24,0x02,0x7e,0xaf,0xef,0x74,0x09,0x0e,0x80,0xfa,0xfb,0xd1,0x19,0x41,
+    0xe5,0xba,0x0f,0x7c,0x0a,0xa4,0x15,0x55,0xa2,0x58,0x8c,0x3a,0x48,0x2c,0xc6,
+    0xde,0x4a,0x76,0xfb,0x72,0xb6,0x61,0xe6,0xd2,0x10,0x44,0x4c,0x33,0xb8,0xd2,
+    0x74,0xb1,0x9d,0x3b,0xcd,0x2f,0xb1,0x4f,0xc3,0x98,0xbd,0x83,0xb7,0x7e,0x75,
+    0xe8,0xa7,0x6a,0xee,0xcc,0x51,0x8c,0x99,0x17,0x67,0x7f,0x27,0xf9,0x0d,0x6a,
+    0xb7,0xd4,0x80,0x17,0x89,0x39,0x9c,0xf3,0xd7,0x0f,0xdf,0xb0,0x55,0x80,0x1d,
+    0xaf,0x57,0x2e,0xd0,0xf0,0x4f,0x42,0x69,0x55,0xbc,0x83,0xd6,0x97,0x83,0x7a,
+    0xe6,0xc6,0x30,0x6d,0x3d,0xb5,0x21,0xa7,0xc4,0x62,0x0a,0x20,0xce,0x5e,0x5a,
+    0x17,0x98,0xb3,0x6f,0x6b,0x9a,0xeb,0x6b,0xa3,0xc4,0x75,0xd8,0x2b,0xdc,0x5c,
+    0x6f,0xec,0x5d,0x49,0xac,0xa8,0xa4,0x2f,0xb8,0x8c,0x4f,0x2e,0x46,0x21,0xee,
+    0x72,0x6a,0x0e,0x22,0x80,0x71,0xc8,0x76,0x40,0x44,0x61,0x16,0xbf,0xa5,0xf8,
+    0x89,0xc7,0xe9,0x87,0xdf,0xbd,0x2e,0x4b,0x4e,0xc2,0x97,0x53,0xe9,0x49,0x1c,
+    0x05,0xb0,0x0b,0x9b,0x9f,0x21,0x19,0x41,0xe9,0xf5,0x61,0xd7,0x33,0x2e,0x2c,
+    0x94,0xb8,0xa8,0x9a,0x3a,0xcc,0x6a,0x24,0x8d,0x19,0x13,0xee,0xb9,0xb0,0x48,
+    0x61
+};
+
+/* helper function */
+static BIGNUM *bn_load_new(const unsigned char *data, int sz)
+{
+    BIGNUM *ret = BN_new();
+    if (ret != NULL)
+        BN_bin2bn(data, sz, ret);
+    return ret;
+}
+
+/* helper function */
+static BIGNUM *bn_load(BN_CTX *ctx, const unsigned char *data, int sz)
+{
+    BIGNUM *ret = BN_CTX_get(ctx);
+    if (ret != NULL)
+        BN_bin2bn(data, sz, ret);
+    return ret;
+}
+
+static int test_check_public_exponent(void)
+{
+    int ret = 0;
+    BIGNUM *e = NULL;
+
+    ret = TEST_ptr(e = BN_new())
+          /* e is too small */
+          && TEST_true(BN_set_word(e, 65535))
+          && TEST_false(rsa_check_public_exponent(e))
+          /* e is even will fail */
+          && TEST_true(BN_set_word(e, 65536))
+          && TEST_false(rsa_check_public_exponent(e))
+          /* e is ok */
+          && TEST_true(BN_set_word(e, 65537))
+          && TEST_true(rsa_check_public_exponent(e))
+          /* e = 2^256 is too big */
+          && TEST_true(BN_lshift(e, BN_value_one(), 256))
+          && TEST_false(rsa_check_public_exponent(e))
+          /* e = 2^256-1 is odd and in range */
+          && TEST_true(BN_sub(e, e, BN_value_one()))
+          && TEST_true(rsa_check_public_exponent(e));
+    BN_free(e);
+    return ret;
+}
+
+static int test_check_prime_factor_range(void)
+{
+    int ret = 0;
+    BN_CTX *ctx = NULL;
+    BIGNUM *p = NULL;
+    BIGNUM *bn_p1 = NULL, *bn_p2 = NULL, *bn_p3 = NULL, *bn_p4 = NULL;
+    /* Some range checks that are larger than 32 bits */
+    static const unsigned char p1[] = { 0x0B, 0x50, 0x4F, 0x33, 0x3F };
+    static const unsigned char p2[] = { 0x10, 0x00, 0x00, 0x00, 0x00 };
+    static const unsigned char p3[] = { 0x0B, 0x50, 0x4F, 0x33, 0x40 };
+    static const unsigned char p4[] = { 0x0F, 0xFF, 0xFF, 0xFF, 0xFF };
+
+    /* (√2)(2^(nbits/2 - 1) <= p <= 2^(nbits/2) - 1
+     * For 8 bits:   0xB.504F <= p <= 0xF
+     * for 72 bits:  0xB504F333F. <= p <= 0xF_FFFF_FFFF
+     */
+    ret = TEST_ptr(p = BN_new())
+          && TEST_ptr(bn_p1 = bn_load_new(p1, sizeof(p1)))
+          && TEST_ptr(bn_p2 = bn_load_new(p2, sizeof(p2)))
+          && TEST_ptr(bn_p3 = bn_load_new(p3, sizeof(p3)))
+          && TEST_ptr(bn_p4 = bn_load_new(p4, sizeof(p4)))
+          && TEST_ptr(ctx = BN_CTX_new())
+          && TEST_true(BN_set_word(p, 0xA))
+          && TEST_false(rsa_check_prime_factor_range(p, 8, ctx))
+          && TEST_true(BN_set_word(p, 0x10))
+          && TEST_false(rsa_check_prime_factor_range(p, 8, ctx))
+          && TEST_true(BN_set_word(p, 0xB))
+          && TEST_true(rsa_check_prime_factor_range(p, 8, ctx))
+          && TEST_true(BN_set_word(p, 0xF))
+          && TEST_true(rsa_check_prime_factor_range(p, 8, ctx))
+          && TEST_false(rsa_check_prime_factor_range(bn_p1, 72, ctx))
+          && TEST_false(rsa_check_prime_factor_range(bn_p2, 72, ctx))
+          && TEST_true(rsa_check_prime_factor_range(bn_p3, 72, ctx))
+          && TEST_true(rsa_check_prime_factor_range(bn_p4, 72, ctx));
+
+    BN_free(bn_p4);
+    BN_free(bn_p3);
+    BN_free(bn_p2);
+    BN_free(bn_p1);
+    BN_free(p);
+    BN_CTX_free(ctx);
+    return ret;
+}
+
+static int test_check_prime_factor(void)
+{
+    int ret = 0;
+    BN_CTX *ctx = NULL;
+    BIGNUM *p = NULL, *e = NULL;
+    BIGNUM *bn_p1 = NULL, *bn_p2 = NULL, *bn_p3 = NULL;
+
+    /* Some range checks that are larger than 32 bits */
+    static const unsigned char p1[] = { 0x0B, 0x50, 0x4f, 0x33, 0x73 };
+    static const unsigned char p2[] = { 0x0B, 0x50, 0x4f, 0x33, 0x75 };
+    static const unsigned char p3[] = { 0x0F, 0x50, 0x00, 0x03, 0x75 };
+
+    ret = TEST_ptr(p = BN_new())
+          && TEST_ptr(bn_p1 = bn_load_new(p1, sizeof(p1)))
+          && TEST_ptr(bn_p2 = bn_load_new(p2, sizeof(p2)))
+          && TEST_ptr(bn_p3 = bn_load_new(p3, sizeof(p3)))
+          && TEST_ptr(e = BN_new())
+          && TEST_ptr(ctx = BN_CTX_new())
+          /* Fails the prime test */
+          && TEST_true(BN_set_word(e, 0x1))
+          && TEST_false(rsa_check_prime_factor(bn_p1, e, 72, ctx))
+          /* p is prime and in range and gcd(p-1, e) = 1 */
+          && TEST_true(rsa_check_prime_factor(bn_p2, e, 72, ctx))
+          /* gcd(p-1,e) = 1 test fails */
+          && TEST_true(BN_set_word(e, 0x2))
+          && TEST_false(rsa_check_prime_factor(p, e, 72, ctx))
+          /* p fails the range check */
+          && TEST_true(BN_set_word(e, 0x1))
+          && TEST_false(rsa_check_prime_factor(bn_p3, e, 72, ctx));
+
+    BN_free(bn_p3);
+    BN_free(bn_p2);
+    BN_free(bn_p1);
+    BN_free(e);
+    BN_free(p);
+    BN_CTX_free(ctx);
+    return ret;
+}
+
+static int test_check_private_exponent(void)
+{
+    int ret = 0;
+    RSA *key = NULL;
+    BN_CTX *ctx = NULL;
+    BIGNUM *p = NULL, *q = NULL, *e = NULL, *d = NULL, *n = NULL;
+
+    ret = TEST_ptr(key = RSA_new())
+          && TEST_ptr(ctx = BN_CTX_new())
+          && TEST_ptr(p = BN_new())
+          && TEST_ptr(q = BN_new())
+          && TEST_ptr(e = BN_new())
+          && TEST_ptr(d = BN_new())
+          && TEST_ptr(n = BN_new())
+          /* lcm(15-1,17-1) = 14*16 / 2 = 112 */
+          && TEST_true(BN_set_word(p, 15))
+          && TEST_true(BN_set_word(q, 17))
+          && TEST_true(BN_set_word(e, 5))
+          && TEST_true(BN_set_word(d, 157))
+          && TEST_true(BN_set_word(n, 15*17))
+          && TEST_true(RSA_set0_factors(key, p, q))
+          && TEST_true(RSA_set0_key(key, n, e, d))
+          /* fails since d >= lcm(p-1, q-1) */
+          && TEST_false(rsa_check_private_exponent(key, 8, ctx))
+          && TEST_true(BN_set_word(d, 45))
+          /* d is correct size and 1 = e.d mod lcm(p-1, q-1) */
+          && TEST_true(rsa_check_private_exponent(key, 8, ctx))
+          /* d is too small compared to nbits */
+          && TEST_false(rsa_check_private_exponent(key, 16, ctx))
+          /* d is too small compared to nbits */
+          && TEST_true(BN_set_word(d, 16))
+          && TEST_false(rsa_check_private_exponent(key, 8, ctx))
+          /* fail if 1 != e.d mod lcm(p-1, q-1) */
+          && TEST_true(BN_set_word(d, 46))
+          && TEST_false(rsa_check_private_exponent(key, 8, ctx));
+
+    RSA_free(key);
+    BN_CTX_free(ctx);
+    return ret;
+}
+
+static int test_check_crt_components(void)
+{
+    const int P = 15;
+    const int Q = 17;
+    const int E = 5;
+    const int N = P*Q;
+    const int DP = 3;
+    const int DQ = 13;
+    const int QINV = 8;
+
+    int ret = 0;
+    RSA *key = NULL;
+    BN_CTX *ctx = NULL;
+    BIGNUM *p = NULL, *q = NULL, *e = NULL;
+
+    ret = TEST_ptr(key = RSA_new())
+          && TEST_ptr(ctx = BN_CTX_new())
+          && TEST_ptr(p = BN_new())
+          && TEST_ptr(q = BN_new())
+          && TEST_ptr(e = BN_new())
+          && TEST_true(BN_set_word(p, P))
+          && TEST_true(BN_set_word(q, Q))
+          && TEST_true(BN_set_word(e, E))
+          && TEST_true(RSA_set0_factors(key, p, q))
+          && TEST_true(rsa_sp800_56b_derive_params_from_pq(key, 8, e, ctx))
+          && TEST_BN_eq_word(key->n, N)
+          && TEST_BN_eq_word(key->dmp1, DP)
+          && TEST_BN_eq_word(key->dmq1, DQ)
+          && TEST_BN_eq_word(key->iqmp, QINV)
+          && TEST_true(rsa_check_crt_components(key, ctx))
+          /* (a) 1 < dP < (p – 1). */
+          && TEST_true(BN_set_word(key->dmp1, 1))
+          && TEST_false(rsa_check_crt_components(key, ctx))
+          && TEST_true(BN_set_word(key->dmp1, P-1))
+          && TEST_false(rsa_check_crt_components(key, ctx))
+          && TEST_true(BN_set_word(key->dmp1, DP))
+          /* (b) 1 < dQ < (q - 1). */
+          && TEST_true(BN_set_word(key->dmq1, 1))
+          && TEST_false(rsa_check_crt_components(key, ctx))
+          && TEST_true(BN_set_word(key->dmq1, Q-1))
+          && TEST_false(rsa_check_crt_components(key, ctx))
+          && TEST_true(BN_set_word(key->dmq1, DQ))
+          /* (c) 1 < qInv < p */
+          && TEST_true(BN_set_word(key->iqmp, 1))
+          && TEST_false(rsa_check_crt_components(key, ctx))
+          && TEST_true(BN_set_word(key->iqmp, P))
+          && TEST_false(rsa_check_crt_components(key, ctx))
+          && TEST_true(BN_set_word(key->iqmp, QINV))
+          /* (d) 1 = (dP . e) mod (p - 1)*/
+          && TEST_true(BN_set_word(key->dmp1, DP+1))
+          && TEST_false(rsa_check_crt_components(key, ctx))
+          && TEST_true(BN_set_word(key->dmp1, DP))
+          /* (e) 1 = (dQ . e) mod (q - 1) */
+          && TEST_true(BN_set_word(key->dmq1, DQ-1))
+          && TEST_false(rsa_check_crt_components(key, ctx))
+          && TEST_true(BN_set_word(key->dmq1, DQ))
+          /* (f) 1 = (qInv . q) mod p */
+          && TEST_true(BN_set_word(key->iqmp, QINV+1))
+          && TEST_false(rsa_check_crt_components(key, ctx))
+          && TEST_true(BN_set_word(key->iqmp, QINV))
+          /* check defaults are still valid */
+          && TEST_true(rsa_check_crt_components(key, ctx));
+
+    BN_free(e);
+    RSA_free(key);
+    BN_CTX_free(ctx);
+    return ret;
+}
+
+static int test_pq_diff(void)
+{
+    int ret = 0;
+    BIGNUM *tmp = NULL, *p = NULL, *q = NULL;
+
+    ret = TEST_ptr(tmp = BN_new())
+          && TEST_ptr(p = BN_new())
+          && TEST_ptr(q = BN_new())
+          /* |1-(2+1)| > 2^1 */
+          && TEST_true(BN_set_word(p, 1))
+          && TEST_true(BN_set_word(q, 1+2))
+          && TEST_false(rsa_check_pminusq_diff(tmp, p, q, 202))
+          /* Check |p - q| > 2^(nbits/2 - 100) */
+          && TEST_true(BN_set_word(q, 1+3))
+          && TEST_true(rsa_check_pminusq_diff(tmp, p, q, 202))
+          && TEST_true(BN_set_word(p, 1+3))
+          && TEST_true(BN_set_word(q, 1))
+          && TEST_true(rsa_check_pminusq_diff(tmp, p, q, 202));
+    BN_free(p);
+    BN_free(q);
+    BN_free(tmp);
+    return ret;
+}
+
+static int test_invalid_keypair(void)
+{
+    int ret = 0;
+    RSA *key = NULL;
+    BN_CTX *ctx = NULL;
+    BIGNUM *p = NULL, *q = NULL, *n = NULL, *e = NULL, *d = NULL;
+
+    ret = TEST_ptr(key = RSA_new())
+          && TEST_ptr(ctx = BN_CTX_new())
+          /* NULL parameters */
+          && TEST_false(rsa_sp800_56b_check_keypair(key, NULL, -1, 2048))
+          /* load key */
+          && TEST_ptr(p = bn_load_new(cav_p, sizeof(cav_p)))
+          && TEST_ptr(q = bn_load_new(cav_q, sizeof(cav_q)))
+          && TEST_ptr(e = bn_load_new(cav_e, sizeof(cav_e)))
+          && TEST_ptr(n = bn_load_new(cav_n, sizeof(cav_n)))
+          && TEST_ptr(d = bn_load_new(cav_d, sizeof(cav_d)))
+          && TEST_true(RSA_set0_key(key, n, e, d))
+          && TEST_true(RSA_set0_factors(key, p, q))
+
+          /* bad strength/key size */
+          && TEST_false(rsa_sp800_56b_check_keypair(key, NULL, 100, 2048))
+          && TEST_false(rsa_sp800_56b_check_keypair(key, NULL, 112, 1024))
+          && TEST_false(rsa_sp800_56b_check_keypair(key, NULL, 128, 2048))
+          && TEST_false(rsa_sp800_56b_check_keypair(key, NULL, 140, 3072))
+          /* mismatching exponent */
+          && TEST_false(rsa_sp800_56b_check_keypair(key, BN_value_one(), -1,
+                        2048))
+          /* bad exponent */
+          && TEST_true(BN_add_word(e, 1))
+          && TEST_false(rsa_sp800_56b_check_keypair(key, NULL, -1,
+                                                    2048))
+          && TEST_true(BN_sub_word(e, 1))
+
+          /* mismatch between bits and modulus */
+          && TEST_false(rsa_sp800_56b_check_keypair(key, NULL, -1, 3072))
+          && TEST_true(rsa_sp800_56b_check_keypair(key, e, 112, 2048))
+          /* check n == pq failure */
+          && TEST_true(BN_add_word(n, 1))
+          && TEST_false(rsa_sp800_56b_check_keypair(key, NULL, -1, 2048))
+          && TEST_true(BN_sub_word(n, 1))
+          /* check p  */
+          && TEST_true(BN_sub_word(p, 2))
+          && TEST_true(BN_mul(n, p, q, ctx))
+          && TEST_false(rsa_sp800_56b_check_keypair(key, NULL, -1, 2048))
+          && TEST_true(BN_add_word(p, 2))
+          && TEST_true(BN_mul(n, p, q, ctx))
+          /* check q  */
+          && TEST_true(BN_sub_word(q, 2))
+          && TEST_true(BN_mul(n, p, q, ctx))
+          && TEST_false(rsa_sp800_56b_check_keypair(key, NULL, -1, 2048))
+          && TEST_true(BN_add_word(q, 2))
+          && TEST_true(BN_mul(n, p, q, ctx));
+
+    RSA_free(key);
+    BN_CTX_free(ctx);
+    return ret;
+}
+
+static int test_fips1864_keygen_kat(void)
+{
+    int ret = 0;
+    RSA *key = NULL;
+    BN_CTX *ctx = NULL;
+    BIGNUM *e, *Xp, *Xp1, *Xp2, *Xq, *Xq1, *Xq2;
+    BIGNUM *p1, *p2, *q1, *q2;
+    BIGNUM *p1_exp, *p2_exp, *q1_exp, *q2_exp;
+    BIGNUM *p_exp, *q_exp, *n_exp, *d_exp;
+    const BIGNUM *p, *q, *n, *d, *e2;
+
+    if (!(TEST_ptr(key = RSA_new()) && TEST_ptr(ctx = BN_CTX_new())))
+        goto err;
+    BN_CTX_start(ctx);
+
+    e = bn_load(ctx, cav_e, sizeof(cav_e));
+    Xp = bn_load(ctx, cav_Xp, sizeof(cav_Xp));
+    Xp1 = bn_load(ctx, cav_Xp1, sizeof(cav_Xp1));
+    Xp2 = bn_load(ctx, cav_Xp2, sizeof(cav_Xp2));
+    Xq = bn_load(ctx, cav_Xq, sizeof(cav_Xq));
+    Xq1 = bn_load(ctx, cav_Xq1, sizeof(cav_Xq1));
+    Xq2 = bn_load(ctx, cav_Xq2, sizeof(cav_Xq2));
+    p1_exp = bn_load(ctx, cav_p1, sizeof(cav_p1));
+    p2_exp = bn_load(ctx, cav_p2, sizeof(cav_p2));
+    q1_exp = bn_load(ctx, cav_q1, sizeof(cav_q1));
+    q2_exp = bn_load(ctx, cav_q2, sizeof(cav_q2));
+    p_exp = bn_load(ctx, cav_p, sizeof(cav_p));
+    q_exp = bn_load(ctx, cav_q, sizeof(cav_q));
+    n_exp = bn_load(ctx, cav_n, sizeof(cav_n));
+    d_exp = bn_load(ctx, cav_d, sizeof(cav_d));
+    p1 = BN_CTX_get(ctx);
+    p2 = BN_CTX_get(ctx);
+    q1 = BN_CTX_get(ctx);
+    q2 = BN_CTX_get(ctx);
+    ret = TEST_ptr(q2)
+          && TEST_true(rsa_fips186_4_gen_prob_primes(key, p1, p2, NULL, Xp, Xp1,
+                                                     Xp2, q1, q2, NULL, Xq, Xq1,
+                                                     Xq2, 2048, e, ctx, NULL))
+          && TEST_true(rsa_sp800_56b_derive_params_from_pq(key, 2048, e, ctx))
+          && TEST_BN_eq(p1_exp, p1)
+          && TEST_BN_eq(p2_exp, p2)
+          && TEST_BN_eq(q1_exp, q1)
+          && TEST_BN_eq(q2_exp, q2);
+    if (!ret)
+        goto err;
+
+    RSA_get0_key(key, &n, &e2, &d);
+    RSA_get0_factors(key, &p, &q);
+    ret = TEST_BN_eq(e, e2)
+          && TEST_BN_eq(p_exp, p)
+          && TEST_BN_eq(q_exp, q)
+          && TEST_BN_eq(n_exp, n)
+          && TEST_BN_eq(d_exp, d);
+err:
+    RSA_free(key);
+    BN_CTX_end(ctx);
+    BN_CTX_free(ctx);
+    return ret;
+}
+
+
+static int keygen_size[] =
+{
+    2048, 3072
+};
+
+static int test_sp80056b_keygen(int id)
+{
+    RSA *key = NULL;
+    int ret;
+    int sz = keygen_size[id];
+
+    ret = TEST_ptr(key = RSA_new())
+          && TEST_true(rsa_sp800_56b_generate_key(key, sz, NULL, NULL))
+          && TEST_true(rsa_sp800_56b_check_public(key))
+          && TEST_true(rsa_sp800_56b_check_private(key))
+          && TEST_true(rsa_sp800_56b_check_keypair(key, NULL, -1, sz));
+
+    RSA_free(key);
+    return ret;
+}
+
+static int test_check_private_key(void)
+{
+    int ret = 0;
+    BIGNUM *n = NULL, *d = NULL, *e = NULL;
+    RSA *key = NULL;
+
+    ret = TEST_ptr(key = RSA_new())
+          /* check NULL pointers fail */
+          && TEST_false(rsa_sp800_56b_check_private(key))
+          /* load private key */
+          && TEST_ptr(n = bn_load_new(cav_n, sizeof(cav_n)))
+          && TEST_ptr(d = bn_load_new(cav_d, sizeof(cav_d)))
+          && TEST_ptr(e = bn_load_new(cav_e, sizeof(cav_e)))
+          && TEST_true(RSA_set0_key(key, n, e, d))
+          /* check d is in range */
+          && TEST_true(rsa_sp800_56b_check_private(key))
+          /* check d is too low */
+          && TEST_true(BN_set_word(d, 0))
+          && TEST_false(rsa_sp800_56b_check_private(key))
+          /* check d is too high */
+          && TEST_ptr(BN_copy(d, n))
+          && TEST_false(rsa_sp800_56b_check_private(key));
+
+    RSA_free(key);
+    return ret;
+}
+
+static int test_check_public_key(void)
+{
+    int ret = 0;
+    BIGNUM *n = NULL, *e = NULL;
+    RSA *key = NULL;
+
+    ret = TEST_ptr(key = RSA_new())
+          /* check NULL pointers fail */
+          && TEST_false(rsa_sp800_56b_check_public(key))
+          /* load public key */
+          && TEST_ptr(e = bn_load_new(cav_e, sizeof(cav_e)))
+          && TEST_ptr(n = bn_load_new(cav_n, sizeof(cav_n)))
+          && TEST_true(RSA_set0_key(key, n, e, NULL))
+          /* check public key is valid */
+          && TEST_true(rsa_sp800_56b_check_public(key))
+          /* check fail if n is even */
+          && TEST_true(BN_add_word(n, 1))
+          && TEST_false(rsa_sp800_56b_check_public(key))
+          && TEST_true(BN_sub_word(n, 1))
+          /* check fail if n is wrong number of bits */
+          && TEST_true(BN_lshift1(n, n))
+          && TEST_false(rsa_sp800_56b_check_public(key))
+          && TEST_true(BN_rshift1(n, n))
+          /* test odd exponent fails */
+          && TEST_true(BN_add_word(e, 1))
+          && TEST_false(rsa_sp800_56b_check_public(key))
+          && TEST_true(BN_sub_word(e, 1))
+          /* modulus fails composite check */
+          && TEST_true(BN_add_word(n, 2))
+          && TEST_false(rsa_sp800_56b_check_public(key));
+
+    RSA_free(key);
+    return ret;
+}
+
+int setup_tests(void)
+{
+    ADD_TEST(test_check_public_exponent);
+    ADD_TEST(test_check_prime_factor_range);
+    ADD_TEST(test_check_prime_factor);
+    ADD_TEST(test_check_private_exponent);
+    ADD_TEST(test_check_crt_components);
+    ADD_TEST(test_check_private_key);
+    ADD_TEST(test_check_public_key);
+    ADD_TEST(test_invalid_keypair);
+    ADD_TEST(test_pq_diff);
+    ADD_TEST(test_fips1864_keygen_kat);
+    ADD_ALL_TESTS(test_sp80056b_keygen, (int)OSSL_NELEM(keygen_size));
+    return 1;
+}
+#endif
diff --git a/test/rsa_test.c b/test/rsa_test.c
index b351cebaae..084f533ac1 100644
--- a/test/rsa_test.c
+++ b/test/rsa_test.c
@@ -42,6 +42,8 @@ int setup_tests(void)
                         BN_bin2bn(dmp1, sizeof(dmp1)-1, NULL),  \
                         BN_bin2bn(dmq1, sizeof(dmq1)-1, NULL),  \
                         BN_bin2bn(iqmp, sizeof(iqmp)-1, NULL)); \
+    if (c == NULL)                                              \
+        return 0;                                               \
     memcpy(c, ctext_ex, sizeof(ctext_ex) - 1);                  \
     return sizeof(ctext_ex) - 1;