bn/bn_{mont|exp}.c: switch to zero-padded intermediate vectors.

Note that exported functions maintain original behaviour, so that
external callers won't observe difference. While internally we can
now perform Montogomery multiplication on fixed-length vectors, fixed
at modulus size. The new functions, bn_to_mont_fixed_top and
bn_mul_mont_fixed_top, are declared in bn_int.h, because one can use
them even outside bn, e.g. in RSA, DSA, ECDSA...

Reviewed-by: Rich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/6810)

(cherry picked from commit 71883868ea5b33416ae8283bcc38dd2d97e5006b)

Resolved conflicts:
	crypto/bn/bn_exp.c
	crypto/bn/bn_lcl.h
	crypto/bn/bn_mont.c
	crypto/include/internal/bn_int.h

5 files changed, 74 insertions, 34 deletions

diff --git a/crypto/Makefile b/crypto/Makefile
index 7869996a9c..ad1b9f018b 100644
--- a/crypto/Makefile
+++ b/crypto/Makefile
@@ -45,7 +45,7 @@ SRC= $(LIBSRC)
 EXHEADER= crypto.h opensslv.h opensslconf.h ebcdic.h symhacks.h \
 	ossl_typ.h
 HEADER=	cryptlib.h buildinf.h md32_common.h o_time.h o_str.h o_dir.h \
-	constant_time_locl.h $(EXHEADER)
+	constant_time_locl.h bn_int.h $(EXHEADER)
 
 ALL=    $(GENERAL) $(SRC) $(HEADER)
 
diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c
index 2eb393d5b2..36b7ba69ad 100644
--- a/crypto/bn/bn_exp.c
+++ b/crypto/bn/bn_exp.c
@@ -473,17 +473,17 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
         ret = 1;
         goto err;
     }
-    if (!BN_to_montgomery(val[0], aa, mont, ctx))
+    if (!bn_to_mont_fixed_top(val[0], aa, mont, ctx))
         goto err;               /* 1 */
 
     window = BN_window_bits_for_exponent_size(bits);
     if (window > 1) {
-        if (!BN_mod_mul_montgomery(d, val[0], val[0], mont, ctx))
+        if (!bn_mul_mont_fixed_top(d, val[0], val[0], mont, ctx))
             goto err;           /* 2 */
         j = 1 << (window - 1);
         for (i = 1; i < j; i++) {
             if (((val[i] = BN_CTX_get(ctx)) == NULL) ||
-                !BN_mod_mul_montgomery(val[i], val[i - 1], d, mont, ctx))
+                !bn_mul_mont_fixed_top(val[i], val[i - 1], d, mont, ctx))
                 goto err;
         }
     }
@@ -505,19 +505,15 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
         for (i = 1; i < j; i++)
             r->d[i] = (~m->d[i]) & BN_MASK2;
         r->top = j;
-        /*
-         * Upper words will be zero if the corresponding words of 'm' were
-         * 0xfff[...], so decrement r->top accordingly.
-         */
-        bn_correct_top(r);
+        r->flags |= BN_FLG_FIXED_TOP;
     } else
 #endif
-    if (!BN_to_montgomery(r, BN_value_one(), mont, ctx))
+    if (!bn_to_mont_fixed_top(r, BN_value_one(), mont, ctx))
         goto err;
     for (;;) {
         if (BN_is_bit_set(p, wstart) == 0) {
             if (!start) {
-                if (!BN_mod_mul_montgomery(r, r, r, mont, ctx))
+                if (!bn_mul_mont_fixed_top(r, r, r, mont, ctx))
                     goto err;
             }
             if (wstart == 0)
@@ -548,12 +544,12 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
         /* add the 'bytes above' */
         if (!start)
             for (i = 0; i < j; i++) {
-                if (!BN_mod_mul_montgomery(r, r, r, mont, ctx))
+                if (!bn_mul_mont_fixed_top(r, r, r, mont, ctx))
                     goto err;
             }
 
         /* wvalue will be an odd number < 2^window */
-        if (!BN_mod_mul_montgomery(r, r, val[wvalue >> 1], mont, ctx))
+        if (!bn_mul_mont_fixed_top(r, r, val[wvalue >> 1], mont, ctx))
             goto err;
 
         /* move the 'window' down further */
@@ -563,6 +559,11 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
         if (wstart < 0)
             break;
     }
+    /*
+     * Done with zero-padded intermediate BIGNUMs. Final BN_from_montgomery
+     * removes padding [if any] and makes return value suitable for public
+     * API consumer.
+     */
 #if defined(SPARC_T4_MONT)
     if (OPENSSL_sparcv9cap_P[0] & (SPARCV9_VIS3 | SPARCV9_PREFER_FPU)) {
         j = mont->N.top;        /* borrow j */
@@ -681,7 +682,7 @@ static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top,
     }
 
     b->top = top;
-    bn_correct_top(b);
+    b->flags |= BN_FLG_FIXED_TOP;
     return 1;
 }
 
@@ -852,16 +853,16 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
         tmp.top = top;
     } else
 #endif
-    if (!BN_to_montgomery(&tmp, BN_value_one(), mont, ctx))
+    if (!bn_to_mont_fixed_top(&tmp, BN_value_one(), mont, ctx))
         goto err;
 
     /* prepare a^1 in Montgomery domain */
     if (a->neg || BN_ucmp(a, m) >= 0) {
         if (!BN_mod(&am, a, m, ctx))
             goto err;
-        if (!BN_to_montgomery(&am, &am, mont, ctx))
+        if (!bn_to_mont_fixed_top(&am, &am, mont, ctx))
             goto err;
-    } else if (!BN_to_montgomery(&am, a, mont, ctx))
+    } else if (!bn_to_mont_fixed_top(&am, a, mont, ctx))
         goto err;
 
 #if defined(SPARC_T4_MONT)
@@ -1128,14 +1129,14 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
          * performance advantage of sqr over mul).
          */
         if (window > 1) {
-            if (!BN_mod_mul_montgomery(&tmp, &am, &am, mont, ctx))
+            if (!bn_mul_mont_fixed_top(&tmp, &am, &am, mont, ctx))
                 goto err;
             if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, 2,
                                               window))
                 goto err;
             for (i = 3; i < numPowers; i++) {
                 /* Calculate a^i = a^(i-1) * a */
-                if (!BN_mod_mul_montgomery(&tmp, &am, &tmp, mont, ctx))
+                if (!bn_mul_mont_fixed_top(&tmp, &am, &tmp, mont, ctx))
                     goto err;
                 if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, i,
                                                   window))
@@ -1159,7 +1160,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
 
             /* Scan the window, squaring the result as we go */
             for (i = 0; i < window; i++, bits--) {
-                if (!BN_mod_mul_montgomery(&tmp, &tmp, &tmp, mont, ctx))
+                if (!bn_mul_mont_fixed_top(&tmp, &tmp, &tmp, mont, ctx))
                     goto err;
                 wvalue = (wvalue << 1) + BN_is_bit_set(p, bits);
             }
@@ -1172,12 +1173,16 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
                 goto err;
 
             /* Multiply the result into the intermediate result */
-            if (!BN_mod_mul_montgomery(&tmp, &tmp, &am, mont, ctx))
+            if (!bn_mul_mont_fixed_top(&tmp, &tmp, &am, mont, ctx))
                 goto err;
         }
     }
 
-    /* Convert the final result from montgomery to standard format */
+    /*
+     * Done with zero-padded intermediate BIGNUMs. Final BN_from_montgomery
+     * removes padding [if any] and makes return value suitable for public
+     * API consumer.
+     */
 #if defined(SPARC_T4_MONT)
     if (OPENSSL_sparcv9cap_P[0] & (SPARCV9_VIS3 | SPARCV9_PREFER_FPU)) {
         am.d[0] = 1;            /* borrow am */
diff --git a/crypto/bn/bn_lcl.h b/crypto/bn/bn_lcl.h
index 00f4f09945..1aa7fe83db 100644
--- a/crypto/bn/bn_lcl.h
+++ b/crypto/bn/bn_lcl.h
@@ -113,6 +113,7 @@
 # define HEADER_BN_LCL_H
 
 # include <openssl/bn.h>
+# include "bn_int.h"
 
 #ifdef  __cplusplus
 extern "C" {
diff --git a/crypto/bn/bn_mont.c b/crypto/bn/bn_mont.c
index cc8f927ee2..d41434a143 100644
--- a/crypto/bn/bn_mont.c
+++ b/crypto/bn/bn_mont.c
@@ -123,12 +123,23 @@
 #define MONT_WORD               /* use the faster word-based algorithm */
 
 #ifdef MONT_WORD
-static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont);
+static int bn_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont);
 #endif
 
 int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
                           BN_MONT_CTX *mont, BN_CTX *ctx)
 {
+    int ret = bn_mul_mont_fixed_top(r, a, b, mont, ctx);
+
+    bn_correct_top(r);
+    bn_check_top(r);
+
+    return ret;
+}
+
+int bn_mul_mont_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
+                          BN_MONT_CTX *mont, BN_CTX *ctx)
+{
     BIGNUM *tmp;
     int ret = 0;
 #if defined(OPENSSL_BN_ASM_MONT) && defined(MONT_WORD)
@@ -140,8 +151,8 @@ int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
         if (bn_mul_mont(r->d, a->d, b->d, mont->N.d, mont->n0, num)) {
             r->neg = a->neg ^ b->neg;
             r->top = num;
-            bn_correct_top(r);
-            return (1);
+            r->flags |= BN_FLG_FIXED_TOP;
+            return 1;
         }
     }
 #endif
@@ -161,13 +172,12 @@ int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
     }
     /* reduce from aRR to aR */
 #ifdef MONT_WORD
-    if (!BN_from_montgomery_word(r, tmp, mont))
+    if (!bn_from_montgomery_word(r, tmp, mont))
         goto err;
 #else
     if (!BN_from_montgomery(r, tmp, mont, ctx))
         goto err;
 #endif
-    bn_check_top(r);
     ret = 1;
  err:
     BN_CTX_end(ctx);
@@ -175,7 +185,7 @@ int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
 }
 
 #ifdef MONT_WORD
-static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont)
+static int bn_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont)
 {
     BIGNUM *n;
     BN_ULONG *ap, *np, *rp, n0, v, carry;
@@ -205,6 +215,7 @@ static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont)
 # endif
 
     r->top = max;
+    r->flags |= BN_FLG_FIXED_TOP;
     n0 = mont->n0[0];
 
     /*
@@ -223,6 +234,7 @@ static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont)
     if (bn_wexpand(ret, nl) == NULL)
         return (0);
     ret->top = nl;
+    ret->flags |= BN_FLG_FIXED_TOP;
     ret->neg = r->neg;
 
     rp = ret->d;
@@ -243,9 +255,6 @@ static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont)
         rp[i] = (carry & ap[i]) | (~carry & rp[i]);
         ap[i] = 0;
     }
-    bn_correct_top(r);
-    bn_correct_top(ret);
-    bn_check_top(ret);
 
     return (1);
 }
@@ -259,8 +268,11 @@ int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont,
     BIGNUM *t;
 
     BN_CTX_start(ctx);
-    if ((t = BN_CTX_get(ctx)) && BN_copy(t, a))
-        retn = BN_from_montgomery_word(ret, t, mont);
+    if ((t = BN_CTX_get(ctx)) && BN_copy(t, a)) {
+        retn = bn_from_montgomery_word(ret, t, mont);
+        bn_correct_top(ret);
+        bn_check_top(ret);
+    }
     BN_CTX_end(ctx);
 #else                           /* !MONT_WORD */
     BIGNUM *t1, *t2;
@@ -298,6 +310,12 @@ int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont,
     return (retn);
 }
 
+int bn_to_mont_fixed_top(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
+                         BN_CTX *ctx)
+{
+    return bn_mul_mont_fixed_top(r, a, &(mont->RR), mont, ctx);
+}
+
 BN_MONT_CTX *BN_MONT_CTX_new(void)
 {
     BN_MONT_CTX *ret;
@@ -334,7 +352,7 @@ void BN_MONT_CTX_free(BN_MONT_CTX *mont)
 
 int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
 {
-    int ret = 0;
+    int i, ret = 0;
     BIGNUM *Ri, *R;
 
     if (BN_is_zero(mod))
@@ -465,6 +483,11 @@ int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
     if (!BN_mod(&(mont->RR), &(mont->RR), &(mont->N), ctx))
         goto err;
 
+    for (i = mont->RR.top, ret = mont->N.top; i < ret; i++)
+        mont->RR.d[i] = 0;
+    mont->RR.top = ret;
+    mont->RR.flags |= BN_FLG_FIXED_TOP;
+
     ret = 1;
  err:
     BN_CTX_end(ctx);
diff --git a/crypto/bn_int.h b/crypto/bn_int.h
new file mode 100644
index 0000000000..a3b0fa7960
--- /dev/null
+++ b/crypto/bn_int.h
@@ -0,0 +1,11 @@
+/*
+ * Some BIGNUM functions assume most significant limb to be non-zero, which
+ * is customarily arranged by bn_correct_top. Output from below functions
+ * is not processed with bn_correct_top, and for this reason it may not be
+ * returned out of public API. It may only be passed internally into other
+ * functions known to support non-minimal or zero-padded BIGNUMs.
+ */
+int bn_mul_mont_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
+                          BN_MONT_CTX *mont, BN_CTX *ctx);
+int bn_to_mont_fixed_top(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
+                         BN_CTX *ctx);