Augment RSA provider to generate CRT coefficients on EVP_PKEY_fromdata()

It would be helpful to be able to generate RSA's dmp1/dmq1/iqmp values
when not provided in the param list to EVP_PKEY_fromdata.  Augment the
provider in ossl_rsa_fromdata to preform this generation iff:
a) At least p q n e and e are provided
b) the new parameter OSSL_PARAM_RSA_DERIVE_PQ is set to 1

Fixes #21826

Reviewed-by: Shane Lontis <shane.lontis@oracle.com>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/21875)

11 files changed, 943 insertions, 123 deletions

diff --git a/CHANGES.md b/CHANGES.md
index 625eacb6d4..57507381e1 100644
--- a/CHANGES.md
+++ b/CHANGES.md
@@ -80,6 +80,12 @@ OpenSSL 3.2
 
 ### Changes between 3.1 and 3.2 [xx XXX xxxx]
 
+ * The EVP_PKEY_fromdata function has been augmented to allow for the derivation
+   of CRT (Chinese Remainder Theorem) parameters when requested.  See the
+   OSSL_PKEY_PARAM_DERIVE_FROM_PQ param in the EVP_PKEY-RSA documentation.
+
+   *Neil Horman*
+
  * The BLAKE2b hash algorithm supports a configurable output length
    by setting the "size" parameter.
 
diff --git a/crypto/rsa/rsa_backend.c b/crypto/rsa/rsa_backend.c
index 7b2efa8862..1a9b783a9b 100644
--- a/crypto/rsa/rsa_backend.c
+++ b/crypto/rsa/rsa_backend.c
@@ -64,22 +64,56 @@ static int collect_numbers(STACK_OF(BIGNUM) *numbers,
 int ossl_rsa_fromdata(RSA *rsa, const OSSL_PARAM params[], int include_private)
 {
     const OSSL_PARAM *param_n, *param_e,  *param_d = NULL;
-    BIGNUM *n = NULL, *e = NULL, *d = NULL;
+    const OSSL_PARAM *param_p, *param_q = NULL;
+    const OSSL_PARAM *param_derive = NULL;
+    BIGNUM *p = NULL, *q = NULL, *n = NULL, *e = NULL, *d = NULL;
     STACK_OF(BIGNUM) *factors = NULL, *exps = NULL, *coeffs = NULL;
     int is_private = 0;
+    int derive_from_pq = 0;
+    BN_CTX *ctx = NULL;
 
     if (rsa == NULL)
         return 0;
 
     param_n = OSSL_PARAM_locate_const(params, OSSL_PKEY_PARAM_RSA_N);
     param_e = OSSL_PARAM_locate_const(params, OSSL_PKEY_PARAM_RSA_E);
-    if (include_private)
-        param_d = OSSL_PARAM_locate_const(params, OSSL_PKEY_PARAM_RSA_D);
 
-    if ((param_n != NULL && !OSSL_PARAM_get_BN(param_n, &n))
-        || (param_e != NULL && !OSSL_PARAM_get_BN(param_e, &e))
-        || (param_d != NULL && !OSSL_PARAM_get_BN(param_d, &d)))
+    if ((param_n == NULL || !OSSL_PARAM_get_BN(param_n, &n))
+        || (param_e == NULL || !OSSL_PARAM_get_BN(param_e, &e))) {
+        ERR_raise(ERR_LIB_RSA, ERR_R_PASSED_NULL_PARAMETER);
         goto err;
+    }
+
+    if (include_private) {
+
+        param_derive = OSSL_PARAM_locate_const(params,
+                                           OSSL_PKEY_PARAM_RSA_DERIVE_FROM_PQ);
+        if ((param_derive != NULL)
+            && !OSSL_PARAM_get_int(param_derive, &derive_from_pq))
+            goto err;
+
+        param_d = OSSL_PARAM_locate_const(params, OSSL_PKEY_PARAM_RSA_D);
+        if (param_d != NULL && !OSSL_PARAM_get_BN(param_d, &d)) {
+            ERR_raise(ERR_LIB_RSA, ERR_R_PASSED_NULL_PARAMETER);
+            goto err;
+        }
+
+        if (derive_from_pq) {
+            ctx = BN_CTX_new_ex(rsa->libctx);
+            if (ctx == NULL)
+                goto err;
+
+            /* we need at minimum p, q */
+            param_p = OSSL_PARAM_locate_const(params, OSSL_PKEY_PARAM_RSA_FACTOR1);
+            param_q = OSSL_PARAM_locate_const(params, OSSL_PKEY_PARAM_RSA_FACTOR2);
+            if ((param_p == NULL || !OSSL_PARAM_get_BN(param_p, &p))
+                || (param_q == NULL || !OSSL_PARAM_get_BN(param_q, &q))) {
+                ERR_raise(ERR_LIB_RSA, ERR_R_PASSED_NULL_PARAMETER);
+                goto err;
+            }
+
+        }
+    }
 
     is_private = (d != NULL);
 
@@ -96,25 +130,121 @@ int ossl_rsa_fromdata(RSA *rsa, const OSSL_PARAM params[], int include_private)
                                 ossl_rsa_mp_coeff_names))
             goto err;
 
-        /* It's ok if this private key just has n, e and d */
+        if (derive_from_pq && sk_BIGNUM_num(exps) == 0
+            && sk_BIGNUM_num(coeffs) == 0) {
+            /*
+             * If we want to use crt to derive our exponents/coefficients, we
+             * need to have at least 2 factors
+             */
+            if (sk_BIGNUM_num(factors) < 2) {
+                ERR_raise(ERR_LIB_RSA, ERR_R_PASSED_NULL_PARAMETER);
+                goto err;
+            }
+
+            /*
+             * if we have more than two factors, n and d must also have
+             * been provided
+             */
+            if (sk_BIGNUM_num(factors) > 2
+                && (param_n == NULL || param_d == NULL)) {
+                ERR_raise(ERR_LIB_RSA, ERR_R_PASSED_NULL_PARAMETER);
+                goto err;
+            }
+
+            /* build our exponents and coefficients here */
+            if (sk_BIGNUM_num(factors) == 2) {
+                /* for 2 factors we can use the sp800 functions to do this */
+                if (!RSA_set0_factors(rsa, sk_BIGNUM_value(factors, 0),
+                                      sk_BIGNUM_value(factors, 1))) {
+                    ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
+                    goto err;
+                }
+                /*
+                 * once consumed by RSA_set0_factors, pop those off the stack
+                 * so we don't free them below
+                 */
+                sk_BIGNUM_pop(factors);
+                sk_BIGNUM_pop(factors);
+
+                /*
+                 * Note: Because we only have 2 factors here, there will be no
+                 * additional pinfo fields to hold additional factors, and
+                 * since we set our key and 2 factors above we can skip
+                 * the call to ossl_rsa_set0_all_params
+                 */
+                if (!ossl_rsa_sp800_56b_derive_params_from_pq(rsa,
+                                                              RSA_bits(rsa),
+                                                              NULL, ctx)) {
+                    ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
+                    goto err;
+                }
+            } else {
+#ifndef FIPS_MODULE
+                /*
+                 * in the multiprime case we have to generate exps/coeffs here
+                 * for each additional prime
+                 */
+                if (!ossl_rsa_multiprime_derive(rsa, RSA_bits(rsa),
+                                                sk_BIGNUM_num(factors),
+                                                rsa->e, factors, exps,
+                                                coeffs)) {
+                    ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
+                    goto err;
+                }
+
+                /*
+                 * Now we should have all our factors, exponents and
+                 * coefficients
+                 */
+                if (!ossl_rsa_set0_all_params(rsa, factors, exps, coeffs)) {
+                    ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
+                    goto err;
+                }
+
+#else
+                /* multiprime case is disallowed in FIPS mode, raise an error */
+                ERR_raise(ERR_LIB_RSA, ERR_R_UNSUPPORTED);
+                goto err;
+#endif
+            }
+
+        } else {
+            /*
+             * It's ok if this private key just has n, e and d
+             * but only if we're not using derive_from_pq
+             */
+            if (sk_BIGNUM_num(factors) != 0
+                && !ossl_rsa_set0_all_params(rsa, factors, exps, coeffs))
+                goto err;
+        }
+        /* sanity check to ensure we used everything in our stacks */
         if (sk_BIGNUM_num(factors) != 0
-            && !ossl_rsa_set0_all_params(rsa, factors, exps, coeffs))
+            || sk_BIGNUM_num(exps) != 0
+            || sk_BIGNUM_num(coeffs) != 0) {
+            ERR_raise_data(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR,
+                           "There are %d, %d, %d elements left on our factors, exps, coeffs stacks\n",
+                           sk_BIGNUM_num(factors), sk_BIGNUM_num(exps),
+                           sk_BIGNUM_num(coeffs));
             goto err;
+        }
     }
 
-
+    BN_clear_free(p);
+    BN_clear_free(q);
     sk_BIGNUM_free(factors);
     sk_BIGNUM_free(exps);
     sk_BIGNUM_free(coeffs);
+    BN_CTX_free(ctx);
     return 1;
 
  err:
     BN_free(n);
     BN_free(e);
     BN_free(d);
-    sk_BIGNUM_pop_free(factors, BN_free);
-    sk_BIGNUM_pop_free(exps, BN_free);
-    sk_BIGNUM_pop_free(coeffs, BN_free);
+    sk_BIGNUM_pop_free(factors, BN_clear_free);
+    sk_BIGNUM_pop_free(exps, BN_clear_free);
+    sk_BIGNUM_pop_free(coeffs, BN_clear_free);
+    BN_CTX_free(ctx);
     return 0;
 }
 
@@ -152,7 +282,7 @@ int ossl_rsa_todata(RSA *rsa, OSSL_PARAM_BLD *bld, OSSL_PARAM params[],
             || !ossl_param_build_set_multi_key_bn(bld, params,
                                                   ossl_rsa_mp_coeff_names,
                                                   coeffs))
-        goto err;
+            goto err;
     }
 
 #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS)
diff --git a/crypto/rsa/rsa_gen.c b/crypto/rsa/rsa_gen.c
index 0cdbb3fde2..f67e1152bb 100644
--- a/crypto/rsa/rsa_gen.c
+++ b/crypto/rsa/rsa_gen.c
@@ -71,15 +71,201 @@ int RSA_generate_multi_prime_key(RSA *rsa, int bits, int primes,
     return rsa_keygen(rsa->libctx, rsa, bits, primes, e_value, cb, 0);
 }
 
+DEFINE_STACK_OF(BIGNUM)
+
+/*
+ * Given input values, q, p, n, d and e, derive the exponents
+ * and coefficients for each prime in this key, placing the result
+ * on their respective exps and coeffs stacks
+ */
 #ifndef FIPS_MODULE
+int ossl_rsa_multiprime_derive(RSA *rsa, int bits, int primes,
+                               BIGNUM *e_value,
+                               STACK_OF(BIGNUM) *factors,
+                               STACK_OF(BIGNUM) *exps,
+                               STACK_OF(BIGNUM) *coeffs)
+{
+    STACK_OF(BIGNUM) *pplist = NULL, *pdlist = NULL;
+    BIGNUM *factor = NULL, *newpp = NULL, *newpd = NULL;
+    BIGNUM *dval = NULL, *newexp = NULL, *newcoeff = NULL;
+    BIGNUM *p = NULL, *q = NULL;
+    BIGNUM *dmp1 = NULL, *dmq1 = NULL, *iqmp = NULL;
+    BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL;
+    BN_CTX *ctx = NULL;
+    BIGNUM *tmp = NULL;
+    int i;
+    int ret = 0;
+
+    ctx = BN_CTX_new_ex(rsa->libctx);
+    if (ctx == NULL)
+        goto err;
+
+    BN_CTX_start(ctx);
+
+    pplist = sk_BIGNUM_new_null();
+    if (pplist == NULL)
+        goto err;
+
+    pdlist = sk_BIGNUM_new_null();
+    if (pdlist == NULL)
+        goto err;
+
+    r0 = BN_CTX_get(ctx);
+    r1 = BN_CTX_get(ctx);
+    r2 = BN_CTX_get(ctx);
+
+    if (r2 == NULL)
+        goto err;
+
+    BN_set_flags(r0, BN_FLG_CONSTTIME);
+    BN_set_flags(r1, BN_FLG_CONSTTIME);
+    BN_set_flags(r2, BN_FLG_CONSTTIME);
+
+    if (BN_copy(r1, rsa->n) == NULL)
+        goto err;
+
+    p = sk_BIGNUM_value(factors, 0);
+    q = sk_BIGNUM_value(factors, 1);
+
+    /* Build list of partial products of primes */
+    for (i = 0; i < sk_BIGNUM_num(factors); i++) {
+        switch (i) {
+        case 0:
+            /* our first prime, p */
+            if (!BN_sub(r2, p, BN_value_one()))
+                goto err;
+            BN_set_flags(r2, BN_FLG_CONSTTIME);
+            if (BN_mod_inverse(r1, r2, rsa->e, ctx) == NULL)
+                goto err;
+            break;
+        case 1:
+            /* second prime q */
+            if (!BN_mul(r1, p, q, ctx))
+                goto err;
+            tmp = BN_dup(r1);
+            if (tmp == NULL)
+                goto err;
+            if (!sk_BIGNUM_insert(pplist, tmp, sk_BIGNUM_num(pplist)))
+                goto err;
+            break;
+        default:
+            factor = sk_BIGNUM_value(factors, i);
+            /* all other primes */
+            if (!BN_mul(r1, r1, factor, ctx))
+                goto err;
+            tmp = BN_dup(r1);
+            if (tmp == NULL)
+                goto err;
+            if (!sk_BIGNUM_insert(pplist, tmp, sk_BIGNUM_num(pplist)))
+                goto err;
+            break;
+        }
+    }
+
+    /* build list of relative d values */
+    /* p -1 */
+    if (!BN_sub(r1, p, BN_value_one()))
+        goto err;
+    if (!BN_sub(r2, q, BN_value_one()))
+        goto err;
+    if (!BN_mul(r0, r1, r2, ctx))
+        goto err;
+    for (i = 2; i < sk_BIGNUM_num(factors); i++) {
+        factor = sk_BIGNUM_value(factors, i);
+        dval = BN_new();
+        if (dval == NULL)
+            goto err;
+        BN_set_flags(dval, BN_FLG_CONSTTIME);
+        if (!BN_sub(dval, factor, BN_value_one()))
+            goto err;
+        if (!BN_mul(r0, r0, dval, ctx))
+            goto err;
+        if (!sk_BIGNUM_insert(pdlist, dval, sk_BIGNUM_num(pdlist)))
+            goto err;
+    }
+
+    /* Calculate dmp1, dmq1 and additional exponents */
+    dmp1 = BN_secure_new();
+    if (dmp1 == NULL)
+        goto err;
+    dmq1 = BN_secure_new();
+    if (dmq1 == NULL)
+        goto err;
+
+    if (!BN_mod(dmp1, rsa->d, r1, ctx))
+        goto err;
+    if (!sk_BIGNUM_insert(exps, dmp1, sk_BIGNUM_num(exps)))
+        goto err;
+    dmp1 = NULL;
+
+    if (!BN_mod(dmq1, rsa->d, r2, ctx))
+        goto err;
+    if (!sk_BIGNUM_insert(exps, dmq1, sk_BIGNUM_num(exps)))
+        goto err;
+    dmq1 = NULL;
+
+    for (i = 2; i < sk_BIGNUM_num(factors); i++) {
+        newpd = sk_BIGNUM_value(pdlist, i - 2);
+        newexp = BN_new();
+        if (newexp == NULL)
+            goto err;
+        if (!BN_mod(newexp, rsa->d, newpd, ctx)) {
+            BN_free(newexp);
+            goto err;
+        }
+        if (!sk_BIGNUM_insert(exps, newexp, sk_BIGNUM_num(exps)))
+            goto err;
+    }
+
+    /* Calculate iqmp and additional coefficients */
+    iqmp = BN_new();
+    if (iqmp == NULL)
+        goto err;
+
+    if (BN_mod_inverse(iqmp, sk_BIGNUM_value(factors, 1),
+                       sk_BIGNUM_value(factors, 0), ctx) == NULL)
+        goto err;
+    if (!sk_BIGNUM_insert(coeffs, iqmp, sk_BIGNUM_num(coeffs)))
+        goto err;
+    iqmp = NULL;
+
+    for (i = 2; i < sk_BIGNUM_num(factors); i++) {
+        newpp = sk_BIGNUM_value(pplist, i - 2);
+        newcoeff = BN_new();
+        if (newcoeff == NULL)
+            goto err;
+        if (BN_mod_inverse(newcoeff, newpp, sk_BIGNUM_value(factors, i),
+                           ctx) == NULL) {
+            BN_free(newcoeff);
+            goto err;
+        }
+        if (!sk_BIGNUM_insert(coeffs, newcoeff, sk_BIGNUM_num(coeffs)))
+            goto err;
+    }
+
+    ret = 1;
+ err:
+    sk_BIGNUM_pop_free(pplist, BN_free);
+    sk_BIGNUM_pop_free(pdlist, BN_free);
+    BN_CTX_end(ctx);
+    BN_CTX_free(ctx);
+    BN_clear_free(dmp1);
+    BN_clear_free(dmq1);
+    BN_clear_free(iqmp);
+    return ret;
+}
+
 static int rsa_multiprime_keygen(RSA *rsa, int bits, int primes,
                                  BIGNUM *e_value, BN_GENCB *cb)
 {
-    BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *tmp, *prime;
+    BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *tmp, *tmp2, *prime;
     int n = 0, bitsr[RSA_MAX_PRIME_NUM], bitse = 0;
     int i = 0, quo = 0, rmd = 0, adj = 0, retries = 0;
     RSA_PRIME_INFO *pinfo = NULL;
     STACK_OF(RSA_PRIME_INFO) *prime_infos = NULL;
+    STACK_OF(BIGNUM) *factors = NULL;
+    STACK_OF(BIGNUM) *exps = NULL;
+    STACK_OF(BIGNUM) *coeffs = NULL;
     BN_CTX *ctx = NULL;
     BN_ULONG bitst = 0;
     unsigned long error = 0;
@@ -104,6 +290,18 @@ static int rsa_multiprime_keygen(RSA *rsa, int bits, int primes,
         return 0;
     }
 
+    factors = sk_BIGNUM_new_null();
+    if (factors == NULL)
+        return 0;
+
+    exps = sk_BIGNUM_new_null();
+    if (exps == NULL)
+        goto err;
+
+    coeffs = sk_BIGNUM_new_null();
+    if (coeffs == NULL)
+        goto err;
+
     ctx = BN_CTX_new_ex(rsa->libctx);
     if (ctx == NULL)
         goto err;
@@ -137,15 +335,6 @@ static int rsa_multiprime_keygen(RSA *rsa, int bits, int primes,
     if (!rsa->q && ((rsa->q = BN_secure_new()) == NULL))
         goto err;
     BN_set_flags(rsa->q, BN_FLG_CONSTTIME);
-    if (!rsa->dmp1 && ((rsa->dmp1 = BN_secure_new()) == NULL))
-        goto err;
-    BN_set_flags(rsa->dmp1, BN_FLG_CONSTTIME);
-    if (!rsa->dmq1 && ((rsa->dmq1 = BN_secure_new()) == NULL))
-        goto err;
-    BN_set_flags(rsa->dmq1, BN_FLG_CONSTTIME);
-    if (!rsa->iqmp && ((rsa->iqmp = BN_secure_new()) == NULL))
-        goto err;
-    BN_set_flags(rsa->iqmp, BN_FLG_CONSTTIME);
 
     /* initialize multi-prime components */
     if (primes > RSA_DEFAULT_PRIME_NUM) {
@@ -220,7 +409,7 @@ static int rsa_multiprime_keygen(RSA *rsa, int bits, int primes,
             ERR_set_mark();
             BN_set_flags(r2, BN_FLG_CONSTTIME);
             if (BN_mod_inverse(r1, r2, rsa->e, ctx) != NULL) {
-               /* GCD == 1 since inverse exists */
+                /* GCD == 1 since inverse exists */
                 break;
             }
             error = ERR_peek_last_error();
@@ -250,8 +439,14 @@ static int rsa_multiprime_keygen(RSA *rsa, int bits, int primes,
             /* i == 0, do nothing */
             if (!BN_GENCB_call(cb, 3, i))
                 goto err;
+            tmp = BN_dup(prime);
+            if (tmp == NULL)
+                goto err;
+            if (!sk_BIGNUM_insert(factors, tmp, sk_BIGNUM_num(factors)))
+                goto err;
             continue;
         }
+
         /*
          * if |r1|, product of factors so far, is not as long as expected
          * (by checking the first 4 bits are less than 0x9 or greater than
@@ -298,6 +493,10 @@ static int rsa_multiprime_keygen(RSA *rsa, int bits, int primes,
                  */
                 i = -1;
                 bitse = 0;
+                sk_BIGNUM_pop_free(factors, BN_clear_free);
+                factors = sk_BIGNUM_new_null();
+                if (factors == NULL)
+                    goto err;
                 continue;
             }
             retries++;
@@ -310,12 +509,20 @@ static int rsa_multiprime_keygen(RSA *rsa, int bits, int primes,
             goto err;
         if (!BN_GENCB_call(cb, 3, i))
             goto err;
+        tmp = BN_dup(prime);
+        if (tmp == NULL)
+            goto err;
+        if (!sk_BIGNUM_insert(factors, tmp, sk_BIGNUM_num(factors)))
+            goto err;
     }
 
     if (BN_cmp(rsa->p, rsa->q) < 0) {
         tmp = rsa->p;
         rsa->p = rsa->q;
         rsa->q = tmp;
+        /* mirror this in our factor stack */
+        if (!sk_BIGNUM_insert(factors, sk_BIGNUM_delete(factors, 0), 1))
+            goto err;
     }
 
     /* calculate d */
@@ -339,79 +546,51 @@ static int rsa_multiprime_keygen(RSA *rsa, int bits, int primes,
             goto err;
     }
 
-    {
-        BIGNUM *pr0 = BN_new();
 
-        if (pr0 == NULL)
-            goto err;
-
-        BN_with_flags(pr0, r0, BN_FLG_CONSTTIME);
-        if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx)) {
-            BN_free(pr0);
-            goto err;               /* d */
-        }
-        /* We MUST free pr0 before any further use of r0 */
-        BN_free(pr0);
-    }
-
-    {
-        BIGNUM *d = BN_new();
-
-        if (d == NULL)
-            goto err;
-
-        BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
-
-        /* calculate d mod (p-1) and d mod (q - 1) */
-        if (!BN_mod(rsa->dmp1, d, r1, ctx)
-            || !BN_mod(rsa->dmq1, d, r2, ctx)) {
-            BN_free(d);
-            goto err;
-        }
-
-        /* calculate CRT exponents */
-        for (i = 2; i < primes; i++) {
-            pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2);
-            /* pinfo->d == r_i - 1 */
-            if (!BN_mod(pinfo->d, d, pinfo->d, ctx)) {
-                BN_free(d);
-                goto err;
-            }
-        }
-
-        /* We MUST free d before any further use of rsa->d */
-        BN_free(d);
+    BN_set_flags(r0, BN_FLG_CONSTTIME);
+    if (BN_mod_inverse(rsa->d, rsa->e, r0, ctx) == NULL) {
+        goto err;               /* d */
     }
 
-    {
-        BIGNUM *p = BN_new();
+    /* derive any missing exponents and coefficients */
+    if (!ossl_rsa_multiprime_derive(rsa, bits, primes, e_value,
+                                    factors, exps, coeffs))
+        goto err;
 
-        if (p == NULL)
+    /*
+     * first 2 factors/exps are already tracked in p/q/dmq1/dmp1
+     * and the first coeff is in iqmp, so pop those off the stack
+     * Note, the first 2 factors/exponents are already tracked by p and q
+     * assign dmp1/dmq1 and iqmp
+     * the remaining pinfo values are separately allocated, so copy and delete 
+     * those
+     */
+    BN_clear_free(sk_BIGNUM_delete(factors, 0));
+    BN_clear_free(sk_BIGNUM_delete(factors, 0));
+    rsa->dmp1 = sk_BIGNUM_delete(exps, 0);
+    rsa->dmq1 = sk_BIGNUM_delete(exps, 0);
+    rsa->iqmp = sk_BIGNUM_delete(coeffs, 0);
+    for (i = 2; i < primes; i++) {
+        pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2);
+        tmp = sk_BIGNUM_delete(factors, 0);
+        BN_copy(pinfo->r, tmp);
+        BN_clear_free(tmp);
+        tmp = sk_BIGNUM_delete(exps, 0);
+        tmp2 = BN_copy(pinfo->d, tmp);
+        BN_clear_free(tmp);
+        if (tmp2 == NULL)
             goto err;
-        BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
-
-        /* calculate inverse of q mod p */
-        if (!BN_mod_inverse(rsa->iqmp, rsa->q, p, ctx)) {
-            BN_free(p);
+        tmp = sk_BIGNUM_delete(coeffs, 0);
+        tmp2 = BN_copy(pinfo->t, tmp);
+        BN_clear_free(tmp);
+        if (tmp2 == NULL)
             goto err;
-        }
-
-        /* calculate CRT coefficient for other primes */
-        for (i = 2; i < primes; i++) {
-            pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2);
-            BN_with_flags(p, pinfo->r, BN_FLG_CONSTTIME);
-            if (!BN_mod_inverse(pinfo->t, pinfo->pp, p, ctx)) {
-                BN_free(p);
-                goto err;
-            }
-        }
-
-        /* We MUST free p before any further use of rsa->p */
-        BN_free(p);
     }
-
     ok = 1;
  err:
+    sk_BIGNUM_free(factors);
+    sk_BIGNUM_free(exps);
+    sk_BIGNUM_free(coeffs);
     if (ok == -1) {
         ERR_raise(ERR_LIB_RSA, ERR_R_BN_LIB);
         ok = 0;
diff --git a/crypto/rsa/rsa_lib.c b/crypto/rsa/rsa_lib.c
index 1c3b33c28b..1bd1a0a7bd 100644
--- a/crypto/rsa/rsa_lib.c
+++ b/crypto/rsa/rsa_lib.c
@@ -744,9 +744,13 @@ int RSA_pkey_ctx_ctrl(EVP_PKEY_CTX *ctx, int optype, int cmd, int p1, void *p2)
 
 DEFINE_STACK_OF(BIGNUM)
 
-int ossl_rsa_set0_all_params(RSA *r, const STACK_OF(BIGNUM) *primes,
-                             const STACK_OF(BIGNUM) *exps,
-                             const STACK_OF(BIGNUM) *coeffs)
+/*
+ * Note: This function deletes values from the parameter
+ * stack values as they are consumed and set in the RSA key.
+ */
+int ossl_rsa_set0_all_params(RSA *r, STACK_OF(BIGNUM) *primes,
+                             STACK_OF(BIGNUM) *exps,
+                             STACK_OF(BIGNUM) *coeffs)
 {
 #ifndef FIPS_MODULE
     STACK_OF(RSA_PRIME_INFO) *prime_infos, *old_infos = NULL;
@@ -757,6 +761,8 @@ int ossl_rsa_set0_all_params(RSA *r, const STACK_OF(BIGNUM) *primes,
         return 0;
 
     pnum = sk_BIGNUM_num(primes);
+
+    /* we need at least 2 primes */
     if (pnum < 2)
         return 0;
 
@@ -764,6 +770,17 @@ int ossl_rsa_set0_all_params(RSA *r, const STACK_OF(BIGNUM) *primes,
                           sk_BIGNUM_value(primes, 1)))
         return 0;
 
+    /*
+     * if we managed to set everything above, remove those elements from the
+     * stack
+     * Note, we do this after the above all to ensure that we have taken
+     * ownership of all the elements in the RSA key to avoid memory leaks
+     * we also use delete 0 here as we are grabbing items from the end of the
+     * stack rather than the start, otherwise we could use pop
+     */
+    sk_BIGNUM_delete(primes, 0);
+    sk_BIGNUM_delete(primes, 0);
+
     if (pnum == sk_BIGNUM_num(exps)
         && pnum == sk_BIGNUM_num(coeffs) + 1) {
 
@@ -771,6 +788,11 @@ int ossl_rsa_set0_all_params(RSA *r, const STACK_OF(BIGNUM) *primes,
                                  sk_BIGNUM_value(exps, 1),
                                  sk_BIGNUM_value(coeffs, 0)))
         return 0;
+
+        /* as above, once we consume the above params, delete them from the list */
+        sk_BIGNUM_delete(exps, 0);
+        sk_BIGNUM_delete(exps, 0);
+        sk_BIGNUM_delete(coeffs, 0);
     }
 
 #ifndef FIPS_MODULE
@@ -786,9 +808,9 @@ int ossl_rsa_set0_all_params(RSA *r, const STACK_OF(BIGNUM) *primes,
             return 0;
 
         for (i = 2; i < pnum; i++) {
-            BIGNUM *prime = sk_BIGNUM_value(primes, i);
-            BIGNUM *exp = sk_BIGNUM_value(exps, i);
-            BIGNUM *coeff = sk_BIGNUM_value(coeffs, i - 1);
+            BIGNUM *prime = sk_BIGNUM_pop(primes);
+            BIGNUM *exp = sk_BIGNUM_pop(exps);
+            BIGNUM *coeff = sk_BIGNUM_pop(coeffs);
             RSA_PRIME_INFO *pinfo = NULL;
 
             if (!ossl_assert(prime != NULL && exp != NULL && coeff != NULL))
diff --git a/crypto/rsa/rsa_local.h b/crypto/rsa/rsa_local.h
index ea70da05ad..f0084aeab4 100644
--- a/crypto/rsa/rsa_local.h
+++ b/crypto/rsa/rsa_local.h
@@ -150,6 +150,10 @@ struct rsa_meth_st {
 /* Macros to test if a pkey or ctx is for a PSS key */
 #define pkey_is_pss(pkey) (pkey->ameth->pkey_id == EVP_PKEY_RSA_PSS)
 #define pkey_ctx_is_pss(ctx) (ctx->pmeth->pkey_id == EVP_PKEY_RSA_PSS)
+int ossl_rsa_multiprime_derive(RSA *rsa, int bits, int primes,
+                                 BIGNUM *e_value,
+                                 STACK_OF(BIGNUM) *factors, STACK_OF(BIGNUM) *exps,
+                                 STACK_OF(BIGNUM) *coeffs);
 
 RSA_PSS_PARAMS *ossl_rsa_pss_params_create(const EVP_MD *sigmd,
                                            const EVP_MD *mgf1md, int saltlen);
diff --git a/crypto/rsa/rsa_sp800_56b_gen.c b/crypto/rsa/rsa_sp800_56b_gen.c
index 9fa85bfdf3..bcc0fceab0 100644
--- a/crypto/rsa/rsa_sp800_56b_gen.c
+++ b/crypto/rsa/rsa_sp800_56b_gen.c
@@ -228,13 +228,16 @@ static int rsa_validate_rng_strength(EVP_RAND_CTX *rng, int nbits)
  * Returns: -1 = error,
  *           0 = d is too small,
  *           1 = success.
+ *
+ * SP800-56b key generation always passes a non NULL value for e.
+ * For other purposes, if e is NULL then it is assumed that e, n and d are
+ * already set in the RSA key and do not need to be recalculated.
  */
 int ossl_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);
@@ -254,32 +257,37 @@ int ossl_rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
     if (ossl_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;
+    /*
+     * if e is provided as a parameter, don't recompute e, d or n
+     */
+    if (e != NULL) {
+        /* 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)
-        goto err;
-    BN_set_flags(rsa->d, BN_FLG_CONSTTIME);
-    if (BN_mod_inverse(rsa->d, e, lcm, ctx) == 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)
+            goto err;
+        BN_set_flags(rsa->d, BN_FLG_CONSTTIME);
+        if (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 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 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)
diff --git a/doc/man7/EVP_PKEY-RSA.pod b/doc/man7/EVP_PKEY-RSA.pod
index dcd38fcee8..96562b6be0 100644
--- a/doc/man7/EVP_PKEY-RSA.pod
+++ b/doc/man7/EVP_PKEY-RSA.pod
@@ -132,6 +132,15 @@ The RSA "e" value. The value may be any odd number greater than or equal to
 65537. The default value is 65537.
 For legacy reasons a value of 3 is currently accepted but is deprecated.
 
+=item "rsa-derive-from-pq"  (B<OSSL_PKEY_PARAM_RSA_DERIVE_FROM_PQ>) <unsigned integer>
+
+Indicate that missing parameters not passed in the parameter list should be
+derived if not provided.  Setting a nonzero value will cause all
+needed exponents and coefficients to be derived if not available.  Setting this
+option requires at least OSSL_PARAM_RSA_FACTOR1, OSSL_PARAM_RSA_FACTOR2,
+and OSSL_PARAM_RSA_N to be provided.  This option is ignored if
+OSSL_KEYMGMT_SELECT_PRIVATE_KEY is not set in the selection parameter.
+
 =back
 
 =head2 RSA key generation parameters for FIPS module testing
diff --git a/include/crypto/rsa.h b/include/crypto/rsa.h
index 8eddc168f6..cb7f84b301 100644
--- a/include/crypto/rsa.h
+++ b/include/crypto/rsa.h
@@ -54,9 +54,9 @@ RSA *ossl_rsa_new_with_ctx(OSSL_LIB_CTX *libctx);
 OSSL_LIB_CTX *ossl_rsa_get0_libctx(RSA *r);
 void ossl_rsa_set0_libctx(RSA *r, OSSL_LIB_CTX *libctx);
 
-int ossl_rsa_set0_all_params(RSA *r, const STACK_OF(BIGNUM) *primes,
-                             const STACK_OF(BIGNUM) *exps,
-                             const STACK_OF(BIGNUM) *coeffs);
+int ossl_rsa_set0_all_params(RSA *r, STACK_OF(BIGNUM) *primes,
+                             STACK_OF(BIGNUM) *exps,
+                             STACK_OF(BIGNUM) *coeffs);
 int ossl_rsa_get0_all_params(RSA *r, STACK_OF(BIGNUM_const) *primes,
                              STACK_OF(BIGNUM_const) *exps,
                              STACK_OF(BIGNUM_const) *coeffs);
diff --git a/test/evp_extra_test.c b/test/evp_extra_test.c
index f3680a0fb4..131879b8e2 100644
--- a/test/evp_extra_test.c
+++ b/test/evp_extra_test.c
@@ -3080,6 +3080,70 @@ static int test_RSA_OAEP_set_null_label(void)
     return ret;
 }
 
+#ifndef OPENSSL_NO_DEPRECATED_3_0
+static int test_RSA_legacy(void)
+{
+    int ret = 0;
+    BIGNUM *p = NULL;
+    BIGNUM *q = NULL;
+    BIGNUM *n = NULL;
+    BIGNUM *e = NULL;
+    BIGNUM *d = NULL;
+    const EVP_MD *md = EVP_sha256();
+    EVP_MD_CTX *ctx = NULL;
+    EVP_PKEY *pkey = NULL;
+    RSA *rsa = NULL;
+
+    if (nullprov != NULL)
+        return TEST_skip("Test does not support a non-default library context");
+
+    if (!TEST_ptr(p = BN_dup(BN_value_one()))
+        || !TEST_ptr(q = BN_dup(BN_value_one()))
+        || !TEST_ptr(n = BN_dup(BN_value_one()))
+        || !TEST_ptr(e = BN_dup(BN_value_one()))
+        || !TEST_ptr(d = BN_dup(BN_value_one())))
+        goto err;
+
+    if (!TEST_ptr(rsa = RSA_new())
+        || !TEST_ptr(pkey = EVP_PKEY_new())
+        || !TEST_ptr(ctx = EVP_MD_CTX_new()))
+        goto err;
+
+    if (!TEST_true(RSA_set0_factors(rsa, p, q)))
+        goto err;
+    p = NULL;
+    q = NULL;
+
+    if (!TEST_true(RSA_set0_key(rsa, n, e, d)))
+        goto err;
+    n = NULL;
+    e = NULL;
+    d = NULL;
+
+    if (!TEST_true(EVP_PKEY_assign_RSA(pkey, rsa)))
+        goto err;
+
+    rsa = NULL;
+
+    if (!TEST_true(EVP_DigestSignInit(ctx, NULL, md, NULL, pkey)))
+        goto err;
+
+    ret = 1;
+
+err:
+    RSA_free(rsa);
+    EVP_MD_CTX_free(ctx);
+    EVP_PKEY_free(pkey);
+    BN_free(p);
+    BN_free(q);
+    BN_free(n);
+    BN_free(e);
+    BN_free(d);
+
+    return re