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_gene