Support multi-prime RSA (RFC 8017)

* Introduce RSA_generate_multi_prime_key to generate multi-prime
  RSA private key. As well as the following functions:
    RSA_get_multi_prime_extra_count
    RSA_get0_multi_prime_factors
    RSA_get0_multi_prime_crt_params
    RSA_set0_multi_prime_params
    RSA_get_version
* Support EVP operations for multi-prime RSA
* Support ASN.1 operations for multi-prime RSA
* Support multi-prime check in RSA_check_key_ex
* Support multi-prime RSA in apps/genrsa and apps/speed
* Support multi-prime RSA manipulation functions
* Test cases and documentation are added
* CHANGES is updated

Reviewed-by: Tim Hudson <tjh@openssl.org>
Reviewed-by: Bernd Edlinger <bernd.edlinger@hotmail.de>
(Merged from https://github.com/openssl/openssl/pull/4241)

29 files changed, 1559 insertions, 99 deletions

diff --git a/CHANGES b/CHANGES
index 0b0c3cab2d..3ae8b4d0bd 100644
--- a/CHANGES
+++ b/CHANGES
@@ -9,6 +9,9 @@
 
  Changes between 1.1.0f and 1.1.1 [xx XXX xxxx]
 
+  *) Add multi-prime RSA (RFC 8017) support.
+     [Paul Yang]
+
   *) Add SM3 implemented according to GB/T 32905-2016
      [ Jack Lloyd <jack.lloyd@ribose.com>,
        Ronald Tse <ronald.tse@ribose.com>,
diff --git a/apps/genrsa.c b/apps/genrsa.c
index b4a986cb58..f147852902 100644
--- a/apps/genrsa.c
+++ b/apps/genrsa.c
@@ -27,13 +27,14 @@ NON_EMPTY_TRANSLATION_UNIT
 # include <openssl/rand.h>
 
 # define DEFBITS 2048
+# define DEFPRIMES 2
 
 static int genrsa_cb(int p, int n, BN_GENCB *cb);
 
 typedef enum OPTION_choice {
     OPT_ERR = -1, OPT_EOF = 0, OPT_HELP,
     OPT_3, OPT_F4, OPT_ENGINE,
-    OPT_OUT, OPT_PASSOUT, OPT_CIPHER,
+    OPT_OUT, OPT_PASSOUT, OPT_CIPHER, OPT_PRIMES,
     OPT_R_ENUM
 } OPTION_CHOICE;
 
@@ -49,6 +50,7 @@ const OPTIONS genrsa_options[] = {
 # ifndef OPENSSL_NO_ENGINE
     {"engine", OPT_ENGINE, 's', "Use engine, possibly a hardware device"},
 # endif
+    {"primes", OPT_PRIMES, 'p', "Specify number of primes"},
     {NULL}
 };
 
@@ -62,7 +64,7 @@ int genrsa_main(int argc, char **argv)
     const BIGNUM *e;
     RSA *rsa = NULL;
     const EVP_CIPHER *enc = NULL;
-    int ret = 1, num = DEFBITS, private = 0;
+    int ret = 1, num = DEFBITS, private = 0, primes = DEFPRIMES;
     unsigned long f4 = RSA_F4;
     char *outfile = NULL, *passoutarg = NULL, *passout = NULL;
     char *prog, *hexe, *dece;
@@ -108,6 +110,10 @@ opthelp:
             if (!opt_cipher(opt_unknown(), &enc))
                 goto end;
             break;
+        case OPT_PRIMES:
+            if (!opt_int(opt_arg(), &primes))
+                goto end;
+            break;
         }
     }
     argc = opt_num_rest();
@@ -131,13 +137,14 @@ opthelp:
     if (out == NULL)
         goto end;
 
-    BIO_printf(bio_err, "Generating RSA private key, %d bit long modulus\n",
-               num);
+    BIO_printf(bio_err, "Generating RSA private key, %d bit long modulus (%d primes)\n",
+               num, primes);
     rsa = eng ? RSA_new_method(eng) : RSA_new();
     if (rsa == NULL)
         goto end;
 
-    if (!BN_set_word(bn, f4) || !RSA_generate_key_ex(rsa, num, bn, cb))
+    if (!BN_set_word(bn, f4)
+        || !RSA_generate_multi_prime_key(rsa, num, primes, bn, cb))
         goto end;
 
     RSA_get0_key(rsa, NULL, &e, NULL);
diff --git a/apps/speed.c b/apps/speed.c
index 063bc1c2dc..c52dac608a 100644
--- a/apps/speed.c
+++ b/apps/speed.c
@@ -339,7 +339,8 @@ static int found(const char *name, const OPT_PAIR *pairs, int *result)
 typedef enum OPTION_choice {
     OPT_ERR = -1, OPT_EOF = 0, OPT_HELP,
     OPT_ELAPSED, OPT_EVP, OPT_DECRYPT, OPT_ENGINE, OPT_MULTI,
-    OPT_MR, OPT_MB, OPT_MISALIGN, OPT_ASYNCJOBS, OPT_R_ENUM
+    OPT_MR, OPT_MB, OPT_MISALIGN, OPT_ASYNCJOBS, OPT_R_ENUM,
+    OPT_PRIMES
 } OPTION_CHOICE;
 
 const OPTIONS speed_options[] = {
@@ -366,6 +367,7 @@ const OPTIONS speed_options[] = {
 #ifndef OPENSSL_NO_ENGINE
     {"engine", OPT_ENGINE, 's', "Use engine, possibly a hardware device"},
 #endif
+    {"primes", OPT_PRIMES, 'p', "Specify number of primes (for RSA only)"},
     {NULL},
 };
 
@@ -1325,6 +1327,7 @@ int speed_main(int argc, char **argv)
         sizeof(test15360)
     };
     int rsa_doit[RSA_NUM] = { 0 };
+    int primes = RSA_DEFAULT_PRIME_NUM;
 #endif
 #ifndef OPENSSL_NO_DSA
     static const unsigned int dsa_bits[DSA_NUM] = { 512, 1024, 2048 };
@@ -1459,6 +1462,10 @@ int speed_main(int argc, char **argv)
             if (!opt_rand(o))
                 goto end;
             break;
+        case OPT_PRIMES:
+            if (!opt_int(opt_arg(), &primes))
+                goto end;
+            break;
         }
     }
     argc = opt_num_rest();
@@ -1615,6 +1622,10 @@ int speed_main(int argc, char **argv)
 
 #ifndef OPENSSL_NO_RSA
     for (i = 0; i < loopargs_len; i++) {
+        if (primes > RSA_DEFAULT_PRIME_NUM) {
+            /* for multi-prime RSA, skip this */
+            break;
+        }
         for (k = 0; k < RSA_NUM; k++) {
             const unsigned char *p;
 
@@ -2395,6 +2406,34 @@ int speed_main(int argc, char **argv)
         if (!rsa_doit[testnum])
             continue;
         for (i = 0; i < loopargs_len; i++) {
+            if (primes > 2) {
+                /* we haven't set keys yet,  generate multi-prime RSA keys */
+                BIGNUM *bn = BN_new();
+
+                if (bn == NULL)
+                    goto end;
+                if (!BN_set_word(bn, RSA_F4)) {
+                    BN_free(bn);
+                    goto end;
+                }
+
+                BIO_printf(bio_err, "Generate multi-prime RSA key for %s\n",
+                           rsa_choices[testnum].name);
+
+                loopargs[i].rsa_key[testnum] = RSA_new();
+                if (loopargs[i].rsa_key[testnum] == NULL) {
+                    BN_free(bn);
+                    goto end;
+                }
+
+                if (!RSA_generate_multi_prime_key(loopargs[i].rsa_key[testnum],
+                                                  rsa_bits[testnum],
+                                                  primes, bn, NULL)) {
+                    BN_free(bn);
+                    goto end;
+                }
+                BN_free(bn);
+            }
             st = RSA_sign(NID_md5_sha1, loopargs[i].buf, 36, loopargs[i].buf2,
                           &loopargs[i].siglen, loopargs[i].rsa_key[testnum]);
             if (st == 0)
diff --git a/crypto/err/openssl.txt b/crypto/err/openssl.txt
index 8547d07882..e7353aa3e8 100644
--- a/crypto/err/openssl.txt
+++ b/crypto/err/openssl.txt
@@ -2224,6 +2224,7 @@ RSA_R_INVALID_HEADER:137:invalid header
 RSA_R_INVALID_LABEL:160:invalid label
 RSA_R_INVALID_MESSAGE_LENGTH:131:invalid message length
 RSA_R_INVALID_MGF1_MD:156:invalid mgf1 md
+RSA_R_INVALID_MULTI_PRIME_KEY:167:invalid multi prime key
 RSA_R_INVALID_OAEP_PARAMETERS:161:invalid oaep parameters
 RSA_R_INVALID_PADDING:138:invalid padding
 RSA_R_INVALID_PADDING_MODE:141:invalid padding mode
@@ -2233,12 +2234,17 @@ RSA_R_INVALID_SALT_LENGTH:150:invalid salt length
 RSA_R_INVALID_TRAILER:139:invalid trailer
 RSA_R_INVALID_X931_DIGEST:142:invalid x931 digest
 RSA_R_IQMP_NOT_INVERSE_OF_Q:126:iqmp not inverse of q
+RSA_R_KEY_PRIME_NUM_INVALID:165:key prime num invalid
 RSA_R_KEY_SIZE_TOO_SMALL:120:key size too small
 RSA_R_LAST_OCTET_INVALID:134:last octet invalid
 RSA_R_MGF1_DIGEST_NOT_ALLOWED:152:mgf1 digest not allowed
 RSA_R_MODULUS_TOO_LARGE:105:modulus too large
+RSA_R_MP_COEFFICIENT_NOT_INVERSE_OF_R:168:mp coefficient not inverse of r
+RSA_R_MP_EXPONENT_NOT_CONGRUENT_TO_D:169:mp exponent not congruent to d
+RSA_R_MP_R_NOT_PRIME:170:mp r not prime
 RSA_R_NO_PUBLIC_EXPONENT:140:no public exponent
 RSA_R_NULL_BEFORE_BLOCK_MISSING:113:null before block missing
+RSA_R_N_DOES_NOT_EQUAL_PRODUCT_OF_PRIMES:172:n does not equal product of primes
 RSA_R_N_DOES_NOT_EQUAL_P_Q:127:n does not equal p q
 RSA_R_OAEP_DECODING_ERROR:121:oaep decoding error
 RSA_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE:148:\
diff --git a/crypto/rsa/build.info b/crypto/rsa/build.info
index 4575b28879..87f924922f 100644
--- a/crypto/rsa/build.info
+++ b/crypto/rsa/build.info
@@ -3,4 +3,4 @@ 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_pmeth.c rsa_crpt.c rsa_x931g.c rsa_meth.c rsa_mp.c
diff --git a/crypto/rsa/rsa_ameth.c b/crypto/rsa/rsa_ameth.c
index 97a37ba47d..98121b5e64 100644
--- a/crypto/rsa/rsa_ameth.c
+++ b/crypto/rsa/rsa_ameth.c
@@ -316,10 +316,11 @@ static int pkey_rsa_print(BIO *bp, const EVP_PKEY *pkey, int off, int priv)
     const RSA *x = pkey->pkey.rsa;
     char *str;
     const char *s;
-    int ret = 0, mod_len = 0;
+    int ret = 0, mod_len = 0, ex_primes;
 
     if (x->n != NULL)
         mod_len = BN_num_bits(x->n);
+    ex_primes = sk_RSA_PRIME_INFO_num(x->prime_infos);
 
     if (!BIO_indent(bp, off, 128))
         goto err;
@@ -328,7 +329,8 @@ static int pkey_rsa_print(BIO *bp, const EVP_PKEY *pkey, int off, int priv)
         goto err;
 
     if (priv && x->d) {
-        if (BIO_printf(bp, "Private-Key: (%d bit)\n", mod_len) <= 0)
+        if (BIO_printf(bp, "Private-Key: (%d bit, %d primes)\n",
+                       mod_len, ex_primes <= 0 ? 2 : ex_primes + 2) <= 0)
             goto err;
         str = "modulus:";
         s = "publicExponent:";
@@ -343,6 +345,8 @@ static int pkey_rsa_print(BIO *bp, const EVP_PKEY *pkey, int off, int priv)
     if (!ASN1_bn_print(bp, s, x->e, NULL, off))
         goto err;
     if (priv) {
+        int i;
+
         if (!ASN1_bn_print(bp, "privateExponent:", x->d, NULL, off))
             goto err;
         if (!ASN1_bn_print(bp, "prime1:", x->p, NULL, off))
@@ -355,6 +359,39 @@ static int pkey_rsa_print(BIO *bp, const EVP_PKEY *pkey, int off, int priv)
             goto err;
         if (!ASN1_bn_print(bp, "coefficient:", x->iqmp, NULL, off))
             goto err;
+        for (i = 0; i < sk_RSA_PRIME_INFO_num(x->prime_infos); i++) {
+            /* print multi-prime info */
+            BIGNUM *bn = NULL;
+            RSA_PRIME_INFO *pinfo;
+            int j;
+
+            pinfo = sk_RSA_PRIME_INFO_value(x->prime_infos, i);
+            for (j = 0; j < 3; j++) {
+                if (!BIO_indent(bp, off, 128))
+                    goto err;
+                switch (j) {
+                case 0:
+                    if (BIO_printf(bp, "prime%d:", i + 3) <= 0)
+                        goto err;
+                    bn = pinfo->r;
+                    break;
+                case 1:
+                    if (BIO_printf(bp, "exponent%d:", i + 3) <= 0)
+                        goto err;
+                    bn = pinfo->d;
+                    break;
+                case 2:
+                    if (BIO_printf(bp, "coefficient%d:", i + 3) <= 0)
+                        goto err;
+                    bn = pinfo->t;
+                    break;
+                default:
+                    break;
+                }
+                if (!ASN1_bn_print(bp, "", bn, NULL, off))
+                    goto err;
+            }
+        }
     }
     if (pkey_is_pss(pkey) && !rsa_pss_param_print(bp, 1, x->pss, off))
         goto err;
diff --git a/crypto/rsa/rsa_asn1.c b/crypto/rsa/rsa_asn1.c
index 43c8fc27ae..9fe62c82eb 100644
--- a/crypto/rsa/rsa_asn1.c
+++ b/crypto/rsa/rsa_asn1.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 2000-2016 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2000-2017 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
@@ -14,7 +14,11 @@
 #include <openssl/asn1t.h>
 #include "rsa_locl.h"
 
-/* Override the default free and new methods */
+/*
+ * Override the default free and new methods,
+ * and calculate helper products for multi-prime
+ * RSA keys.
+ */
 static int rsa_cb(int operation, ASN1_VALUE **pval, const ASN1_ITEM *it,
                   void *exarg)
 {
@@ -27,10 +31,23 @@ static int rsa_cb(int operation, ASN1_VALUE **pval, const ASN1_ITEM *it,
         RSA_free((RSA *)*pval);
         *pval = NULL;
         return 2;
+    } else if (operation == ASN1_OP_D2I_POST) {
+        if (((RSA *)*pval)->version != RSA_ASN1_VERSION_MULTI) {
+            /* not a multi-prime key, skip */
+            return 1;
+        }
+        return (rsa_multip_calc_product((RSA *)*pval) == 1) ? 2 : 0;
     }
     return 1;
 }
 
+/* Based on definitions in RFC 8017 appendix A.1.2 */
+ASN1_SEQUENCE(RSA_PRIME_INFO) = {
+        ASN1_SIMPLE(RSA_PRIME_INFO, r, CBIGNUM),
+        ASN1_SIMPLE(RSA_PRIME_INFO, d, CBIGNUM),
+        ASN1_SIMPLE(RSA_PRIME_INFO, t, CBIGNUM),
+} ASN1_SEQUENCE_END(RSA_PRIME_INFO)
+
 ASN1_SEQUENCE_cb(RSAPrivateKey, rsa_cb) = {
         ASN1_EMBED(RSA, version, INT32),
         ASN1_SIMPLE(RSA, n, BIGNUM),
@@ -40,7 +57,8 @@ ASN1_SEQUENCE_cb(RSAPrivateKey, rsa_cb) = {
         ASN1_SIMPLE(RSA, q, CBIGNUM),
         ASN1_SIMPLE(RSA, dmp1, CBIGNUM),
         ASN1_SIMPLE(RSA, dmq1, CBIGNUM),
-        ASN1_SIMPLE(RSA, iqmp, CBIGNUM)
+        ASN1_SIMPLE(RSA, iqmp, CBIGNUM),
+        ASN1_SEQUENCE_OF_OPT(RSA, prime_infos, RSA_PRIME_INFO)
 } ASN1_SEQUENCE_END_cb(RSA, RSAPrivateKey)
 
 
diff --git a/crypto/rsa/rsa_chk.c b/crypto/rsa/rsa_chk.c
index 00260fb18e..4cf682258b 100644
--- a/crypto/rsa/rsa_chk.c
+++ b/crypto/rsa/rsa_chk.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 1999-2016 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1999-2017 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
@@ -20,7 +20,8 @@ int RSA_check_key_ex(const RSA *key, BN_GENCB *cb)
 {
     BIGNUM *i, *j, *k, *l, *m;
     BN_CTX *ctx;
-    int ret = 1;
+    int ret = 1, ex_primes = 0, idx;
+    RSA_PRIME_INFO *pinfo;
 
     if (key->p == NULL || key->q == NULL || key->n == NULL
             || key->e == NULL || key->d == NULL) {
@@ -28,6 +29,13 @@ int RSA_check_key_ex(const RSA *key, BN_GENCB *cb)
         return 0;
     }
 
+    /* multi-prime? */
+    if (key->version == RSA_ASN1_VERSION_MULTI
+        && (ex_primes = sk_RSA_PRIME_INFO_num(key->prime_infos)) <= 0) {
+        RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_INVALID_MULTI_PRIME_KEY);
+        return 0;
+    }
+
     i = BN_new();
     j = BN_new();
     k = BN_new();
@@ -62,17 +70,37 @@ int RSA_check_key_ex(const RSA *key, BN_GENCB *cb)
         RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_Q_NOT_PRIME);
     }
 
-    /* n = p*q? */
+    /* r_i prime? */
+    for (idx = 0; idx < ex_primes; idx++) {
+        pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx);
+        if (BN_is_prime_ex(pinfo->r, BN_prime_checks, NULL, cb) != 1) {
+            ret = 0;
+            RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_MP_R_NOT_PRIME);
+        }
+    }
+
+    /* n = p*q * r_3...r_i? */
     if (!BN_mul(i, key->p, key->q, ctx)) {
         ret = -1;
         goto err;
     }
+    for (idx = 0; idx < ex_primes; idx++) {
+        pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx);
+        if (!BN_mul(i, i, pinfo->r, ctx)) {
+            ret = -1;
+            goto err;
+        }
+    }
     if (BN_cmp(i, key->n) != 0) {
         ret = 0;
-        RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_N_DOES_NOT_EQUAL_P_Q);
+        if (ex_primes)
+            RSAerr(RSA_F_RSA_CHECK_KEY_EX,
+                   RSA_R_N_DOES_NOT_EQUAL_PRODUCT_OF_PRIMES);
+        else
+            RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_N_DOES_NOT_EQUAL_P_Q);
     }
 
-    /* d*e = 1  mod lcm(p-1,q-1)? */
+    /* d*e = 1  mod \lambda(n)? */
     if (!BN_sub(i, key->p, BN_value_one())) {
         ret = -1;
         goto err;
@@ -82,7 +110,7 @@ int RSA_check_key_ex(const RSA *key, BN_GENCB *cb)
         goto err;
     }
 
-    /* now compute k = lcm(i,j) */
+    /* now compute k = \lambda(n) = LCM(i, j, r_3 - 1...) */
     if (!BN_mul(l, i, j, ctx)) {
         ret = -1;
         goto err;
@@ -91,6 +119,21 @@ int RSA_check_key_ex(const RSA *key, BN_GENCB *cb)
         ret = -1;
         goto err;
     }
+    for (idx = 0; idx < ex_primes; idx++) {
+        pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx);
+        if (!BN_sub(k, pinfo->r, BN_value_one())) {
+            ret = -1;
+            goto err;
+        }
+        if (!BN_mul(l, l, k, ctx)) {
+            ret = -1;
+            goto err;
+        }
+        if (!BN_gcd(m, m, k, ctx)) {
+            ret = -1;
+            goto err;
+        }
+    }
     if (!BN_div(k, NULL, l, m, ctx)) { /* remainder is 0 */
         ret = -1;
         goto err;
@@ -145,6 +188,32 @@ int RSA_check_key_ex(const RSA *key, BN_GENCB *cb)
         }
     }
 
+    for (idx = 0; idx < ex_primes; idx++) {
+        pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx);
+        /* d_i = d mod (r_i - 1)? */
+        if (!BN_sub(i, pinfo->r, BN_value_one())) {
+            ret = -1;
+            goto err;
+        }
+        if (!BN_mod(j, key->d, i, ctx)) {
+            ret = -1;
+            goto err;
+        }
+        if (BN_cmp(j, pinfo->d) != 0) {
+            ret = 0;
+            RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_MP_EXPONENT_NOT_CONGRUENT_TO_D);
+        }
+        /* t_i = R_i ^ -1 mod r_i ? */
+        if (!BN_mod_inverse(i, pinfo->pp, pinfo->r, ctx)) {
+            ret = -1;
+            goto err;
+        }
+        if (BN_cmp(i, pinfo->t) != 0) {
+            ret = 0;
+            RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_MP_COEFFICIENT_NOT_INVERSE_OF_R);
+        }
+    }
+
  err:
     BN_free(i);
     BN_free(j);
diff --git a/crypto/rsa/rsa_err.c b/crypto/rsa/rsa_err.c
index 74b0feeae4..f7d29e1999 100644
--- a/crypto/rsa/rsa_err.c
+++ b/crypto/rsa/rsa_err.c
@@ -147,6 +147,8 @@ static const ERR_STRING_DATA RSA_str_reasons[] = {
     {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_INVALID_MESSAGE_LENGTH),
     "invalid message length"},
     {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_INVALID_MGF1_MD), "invalid mgf1 md"},
+    {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_INVALID_MULTI_PRIME_KEY),
+    "invalid multi prime key"},
     {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_INVALID_OAEP_PARAMETERS),
     "invalid oaep parameters"},
     {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_INVALID_PADDING), "invalid padding"},
@@ -163,14 +165,23 @@ static const ERR_STRING_DATA RSA_str_reasons[] = {
     "invalid x931 digest"},
     {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_IQMP_NOT_INVERSE_OF_Q),
     "iqmp not inverse of q"},
+    {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_KEY_PRIME_NUM_INVALID),
+    "key prime num invalid"},
     {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_KEY_SIZE_TOO_SMALL), "key size too small"},
     {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_LAST_OCTET_INVALID), "last octet invalid"},
     {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_MGF1_DIGEST_NOT_ALLOWED),
     "mgf1 digest not allowed"},
     {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_MODULUS_TOO_LARGE), "modulus too large"},
+    {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_MP_COEFFICIENT_NOT_INVERSE_OF_R),
+    "mp coefficient not inverse of r"},
+    {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_MP_EXPONENT_NOT_CONGRUENT_TO_D),
+    "mp exponent not congruent to d"},
+    {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_MP_R_NOT_PRIME), "mp r not prime"},
     {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_NO_PUBLIC_EXPONENT), "no public exponent"},
     {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_NULL_BEFORE_BLOCK_MISSING),
     "null before block missing"},
+    {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_N_DOES_NOT_EQUAL_PRODUCT_OF_PRIMES),
+    "n does not equal product of primes"},
     {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_N_DOES_NOT_EQUAL_P_Q),
     "n does not equal p q"},
     {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_OAEP_DECODING_ERROR),
diff --git a/crypto/rsa/rsa_gen.c b/crypto/rsa/rsa_gen.c
index 4ced965519..f7f60754ad 100644
--- a/crypto/rsa/rsa_gen.c
+++ b/crypto/rsa/rsa_gen.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2017 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
@@ -19,7 +19,7 @@
 #include <openssl/bn.h>
 #include "rsa_locl.h"
 
-static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value,
+static int rsa_builtin_keygen(RSA *rsa, int bits, int primes, BIGNUM *e_value,
                               BN_GENCB *cb);
 
 /*
@@ -31,17 +31,43 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value,
  */
 int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
 {
-    if (rsa->meth->rsa_keygen)
+    if (rsa->meth->rsa_keygen != NULL)
         return rsa->meth->rsa_keygen(rsa, bits, e_value, cb);
-    return rsa_builtin_keygen(rsa, bits, e_value, cb);
+
+    return RSA_generate_multi_prime_key(rsa, bits, RSA_DEFAULT_PRIME_NUM,
+                                        e_value, cb);
 }
 
-static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value,
+int RSA_generate_multi_prime_key(RSA *rsa, int bits, int primes,
+                                 BIGNUM *e_value, BN_GENCB *cb)
+{
+    /* 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,
+                                                 e_value, cb);
+    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)
 {
-    BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *r3 = NULL, *tmp;
-    int bitsp, bitsq, ok = -1, n = 0;
+    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;
+    RSA_PRIME_INFO *pinfo = NULL;
+    STACK_OF(RSA_PRIME_INFO) *prime_infos = NULL;
     BN_CTX *ctx = NULL;
+    BN_ULONG bitst = 0;
+
+    /*
+     * From Github pull request #4241:
+     *
+     * We are in disagreement on how to handle security trade-off, in other
+     * words:
+     *
+     * mechanical-check-for-maximum-of-16-prime-factors vs.
+     * limiting-number-depending-on-length-less-factors-for-shorter-keys.
+     */
 
     /*
      * When generating ridiculously small keys, we can get stuck
@@ -53,6 +79,12 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value,
         goto err;
     }
 
+    if (primes < RSA_DEFAULT_PRIME_NUM
+        || primes > RSA_MAX_PRIME_NUM || bits <= primes) {
+        RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, RSA_R_KEY_PRIME_NUM_INVALID);
+        goto err;
+    }
+
     ctx = BN_CTX_new();
     if (ctx == NULL)
         goto err;
@@ -60,12 +92,29 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value,
     r0 = BN_CTX_get(ctx);
     r1 = BN_CTX_get(ctx);
     r2 = BN_CTX_get(ctx);
-    r3 = BN_CTX_get(ctx);
-    if (r3 == NULL)
+    if (r2 == NULL)
+        goto err;
+
+    /* divide bits into 'primes' pieces evenly */
+    quo = bits / primes;
+    rmd = bits % primes;
+
+    if (primes > RSA_DEFAULT_PRIME_NUM && quo < RSA_MIN_PRIME_SIZE) {
+        /*
+         * this means primes are too many for the key bits.
+         *
+         * This only affects multi-prime keys. For normal RSA,
+         * it's limited above (bits >= 16, hence each prime >= 8).
+         *
+         * This is done in this way because the original normal
+         * RSA's behavior should not alter at least in OpenSSL 1.1.1.
+         */
+        RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, RSA_R_KEY_PRIME_NUM_INVALID);
         goto err;
+    }
 
-    bitsp = (bits + 1) / 2;
-    bitsq = bits - bitsp;
+    for (i = 0; i < primes; i++)
+        bitsr[i] = (i < rmd) ? quo + 1 : quo;
 
     /* We need the RSA components non-NULL */
     if (!rsa->n && ((rsa->n = BN_new()) == NULL))
@@ -85,62 +134,191 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value,
     if (!rsa->iqmp && ((rsa->iqmp = BN_secure_new()) == NULL))
         goto err;
 
+    /* initialize multi-prime components */
+    if (primes > RSA_DEFAULT_PRIME_NUM) {
+        rsa->version = RSA_ASN1_VERSION_MULTI;
+        prime_infos = sk_RSA_PRIME_INFO_new_reserve(NULL, primes - 2);
+        if (prime_infos == NULL)
+            goto err;
+        if (rsa->prime_infos != NULL) {
+            /* could this happen? */
+            sk_RSA_PRIME_INFO_pop_free(rsa->prime_infos, rsa_multip_info_free);
+        }
+        rsa->prime_infos = prime_infos;
+
+        /* prime_info from 2 to |primes| -1 */
+        for (i = 2; i < primes; i++) {
+            pinfo = rsa_multip_info_new();
+            if (pinfo == NULL)
+                goto err;
+            (void)sk_RSA_PRIME_INFO_push(prime_infos, pinfo);
+        }
+    }
+
     if (BN_copy(rsa->e, e_value) == NULL)
         goto err;
 
-    /* generate p and q */
-    for (;;) {
-        if (!BN_generate_prime_ex(rsa->p, bitsp, 0, NULL, NULL, cb))
-            goto err;
-        if (!BN_sub(r2, rsa->p, BN_value_one()))
-            goto err;
-        if (!BN_gcd(r1, r2, rsa->e, ctx))
-            goto err;
-        if (BN_is_one(r1))
-            break;
-        if (!BN_GENCB_call(cb, 2, n++))
+    /* generate p, q and other primes (if any) */
+    for (i = 0; i < primes; i++) {
+        adj = 0;
+        retries = 0;
+
+        if (i == 0) {
+            prime = rsa->p;
+        } else if (i == 1) {
+            prime = rsa->q;
+        } else {
+            pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2);
+            prime = pinfo->r;
+        }
+
+        for (;;) {
+ redo:
+            if (!BN_generate_prime_ex(prime, bitsr[i] + adj, 0, NULL, NULL, cb))
+                goto err;
+            /*
+             * prime should not be equal to p, q, r_3...
+             * (those primes prior to this one)
+             */
+            {
+                int j;
+
+                for (j = 0; j < i; j++) {
+                    BIGNUM *prev_prime;
+
+                    if (j == 0)
+                        prev_prime = rsa->p;
+                    else if (j == 1)
+                        prev_prime = rsa->q;
+                    else
+                        prev_prime = sk_RSA_PRIME_INFO_value(prime_infos,
+                                                             j - 2)->r;
+
+                    if (!BN_cmp(prime, prev_prime)) {
+                        goto redo;
+                    }
+                }
+            }
+            if (!BN_sub(r2, prime, BN_value_one()))
+                goto err;
+            if (!BN_gcd(r1, r2, rsa->e, ctx))
+                goto err;
+            if (BN_is_one(r1))
+                break;
+            if (!BN_GENCB_call(cb, 2, n++))
+                goto err;
+        }
+
+        bitse += bitsr[i];
+
+        /* calculate n immediately to see if it's sufficient */
+        if (i == 1) {
+            /* we get at least 2 primes */
+            if (!BN_mul(r1, rsa->p, rsa->q, ctx))
+                goto err;
+        } else if (i != 0) {
+            /* modulus n = p * q * r_3 * r_4 ... */
+            if (!BN_mul(r1, rsa->n, prime, ctx))
+                goto err;
+        } else {
+            /* i == 0, do nothing */
+            if (!BN_GENCB_call(cb, 3, i))
+                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
+         * 0xF). If so, re-generate the last prime.
+         *
+         * NOTE: This actually can't happen in two-prime case, because of
+         * the way factors are generated.
+         *
+         * Besides, another consideration is, for multi-prime case, even the
+         * length modulus is as long as expected, the modulus could start at
+         * 0x8, which could be utilized to distinguish a multi-prime private
+         * key by using the modulus in a certificate. This is also covered
+         * by checking the length should not be less than 0x9.
+         */
+        if (!BN_rshift(r2, r1, bitse - 4))
             goto err;
-    }
-    if (!BN_GENCB_call(cb, 3, 0))
-        goto err;
-    for (;;) {
-        do {
-            if (!BN_generate_prime_ex(rsa->q, bitsq, 0, NULL, NULL, cb))
+        bitst = BN_get_word(r2);
+
+        if (bitst < 0x9 || bitst > 0xF) {
+            /*
+             * For keys with more than 4 primes, we attempt longer factor to
+             * meet length requirement.
+             *
+             * Otherwise, we just re-generate the prime with the same length.
+             *
+             * This strategy has the following goals:
+             *
+             * 1. 1024-bit factors are effcient when using 3072 and 4096-bit key
+             * 2. stay the same logic with normal 2-prime key
+             */
+            bitse -= bitsr[i];
+            if (!BN_GENCB_call(cb, 2, n++))
                 goto err;
-        } while (BN_cmp(rsa->p, rsa->q) == 0);
-        if (!BN_sub(r2, rsa->q, BN_value_one()))
+            if (primes > 4) {
+                if (bitst < 0x9)
+                    adj++;
+                else
+                    adj--;
+            } else if (retries == 4) {
+                /*
+                 * re-generate all primes from scratch, mainly used
+                 * in 4 prime case to avoid long loop. Max retry times
+                 * is set to 4.
+                 */
+                i = -1;
+                bitse = 0;
+                continue;
+            }
+            retries++;
+            goto redo;
+        }
+        /* save product of primes for further use, for multi-prime only */
+        if (i > 1 && BN_copy(pinfo->pp, rsa->n) == NULL)
             goto err;
-        if (!BN_gcd(r1, r2, rsa->e, ctx))
+        if (BN_copy(rsa->n, r1) == NULL)
             goto err;
-        if (BN_is_one(r1))
-            break;
-        if (!BN_GENCB_call(cb, 2, n++))
+        if (!BN_GENCB_call(cb, 3, i))
             goto err;
     }
-    if (!BN_GENCB_call(cb, 3, 1))
-        goto err;
+
     if (BN_cmp(rsa->p, rsa->q) < 0) {
         tmp = rsa->p;
         rsa->p = rsa->q;
         rsa->q = tmp;
     }
 
-    /* calculate n */
-    if (!BN_mul(rsa->n, rsa->p, rsa->q, ctx))
-        goto err;
-
     /* calculate d */
+
+    /* p - 1 */
     if (!BN_sub(r1, rsa->p, BN_value_one()))
-        goto err;               /* p-1 */
+        goto err;
+    /* q - 1 */
     if (!BN_sub(r2, rsa->q, BN_value_one()))
-        goto err;               /* q-1 */
+        goto err;
+    /* (p - 1)(q - 1) */
     if (!BN_mul(r0, r1, r2, ctx))
-        goto err;               /* (p-1)(q-1) */
+        goto err;
+    /* multi-prime */
+    for (i = 2; i < primes; i++) {
+        pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2);
+        /* save r_i - 1 to pinfo->d temporarily */
+        if (!BN_sub(pinfo->d, pinfo->r, BN_value_one()))
+            goto err;
+        if (!BN_mul(r0, r0, pinfo->d, ctx))
+            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);
@@ -155,15 +333,26 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value,
 
         if (d == NULL)
             goto err;
+
         BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 
-        if (   /* calculate d mod (p-1) */
-               !BN_mod(rsa->dmp1, d, r1, ctx)
-               /* calculate d mod (q-1) */
+        /* 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);
     }
@@ -180,6 +369,17 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value,
             BN_free(p);
             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);
     }
@@ -193,6 +393,5 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value,
     if (ctx != NULL)
         BN_CTX_end(ctx);
     BN_CTX_free(ctx);
-
     return ok;
 }
diff --git a/crypto/rsa/rsa_lib.c b/crypto/rsa/rsa_lib.c
index e43d8238b5..198dbd3fc7 100644
--- a/crypto/rsa/rsa_lib.c
+++ b/crypto/rsa/rsa_lib.c
@@ -134,6 +134,7 @@ void RSA_free(RSA *r)
     BN_clear_free(r->dmq1);
     BN_clear_free(r->iqmp);
     RSA_PSS_PARAMS_free(r->pss);
+    sk_RSA_PRIME_INFO_pop_free(r->prime_infos, rsa_multip_info_free);
     BN_BLINDING_free(r->blinding);
     BN_BLINDING_free(r->mt_blinding);
     OPENSSL_free(r->bignum_data);
@@ -240,6 +241,71 @@ int RSA_set0_crt_params(RSA *r, BIGNUM *dmp1, BIGNUM *dmq1, BIGNUM *iqmp)
     return 1;
 }
 
+/*
+ * Is it better to export RSA_PRIME_INFO structure
+ * and related functions to let user pass a triplet?
+ */
+int RSA_set0_multi_prime_params(RSA *r, BIGNUM *primes[], BIGNUM *exps[],
+                                BIGNUM *coeffs[], int pnum)
+{
+    STACK_OF(RSA_PRIME_INFO) *prime_infos, *old = NULL;
+    RSA_PRIME_INFO *pinfo;
+    int i;
+
+    if (primes == NULL || exps == NULL || coeffs == NULL || pnum == 0)
+        return 0;
+
+    prime_infos = sk_RSA_PRIME_INFO_new_reserve(NULL, pnum);
+    if (prime_infos == NULL)
+        return 0;
+
+    if (r->prime_infos != NULL)
+        old = r->prime_infos;
+
+    for (i = 0; i < pnum; i++) {
+        pinfo = rsa_multip_info_new();
+        if (pinfo == NULL)
+            goto err;
+        if (primes[i] != NULL && exps[i] != NULL && coeffs[i] != NULL) {
+            BN_free(pinfo->r);
+            BN_free(pinfo->d);
+            BN_free(pinfo->t);
+            pinfo->r = primes[i];
+            pinfo->d = exps[i];
+            pinfo->t = coeffs[i];
+        } else {
+            rsa_multip_info_free(pinfo);
+            goto err;
+        }
+        (void)sk_RSA_PRIME_INFO_push(prime_infos, pinfo);
+    }
+
+    r->prime_infos = prime_infos;
+
+    if (!rsa_multip_calc_product(r)) {
+        r->prime_infos = old;
+        goto err;
+    }
+
+    if (old != NULL) {
+        /*
+         * This is hard to deal with, since the old infos could
+         * also be set by this function and r, d, t should not
+         * be freed in that case. So currently, stay consistent
+         * with other *set0* functions: just free it...
+         */
+        sk_RSA_PRIME_INFO_pop_free(old, rsa_multip_info_free);
+    }
+
+    r->version = RSA_ASN1_VERSION_MULTI;
+
+    return 1;
+ err:
+    /* r, d, t should not be freed */
+    sk_RSA_PRIME_INFO_pop_free(prime_infos, rsa_multip_info_free_ex);
+    return 0;
+}
+
 void RSA_get0_key(const RSA *r,
                   const BIGNUM **n, const BIGNUM **e, const BIGNUM **d)
 {
@@ -259,6 +325,36 @@ void RSA_get0_factors(const RSA *r, const BIGNUM **p, const BIGNUM **q)
         *q = r->q;
 }
 
+int RSA_get_multi_prime_extra_count(const RSA *r)
+{
+    int pnum;
+
+    pnum = sk_RSA_PRIME_INFO_num(r->prime_infos);
+    if (pnum <= 0)
+        pnum = 0;
+    return pnum;
+}
+
+int RSA_get0_multi_prime_factors(const RSA *r, const BIGNUM *primes[])
+{
+    int pnum, i;
+    RSA_PRIME_INFO *pinfo;
+
+    if ((pnum = RSA_get_multi_prime_extra_count(r)) == 0)
+        return 0;
+
+    /*
+     * return other primes
+     * it's caller's responsibility to allocate oth_primes[pnum]
+     */
+    for (i = 0; i < pnum; i++) {
+        pinfo = sk_RSA_PRIME_INFO_value(r->prime_infos, i);
+        primes[i] = pinfo->r;
+    }
+
+    return 1;
+}
+
 void RSA_get0_crt_params(const RSA *r,
                          const BIGNUM **dmp1, const BIGNUM **dmq1,
                          const BIGNUM **iqmp)
@@ -271,6 +367,32 @@ void RSA_get0_crt_params(const RSA *r,
         *iqmp = r->iqmp;
 }
 
+int RSA_get0_multi_prime_crt_params(const RSA *r, const BIGNUM *exps[],
+                                    const BIGNUM *coeffs[])
+{
+    int pnum;
+
+    if ((pnum = RSA_get_multi_prime_extra_count(r)) == 0)
+        return 0;
+
+    /* return other primes */
+    if (exps != NULL || coeffs != NULL) {
+        RSA_PRIME_INFO *pinfo;
+        int i;
+
+        /* it's the user's job to guarantee the buffer length */
+        for (i = 0; i < pnum; i++) {
+            pinfo = sk_RSA_PRIME_INFO_value(r->prime_infos, i);
+            if (exps != NULL)
+                exps[i] = pinfo->d;
+            if (coeffs != NULL)
+                coeffs[i] = pinfo->t;
+        }
+    }
+
+    return 1;
+}
+
 void RSA_clear_flags(RSA *r, int flags)
 {
     r->flags &= ~flags;
@@ -286,6 +408,12 @@ void RSA_set_flags(RSA *r, int flags)
     r->flags |= flags;
 }
 
+int RSA_get_version(RSA *r)
+{
+    /* { two-prime(0), multi(1) } */
+    return r->version;
+}
+
 ENGINE *RSA_get0_engine(const RSA *r)
 {
     return r->engine;
diff --git a/crypto/rsa/rsa_locl.h b/crypto/rsa/rsa_locl.h
index be3ef0cf64..6a53d89ede 100644
--- a/crypto/rsa/rsa_locl.h
+++ b/crypto/rsa/rsa_locl.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2006-2016 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2006-2017 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
@@ -10,6 +10,21 @@
 #include <openssl/rsa.h>
 #include "internal/refcount.h"
 
+#define RSA_MAX_PRIME_NUM 16
+#define RSA_MIN_PRIME_SIZE 64
+
+typedef struct rsa_prime_info_st {
+    BIGNUM *r;
+    BIGNUM *d;
+    BIGNUM *t;
+    /* save product of primes prior to this one */
+    BIGNUM *pp;
+    BN_MONT_CTX *m;
+} RSA_PRIME_INFO;
+
+DECLARE_ASN1_ITEM(RSA_PRIME_INFO)
+DEFINE_STACK_OF(RSA_PRIME_INFO)
+
 struct rsa_st {
     /*
      * The first parameter is used to pickup errors where this is passed
@@ -28,6 +43,8 @@ struct rsa_st {
     BIGNUM *dmp1;
     BIGNUM *dmq1;
     BIGNUM *iqmp;
+    /* for multi-prime RSA, defined in RFC 8017 */
+    STACK_OF(RSA_PRIME_INFO) *prime_infos;
     /* If a PSS only key this contains the parameter restrictions */
     RSA_PSS_PARAMS *pss;
     /* be careful using this if the RSA structure is shared */
@@ -91,6 +108,8 @@ struct rsa_meth_st {
      * things as "builtin software" implementations.
      */
     int (*rsa_keygen) (RSA *rsa, int bits, BIGNUM *e, BN_GENCB *cb);
+    int (*rsa_multi_prime_keygen) (RSA *rsa, int bits, int primes,
+                                   BIGNUM *e, BN_GENCB *cb);
 };
 
 extern int int_rsa_verify(int dtype, const unsigned char *m,
@@ -105,3 +124,8 @@ RSA_PSS_PARAMS *rsa_pss_params_create(const EVP_MD *sigmd,
                                       const EVP_MD *mgf1md, int saltlen);
 int rsa_pss_get_param(const RSA_PSS_PARAMS *pss, const EVP_MD **pmd,
                       const EVP_MD **pmgf1md, int *psaltlen);
+/* internal function to clear and free multi-prime parameters */
+void rsa_multip_info_free_ex(RSA_PRIME_INFO *pinfo);
+void rsa_multip_info_free(RSA_PRIME_INFO *pinfo);
+RSA_PRIME_INFO *rsa_multip_info_new(void);
+int rsa_multip_calc_product(RSA *rsa);
diff --git a/crypto/rsa/rsa_meth.c b/crypto/rsa/rsa_meth.c
index 9480abd700..5dccc330dc 100644
--- a/crypto/rsa/rsa_meth.c
+++ b/crypto/rsa/rsa_meth.c
@@ -271,3 +271,17 @@ int RSA_meth_set_keygen(RSA_METHOD *meth,
     return 1;
 }
 
+int (*RSA_meth_get_multi_prime_keygen(const RSA_METHOD *meth))
+    (RSA *rsa, int bits, int primes, BIGNUM *e, BN_GENCB *cb)
+{
+    return meth->rsa_multi_prime_keygen;
+}
+
+int RSA_meth_set_multi_prime_keygen(RSA_METHOD *meth,
+                                    int (*keygen) (RSA *rsa, int bits,
+                                                   int primes, BIGNUM *e,
+                                                   BN_GENCB *cb))
+{
+    meth->rsa_multi_prime_keygen = keygen;
+    return 1;
+}
diff --git a/crypto/rsa/rsa_mp.c b/crypto/rsa/rsa_mp.c
new file mode 100644
index 0000000000..d970564840
--- /dev/null
+++ b/crypto/rsa/rsa_mp.c
@@ -0,0 +1,95 @@
+/*
+ * Copyright 2017 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2017 BaishanCloud. 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/bn.h>
+#include "rsa_locl.h"
+
+void rsa_multip_info_free_ex(RSA_PRIME_INFO *pinfo)
+{
+    /* free pp and pinfo only */
+    BN_clear_free(pinfo->pp);
+    OPENSSL_free(pinfo);
+}
+
+void rsa_multip_info_free(RSA_PRIME_INFO *pinfo)
+{
+    /* free a RSA_PRIME_INFO structure */
+    BN_clear_free(pinfo->r);
+    BN_clear_free(pinfo->d);
+    BN_clear_free(pinfo->t);
+    rsa_multip_info_free_ex(pinfo);
+}
+
+RSA_PRIME_INFO *rsa_multip_info_new(void)
+{
+    RSA_PRIME_INFO *pinfo;
+
+    /* create a RSA_PRIME_INFO structure */
+    pinfo = OPENSSL_zalloc(sizeof(RSA_PRIME_INFO));
+    if (pinfo == NULL)
+        return NULL;
+    if ((pinfo->r = BN_secure_new()) == NULL)
+        goto err;
+    if ((pinfo->d = BN_secure_new()) == NULL)
+        goto err;
+    if ((pinfo->t = BN_secure_new()) == NULL)
+        goto err;
+    if ((pinfo->pp = BN_secure_new()) == NULL)
+        goto err;
+
+    return pinfo;
+
+ err:
+    BN_free(pinfo->r);
+    BN_free(pinfo->d);
+    BN_free(pinfo->t);
+    BN_free(pinfo->pp);
+    return NULL;
+}
+
+/* Refill products of primes */
+int rsa_multip_calc_product(RSA *rsa)
+{
+    RSA_PRIME_INFO *pinfo;
+    BIGNUM *p1 = NULL, *p2 = NULL;
+    BN_CTX *ctx = NULL;
+    int i, rv = 0, ex_primes;
+
+    if ((ex_primes = sk_RSA_PRIME_INFO_num(rsa->prime_infos)) <= 0) {
+        /* invalid */
+        goto err;
+    }
+
+    if ((ctx = BN_CTX_new()) == NULL)
+        goto err;
+
+    /* calculate pinfo->pp = p * q for first 'extra' prime */
+    p1 = rsa->p;
+    p2 = rsa->q;
+
+    for (i = 0; i < ex_primes; i++) {
+        pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
+        if (pinfo->pp == NULL) {
+            pinfo->pp = BN_secure_new();
+            if (pinfo->pp == NULL)
+                goto err;
+        }
+        if (!BN_mul(pinfo->pp, p1, p2, ctx))
+            goto err;
+        /* save previous one */
+        p1 = pinfo->pp;
+        p2 = pinfo->r;
+    }
+
+    rv = 1;
+ err:
+    BN_CTX_free(ctx);
+    return rv;
+}
diff --git a/crypto/rsa/rsa_ossl.c b/crypto/rsa/rsa_ossl.c
index 40c84dd3c2..ced11ad883 100644
--- a/crypto/rsa/rsa_ossl.c
+++ b/crypto/rsa/rsa_ossl.c
@@ -38,7 +38,8 @@ static RSA_METHOD rsa_pkcs1_ossl_meth = {
     NULL,
     0,                          /* rsa_sign */
     0,                          /* rsa_verify */
-    NULL                        /* rsa_keygen */
+    NULL,                       /* rsa_keygen */
+    NULL                        /* rsa_multi_prime_keygen */
 };
 
 static const RSA_METHOD *default_RSA_meth = &rsa_pkcs1_ossl_meth;
@@ -308,6 +309,7 @@ static int rsa_ossl_private_encrypt(int flen, const unsigned char *from,
     }
 
     if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
+        (rsa->version == RSA_ASN1_VERSION_MULTI) ||
         ((rsa->p != NULL) &&
          (rsa->q != NULL) &&
          (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
@@ -437,6 +439,7 @@ static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
 
     /* do the decrypt */
     if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
+        (rsa->version == RSA_ASN1_VERSION_MULTI) ||
         ((rsa->p != NULL) &&
          (rsa->q != NULL) &&
          (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
@@ -601,17 +604,23 @@ static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
 
 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
 {
-    BIGNUM *r1, *m1, *vrfy;
-    int ret = 0;
+    BIGNUM *r1, *m1, *vrfy, *r2, *m[RSA_MAX_PRIME_NUM];
+    int ret = 0, i, ex_primes = 0;
+    RSA_PRIME_INFO *pinfo;
 
     BN_CTX_start(ctx);
 
     r1 = BN_CTX_get(ctx);
+    r2 = BN_CTX_get(ctx);
     m1 = BN_CTX_get(ctx);
     vrfy = BN_CTX_get(ctx);
     if (vrfy == NULL)
         goto err;
 
+    if (rsa->version == RSA_ASN1_VERSION_MULTI
+        && (ex_primes = sk_RSA_PRIME_INFO_num(rsa->prime_infos)) <= 0)
+        goto err;
+
     {
         BIGNUM *p = BN_new(), *q = BN_new();
 
@@ -636,6 +645,28 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
                 BN_free(q);
                 goto err;
             }
+            if (ex_primes > 0) {
+                /* cache BN_MONT_CTX for other primes */
+                BIGNUM *r = BN_new();
+
+                if (r == NULL) {
+                    BN_free(p);
+                    BN_free(q);
+                    goto err;
+                }
+
+                for (i = 0; i < ex_primes; i++) {
+                    pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
+                    BN_with_flags(r, pinfo->r, BN_FLG_CONSTTIME);
+                    if (!BN_MONT_CTX_set_locked(&pinfo->m, rsa->lock, r, ctx)) {
+                        BN_free(p);
+                        BN_free(q);
+                        BN_free(r);
+                        goto err;
+                    }
+                }
+                BN_free(r);
+            }
         }
         /*
          * We MUST free p and q before any further use of rsa->p and rsa->q
@@ -705,6 +736,56 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
         BN_free(dmp1);
     }
 
+    /*
+     * calculate m_i in multi-prime case
+     *
+     * TODO:
+     * 1. squash the following two loops and calculate |m_i| there.
+     * 2. remove cc and reuse |c|.
+     * 3. remove |dmq1| and |dmp1| in previous block and use |di|.
+     *
+     * If these things are done, the code will be more readable.
+     */
+    if (ex_primes > 0) {
+        BIGNUM *di = BN_new(), *cc = BN_new();
+
+        if (cc == NULL || di == NULL) {
+            BN_free(cc);
+            BN_free(di);
+            goto err;
+        }
+
+        for (i = 0; i < ex_primes; i++) {
+            /* prepare m_i */
+            if ((m[i] = BN_CTX_get(ctx)) == NULL) {
+                BN_free(cc);
+                BN_free(di);
+                goto err;
+            }
+
+            pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
+
+            /* prepare c and d_i */
+            BN_with_flags(cc, I, BN_FLG_CONSTTIME);
+            BN_with_flags(di, pinfo->d, BN_FLG_CONSTTIME);
+
+            if (!BN_mod(r1, cc, pinfo->r, ctx)) {
+                BN_free(cc);
+                BN_free(di);
+                goto err;
+            }
+            /* compute r1 ^ d_i mod r_i */
+            if (!rsa->meth->bn_mod_exp(m[i], r1, di, pinfo->r, ctx, pinfo->m)) {
+                BN_free(cc);
+                BN_free(di);
+                goto err;
+            }
+        }
+
+        BN_free(cc);
+        BN_free(di);
+    }
+
     if (!BN_sub(r0, r0, m1))
         goto err;
     /*
@@ -747,6 +828,49 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
     if (!BN_add(r0, r1, m1))
         goto err;
 
+    /* add m_i to m in multi-prime case */
+    if (ex_primes > 0) {
+        BIGNUM *pr2 = BN_new();
+
+        if (pr2 == NULL)
+            goto err;
+
+        for (i = 0; i < ex_primes; i++) {
+            pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
+            if (!BN_sub(r1, m[i], r0)) {
+                BN_free(pr2);
+                goto err;
+            }
+
+            if (!BN_mul(r2, r1, pinfo->t, ctx)) {
+                BN_free(pr2);
+                goto err;
+            }
+
+            BN_with_flags(pr2, r2, BN_FLG_CONSTTIME);
+
+            if (!BN_mod(r1, pr2, pinfo->r, ctx)) {
+                BN_free(pr2);
+                goto err;
+            }
+
+            if (BN_is_negative(r1))
+                if (!BN_add(r1, r1, pinfo->r)) {
+                    BN_free(pr2);
+                    goto err;
+                }
+            if (!BN_mul(r1, r1, pinfo->pp, ctx)) {
+                BN_free(pr2);
+                goto err;
+            }
+            if (!BN_add(r0, r0, r1)) {
+                BN_free(pr2);
+                goto err;
+            }
+        }
+        BN_free(pr2);
+    }
+
     if (rsa->e && rsa->n) {
         if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx,
                                    rsa->_method_mod_n))
@@ -799,8 +923,15 @@ static int rsa_ossl_init(RSA *rsa)
 
 static int rsa_ossl_finish(RSA *rsa)
 {
+    int i;
+    RSA_PRIME_INFO *pinfo;
+
     BN_MONT_CTX_free(rsa->_method_mod_n);
     BN_MONT_CTX_free(rsa->_method_mod_p);
     BN_MONT_CTX_free(rsa->_method_mod_q);
+    for (i = 0; i < sk_RSA_PRIME_INFO_num(rsa->prime_infos); i++) {
+        pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
+        BN_MONT_CTX_free(pinfo->m);
+    }
     return 1;
 }
diff --git a/crypto/rsa/rsa_pmeth.c b/crypto/rsa/rsa_pmeth.c
index 5e2df3e8ff..8a114cff89 100644
--- a/crypto/rsa/rsa_pmeth.c
+++ b/crypto/rsa/rsa_pmeth.c
@@ -25,6 +25,7 @@ typedef struct {
     /* Key gen parameters */
     int nbits;
     BIGNUM *pub_exp;
+    int primes;
     /* Keygen callback info */
     int gentmp[2];
     /* RSA padding mode */
@@ -54,6 +55,7 @@ static int pkey_rsa_init(EVP_PKEY_CTX *ctx)
     if (rctx == NULL)
         return 0;
     rctx->nbits = 1024;
+    rctx->primes = RSA_DEFAULT_PRIME_NUM;
     if (pkey_ctx_is_pss(ctx))
         rctx->pad_mode = RSA_PKCS1_PSS_PADDING;
     else
@@ -473,6 +475,14 @@ static int pkey_rsa_ctrl(EVP_PKEY_CTX *ctx, int type, int p1, void *p2)
         rctx->pub_exp = p2;
         return 1;
 
+    case EVP_PKEY_CTRL_RSA_KEYGEN_PRIMES:
+        if (p1 < RSA_DEFAULT_PRIME_NUM || p1 > RSA_MAX_PRIME_NUM) {
+            RSAerr(RSA_F_PKEY_RSA_CTRL, RSA_R_KEY_PRIME_NUM_INVALID);
+            return -2;
+        }
+        rctx->primes = p1;
+        return 1;
+
     case EVP_PKEY_CTRL_RSA_OAEP_MD:
     case EVP_PKEY_CTRL_GET_RSA_OAEP_MD:
         if (rctx->pad_mode != RSA_PKCS1_OAEP_PADDING) {
@@ -583,6 +593,7 @@ static int pkey_rsa_ctrl_str(EVP_PKEY_CTX *ctx,
     }
     if (strcmp(type, "rsa_padding_mode") == 0) {
         int pm;
+
         if (strcmp(value, "pkcs1") == 0) {
             pm = RSA_PKCS1_PADDING;
         } else if (strcmp(value, "sslv23") == 0) {
@@ -606,6 +617,7 @@ static int pkey_rsa_ctrl_str(EVP_PKEY_CTX *ctx,
 
     if (strcmp(type, "rsa_pss_saltlen") == 0) {
         int saltlen;
+
         if (!strcmp(value, "digest"))
             saltlen = RSA_PSS_SALTLEN_DIGEST;
         else if (!strcmp(value, "max"))
@@ -618,13 +630,14 @@ static int pkey_rsa_ctrl_str(EVP_PKEY_CTX *ctx,
     }
 
     if (strcmp(type, "rsa_keygen_bits") == 0) {
-        int nbits;
-        nbits = atoi(value);
+        int nbits = atoi(value);
+
         return EVP_PKEY_CTX_set_rsa_keygen_bits(ctx, nbits);
     }
 
     if (strcmp(type, "rsa_keygen_pubexp") == 0) {
         int ret;
+
         BIGNUM *pubexp = NULL;
         if (!BN_asc2bn(&pubexp, value))
             return 0;
@@ -634,6 +647,12 @@ static int pkey_rsa_ctrl_str(EVP_PKEY_CTX *ctx,
         return ret;
     }
 
+    if (strcmp(type, "rsa_keygen_primes") == 0) {
+        int nprimes = atoi(value);
+
+        return EVP_PKEY_CTX_set_rsa_keygen_primes(ctx, nprimes);
+    }
+
     if (strcmp(type, "rsa_mgf1_md") == 0)
         return EVP_PKEY_CTX_md(ctx,
                                EVP_PKEY_OP_TYPE_SIG | EVP_PKEY_OP_TYPE_CRYPT,
@@ -664,6 +683,7 @@ static int pkey_rsa_ctrl_str(EVP_PKEY_CTX *ctx,
         unsigned char *lab;
         long lablen;
         int ret;
+
         lab = OPENSSL_hexstr2buf(value, &lablen);
         if (!lab)
             return 0;
@@ -718,7 +738,8 @@ static int pkey_rsa_keygen(EVP_PKEY_CTX *ctx, EVP_PKEY *pkey)
     } else {
         pcb = NULL;
     }
-    ret = RSA_generate_key_ex(rsa, rctx->nbits, rctx->pub_exp, pcb);
+    ret = RSA_generate_multi_prime_key(rsa, rctx->nbits, rctx->primes,
+                                       rctx->pub_exp, pcb);
     BN_GENCB_free(pcb);
     if (ret > 0 && !rsa_set_pss_param(rsa, ctx)) {
         RSA_free(rsa);
diff --git a/doc/man1/genpkey.pod b/doc/man1/genpkey.pod
index ddfd04002c..d8f1c24f74 100644
--- a/doc/man1/genpkey.pod
+++ b/doc/man1/genpkey.pod
@@ -105,6 +105,29 @@ below.
 
 The number of bits in the generated key. If not specified 1024 is used.
 
+=item B<rsa_keygen_primes:numprimes>
+
+The number of primes in the generated key. If not specified 2 is used.
+
+=item B<rsa_keygen_pubexp:value>
+
+The RSA public exponent value. This can be a large decimal or
+hexadecimal value if preceded by B<0x>. Default value is 65537.
+
+=back
+
+=head1 RSA-PSS KEY GENERATION OPTIONS
+
+Note: by default an B<RSA-PSS> key has no parameter restrictions.
+
+=over 4
+
+=item B<rsa_keygen_bits:numbits>, B<rsa_keygen_pubexp:value>
+
+These options have the same meaning as the B<RSA> algorithm.
+
+=item B<rsa_pss_keygen_md:digest>
+
 =item B<rsa_keygen_pubexp:value>
 
 The RSA public exponent value. This can be a large decimal or
diff --git a/doc/man1/genrsa.pod b/doc/man1/genrsa.pod
index f6a2d8a7f3..3e42c98f5d 100644
--- a/doc/man1/genrsa.pod
+++ b/doc/man1/genrsa.pod
@@ -28,6 +28,7 @@ B<openssl> B<genrsa>
 [B<-rand file...>]
 [B<-writerand file>]
 [B<-engine id>]
+[B<-primes num>]
 [B<numbits>]
 
 =head1 DESCRIPTION
@@ -83,6 +84,13 @@ to attempt to obtain a functional reference to the specified engine,
 thus initialising it if needed. The engine will then be set as the default
 for all available algorithms.
 
+=item B<-primes num>
+
+Specify the number of primes to use while generating the RSA key. The B<num>
+parameter must be a positive integer that is greater than 1 and less than 16.
+If B<num> is greater than 2, then the generated key is called a 'multi-prime'
+RSA key, which is defined in RFC 8017.
+
 =item B<numbits>
 
 The size of the private key to generate in bits. This must be the last option
@@ -92,15 +100,17 @@ specified. The default is 2048.
 
 =head1 NOTES
 
-RSA private key generation essentially involves the generation of two prime
-numbers. When generating a private key various symbols will be output to
+RSA private key generation essentially involves the generation of two or more
+prime numbers. When generating a private key various symbols will be output to
 indicate the progress of the generation. A B<.> represents each number which
 has passed an initial sieve test, B<+> means a number has passed a single
-round of the Miller-Rabin primality test. A newline means that the number has
-passed all the prime tests (the actual number depends on the key size).
+round of the Miller-Rabin primality test, B<*> means the current prime starts
+a regenerating progress due to some failed tests. A newline means that the number
+has passed all the prime tests (the actual number depends on the key size).
 
 Because key generation is a random process the time taken to generate a key
-may vary somewhat.
+may vary somewhat. But in general, more primes lead to less generation time
+of a key.
 
 =head1 BUGS
 
diff --git a/doc/man1/speed.pod b/doc/man1/speed.pod
index d8d5f6f22b..80602a4625 100644
--- a/doc/man1/speed.pod
+++ b/doc/man1/speed.pod
@@ -15,6 +15,7 @@ B<openssl speed>
 [B<-decrypt>]
 [B<-rand file...>]
 [B<-writerand file>]
+[B<-primes num>]
 [B<algorithm...>]
 
 =head1 DESCRIPTION
@@ -65,6 +66,11 @@ all others.
 Writes random data to the specified I<file> upon exit.
 This can be used with a subsequent B<-rand> flag.
 
+=item B<-primes num>
+
+Generate a B<num>-prime RSA key and use it to run the benchmarks. This option
+is only effective if RSA algorithm is specified to test.
+
 =item B<[zero or more test algorithms]>
 
 If any options are given, B<speed> tests those algorithms, otherwise all of
diff --git a/doc/man3/RSA_generate_key.pod b/doc/man3/RSA_generate_key.pod
index be18ae24ff..6e8e50c0ca 100644
--- a/doc/man3/RSA_generate_key.pod
+++ b/doc/man3/RSA_generate_key.pod
@@ -2,13 +2,15 @@
 
 =head1 NAME
 
-RSA_generate_key_ex, RSA_generate_key - generate RSA key pair
+RSA_generate_key_ex, RSA_generate_key,
+RSA_generate_multi_prime_key - generate RSA key pair
 
 =head1 SYNOPSIS
 
  #include <openssl/rsa.h>
 
  int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e, BN_GENCB *cb);
+ int RSA_generate_multi_prime_key(RSA *rsa, int bits, int primes, BIGNUM *e, BN_GENCB *cb);
 
 Deprecated:
 
@@ -19,13 +21,19 @@ Deprecated:
 
 =head1 DESCRIPTION
 
-RSA_generate_key_ex() generates a key pair and stores it in the B<RSA>
-structure provided in B<rsa>. The pseudo-random number generator must
+RSA_generate_key_ex() generates a 2-prime RSA key pair and stores it in the
+B<RSA> structure provided in B<rsa>. The pseudo-random number generator must
 be seeded prior to calling RSA_generate_key_ex().
 
-The modulus size will be of length B<bits>, and the public exponent will be
-B<e>. Key sizes with B<num> E<lt> 1024 should be considered insecure.
-The exponent is an odd number, typically 3, 17 or 65537.
+RSA_generate_multi_prime_key() generates a multi-prime RSA key pair and stores
+it in the B<RSA> structure provided in B<rsa>. The number of primes is given by
+the B<primes> parameter. The pseudo-random number generator must be seeded prior
+to calling RSA_generate_multi_prime_key().
+
+The modulus size will be of length B<bits>, the number of primes to form the
+modulus will be B<primes>, and the public exponent will be B<e>. Key sizes
+with B<num> E<lt> 1024 should be considered insecure. The exponent is an odd
+number, typically 3, 17 or 65537.
 
 A callback function may be used to provide feedback about the
 progress of the key generation. If B<cb> is not B<NULL>, it
@@ -55,10 +63,12 @@ it is called as B<BN_GENCB_call(cb, 3, 0)>.
 
 =back
 
-The process is then repeated for prime q with B<BN_GENCB_call(cb, 3, 1)>.
+The process is then repeated for prime q and other primes (if any)
+with B<BN_GENCB_call(cb, 3, i)> where B<i> indicates the i-th prime.
 
 =head1 RETURN VALUE
 
+RSA_generate_multi_prime_key() returns 1 on success or 0 on error.
 RSA_generate_key_ex() returns 1 on success or 0 on error.
 The error codes can be obtained by L<ERR_get_error(3)>.
 
@@ -81,7 +91,7 @@ RSA_generate_key_ex() intsead.
 
 =head1 COPYRIGHT
 
-Copyright 2000-2016 The OpenSSL Project Authors. All Rights Reserved.
+Copyright 2000-2017 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
diff --git a/doc/man3/RSA_get0_key.pod b/doc/man3/RSA_get0_key.pod
index 55a39a3105..6e6576e7f3 100644
--- a/doc/man3/RSA_get0_key.pod
+++ b/doc/man3/RSA_get0_key.pod
@@ -4,8 +4,10 @@
 
 RSA_set0_key, RSA_set0_factors, RSA_set0_crt_params, RSA_get0_key,
 RSA_get0_factors, RSA_get0_crt_params, RSA_clear_flags,
-RSA_test_flags, RSA_set_flags, RSA_get0_engine - Routines for getting
-and setting data in an RSA object
+RSA_test_flags, RSA_set_flags, RSA_get0_engine, RSA_get_multi_prime_extra_count,
+RSA_get0_multi_prime_factors, RSA_get0_multi_prime_crt_params,
+RSA_set0_multi_prime_params, RSA_get_version
+- Routines for getting and setting data in an RSA object
 
 =head1 SYNOPSIS
 
@@ -24,6 +26,13 @@ and setting data in an RSA object
  int RSA_test_flags(const RSA *r, int flags);
  void RSA_set_flags(RSA *r, int flags);
  ENGINE *RSA_get0_engine(RSA *r);
+ int RSA_get_multi_prime_extra_count(const RSA *r);
+ int RSA_get0_multi_prime_factors(const RSA *r, const BIGNUM *primes[]);
+ int RSA_get0_multi_prime_crt_params(const RSA *r, const BIGNUM *exps[],
+                                     const BIGNUM *coeffs[]);
+ int RSA_set0_multi_prime_params(RSA *r, BIGNUM *primes[], BIGNUM *exps[],
+                                BIGNUM *coeffs[], int pnum);
+ int RSA_get_version(RSA *r);
 
 =head1 DESCRIPTION
 
@@ -36,6 +45,11 @@ private key (see PKCS#1 section 3 Key Types), where B<p> and B<q> are
 the first and second factor of B<n> and B<dmp1>, B<dmq1> and B<iqmp>
 are the exponents and coefficient for CRT calculations.
 
+For multi-prime RSA (defined in RFC 8017), there are also one or more
+'triplet' in an RSA object. A triplet contains three members, B<r>, B<d>
+and B<t>. B<r> is the additional prime besides B<p> and B<q>. B<d> and
+B<t> are the exponent and coefficient for CRT calculations.
+
 The B<n>, B<e> and B<d> parameters can be obtained by calling
 RSA_get0_key().  If they have not been set yet, then B<*n>, B<*e> and
 B<*d> will be set to NULL.  Otherwise, they are set to pointers to
@@ -59,9 +73,15 @@ B<dmq1> and B<iqmp> parameters can be obtained and set with
 RSA_get0_crt_params() and RSA_set0_crt_params().
 
 For RSA_get0_key(), RSA_get0_factors(), and RSA_get0_crt_params(),
-NULL value BIGNUM ** output parameters are permitted.  The functions
+NULL value BIGNUM ** output parameters are permitted. The functions
 ignore NULL parameters but return values for other, non-NULL, parameters.
 
+For multi-prime RSA, RSA_get0_multi_prime_factors() and RSA_get0_multi_prime_params()
+can be used to obtain other primes and related CRT parameters. The
+return values are stored in an array of B<BIGNUM *>. RSA_set0_multi_prime_params()
+sets a collect of multi-prime 'triplet' members (prime, exponent and coefficient)
+into an RSA object.
+
 RSA_set_flags() sets the flags in the B<flags> parameter on the RSA
 object. Multiple flags can be passed in one go (bitwise ORed together).
 Any flags that are already set are left set. RSA_test_flags() tests to
@@ -74,6 +94,8 @@ RSA object.
 RSA_get0_engine() returns a handle to the ENGINE that has been set for
 this RSA object, or NULL if no such ENGINE has been set.
 
+RSA_get_version() returns the version of an RSA object B<r>.
+
 =head1 NOTES
 
 Values retrieved with RSA_get0_key() are owned by the RSA object used
@@ -82,10 +104,27 @@ needed, duplicate the received value using BN_dup() and pass the
 duplicate.  The same applies to RSA_get0_factors() and RSA_set0_factors()
 as well as RSA_get0_crt_params() and RSA_set0_crt_params().
 
+The caller should obtain the size by calling RSA_get_multi_prime_extra_count()
+in advance and allocate sufficient buffer to store the return values before
+calling RSA_get0_multi_prime_factors() and RSA_get0_multi_prime_params().
+
+RSA_set0_multi_prime_params() always clears the original multi-prime
+triplets in RSA object B<r> and assign the new set of triplets into it.
+
 =head1 RETURN VALUES
 
-RSA_set0_key(), RSA_set0_factors and RSA_set0_crt_params() return 1 on
-success or 0 on failure.
+RSA_set0_key(), RSA_set0_factors(), RSA_set0_crt_params() and
+RSA_set0_multi_prime_params() return 1 on success or 0 on failure.
+
+RSA_get0_multi_prime_factors() and RSA_get0_multi_prime_crt_params() return
+1 on success or 0 on failure.
+
+RSA_get_multi_prime_extra_count() returns two less than the number of primes
+in use, which is 0 for traditional RSA and the number of extra primes for
+multi-prime RSA.
+
+RSA_get_version() returns B<RSA_ASN1_VERSION_MULTI> for multi-prime RSA and
+B<RSA_ASN1_VERSION_DEFAULT> for normal two-prime RSA, as defined in RFC 8017.
 
 RSA_test_flags() returns the current state of the flags in the RSA object.
 
@@ -98,11 +137,15 @@ L<RSA_new(3)>, L<RSA_size(3)>
 
 =head1 HISTORY
 
-The functions described here were added in OpenSSL 1.1.0.
+RSA_get_multi_prime_extra_count(), RSA_get0_multi_prime_factors(),
+RSA_get0_multi_prime_crt_params(), RSA_set0_multi_prime_params(),
+and RSA_get_version() functions were added in OpenSSL 1.1.1.
+
+Other functions described here were added in OpenSSL 1.1.0.
 
 =head1 COPYRIGHT
 
-Copyright 2016 The OpenSSL Project Authors. All Rights Reserved.
+Copyright 2016-2017 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
diff --git a/doc/man3/RSA_meth_new.pod b/doc/man3/RSA_meth_new.pod
index a578389ba8..fde1a41e64 100644
--- a/doc/man3/RSA_meth_new.pod
+++ b/doc/man3/RSA_meth_new.pod
@@ -12,7 +12,8 @@ RSA_meth_set_priv_dec, RSA_meth_get_mod_exp, RSA_meth_set_mod_exp,
 RSA_meth_get_bn_mod_exp, RSA_meth_set_bn_mod_exp, RSA_meth_get_init,
 RSA_meth_set_init, RSA_meth_get_finish, RSA_meth_set_finish,
 RSA_meth_get_sign, RSA_meth_set_sign, RSA_meth_get_verify,
-RSA_meth_set_verify, RSA_meth_get_keygen, RSA_meth_set_keygen
+RSA_meth_set_verify, RSA_meth_get_keygen, RSA_meth_set_keygen,
+RSA_meth_get_multi_prime_keygen, RSA_meth_set_multi_prime_keygen
 - Routines to build up RSA methods
 
 =head1 SYNOPSIS
@@ -111,6 +112,15 @@ RSA_meth_set_verify, RSA_meth_get_keygen, RSA_meth_set_keygen
                          int (*keygen)(RSA *rsa, int bits, BIGNUM *e,
                                        BN_GENCB *cb));
 
+ int (*RSA_meth_get_multi_prime_keygen(const RSA_METHOD *meth))(RSA *rsa, int bits,
+                                                                int primes, BIGNUM *e,
+                                                                BN_GENCB *cb);
+
+ int RSA_meth_set_multi_prime_keygen(RSA_METHOD *meth,
+                                     int (*keygen) (RSA *rsa, int bits,
+                                                    int primes, BIGNUM *e,
+                                                    BN_GENCB *cb));
+
 =head1 DESCRIPTION
 
 The B<RSA_METHOD> type is a structure used for the provision of custom
@@ -193,8 +203,14 @@ by this function. This function may be NULL.
 RSA_meth_get_keygen() and RSA_meth_set_keygen() get and set the
 function used for generating a new RSA key pair respectively. This
 function will be called in response to the application calling
-RSA_generate_key(). The parameter for the function has the same
-meaning as for RSA_generate_key().
+RSA_generate_key_ex(). The parameter for the function has the same
+meaning as for RSA_generate_key_ex().
+
+RSA_meth_get_multi_prime_keygen() and RSA_meth_set_multi_prime_keygen() get
+and set the function used for generating a new multi-prime RSA key pair
+respectively. This function will be called in response to the application calling
+RSA_generate_multi_prime_key(). The parameter for the function has the same
+meaning as for RSA_generate_multi_prime_key().
 
 RSA_meth_get_pub_enc(), RSA_meth_set_pub_enc(),
 RSA_meth_get_pub_dec(), RSA_meth_set_pub_dec(),
@@ -223,12 +239,16 @@ success or 0 on failure.
 
 =head1 SEE ALSO
 
-L<RSA_new(3)>, L<RSA_generate_key(3)>, L<RSA_sign(3)>,
-L<RSA_set_method(3)>, L<RSA_size(3)>, L<RSA_get0_key(3)>
+L<RSA_new(3)>, L<RSA_generate_key_ex(3)>, L<RSA_sign(3)>,
+L<RSA_set_method(3)>, L<RSA_size(3)>, L<RSA_get0_key(3)>,
+L<RSA_generate_multi_prime_key(3)>
 
 =head1 HISTORY
 
-The functions described here were added in OpenSSL 1.1.0.
+RSA_meth_get_multi_prime_keygen() and RSA_meth_set_multi_prime_keygen() were
+added in OpenSSL 1.1.1.
+
+Other functions described here were added in OpenSSL 1.1.0.
 
 =head1 COPYRIGHT
 
diff --git a/include/openssl/rsa.h b/include/openssl/rsa.h
index f45ea2e90c..8985219aee 100644
--- a/include/openssl/rsa.h
+++ b/include/openssl/rsa.h
@@ -45,6 +45,12 @@ extern "C" {
 # define RSA_3   0x3L
 # define RSA_F4  0x10001L
 
+/* based on RFC 8017 appendix A.1.2 */
+# define RSA_ASN1_VERSION_DEFAULT        0
+# define RSA_ASN1_VERSION_MULTI          1
+
+# define RSA_DEFAULT_PRIME_NUM           2
+
 # define RSA_METHOD_FLAG_NO_CHECK        0x0001/* don't check pub/private
                                                 * match */
 
@@ -120,6 +126,10 @@ extern "C" {
         RSA_pkey_ctx_ctrl(ctx, EVP_PKEY_OP_KEYGEN, \
                           EVP_PKEY_CTRL_RSA_KEYGEN_PUBEXP, 0, pubexp)
 
+# define EVP_PKEY_CTX_set_rsa_keygen_primes(ctx, primes) \
+        RSA_pkey_ctx_ctrl(ctx, EVP_PKEY_OP_KEYGEN, \
+                          EVP_PKEY_CTRL_RSA_KEYGEN_PRIMES, primes, NULL)
+
 # define  EVP_PKEY_CTX_set_rsa_mgf1_md(ctx, md) \
         RSA_pkey_ctx_ctrl(ctx, EVP_PKEY_OP_TYPE_SIG | EVP_PKEY_OP_TYPE_CRYPT, \
                           EVP_PKEY_CTRL_RSA_MGF1_MD, 0, (void *)(md))
@@ -170,6 +180,8 @@ extern "C" {
 # define EVP_PKEY_CTRL_GET_RSA_OAEP_MD   (EVP_PKEY_ALG_CTRL + 11)
 # define EVP_PKEY_CTRL_GET_RSA_OAEP_LABEL (EVP_PKEY_ALG_CTRL + 12)
 
+# define EVP_PKEY_CTRL_RSA_KEYGEN_PRIMES  (EVP_PKEY_ALG_CTRL + 13)
+
 # define RSA_PKCS1_PADDING       1
 # define RSA_SSLV23_PADDING      2
 # define RSA_NO_PADDING          3
@@ -192,15 +204,22 @@ int RSA_security_bits(const RSA *rsa);
 int RSA_set0_key(RSA *r, BIGNUM *n, BIGNUM *e, BIGNUM *d);
 int RSA_set0_factors(RSA *r, BIGNUM *p, BIGNUM *q);
 int RSA_set0_crt_params(RSA *r,BIGNUM *dmp1, BIGNUM *dmq1, BIGNUM *iqmp);
+int RSA_set0_multi_prime_params(RSA *r, BIGNUM *primes[], BIGNUM *exps[],
+                                BIGNUM *coeffs[], int pnum);
 void RSA_get0_key(const RSA *r,
                   const BIGNUM **n, const BIGNUM **e, const BIGNUM **d);
 void RSA_get0_factors(const RSA *r, const BIGNUM **p, const BIGNUM **q);
+int RSA_get_multi_prime_extra_count(const RSA *r);
+int RSA_get0_multi_prime_factors(const RSA *r, const BIGNUM *primes[]);
 void RSA_get0_crt_params(const RSA *r,
                          const BIGNUM **dmp1, const BIGNUM **dmq1,
                          const BIGNUM **iqmp);
+int RSA_get0_multi_prime_crt_params(const RSA *r, const BIGNUM *exps[],
+                                    const BIGNUM *coeffs[]);
 void RSA_clear_flags(RSA *r, int flags);
 int RSA_test_flags(const RSA *r, int flags);
 void RSA_set_flags(RSA *r, int flags);
+int RSA_get_version(RSA *r);
 ENGINE *RSA_get0_engine(const RSA *r);
 
 /* Deprecated version */
@@ -210,6 +229,9 @@ DEPRECATEDIN_0_9_8(RSA *RSA_generate_key(int bits, unsigned long e, void
 
 /* New version */
 int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e, BN_GENCB *cb);
+/* Multi-prime version */
+int RSA_generate_multi_prime_key(RSA *rsa, int bits, int primes,
+                                 BIGNUM *e, BN_GENCB *cb);
 
 int RSA_X931_derive_ex(RSA *rsa, BIGNUM *p1, BIGNUM *p2, BIGNUM *q1,
                        BIGNUM *q2, const BIGNUM *Xp1, const BIGNUM *Xp2,
@@ -468,6 +490,12 @@ int (*RSA_meth_get_keygen(const RSA_METHOD *meth))
 int RSA_meth_set_keygen(RSA_METHOD *rsa,
                         int (*keygen) (RSA *rsa, int bits, BIGNUM *e,
                                        BN_GENCB *cb));
+int (*RSA_meth_get_multi_prime_keygen(const RSA_METHOD *meth))
+    (RSA *rsa, int bits, int primes, BIGNUM *e, BN_GENCB *cb);
+int RSA_meth_set_multi_prime_keygen(RSA_METHOD *meth,
+                                    int (*keygen) (RSA *rsa, int bits,
+                                                   int primes, BIGNUM *e,
+                                                   BN_GENCB *cb));
 int ERR_load_RSA_strings(void);
 
 #  ifdef  __cplusplus
diff --git a/include/openssl/rsaerr.h b/include/openssl/rsaerr.h
index 6e6aac28b0..94bfd93fc7 100644
--- a/include/openssl/rsaerr.h
+++ b/include/openssl/rsaerr.h
@@ -114,6 +114,7 @@ int ERR_load_RSA_strings(void);
 # define RSA_R_INVALID_LABEL                              160
 # define RSA_R_INVALID_MESSAGE_LENGTH                     131
 # define RSA_R_INVALID_MGF1_MD                            156
+# define RSA_R_INVALID_MULTI_PRIME_KEY                    167
 # define RSA_R_INVALID_OAEP_PARAMETERS                    161
 # define RSA_R_INVALID_PADDING                            138
 # define RSA_R_INVALID_PADDING_MODE                       141
@@ -123,12 +124,17 @@ int ERR_load_RSA_strings(void);
 # define RSA_R_INVALID_TRAILER                            139
 # define RSA_R_INVALID_X931_DIGEST                        142
 # define RSA_R_IQMP_NOT_INVERSE_OF_Q                      126
+# define RSA_R_KEY_PRIME_NUM_INVALID                      165
 # define RSA_R_KEY_SIZE_TOO_SMALL                         120
 # define RSA_R_LAST_OCTET_INVALID                         134
 # define RSA_R_MGF1_DIGEST_NOT_ALLOWED                    152
 # define RSA_R_MODULUS_TOO_LARGE                          105
+# define RSA_R_MP_COEFFICIENT_NOT_INVERSE_OF_R            168
+# define RSA_R_MP_EXPONENT_NOT_CONGRUENT_TO_D             169
+# define RSA_R_MP_R_NOT_PRIME                             170
 # define RSA_R_NO_PUBLIC_EXPONENT                         140
 # define RSA_R_NULL_BEFORE_BLOCK_MISSING                  113
+# define RSA_R_N_DOES_NOT_EQUAL_PRODUCT_OF_PRIMES         172
 # define RSA_R_N_DOES_NOT_EQUAL_P_Q                       127
 # define RSA_R_OAEP_DECODING_ERROR                        121
 # define RSA_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE   148
diff --git a/test/build.info b/test/build.info
index d7cfd7e6c4..3d7af31ab6 100644
--- a/test/build.info
+++ b/test/build.info
@@ -46,7 +46,7 @@ INCLUDE_MAIN___test_libtestutil_OLB = /INCLUDE=MAIN
           x509_time_test x509_dup_cert_test x509_check_cert_pkey_test \
           recordlentest drbgtest sslbuffertest \
           time_offset_test pemtest ssl_cert_table_internal_test ciphername_test \
-          servername_test ocspapitest
+          servername_test ocspapitest rsa_mp_test
 
   SOURCE[aborttest]=aborttest.c
   INCLUDE[aborttest]=../include
@@ -152,6 +152,10 @@ INCLUDE_MAIN___test_libtestutil_OLB = /INCLUDE=MAIN
   INCLUDE[rsa_test]=.. ../include
   DEPEND[rsa_test]=../libcrypto libtestutil.a
 
+  SOURCE[rsa_mp_test]=rsa_mp_test.c
+  INCLUDE[rsa_mp_test]=.. ../include
+  DEPEND[rsa_mp_test]=../libcrypto libtestutil.a
+
   SOURCE[evp_test]=evp_test.c
   INCLUDE[evp_test]=../include
   DEPEND[evp_test]=../libcrypto libtestutil.a
diff --git a/test/recipes/15-test_mp_rsa.t b/test/recipes/15-test_mp_rsa.t
new file mode 100644
index 0000000000..f601c4c11d
--- /dev/null
+++ b/test/recipes/15-test_mp_rsa.t
@@ -0,0 +1,126 @@
+#! /usr/bin/env perl
+# Copyright 2017 The OpenSSL Project Authors. All Rights Reserved.
+# Copyright 2017 BaishanCloud. 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 warnings;
+
+use File::Spec;
+use OpenSSL::Test qw/:DEFAULT data_file/;
+use OpenSSL::Test::Utils;
+
+setup("test_mp_rsa");
+
+plan tests => 61;
+
+ok(run(test(["rsa_mp_test"])), "running rsa multi prime test");
+
+my $cleartext = data_file("plain_text");
+
+my @test_param = (
+    # 3 primes, 2048-bit
+    {
+        primes => '3',
+        bits => '2048',
+    },
+    # 4 primes, 2048-bit
+    {
+        primes => '4',
+        bits => '2048',
+    },
+    # 8 primes, 2048-bit
+    {
+        primes => '8',
+        bits => '2048',
+    },
+    # 15 primes, 2048-bit
+    {
+        primes => '15',
+        bits => '2048',
+    },
+    # 8 primes, 15360-bit (3 & 4 primes for 15360 bit is too long to gen a key)
+    {
+        primes => '8',
+        bits => '15360',
+    },
+    # 15 primes, 15360-bit
+    {
+        primes => '15',
+        bits => '15360',
+    },
+);
+
+# genrsa
+run_mp_tests(0);
+# evp
+run_mp_tests(1);
+
+sub run_mp_tests {
+    my $evp = shift;
+
+    foreach my $param (@test_param) {
+        my $primes = $param->{primes};
+        my $bits = $param->{bits};
+        my $name = ($evp ? "evp" : "") . "${bits}p${primes}";
+
+        if ($evp) {
+            ok(run(app([ 'openssl', 'genpkey', '-out', 'rsamptest.pem',
+                         '-algorithm', 'RSA', '-pkeyopt', "rsa_keygen_primes:$primes",
+                         '-pkeyopt', "rsa_keygen_bits:$bits"])), "genrsa $name");
+        } else {
+            ok(run(app([ 'openssl', 'genrsa', '-out', 'rsamptest.pem',
+                         '-primes', $primes, $bits])), "genrsa $name");
+        }
+
+        ok(run(app([ 'openssl', 'rsa', '-check', '-in', 'rsamptest.pem',
+                     '-noout'])), "rsa -check $name");
+        if ($evp) {
+            ok(run(app([ 'openssl', 'pkeyutl', '-inkey', 'rsamptest.pem',
+                         '-encrypt', '-in', $cleartext,
+                         '-out', 'rsamptest.enc' ])), "rsa $name encrypt");
+            ok(run(app([ 'openssl', 'pkeyutl', '-inkey', 'rsamptest.pem',
+                         '-decrypt', '-in', 'rsamptest.enc',
+                         '-out', 'rsamptest.dec' ])), "rsa $name decrypt");
+        } else {
+            ok(run(app([ 'openssl', 'rsautl', '-inkey', 'rsamptest.pem',
+                         '-encrypt', '-in', $cleartext,
+                         '-out', 'rsamptest.enc' ])), "rsa $name encrypt");
+            ok(run(app([ 'openssl', 'rsautl', '-inkey', 'rsamptest.pem',
+                         '-decrypt', '-in', 'rsamptest.enc',
+                         '-out', 'rsamptest.dec' ])), "rsa $name decrypt");
+        }
+
+        ok(check_msg(), "rsa $name check result");
+
+        # clean up temp files
+        unlink 'rsamptest.pem';
+        unlink 'rsamptest.enc';
+        unlink 'rsamptest.dec';
+    }
+}
+
+sub check_msg {
+    my $msg;
+    my $dec;
+
+    open(my $fh, "<", $cleartext) or return 0;
+    binmode $fh;
+    read($fh, $msg, 10240);
+    close $fh;
+    open($fh, "<", "rsamptest.dec") or return 0;
+    binmode $fh;
+    read($fh, $dec, 10240);
+    close $fh;
+
+    if ($msg ne $dec) {
+        print STDERR "cleartext and decrypted are not the same";
+        return 0;
+    }
+    return 1;
+}
diff --git a/test/recipes/15-test_mp_rsa_data/plain_text b/test/recipes/15-test_mp_rsa_data/plain_text
new file mode 100644
index 0000000000..60d11c0f69
--- /dev/null
+++ b/test/recipes/15-test_mp_rsa_data/plain_text
@@ -0,0 +1,4 @@
+It was the best of times, it was the worst of times,
+it was the age of wisdom, it was the age of foolishness,
+it was the epoch of belief, it was the epoch of incredulity,
+it was the season of Light, it was the season of Darkness.
diff --git a/test/rsa_mp_test.c b/test/rsa_mp_test.c
new file mode 100644
index 0000000000..ea4701e762
--- /dev/null
+++ b/test/rsa_mp_test.c
@@ -0,0 +1,370 @@
+/*
+ * Copyright 2017 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2017 BaishanCloud. 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
+ */
+
+/* This aims to test the setting functions */
+
+#include <stdio.h>
+#include <string.h>
+
+#include <openssl/crypto.h>
+#include <openssl/err.h>
+#include <openssl/rand.h>
+#include <openssl/bn.h>
+
+#include "testutil.h"
+
+#ifndef OPENSSL_NO_RSA
+# include <openssl/rsa.h>
+
+#define NUM_EXTRA_PRIMES 5
+
+static int key4096p7(RSA *key)
+{
+    /* C90 requires string should <= 509 bytes */
+    static unsigned char n1[] =
+        "\x00\xeb\xa2\x2b\x74\x76\x32\x33\xbf\xb9\x9a\xe4\xb0\x84\xac"
+        "\x9a\x20\x1b\xe6\x1a\x22\x3f\xcd\x13\xe1\x42\xee\xd8\x1a\x6e"
+        "\xe3\xd5\x91\x1e\xee\x32\x5c\x78\x76\x8b\x5d\x82\x6f\xd0\xaf"
+        "\xa3\x56\xd6\x15\x5f\x64\xb3\x5a\xcf\xc8\x7d\xa3\xb1\x3d\x10"
+        "\xbf\x47\x00\xa9\xc9\x96\x9d\xfd\x7c\x82\x4f\xb5\x70\x39\xd4"
+        "\xd9\x0f\xd7\xd9\x86\xd4\xd4\x35\x06\x35\x07\xa3\x1b\x8c\xf4"
+        "\x35\xb8\xb2\xd4\xa3\xbe\x6c\x64\x7d\x74\x17\x88\x36\x07\x32"
+        "\x6f\x84\x48\xd4\xb8\x4a\x12\xba\xe8\x40\x5b\xc6\xa5\xa4\x11"
+        "\x0d\x8a\xa6\x60\x3d\x98\x8b\xf8\x11\x8f\x43\xab\x2f\x95\x0f"
+        "\x3b\x20\x3f\x48\x88\xaa\x3d\x20\xa6\xaf\x6a\xdf\xc0\x95\x38"
+        "\xff\x47\x7c\x8a\x8b\xec\x76\x45\x43\xd0\x06\x7c\x71\x76\x5f"
+        "\x0d\x11\x58\x0a\xa9\x0e\x7e\x07\xe9\x89\xc1\x9e\x56\x6d\x08"
+        "\xe4\xe3\x16\xb4\xa0\x03\x7a\x49\x96\xa8\x88\xcf\x89\xe3\xdb"
+        "\x47\x0c\xd2\x1b\x6f\x67\x4d\xc8\xee\x53\xe9\x0b\x3d\xe5\x11"
+        "\x9d\x85\x75\xfe\x26\x4a\x99\x58\x79\x28\x91\x03\x8b\xe4\xbf"
+        "\x49\xd3\xfa\x8e\x25\xe3\xb1\xb2\xc2\x33\xd9\x8b\xe0\x9d\x1b"
+        "\xa4\xa0\xcf\x05\x5f\xb9\x19\x65\x74\x24\xae\x2e\x33\xc8\xd9";
+
+    static unsigned char n2[] =
+        "\x55\xae\xcb\x37\xa1\x3b\x95\xf7\x5f\xff\x1f\x06\x4a\xab\x85"
+        "\x94\x37\x15\x6f\xf2\xc8\x9b\x73\xb9\x1d\x8e\x30\x63\x5a\xa1"
+        "\x84\x31\xa8\xbe\x7e\x4f\xeb\xa0\xe6\x73\xc7\xbe\xd4\x5e\xe7"
+        "\x5e\xae\x5d\xfd\xf7\xf5\xa4\xb6\xb8\x3c\x15\xac\x1b\xcd\x3a"
+        "\xb6\xbd\xa9\x11\xd0\x44\xa5\x08\x7e\x60\x1d\x1d\x4d\xa6\xd7"
+        "\x06\xe5\x4f\x37\x0d\x5c\xbd\xad\x8d\x40\x18\xbd\xc7\x58\x20"
+        "\xed\xa8\x4d\xd8\x29\xdc\x42\x4f\x50\xa6\x03\xf0\xa5\xa2\x18"
+        "\x2b\xdd\x1c\x0e\x89\x3f\xbc\x5d\x35\xac\xa8\x55\x6d\x17\x28"
+        "\xae\xee\x78\xeb\x6d\x7a\x21\xd6\x6c\xdd\x21\x1d\xcc\xe5\xb0"
+        "\xf2\xef\x7f\x1d\x8a\xb7\x95\xaf\x40\xb5\x5c\x8b\x0d\x59\x45"
+        "\x21\x86\x34\x6d\x13\xd7\x14\xa5\x0e\xca\x88\x32\x57\xfe\x2d"
+        "\xd1\xcb\xad\x14\xbe\x30\xb1\x69\x9b\x72\x82\xad\x47\xb5\x45"
+        "\xc8\x65\x83\xce\x07\x21\x15\x6b\x65\x9d\xf3\x4d\x92\x19\xbe"
+        "\x67\x73\xd0\x60\x9f\xc7\xef\xee\xfa\xb0\xd3\xa4\x95\x81\xb0"
+        "\xbd\x4b\xd5\xf8\xbd\xbd\x9f\x41\x41\xc0\xfd\xe9\x17\xe3\x16"
+        "\xd3\xdc\xc8\xe2\xa5\xca\xff\xea\x91\xf4\x33\xc0\xfb\xdc\x02"
+        "\x62\x0a\x4e\x26\x92\xb5\x13\xec\x43\xd2\x25\x19\xe2\x6d\xef"
+        "\xea\x38\x75";
+
+    static unsigned char e[] = "\x01\x00\x01";
+
+    static unsigned char d1[] =
+        "\x60\x43\x92\x69\x33\xd8\x72\x97\xc3\x25\xea\x83\xca\xd0\x10"
+        "\xef\x49\x36\x8a\x3a\xaf\xc2\x02\x7b\x26\xb3\x19\x0a\x43\x7f"
+        "\x44\xc2\xd2\xd6\x11\x31\x01\xed\xbc\x25\xe9\xa1\xf0\xa9\xb0"
+        "\x9b\x4b\x3e\xd4\x07\xf9\xd6\x01\xc9\x30\xba\xed\x2f\xbb\x65"
+        "\xc9\x86\x15\xd7\x4b\x77\x24\x15\xf7\xce\xc4\x9b\x21\x62\x4d"
+        "\xde\x77\xf0\x1e\x62\x49\x54\xda\xda\xcd\xdd\x0f\x53\xe2\xd2"
+        "\x39\x4f\x60\x8e\xec\xe3\x49\x1b\xe7\x9a\x3e\x17\x8e\x5a\x77"
+        "\x4a\x15\xf6\x57\xc5\xfe\x2b\xa5\x94\x04\x94\x9c\xe7\xa8\xcc"
+        "\x07\x4b\xd8\xb8\x55\xaa\xdf\x33\xca\x2c\x8c\xee\x61\x1a\x89"
+        "\x0d\x3b\xcd\x16\x28\xb5\x50\x62\x2f\xb1\x9e\x61\x27\xd7\xf1"
+        "\xe1\x22\x58\x84\xcd\x18\xc3\xbf\xde\x52\x25\xdd\xc1\xcd\x2a"
+        "\x20\x78\x5e\xde\x65\x6a\x25\x12\x2d\x78\x28\xdb\x2c\x6f\x1b"
+        "\x65\x71\x1b\x2e\x1c\x18\x62\xf6\x71\x82\xdc\xa8\x80\x0e\xb5"
+        "\x8b\x09\x97\xc3\x81\xe1\x23\x2e\x40\x75\xbf\xd3\x78\xdc\xd5"
+        "\xc3\xe6\x75\x8b\xb0\x48\x7a\x78\x7d\xfe\xcc\x4c\xa1\x40\x11"
+        "\x20\xbe\x2a\xc1\xaf\x18\x53\x45\x6a\xb4\x2a\x0a\xc9\x01\x36"
+        "\x60\xf1\x61\x97\x73\xde\xac\x3e\x24\xff\x5b\x25\xdb\x93\x97";
+
+    static unsigned char d2[] =
+        "\x03\xf4\xef\x4a\x73\x47\xa8\x31\xd1\x63\x5b\xba\xa6\xe2\x7a"
+        "\xd8\xef\xea\x2f\x04\x76\x3c\x7a\x8d\x4e\xc1\x81\xc5\x39\x4f"
+        "\x09\xc4\xb1\xfb\x75\xd0\xae\x32\x2e\x44\xa3\xb6\xdc\x60\xc6"
+        "\x60\x1e\x40\x6f\x04\xc2\x7a\xd3\x0f\x8a\xa4\x23\x8f\x0e\x2e"
+        "\x2a\xcd\x65\x2a\x6e\x97\xa8\xe5\x01\x96\xd1\x41\x27\xa5\x16"
+        "\x2f\xb0\x15\x0a\x33\x06\x72\x40\xa5\xe4\x74\xbe\x4a\x87\x28"
+        "\x8a\x68\xea\x39\x42\x08\x47\xff\x9d\x9e\x06\x03\xfa\x4a\x6a"
+        "\xbb\xe5\x6f\x97\x05\x5f\xae\x47\xe6\xc4\xe0\x48\x62\x65\x9b"
+        "\x91\x50\xda\x84\xcf\xa3\xb2\x9d\x51\x84\x02\x4b\xe6\x12\xa2"
+        "\x87\x6e\x1f\x43\x2f\x90\x36\xb1\x15\xc6\xf6\xe0\xde\x52\x39"
+        "\x8e\x22\x39\x8c\x4f\x1c\x08\xac\x55\x5c\xa9\x69\x4e\x77\x8d"
+        "\x74\x6e\x0b\x06\xda\x61\xcd\xe2\xc8\xc6\x02\x54\x70\x05\xc1"
+        "\x50\x6d\x5e\x3e\x66\x7d\x41\x3c\x57\x68\x8a\x16\xb9\xd8\x29"
+        "\xfb\xeb\x05\x57\x87\xdc\x88\xc6\x91\x67\x3c\xcc\x19\x28\xa1"
+        "\x23\x54\xc3\x88\xc4\x28\x63\xca\xf7\xb2\xea\x34\xa1\x9e\xc1"
+        "\xca\x9b\x96\xe7\x4d\x82\x22\xf9\xcb\xc3\x2a\x3f\x19\xe3\x7c"
+        "\xce\x8c\x66\x45\xfe\xe6\x31\x31\x66\xd4\x1a\xb5\x47\x98\xea"
+        "\x80\x01";
+
+    static unsigned char p[] =
+        "\x03\xf5\x90\x21\xf3\xa6\x13\xdd\x33\x2a\x4c\x1f\x53\xd6\x9e"
+        "\x64\x1d\xfc\xed\xfb\xa1\xe6\xd0\x80\xd1\x6a\xcd\x20\x68\xea"
+        "\x75\x72\x59\x24\x8b\x1b\x28\x37\xbd\x8f\xc4\xc9\xb6\xda\xef"
+        "\x55\xb9\x0e\x26\x93\x8a\x8a\xec\x2f\x47\xe6\x4e\xa9\x42\xfb"
+        "\x02\x28\x5e\x37\xb7\x5a\x61\xfa\x39\xab\x63\x61\x1b\xbb";
+
+    static unsigned char q[] =
+        "\x01\xea\x64\x6e\x7d\xaa\xd7\x6a\xfa\x0c\x52\xfa\x2b\x00\x51"
+        "\x7d\x4d\xc3\x9f\x1d\x21\xb2\x62\x11\xd4\x7d\x0e\xc2\xe7\xdf"
+        "\xd0\x04\xd6\x30\x02\x54\xb2\xa5\xb7\x85\xd5\x96\xc7\x24\x83"
+        "\x8e\x3d\x60\xc3\x42\xa5\xa3\x76\xdd\x6e\x60\xa0\xbf\x85\x05"
+        "\xb6\x52\x32\xeb\x41\x6f\x08\xc8\x56\x43\xd8\x80\x06\xf7";
+
+    static unsigned char dmp1[] =
+        "\x03\xcc\x5c\xe7\x45\x91\x49\xb3\x47\x77\xc7\xa9\xb2\x4b\xce"
+        "\x8e\xab\xfa\x4f\xf1\xbd\x63\xeb\x19\xfa\x4e\x64\xd6\x37\xf0"
+        "\xde\x95\xc2\x11\x7d\xe6\xa2\xd1\xbe\xe9\x23\x58\x85\x35\x4a"
+        "\xb0\xc9\xa5\x5a\xba\xe7\x09\xda\x06\x8e\x0a\xd3\xe2\x2c\x61"
+        "\x14\xb3\xd7\x97\xca\x2e\x4a\x9a\xbd\x22\xc0\x67\x94\x2b";
+
+    static unsigned char dmq1[] =
+        "\x01\x66\x28\x8d\xce\x38\x8d\x76\xb3\x43\x77\x03\x01\x8f\x0c"
+        "\xf5\x40\x6b\x84\x75\x69\x5b\xf8\x66\x5f\x54\x2b\x08\xcd\x03"
+        "\x58\xd1\x7f\x81\xb6\xe2\x17\x4c\x13\x3a\xab\x21\xa1\x36\x98"
+        "\xe2\xb5\x0f\x4b\xed\x0c\x3e\xd4\x1c\xab\x75\xe5\x51\x9b\x9c"
+        "\xed\x69\x21\x89\x52\xd3\xfe\x8d\x1a\xfc\x18\x4e\x81\x47";
+
+    static unsigned char iqmp[] =
+        "\x02\x31\xad\xe8\xa5\xa9\x5d\x52\x70\x68\xc1\x6e\x6b\x4e\xb5"
+        "\x0b\xc2\xd9\x89\xe5\xbc\x46\xca\xac\xac\x04\xe2\x39\x7f\xc4"
+        "\xa0\xe4\x9e\x8a\xb8\x1e\x67\x66\x85\xb8\x3e\x42\x7c\xc7\x2c"
+        "\x02\x64\x7c\xd3\x40\xda\x5d\x9f\x38\xa7\x7c\x30\xcd\x6b\x7d"
+        "\x4d\xd0\x77\x2d\x9b\xd1\xc3\x55\x03\x69\x3d\xda\x48\xe2";
+
+    static char *primes[] = {
+        "\x01\xb2\xe2\xf7\x3b\x29\xdc\x90\xf9\xc4\x5a\x75\x09\x00\xbe"
+        "\xec\xa6\x97\xbc\x47\x89\x24\x71\x48\xa7\xc9\xc8\xed\x9c\x88"
+        "\xb9\x9f\xcd\x79\xc9\x2d\xb1\x78\xf7\x54\x2c\x28\x01\x37\x01"
+        "\xa0\xff\xf2\x69\x52\x93\xf0\x16\x08\xaa\x2f\xff\x35\x14\x2d"
+        "\x65\x8d\x21\x05\x30\x84\x9b\xcb\x58\x42\xc6\x9b\xa7\xb5",
+
+        "\x01\xb7\x66\xfe\xb5\x94\xf8\x46\xcb\x06\x2a\x7a\xd4\x35\xe4"
+        "\x68\x6d\xcf\x58\x0b\xb3\x12\xe6\x7b\x66\xee\x36\xf5\x1f\x79"
+        "\x8f\x82\x1e\xd9\x97\x33\x45\x37\xa3\x84\x54\xab\x4b\x12\x96"
+        "\x76\x9f\xf9\x98\x02\xf1\x5e\xcb\x97\xe8\x13\xde\x91\x0b\xd5"
+        "\xec\x7f\x2b\x27\x55\xc1\x69\x58\xad\x8b\xaa\xce\x68\xc5",
+
+        "\x01\xbe\xdf\xa5\x33\xfb\xa1\xfa\xf6\xd2\x43\xcd\x76\x3e\x23"
+        "\xa2\xf7\x29\xeb\x65\xe5\xae\xe8\xfc\xfd\xca\x55\x16\x01\x57"
+        "\xcd\xca\x9e\x83\xf9\x61\x6a\x17\xac\x61\xec\x04\x32\x9f\x69"
+        "\xb8\x6d\x66\x33\x9b\xef\xf4\x91\xf1\x99\x02\xc2\xea\x58\x6e"
+        "\xad\x3d\x0e\xa9\x87\x17\x7c\x9b\x72\xcc\xab\x1c\x93\x2b",
+
+        "\x03\x2f\x4a\x9c\x49\x66\x9d\xbc\xae\xec\x54\x7d\xe6\x07\x52"
+        "\xc2\x9a\x09\xf5\xa7\x56\xa6\x68\x45\x38\x75\x7d\xb0\x0e\xee"
+        "\xf3\x23\xec\x74\x1e\x3b\xc0\x58\x1d\x43\xd9\x35\x15\x7e\x2f"
+        "\x28\xff\x08\x7a\x79\x44\xfc\x24\x06\xc5\x3f\xaa\xe0\xfa\xb2"
+        "\x1f\xd9\x4e\xd8\xc8\xda\xed\x1f\xaa\x77\x64\xae\xb3\xe3",
+
+        "\x01\xea\xaa\x9d\x90\x67\x3b\x2f\x9a\xe3\x7b\x56\x5c\x35\x9f"
+        "\x65\x0b\x0c\x3b\xa6\x60\x5f\x98\x36\x2c\xb6\xaa\xdb\xb2\x86"
+        "\x8b\x20\xba\xa4\x85\x7b\xa8\x80\x41\xee\x22\x1c\x7a\x92\xf5"
+        "\x39\x4e\x4a\x0b\x29\x0b\xe7\xdd\x3c\xb6\x51\xec\xc3\x26\xbc"
+        "\x33\x11\xbc\x29\x7a\x10\x68\x32\x55\xb4\x15\xd9\x8e\xc1"
+    };
+
+    static int primes_len[] = { 74, 74, 74, 74, 74 };
+
+    static char *exponents[] = {
+        "\x01\xa4\x49\xb7\x57\xc5\x50\x36\x08\x3c\xdc\x93\x29\x1d\x40"
+        "\x67\x63\x65\x57\x7f\xe7\x29\x82\x16\x0e\x9a\x74\x06\x37\x76"
+        "\xe7\xb6\x6a\x15\x5d\xf9\x3c\x00\x45\x3f\x62\xe1\x52\xb3\x3f"
+        "\x6e\xc2\x8d\x1b\x7e\xc4\x1c\x8e\x9e\xd7\x23\x45\xc8\x9d\x74"
+        "\x76\x25\x5b\x99\x31\x57\xa7\x5d\x71\x32\x2f\xd1\x74\xd5",
+
+        "\x01\x3a\xa4\x6d\x05\xf7\xeb\xa5\x3d\xe2\x67\x6e\xd7\x20\xd4"
+        "\x33\x17\x56\xdf\x34\x59\x81\xd2\x3b\x51\x64\x89\x44\x13\xca"
+        "\xc7\x41\xa4\xf7\xa8\xf6\xd4\xbc\xd7\xc1\x7d\xa3\xbf\x39\x4b"
+        "\x37\x1c\xac\xec\xf6\x46\x82\xdc\x05\x25\xf1\x7c\x71\x9e\xe9"
+        "\x0b\xd5\xb0\x40\x15\x7f\x4f\x01\x6a\x1c\x56\x2e\x42\x05",
+
+        "\x00\x9b\xd7\x14\x9e\xcf\x47\x4a\xe5\x1e\xa8\xc4\x93\x52\xd2"
+        "\x4c\xb7\xd3\x67\xa3\x4e\x79\x34\x09\x5e\x5c\x5c\x55\xe3\x3c"
+        "\x02\xa9\x81\xa4\x56\xa8\xb1\x3d\xf6\x40\xe3\xf5\x06\xce\x6f"
+        "\x29\x01\x05\xde\x43\xa8\x67\xeb\x29\x8d\x09\xd8\x7d\xaf\x3f"
+        "\x51\xac\xf4\x5b\x0c\xa0\x95\x35\x04\xd0\xf9\x6f\x6a\xa7",
+
+        "\x02\xfd\x38\x42\x48\x82\x90\x3a\xb0\xd4\x10\xd9\xba\x35\xd5"
+        "\x6f\xe1\xb4\xc7\x65\x30\xe7\x2f\xa7\x08\xbe\xfe\x21\x69\x62"
+        "\xcd\xc3\x42\x04\x1a\xfc\x6a\x24\x4a\x13\x8c\xa3\x4e\x71\x09"
+        "\x42\xa9\x5d\x03\xd7\x1e\xf0\xa9\xbf\xd1\x13\x59\x07\xa1\x45"
+        "\xde\xae\xd0\x5a\x98\xeb\x22\xf5\x3d\xc2\xa2\x35\x77\x91",
+
+        "\x13\x1d\x2c\x60\x28\xb5\x54\x88\x6b\x1e\x2d\xe2\x0f\xb0\xb2"
+        "\xe5\xf8\x47\x06\x97\x30\x82\x24\x72\x1f\x77\x8e\x71\x68\xee"
+        "\x58\x8b\x0c\xc7\xaa\x66\x89\x00\x88\x7f\x49\xae\xb8\xb4\xd6"
+        "\xd3\xa6\xec\xc2\x5f\x95\x5b\xb7\xf6\xbe\x40\x43\xe5\xe9\x64"
+        "\xef\xe6\xed\x92\xb4\xba\xea\x63\x0e\x4d\xdf\x98\xc1"
+    };
+
+    static int exps_len[] = { 74, 74, 74, 74, 73 };
+
+    static char *coefficients[] = {
+        "\x18\x19\x50\xc2\x69\x6a\x63\x66\x40\x6a\x43\xa6\x7d\x0d\x12"
+        "\x0f\x04\x3a\xe7\xb2\x1c\xe3\xfc\x6f\xa7\x8b\x5e\x99\xe3\x43"
+        "\x97\x68\x10\xee\x68\x73\x01\xc6\xaf\x5e\x26\xaf\xcc\x1f\x39"
+        "\x9c\x8d\xa9\x06\x80\x21\x7a\xaa\x29\x8a\x4b\x71\x03\xb0\x9a"
+        "\x2f\xd6\x6b\xb0\x0b\x93\xc9\x4d\x0b\x9d\x3f\xe6\x21",
+
+        "\x00\xa4\x80\x6e\xef\x34\xba\x3f\xe7\x96\xec\x25\x16\x25\xe9"
+        "\x77\x5f\x61\xb1\x48\xdb\x03\xfa\x80\xf3\xbd\x20\xd1\x60\x9a"
+        "\x10\x9d\xf0\x1b\xff\xb8\x50\x14\x54\x75\x53\x2b\x89\x9f\x39"
+        "\x96\x63\x05\x89\xfb\xfb\x7f\x59\x93\xdc\x61\xe2\x8c\xfc\x5a"
+        "\x6f\x2c\x6a\xcf\xd4\xac\xa5\x81\xf2\xdd\x68\x75\xd4\x48",
+
+        "\x00\xf6\xec\xd6\x98\x10\x42\x38\x94\x30\x2c\xd4\xe7\xb1\x5f"
+        "\xa2\xfd\xc9\xc4\x92\x78\xf6\x31\x34\xb7\x26\xa1\x7f\x0b\xa3"
+        "\xc3\xf6\x4f\xd0\x05\x4e\x98\x1b\xa5\x98\xde\x26\xb8\xc2\x14"
+        "\x12\xa4\xae\x2f\xd8\x48\x39\x1b\x33\x1d\x0f\x72\xaf\xd3\x8d"
+        "\xd8\xb0\x9f\x52\x42\x5d\xae\xf6\x3c\xe1\xd2\x09\xd8\x53",
+
+        "\x00\xb3\xce\x4b\x87\x41\x21\x34\x7b\xe3\x64\x74\xef\x9f\x71"
+        "\xcc\x01\x19\x50\x69\xbb\x5f\x69\xc8\xbc\x62\x8b\x4d\xa9\x73"
+        "\x23\x7f\xc6\xce\xfa\xe7\x96\xa7\x22\x44\x33\x32\x47\x60\x23"
+        "\xb4\xd2\x5e\xa4\xa1\xbd\x31\x1f\x04\x1a\xdf\xdb\x05\xe9\x4c"
+        "\x44\xfb\x9b\x73\xfe\x25\x3d\x7a\x61\xc2\x22\x9a\xd6\x18",
+
+        "\x01\x8d\x43\x63\x89\x6d\x97\xf3\x4a\x3e\x10\xa0\x94\x46\x1a"
+        "\x1c\x34\x22\xb3\xe3\x21\xff\xad\xf2\x1b\x56\x74\x32\xdc\xd2"
+        "\x0e\xd7\x3a\x9c\xe9\x87\xcc\xf1\x9c\x56\xfe\xff\x2f\x3d\xec"
+        "\x70\xba\xfb\x5d\x37\xa8\x57\xd1\xc4\xa9\x1b\xc9\xdc\x76\x68"
+        "\xca\x7d\x39\x59\x97\x2d\x07\x03\x52\xf6\x8d\xb6\x0e\x24"
+    };
+
+    static int coeffs_len[] = { 73, 74, 74, 74, 74 };
+
+    BIGNUM **pris = NULL, **exps = NULL, **coeffs = NULL;
+    int i, rv = 512;
+    unsigned char *n, *d;
+    size_t len_n, len_d;
+
+    len_n = sizeof(n1) + sizeof(n2) - 2;
+    n = OPENSSL_zalloc(len_n);
+    if (n == NULL)
+        return 0;
+
+    memcpy(n, n1, sizeof(n1) - 1);
+    memcpy(n + sizeof(n1) - 1, n2, sizeof(n2) - 1);
+
+    len_d = sizeof(d1) + sizeof(d2) - 2;
+    d = OPENSSL_zalloc(len_d);
+    if (d == NULL)
+        goto err;
+
+    memcpy(d, d1, sizeof(d1) - 1);
+    memcpy(d + sizeof(d1) - 1, d2, sizeof(d2) - 1);
+
+    if (!TEST_int_eq(RSA_set0_key(key,
+                                  BN_bin2bn(n, len_n, NULL),
+                                  BN_bin2bn(e, sizeof(e) - 1, NULL),
+                                  BN_bin2bn(d, len_d, NULL)), 1))
+        goto err;
+
+    if (!TEST_int_eq(RSA_set0_factors(key,
+                                      BN_bin2bn(p, sizeof(p) - 1, NULL),
+                                      BN_bin2bn(q, sizeof(q) - 1, NULL)), 1))
+        goto err;
+
+    if (!TEST_int_eq(RSA_set0_crt_params(key,
+                                         BN_bin2bn(dmp1, sizeof(dmp1) - 1, NULL),
+                                         BN_bin2bn(dmq1, sizeof(dmq1) - 1, NULL),
+                                         BN_bin2bn(iqmp, sizeof(iqmp) - 1,
+                                                   NULL)), 1))
+        return 0;
+
+    pris = OPENSSL_zalloc(sizeof(BIGNUM *) * NUM_EXTRA_PRIMES);
+    exps = OPENSSL_zalloc(sizeof(BIGNUM *) * NUM_EXTRA_PRIMES);
+    coeffs = OPENSSL_zalloc(sizeof(BIGNUM *) * NUM_EXTRA_PRIMES);
+    if (!TEST_ptr(pris) || !TEST_ptr(exps) || !TEST_ptr(coeffs))
+        goto err;
+
+    for (i = 0; i < NUM_EXTRA_PRIMES; i++) {
+        pris[i] = BN_bin2bn((unsigned char *)primes[i], primes_len[i], NULL);
+        exps[i] = BN_bin2bn((unsigned char *)exponents[i], exps_len[i], NULL);
+        coeffs[i] = BN_bin2bn((unsigned char *)coefficients[i],
+                              coeffs_len[i], NULL);
+        if (!TEST_ptr(pris[i]) || !TEST_ptr(exps[i]) || !TEST_ptr(coeffs[i]))
+            goto err;
+    }
+
+    if (!TEST_true(RSA_set0_multi_prime_params(key, pris, exps,
+                                               coeffs, NUM_EXTRA_PRIMES)))
+        goto err;
+
+ ret:
+    OPENSSL_free(pris);
+    OPENSSL_free(exps);
+    OPENSSL_free(coeffs);
+    OPENSSL_free(n);
+    OPENSSL_free(d);
+    return rv;
+ err:
+    for (i = 0; i < 5; i++) {
+        if (pris != NULL)
+            BN_free(pris[i]);
+        if (exps != NULL)
+            BN_free(exps[i]);
+        if (coeffs != NULL)
+            BN_free(coeffs[i]);
+    }
+    rv = 0;
+    goto ret;
+}
+
+static int test_rsa_mp(void)
+{
+    int ret = 0;
+    RSA *key;
+    unsigned char ptext[512];
+    unsigned char ctext[512];
+    static unsigned char ptext_ex[] = "\x54\x85\x9b\x34\x2c\x49\xea\x2a";
+    int plen;
+    int clen = 0;
+    int num;
+
+    plen = sizeof(ptext_ex) - 1;
+    key = RSA_new();
+    if (!TEST_ptr(key))
+        goto err;
+    clen = key4096p7(key);
+    if (!TEST_int_eq(clen, 512))
+        goto err;
+
+    if (!TEST_true(RSA_check_key_ex(key, NULL)))
+        goto err;
+
+    num = RSA_public_encrypt(plen, ptext_ex, ctext, key,
+                             RSA_PKCS1_PADDING);
+    if (!TEST_int_eq(num, clen))
+        goto err;
+
+    num = RSA_private_decrypt(num, ctext, ptext, key, RSA_PKCS1_PADDING);
+    if (!TEST_mem_eq(ptext, num, ptext_ex, plen))
+        goto err;
+
+    ret = 1;
+err:
+    RSA_free(key);
+    return ret;
+}
+#endif
+
+int setup_tests(void)
+{
+#ifndef OPENSSL_NO_RSA
+    ADD_TEST(test_rsa_mp);
+#endif
+    return 1;
+}
diff --git a/util/libcrypto.num b/util/libcrypto.num
index 8d9db312a6..10ffa2c3d5 100644
--- a/util/libcrypto.num
+++ b/util/libcrypto.num
@@ -4438,3 +4438,11 @@ EVP_PKEY_asn1_set_param_check           4382	1_1_1	EXIST::FUNCTION:
 DH_check_ex                             4383	1_1_1	EXIST::FUNCTION:DH
 DH_check_pub_key_ex                     4384	1_1_1	EXIST::FUNCTION:DH
 DH_check_params_ex                      4385	1_1_1	EXIST::FUNCTION:DH
+RSA_generate_multi_prime_key            4386	1_1_1	EXIST::FUNCTION:RSA
+RSA_get_multi_prime_extra_count         4387	1_1_1	EXIST::FUNCTION:RSA
+RSA_get0_multi_prime_factors            4388	1_1_1	EXIST::FUNCTION:RSA
+RSA_get0_multi_prime_crt_params         4389	1_1_1	EXIST::FUNCTION:RSA
+RSA_set0_multi_prime_params             4390	1_1_1	EXIST::FUNCTION:RSA
+RSA_get_version                         4391	1_1_1	EXIST::FUNCTION:RSA
+RSA_meth_get_multi_prime_keygen         4392	1_1_1	EXIST::FUNCTION:RSA
+RSA_meth_set_multi_prime_keygen         4393	1_1_1	EXIST::FUNCTION:RSA