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)

12 files changed, 813 insertions, 66 deletions

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.