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)

7 files changed, 811 insertions, 3 deletions

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;
+}