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/lib/libcrypto/bn/bn_mont.c b/lib/libcrypto/bn/bn_mont.c
index d2ca4404f9f..e92ceae5f48 100644
--- a/lib/libcrypto/bn/bn_mont.c
+++ b/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);