Implement bn_montgomery_multiply()

Provide a constant-time-style Montgomery multiplication implementation.
Use this in place of the assembly bn_mul_mont() on platforms that either
do not have an assembly implementation or have not compiled it in.

Also use this as the fallback version for bn_mul_mont(), rather than
falling back to a non-constant time implementation.

ok beck@ tb@

1 files changed, 86 insertions, 3 deletions

diff --git a/src/lib/libcrypto/bn/bn_mont.c b/src/lib/libcrypto/bn/bn_mont.c
index d2ca4404f9..e92ceae5f4 100644
--- a/src/lib/libcrypto/bn/bn_mont.c
+++ b/src/lib/libcrypto/bn/bn_mont.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_mont.c,v 1.49 2023/03/07 06:15:09 jsing Exp $ */
+/* $OpenBSD: bn_mont.c,v 1.50 2023/03/07 06:19:44 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -336,12 +336,95 @@ bn_mod_mul_montgomery_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
         return ret;
 }
 
+/*
+ * bn_montgomery_multiply_words() computes r = aR * bR * R^-1 = abR for the
+ * given word arrays. The caller must ensure that rp, ap, bp and np are all
+ * n_len words in length, while tp must be n_len * 2 + 2 words in length.
+ */
+void
+bn_montgomery_multiply_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
+    const BN_ULONG *np, BN_ULONG *tp, BN_ULONG n0, int n_len)
+{
+        BN_ULONG carry, mask;
+        int i;
+
+        for (i = 0; i < n_len * 2 + 2; i++)
+                tp[i] = 0;
+
+        for (i = 0; i < n_len; i++) {
+                carry = bn_mul_add_words(tp, ap, n_len, bp[i]);
+                bn_addw(tp[n_len], carry, &tp[n_len + 1], &tp[n_len]);
+
+                carry = bn_mul_add_words(tp, np, n_len, tp[0] * n0);
+                bn_addw(tp[n_len], carry, &carry, &tp[n_len]);
+                bn_addw(tp[n_len + 1], carry, &carry, &tp[n_len + 1]);
+
+                tp++;
+        }
+
+        /*
+         * The output is now in the range of [0, 2N). Attempt to reduce once by
+         * subtracting the modulus. If the reduction was necessary then the
+         * result is already in r, otherwise copy the value prior to reduction
+         * from tp.
+         */
+        mask = bn_ct_ne_zero(tp[n_len]) - bn_sub_words(rp, tp, np, n_len);
+
+        for (i = 0; i < n_len; i++) {
+                *rp = (*rp & ~mask) | (*tp & mask);
+                rp++;
+                tp++;
+        }
+}
+
+/*
+ * bn_montgomery_multiply() computes r = aR * bR * R^-1 = abR for the given
+ * BIGNUMs. The caller must ensure that the modulus is two or more words in
+ * length and that a and b have the same number of words as the modulus.
+ */
+int
+bn_montgomery_multiply(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
+    BN_MONT_CTX *mctx, BN_CTX *ctx)
+{
+        BIGNUM *t;
+        int ret = 0;
+
+        BN_CTX_start(ctx);
+
+        if (mctx->N.top <= 1 || a->top != mctx->N.top || b->top != mctx->N.top)
+                goto err;
+        if (!bn_wexpand(r, mctx->N.top))
+                goto err;
+
+        if ((t = BN_CTX_get(ctx)) == NULL)
+                goto err;
+        if (!bn_wexpand(t, mctx->N.top * 2 + 2))
+                goto err;
+
+        bn_montgomery_multiply_words(r->d, a->d, b->d, mctx->N.d, t->d,
+            mctx->n0[0], mctx->N.top);
+
+        r->top = mctx->N.top;
+        bn_correct_top(r);
+
+        BN_set_negative(r, a->neg ^ b->neg);
+
+        ret = 1;
+ err:
+        BN_CTX_end(ctx);
+
+        return ret;
+}
+
 #ifndef OPENSSL_BN_ASM_MONT
 int
 bn_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
     BN_MONT_CTX *mctx, BN_CTX *ctx)
 {
-        return bn_mod_mul_montgomery_simple(r, a, b, mctx, ctx);
+        if (mctx->N.top <= 1 || a->top != mctx->N.top || b->top != mctx->N.top)
+                return bn_mod_mul_montgomery_simple(r, a, b, mctx, ctx);
+
+        return bn_montgomery_multiply(r, a, b, mctx, ctx);
 }
 #else
 
@@ -360,7 +443,7 @@ bn_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
          * another implementation.
          */
         if (!bn_mul_mont(r->d, a->d, b->d, mctx->N.d, mctx->n0, mctx->N.top))
-                return bn_mod_mul_montgomery_simple(r, a, b, mctx, ctx);
+                return bn_montgomery_multiply(r, a, b, mctx, ctx);
 
         r->top = mctx->N.top;
         bn_correct_top(r);