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>
Reviewed-by: David Benjamin <davidben@google.com>
(Merged from https://github.com/openssl/openssl/pull/6662)

1 files changed, 34 insertions, 11 deletions

diff --git a/crypto/bn/bn_mont.c b/crypto/bn/bn_mont.c
index 3c47351962..683e8e946b 100644
--- a/crypto/bn/bn_mont.c
+++ b/crypto/bn/bn_mont.c
@@ -20,12 +20,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;
     int num = mont->N.top;
@@ -37,7 +48,7 @@ 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);
+            r->flags |= BN_FLG_FIXED_TOP;
             return 1;
         }
     }
@@ -61,13 +72,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);
@@ -75,7 +85,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;
@@ -102,6 +112,7 @@ static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont)
         memset(&rp[r->top], 0, sizeof(*rp) * i);
 
     r->top = max;
+    r->flags |= BN_FLG_FIXED_TOP;
     n0 = mont->n0[0];
 
     /*
@@ -120,6 +131,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;
@@ -140,9 +152,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;
 }
@@ -156,8 +165,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;
@@ -195,6 +207,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;
@@ -232,7 +250,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))
@@ -367,6 +385,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);