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@
author: jsing <> 2023-03-07 06:19:44 +0000
committer: jsing <> 2023-03-07 06:19:44 +0000
commit: 4320ee92fb55c991eec4cdc78f60c762533babb7 (patch)
tree: 6a167a9b374a6e5a6fc9fb06d04f4cff22727f76 /src/lib
parent: 9d27b98c03802e34828891a1a14e03f9ff09e110 (diff)
download: openbsd-4320ee92fb55c991eec4cdc78f60c762533babb7.tar.gz
openbsd-4320ee92fb55c991eec4cdc78f60c762533babb7.tar.bz2
openbsd-4320ee92fb55c991eec4cdc78f60c762533babb7.zip
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);
author	jsing <>	2023-03-07 06:19:44 +0000
committer	jsing <>	2023-03-07 06:19:44 +0000
commit	4320ee92fb55c991eec4cdc78f60c762533babb7 (patch)
tree	6a167a9b374a6e5a6fc9fb06d04f4cff22727f76 /src/lib
parent	9d27b98c03802e34828891a1a14e03f9ff09e110 (diff)
download	openbsd-4320ee92fb55c991eec4cdc78f60c762533babb7.tar.gz openbsd-4320ee92fb55c991eec4cdc78f60c762533babb7.tar.bz2 openbsd-4320ee92fb55c991eec4cdc78f60c762533babb7.zip

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 @@
1	/* $OpenBSD: bn_mont.c,v 1.49 2023/03/07 06:15:09 jsing Exp $ */	1	/* $OpenBSD: bn_mont.c,v 1.50 2023/03/07 06:19:44 jsing Exp $ */
2	/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)	2	/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3	* All rights reserved.	3	* All rights reserved.
4	*	4	*
@@ -336,12 +336,95 @@ bn_mod_mul_montgomery_simple(BIGNUM r, const BIGNUM a, const BIGNUM *b,
336	return ret;	336	return ret;
337	}	337	}
338		338
		339	/*
		340	* bn_montgomery_multiply_words() computes r = aR * bR * R^-1 = abR for the
		341	* given word arrays. The caller must ensure that rp, ap, bp and np are all
		342	* n_len words in length, while tp must be n_len * 2 + 2 words in length.
		343	*/
		344	void
		345	bn_montgomery_multiply_words(BN_ULONG rp, const BN_ULONG ap, const BN_ULONG *bp,
		346	const BN_ULONG np, BN_ULONG tp, BN_ULONG n0, int n_len)
		347	{
		348	BN_ULONG carry, mask;
		349	int i;
		350
		351	for (i = 0; i < n_len * 2 + 2; i++)
		352	tp[i] = 0;
		353
		354	for (i = 0; i < n_len; i++) {
		355	carry = bn_mul_add_words(tp, ap, n_len, bp[i]);
		356	bn_addw(tp[n_len], carry, &tp[n_len + 1], &tp[n_len]);
		357
		358	carry = bn_mul_add_words(tp, np, n_len, tp[0] * n0);
		359	bn_addw(tp[n_len], carry, &carry, &tp[n_len]);
		360	bn_addw(tp[n_len + 1], carry, &carry, &tp[n_len + 1]);
		361
		362	tp++;
		363	}
		364
		365	/*
		366	* The output is now in the range of [0, 2N). Attempt to reduce once by
		367	* subtracting the modulus. If the reduction was necessary then the
		368	* result is already in r, otherwise copy the value prior to reduction
		369	* from tp.
		370	*/
		371	mask = bn_ct_ne_zero(tp[n_len]) - bn_sub_words(rp, tp, np, n_len);
		372
		373	for (i = 0; i < n_len; i++) {
		374	rp = (rp & ~mask) \| (*tp & mask);
		375	rp++;
		376	tp++;
		377	}
		378	}
		379
		380	/*
		381	* bn_montgomery_multiply() computes r = aR * bR * R^-1 = abR for the given
		382	* BIGNUMs. The caller must ensure that the modulus is two or more words in
		383	* length and that a and b have the same number of words as the modulus.
		384	*/
		385	int
		386	bn_montgomery_multiply(BIGNUM r, const BIGNUM a, const BIGNUM *b,
		387	BN_MONT_CTX mctx, BN_CTX ctx)
		388	{
		389	BIGNUM *t;
		390	int ret = 0;
		391
		392	BN_CTX_start(ctx);
		393
		394	if (mctx->N.top <= 1 \|\| a->top != mctx->N.top \|\| b->top != mctx->N.top)
		395	goto err;
		396	if (!bn_wexpand(r, mctx->N.top))
		397	goto err;
		398
		399	if ((t = BN_CTX_get(ctx)) == NULL)
		400	goto err;
		401	if (!bn_wexpand(t, mctx->N.top * 2 + 2))
		402	goto err;
		403
		404	bn_montgomery_multiply_words(r->d, a->d, b->d, mctx->N.d, t->d,
		405	mctx->n0[0], mctx->N.top);
		406
		407	r->top = mctx->N.top;
		408	bn_correct_top(r);
		409
		410	BN_set_negative(r, a->neg ^ b->neg);
		411
		412	ret = 1;
		413	err:
		414	BN_CTX_end(ctx);
		415
		416	return ret;
		417	}
		418
339	#ifndef OPENSSL_BN_ASM_MONT	419	#ifndef OPENSSL_BN_ASM_MONT
340	int	420	int
341	bn_mod_mul_montgomery(BIGNUM r, const BIGNUM a, const BIGNUM *b,	421	bn_mod_mul_montgomery(BIGNUM r, const BIGNUM a, const BIGNUM *b,
342	BN_MONT_CTX mctx, BN_CTX ctx)	422	BN_MONT_CTX mctx, BN_CTX ctx)
343	{	423	{
344	return bn_mod_mul_montgomery_simple(r, a, b, mctx, ctx);	424	if (mctx->N.top <= 1 \|\| a->top != mctx->N.top \|\| b->top != mctx->N.top)
		425	return bn_mod_mul_montgomery_simple(r, a, b, mctx, ctx);
		426
		427	return bn_montgomery_multiply(r, a, b, mctx, ctx);
345	}	428	}
346	#else	429	#else
347		430
@@ -360,7 +443,7 @@ bn_mod_mul_montgomery(BIGNUM r, const BIGNUM a, const BIGNUM *b,
360	* another implementation.	443	* another implementation.
361	*/	444	*/
362	if (!bn_mul_mont(r->d, a->d, b->d, mctx->N.d, mctx->n0, mctx->N.top))	445	if (!bn_mul_mont(r->d, a->d, b->d, mctx->N.d, mctx->n0, mctx->N.top))
363	return bn_mod_mul_montgomery_simple(r, a, b, mctx, ctx);	446	return bn_montgomery_multiply(r, a, b, mctx, ctx);
364		447
365	r->top = mctx->N.top;	448	r->top = mctx->N.top;
366	bn_correct_top(r);	449	bn_correct_top(r);