X-Git-Url: https://git.openssl.org/gitweb/?p=openssl.git;a=blobdiff_plain;f=crypto%2Frsa%2Frsa_ossl.c;h=465134257fcc7d5ecd8e9c5d0690a03bb40e4c0c;hp=1aeaae929f013d4a406a45c13190b7865da81494;hb=9c6d536f532a737216f2ae0e7d168c99ed989a0d;hpb=2039c421b0e5b75ffcf6a88e39cc09089b4303dc

diff --git a/crypto/rsa/rsa_ossl.c b/crypto/rsa/rsa_ossl.c
index 1aeaae929f..465134257f 100644
--- a/crypto/rsa/rsa_ossl.c
+++ b/crypto/rsa/rsa_ossl.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2018 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
@@ -9,10 +9,8 @@
 
 #include "internal/cryptlib.h"
 #include "internal/bn_int.h"
-#include <openssl/rand.h>
 #include "rsa_locl.h"
-
-#ifndef RSA_NULL
+#include "internal/constant_time_locl.h"
 
 static int rsa_ossl_public_encrypt(int flen, const unsigned char *from,
                                   unsigned char *to, RSA *rsa, int padding);
@@ -27,7 +25,7 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *i, RSA *rsa,
 static int rsa_ossl_init(RSA *rsa);
 static int rsa_ossl_finish(RSA *rsa);
 static RSA_METHOD rsa_pkcs1_ossl_meth = {
-    "OpenSSL PKCS#1 RSA (from Eric Young)",
+    "OpenSSL PKCS#1 RSA",
     rsa_ossl_public_encrypt,
     rsa_ossl_public_decrypt,     /* signature verification */
     rsa_ossl_private_encrypt,    /* signing */
@@ -41,19 +39,37 @@ 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;
+
+void RSA_set_default_method(const RSA_METHOD *meth)
+{
+    default_RSA_meth = meth;
+}
+
+const RSA_METHOD *RSA_get_default_method(void)
+{
+    return default_RSA_meth;
+}
+
 const RSA_METHOD *RSA_PKCS1_OpenSSL(void)
 {
     return &rsa_pkcs1_ossl_meth;
 }
 
+const RSA_METHOD *RSA_null_method(void)
+{
+    return NULL;
+}
+
 static int rsa_ossl_public_encrypt(int flen, const unsigned char *from,
                                   unsigned char *to, RSA *rsa, int padding)
 {
     BIGNUM *f, *ret;
-    int i, j, k, num = 0, r = -1;
+    int i, num = 0, r = -1;
     unsigned char *buf = NULL;
     BN_CTX *ctx = NULL;
 
@@ -82,7 +98,7 @@ static int rsa_ossl_public_encrypt(int flen, const unsigned char *from,
     ret = BN_CTX_get(ctx);
     num = BN_num_bytes(rsa->n);
     buf = OPENSSL_malloc(num);
-    if (f == NULL || ret == NULL || buf == NULL) {
+    if (ret == NULL || buf == NULL) {
         RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, ERR_R_MALLOC_FAILURE);
         goto err;
     }
@@ -118,8 +134,8 @@ static int rsa_ossl_public_encrypt(int flen, const unsigned char *from,
     }
 
     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
-        if (!BN_MONT_CTX_set_locked
-            (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx))
+        if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
+                                    rsa->n, ctx))
             goto err;
 
     if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx,
@@ -127,21 +143,16 @@ static int rsa_ossl_public_encrypt(int flen, const unsigned char *from,
         goto err;
 
     /*
-     * put in leading 0 bytes if the number is less than the length of the
-     * modulus
+     * BN_bn2binpad puts in leading 0 bytes if the number is less than
+     * the length of the modulus.
      */
-    j = BN_num_bytes(ret);
-    i = BN_bn2bin(ret, &(to[num - j]));
-    for (k = 0; k < (num - i); k++)
-        to[k] = 0;
-
-    r = num;
+    r = BN_bn2binpad(ret, to, num);
  err:
     if (ctx != NULL)
         BN_CTX_end(ctx);
     BN_CTX_free(ctx);
     OPENSSL_clear_free(buf, num);
-    return (r);
+    return r;
 }
 
 static BN_BLINDING *rsa_get_blinding(RSA *rsa, int *local, BN_CTX *ctx)
@@ -186,12 +197,12 @@ static BN_BLINDING *rsa_get_blinding(RSA *rsa, int *local, BN_CTX *ctx)
 static int rsa_blinding_convert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind,
                                 BN_CTX *ctx)
 {
-    if (unblind == NULL)
+    if (unblind == NULL) {
         /*
          * Local blinding: store the unblinding factor in BN_BLINDING.
          */
         return BN_BLINDING_convert_ex(f, NULL, b, ctx);
-    else {
+    } else {
         /*
          * Shared blinding: store the unblinding factor outside BN_BLINDING.
          */
@@ -224,7 +235,7 @@ static int rsa_ossl_private_encrypt(int flen, const unsigned char *from,
                                    unsigned char *to, RSA *rsa, int padding)
 {
     BIGNUM *f, *ret, *res;
-    int i, j, k, num = 0, r = -1;
+    int i, num = 0, r = -1;
     unsigned char *buf = NULL;
     BN_CTX *ctx = NULL;
     int local_blinding = 0;
@@ -243,7 +254,7 @@ static int rsa_ossl_private_encrypt(int flen, const unsigned char *from,
     ret = BN_CTX_get(ctx);
     num = BN_num_bytes(rsa->n);
     buf = OPENSSL_malloc(num);
-    if (f == NULL || ret == NULL || buf == NULL) {
+    if (ret == NULL || buf == NULL) {
         RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE);
         goto err;
     }
@@ -276,6 +287,11 @@ static int rsa_ossl_private_encrypt(int flen, const unsigned char *from,
         goto err;
     }
 
+    if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
+        if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
+                                    rsa->n, ctx))
+            goto err;
+
     if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
         blinding = rsa_get_blinding(rsa, &local_blinding, ctx);
         if (blinding == NULL) {
@@ -294,39 +310,27 @@ 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))) {
         if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx))
             goto err;
     } else {
-        BIGNUM *d = NULL, *local_d = NULL;
-
-        if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
-            local_d = d = BN_new();
-            if (d == NULL) {
-                RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE);
-                goto err;
-            }
-            BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
-        } else {
-            d = rsa->d;
+        BIGNUM *d = BN_new();
+        if (d == NULL) {
+            RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE);
+            goto err;
         }
-
-        if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
-            if (!BN_MONT_CTX_set_locked
-                (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx)) {
-                BN_free(local_d);
-                goto err;
-            }
+        BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 
         if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx,
                                    rsa->_method_mod_n)) {
-            BN_free(local_d);
+            BN_free(d);
             goto err;
         }
-        /* We MUST free local_d before any further use of rsa->d */
-        BN_free(local_d);
+        /* We MUST free d before any further use of rsa->d */
+        BN_free(d);
     }
 
     if (blinding)
@@ -334,30 +338,27 @@ static int rsa_ossl_private_encrypt(int flen, const unsigned char *from,
             goto err;
 
     if (padding == RSA_X931_PADDING) {
-        BN_sub(f, rsa->n, ret);
+        if (!BN_sub(f, rsa->n, ret))
+            goto err;
         if (BN_cmp(ret, f) > 0)
             res = f;
         else
             res = ret;
-    } else
+    } else {
         res = ret;
+    }
 
     /*
-     * put in leading 0 bytes if the number is less than the length of the
-     * modulus
+     * BN_bn2binpad puts in leading 0 bytes if the number is less than
+     * the length of the modulus.
      */
-    j = BN_num_bytes(res);
-    i = BN_bn2bin(res, &(to[num - j]));
-    for (k = 0; k < (num - i); k++)
-        to[k] = 0;
-
-    r = num;
+    r = BN_bn2binpad(res, to, num);
  err:
     if (ctx != NULL)
         BN_CTX_end(ctx);
     BN_CTX_free(ctx);
     OPENSSL_clear_free(buf, num);
-    return (r);
+    return r;
 }
 
 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
@@ -365,7 +366,6 @@ static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
 {
     BIGNUM *f, *ret;
     int j, num = 0, r = -1;
-    unsigned char *p;
     unsigned char *buf = NULL;
     BN_CTX *ctx = NULL;
     int local_blinding = 0;
@@ -384,7 +384,7 @@ static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
     ret = BN_CTX_get(ctx);
     num = BN_num_bytes(rsa->n);
     buf = OPENSSL_malloc(num);
-    if (f == NULL || ret == NULL || buf == NULL) {
+    if (ret == NULL || buf == NULL) {
         RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE);
         goto err;
     }
@@ -428,46 +428,40 @@ 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))) {
         if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx))
             goto err;
     } else {
-        BIGNUM *d = NULL, *local_d = NULL;
-
-        if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
-            local_d = d = BN_new();
-            if (d == NULL) {
-                RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE);
-                goto err;
-            }
-            BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
-        } else {
-            d = rsa->d;
+        BIGNUM *d = BN_new();
+        if (d == NULL) {
+            RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE);
+            goto err;
         }
+        BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 
         if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
-            if (!BN_MONT_CTX_set_locked
-                (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx)) {
-                BN_free(local_d);
+            if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
+                                        rsa->n, ctx)) {
+                BN_free(d);
                 goto err;
             }
         if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx,
                                    rsa->_method_mod_n)) {
-            BN_free(local_d);
+            BN_free(d);
             goto err;
         }
-        /* We MUST free local_d before any further use of rsa->d */
-        BN_free(local_d);
+        /* We MUST free d before any further use of rsa->d */
+        BN_free(d);
     }
 
     if (blinding)
         if (!rsa_blinding_invert(blinding, ret, unblind, ctx))
             goto err;
 
-    p = buf;
-    j = BN_bn2bin(ret, p);      /* j is only used with no-padding mode */
+    j = BN_bn2binpad(ret, buf, num);
 
     switch (padding) {
     case RSA_PKCS1_PADDING:
@@ -480,21 +474,21 @@ static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
         r = RSA_padding_check_SSLv23(to, num, buf, j, num);
         break;
     case RSA_NO_PADDING:
-        r = RSA_padding_check_none(to, num, buf, j, num);
+        memcpy(to, buf, (r = j));
         break;
     default:
         RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
         goto err;
     }
-    if (r < 0)
-        RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_PADDING_CHECK_FAILED);
+    RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_PADDING_CHECK_FAILED);
+    err_clear_last_constant_time(r >= 0);
 
  err:
     if (ctx != NULL)
         BN_CTX_end(ctx);
     BN_CTX_free(ctx);
     OPENSSL_clear_free(buf, num);
-    return (r);
+    return r;
 }
 
 /* signature verification */
@@ -503,7 +497,6 @@ static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
 {
     BIGNUM *f, *ret;
     int i, num = 0, r = -1;
-    unsigned char *p;
     unsigned char *buf = NULL;
     BN_CTX *ctx = NULL;
 
@@ -532,7 +525,7 @@ static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
     ret = BN_CTX_get(ctx);
     num = BN_num_bytes(rsa->n);
     buf = OPENSSL_malloc(num);
-    if (f == NULL || ret == NULL || buf == NULL) {
+    if (ret == NULL || buf == NULL) {
         RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, ERR_R_MALLOC_FAILURE);
         goto err;
     }
@@ -556,8 +549,8 @@ static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
     }
 
     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
-        if (!BN_MONT_CTX_set_locked
-            (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx))
+        if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
+                                    rsa->n, ctx))
             goto err;
 
     if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx,
@@ -568,8 +561,7 @@ static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
         if (!BN_sub(ret, rsa->n, ret))
             goto err;
 
-    p = buf;
-    i = BN_bn2bin(ret, p);
+    i = BN_bn2binpad(ret, buf, num);
 
     switch (padding) {
     case RSA_PKCS1_PADDING:
@@ -579,7 +571,7 @@ static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
         r = RSA_padding_check_X931(to, num, buf, i, num);
         break;
     case RSA_NO_PADDING:
-        r = RSA_padding_check_none(to, num, buf, i, num);
+        memcpy(to, buf, (r = i));
         break;
     default:
         RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
@@ -593,136 +585,216 @@ static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
         BN_CTX_end(ctx);
     BN_CTX_free(ctx);
     OPENSSL_clear_free(buf, num);
-    return (r);
+    return r;
 }
 
 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 - 2];
+    int ret = 0, i, ex_primes = 0, smooth = 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;
 
-    {
-        BIGNUM *local_p = NULL, *local_q = NULL;
-        BIGNUM *p = NULL, *q = NULL;
+    if (rsa->version == RSA_ASN1_VERSION_MULTI
+        && ((ex_primes = sk_RSA_PRIME_INFO_num(rsa->prime_infos)) <= 0
+             || ex_primes > RSA_MAX_PRIME_NUM - 2))
+        goto err;
+
+    if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) {
+        BIGNUM *factor = BN_new();
+
+        if (factor == NULL)
+            goto err;
 
         /*
          * Make sure BN_mod_inverse in Montgomery initialization uses the
-         * BN_FLG_CONSTTIME flag (unless RSA_FLAG_NO_CONSTTIME is set)
+         * BN_FLG_CONSTTIME flag
          */
-        if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
-            local_p = p = BN_new();
-            if (p == NULL)
-                goto err;
-            BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
-
-            local_q = q = BN_new();
-            if (q == NULL) {
-                BN_free(local_p);
-                goto err;
-            }
-            BN_with_flags(q, rsa->q, BN_FLG_CONSTTIME);
-        } else {
-            p = rsa->p;
-            q = rsa->q;
+        if (!(BN_with_flags(factor, rsa->p, BN_FLG_CONSTTIME),
+              BN_MONT_CTX_set_locked(&rsa->_method_mod_p, rsa->lock,
+                                     factor, ctx))
+            || !(BN_with_flags(factor, rsa->q, BN_FLG_CONSTTIME),
+                 BN_MONT_CTX_set_locked(&rsa->_method_mod_q, rsa->lock,
+                                        factor, ctx))) {
+            BN_free(factor);
+            goto err;
         }
-
-        if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) {
-            if (!BN_MONT_CTX_set_locked
-                (&rsa->_method_mod_p, rsa->lock, p, ctx)
-                || !BN_MONT_CTX_set_locked(&rsa->_method_mod_q,
-                                           rsa->lock, q, ctx)) {
-                BN_free(local_p);
-                BN_free(local_q);
+        for (i = 0; i < ex_primes; i++) {
+            pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
+            BN_with_flags(factor, pinfo->r, BN_FLG_CONSTTIME);
+            if (!BN_MONT_CTX_set_locked(&pinfo->m, rsa->lock, factor, ctx)) {
+                BN_free(factor);
                 goto err;
             }
         }
         /*
-         * We MUST free local_p and local_q before any further use of rsa->p and
-         * rsa->q
+         * We MUST free |factor| before any further use of the prime factors
          */
-        BN_free(local_p);
-        BN_free(local_q);
+        BN_free(factor);
+
+        smooth = (ex_primes == 0)
+                 && (rsa->meth->bn_mod_exp == BN_mod_exp_mont)
+                 && (BN_num_bits(rsa->q) == BN_num_bits(rsa->p));
     }
 
     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
-        if (!BN_MONT_CTX_set_locked
-            (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx))
+        if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
+                                    rsa->n, ctx))
             goto err;
 
+    if (smooth) {
+        /*
+         * Conversion from Montgomery domain, a.k.a. Montgomery reduction,
+         * accepts values in [0-m*2^w) range. w is m's bit width rounded up
+         * to limb width. So that at the very least if |I| is fully reduced,
+         * i.e. less than p*q, we can count on from-to round to perform
+         * below modulo operations on |I|. Unlike BN_mod it's constant time.
+         */
+        if (/* m1 = I moq q */
+            !bn_from_mont_fixed_top(m1, I, rsa->_method_mod_q, ctx)
+            || !bn_to_mont_fixed_top(m1, m1, rsa->_method_mod_q, ctx)
+            /* m1 = m1^dmq1 mod q */
+            || !BN_mod_exp_mont_consttime(m1, m1, rsa->dmq1, rsa->q, ctx,
+                                          rsa->_method_mod_q)
+            /* r1 = I mod p */
+            || !bn_from_mont_fixed_top(r1, I, rsa->_method_mod_p, ctx)
+            || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx)
+            /* r1 = r1^dmp1 mod p */
+            || !BN_mod_exp_mont_consttime(r1, r1, rsa->dmp1, rsa->p, ctx,
+                                          rsa->_method_mod_p)
+            /* r1 = (r1 - m1) mod p */
+            /*
+             * bn_mod_sub_fixed_top is not regular modular subtraction,
+             * it can tolerate subtrahend to be larger than modulus, but
+             * not bit-wise wider. This makes up for uncommon q>p case,
+             * when |m1| can be larger than |rsa->p|.
+             */
+            || !bn_mod_sub_fixed_top(r1, r1, m1, rsa->p)
+
+            /* r1 = r1 * iqmp mod p */
+            || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx)
+            || !bn_mul_mont_fixed_top(r1, r1, rsa->iqmp, rsa->_method_mod_p,
+                                      ctx)
+            /* r0 = r1 * q + m1 */
+            || !bn_mul_fixed_top(r0, r1, rsa->q, ctx)
+            || !bn_mod_add_fixed_top(r0, r0, m1, rsa->n))
+            goto err;
+
+        goto tail;
+    }
+
     /* compute I mod q */
     {
-        BIGNUM *local_c = NULL;
-        const BIGNUM *c;
-        if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
-            local_c = BN_new();
-            if (local_c == NULL)
-                goto err;
-            BN_with_flags(local_c, I, BN_FLG_CONSTTIME);
-            c = local_c;
-        } else {
-            c = I;
-        }
+        BIGNUM *c = BN_new();
+        if (c == NULL)
+            goto err;
+        BN_with_flags(c, I, BN_FLG_CONSTTIME);
+
         if (!BN_mod(r1, c, rsa->q, ctx)) {
-            BN_free(local_c);
+            BN_free(c);
             goto err;
         }
 
         {
-            BIGNUM *local_dmq1 = NULL, *dmq1;
-            /* compute r1^dmq1 mod q */
-            if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
-                dmq1 = local_dmq1 = BN_new();
-                if (local_dmq1 == NULL) {
-                    BN_free(local_c);
-                    goto err;
-                }
-                BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME);
-            } else {
-                dmq1 = rsa->dmq1;
+            BIGNUM *dmq1 = BN_new();
+            if (dmq1 == NULL) {
+                BN_free(c);
+                goto err;
             }
+            BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME);
+
+            /* compute r1^dmq1 mod q */
             if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx,
-                rsa->_method_mod_q)) {
-                BN_free(local_c);
-                BN_free(local_dmq1);
+                                       rsa->_method_mod_q)) {
+                BN_free(c);
+                BN_free(dmq1);
                 goto err;
             }
-            /* We MUST free local_dmq1 before any further use of rsa->dmq1 */
-            BN_free(local_dmq1);
+            /* We MUST free dmq1 before any further use of rsa->dmq1 */
+            BN_free(dmq1);
         }
 
         /* compute I mod p */
         if (!BN_mod(r1, c, rsa->p, ctx)) {
-            BN_free(local_c);
+            BN_free(c);
             goto err;
         }
-        /* We MUST free local_c before any further use of I */
-        BN_free(local_c);
+        /* We MUST free c before any further use of I */
+        BN_free(c);
     }
 
     {
-        BIGNUM *local_dmp1 = NULL, *dmp1;
+        BIGNUM *dmp1 = BN_new();
+        if (dmp1 == NULL)
+            goto err;
+        BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME);
+
         /* compute r1^dmp1 mod p */
-        if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
-            dmp1 = local_dmp1 = BN_new();
-            if (local_dmp1 == NULL)
-                goto err;
-            BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME);
-        } else {
-            dmp1 = rsa->dmp1;
-        }
         if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx,
                                    rsa->_method_mod_p)) {
-            BN_free(local_dmp1);
+            BN_free(dmp1);
             goto err;
         }
-        /* We MUST free local_dmp1 before any further use of rsa->dmp1 */
-        BN_free(local_dmp1);
+        /* We MUST free dmp1 before any further use of rsa->dmp1 */
+        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))
@@ -739,22 +811,17 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
         goto err;
 
     {
-        BIGNUM *local_r1 = NULL, *pr1;
-        /* Turn BN_FLG_CONSTTIME flag on before division operation */
-        if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
-            pr1 = local_r1 = BN_new();
-            if (local_r1 == NULL)
-                goto err;
-            BN_with_flags(pr1, r1, BN_FLG_CONSTTIME);
-        } else {
-            pr1 = r1;
-        }
+        BIGNUM *pr1 = BN_new();
+        if (pr1 == NULL)
+            goto err;
+        BN_with_flags(pr1, r1, BN_FLG_CONSTTIME);
+
         if (!BN_mod(r0, pr1, rsa->p, ctx)) {
-            BN_free(local_r1);
+            BN_free(pr1);
             goto err;
         }
-        /* We MUST free local_r1 before any further use of r1 */
-        BN_free(local_r1);
+        /* We MUST free pr1 before any further use of r1 */
+        BN_free(pr1);
     }
 
     /*
@@ -772,10 +839,61 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
     if (!BN_add(r0, r1, m1))
         goto err;
 
-    if (rsa->e && rsa->n) {
-        if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx,
-                                   rsa->_method_mod_n))
+    /* 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);
+    }
+
+ tail:
+    if (rsa->e && rsa->n) {
+        if (rsa->meth->bn_mod_exp == BN_mod_exp_mont) {
+            if (!BN_mod_exp_mont(vrfy, r0, rsa->e, rsa->n, ctx,
+                                 rsa->_method_mod_n))
+                goto err;
+        } else {
+            bn_correct_top(r0);
+            if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx,
+                                       rsa->_method_mod_n))
+                goto err;
+        }
         /*
          * If 'I' was greater than (or equal to) rsa->n, the operation will
          * be equivalent to using 'I mod n'. However, the result of the
@@ -784,6 +902,11 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
          */
         if (!BN_sub(vrfy, vrfy, I))
             goto err;
+        if (BN_is_zero(vrfy)) {
+            bn_correct_top(r0);
+            ret = 1;
+            goto err;   /* not actually error */
+        }
         if (!BN_mod(vrfy, vrfy, rsa->n, ctx))
             goto err;
         if (BN_is_negative(vrfy))
@@ -796,44 +919,52 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
              * return that instead.
              */
 
-            BIGNUM *local_d = NULL;
-            BIGNUM *d = NULL;
+            BIGNUM *d = BN_new();
+            if (d == NULL)
+                goto err;
+            BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 
-            if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
-                local_d = d = BN_new();
-                if (d == NULL)
-                    goto err;
-                BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
-            } else {
-                d = rsa->d;
-            }
             if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx,
                                        rsa->_method_mod_n)) {
-                BN_free(local_d);
+                BN_free(d);
                 goto err;
             }
-            /* We MUST free local_d before any further use of rsa->d */
-            BN_free(local_d);
+            /* We MUST free d before any further use of rsa->d */
+            BN_free(d);
         }
     }
+    /*
+     * It's unfortunate that we have to bn_correct_top(r0). What hopefully
+     * saves the day is that correction is highly unlike, and private key
+     * operations are customarily performed on blinded message. Which means
+     * that attacker won't observe correlation with chosen plaintext.
+     * Secondly, remaining code would still handle it in same computational
+     * time and even conceal memory access pattern around corrected top.
+     */
+    bn_correct_top(r0);
     ret = 1;
  err:
     BN_CTX_end(ctx);
-    return (ret);
+    return ret;
 }
 
 static int rsa_ossl_init(RSA *rsa)
 {
     rsa->flags |= RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE;
-    return (1);
+    return 1;
 }
 
 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);
-    return (1);
+    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;
 }
-
-#endif