Support multi-prime RSA (RFC 8017)

[openssl.git] / crypto / rsa / rsa_ossl.c

diff --git a/crypto/rsa/rsa_ossl.c b/crypto/rsa/rsa_ossl.c
index 40c84dd3c20d0bcc5e95279ed1e6e7904a9eae58..ced11ad883c98e17b53e073e4da63c5010d5f0ea 100644 (file)
--- 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;
 }