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)

1 files changed, 95 insertions, 0 deletions

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