Provide bn_mod_{add,sub,mul}_words().

These implement constant time modular addition, subtraction and
multiplication in the Montegomery domain.

ok tb@

4 files changed, 94 insertions, 5 deletions

diff --git a/src/lib/libcrypto/Makefile b/src/lib/libcrypto/Makefile
index a05042986c..dd64f07f48 100644
--- a/src/lib/libcrypto/Makefile
+++ b/src/lib/libcrypto/Makefile
@@ -1,4 +1,4 @@
-# $OpenBSD: Makefile,v 1.232 2025/05/25 04:53:05 jsing Exp $
+# $OpenBSD: Makefile,v 1.233 2025/05/25 04:58:32 jsing Exp $
 
 LIB=    crypto
 LIBREBUILD=y
@@ -173,6 +173,7 @@ SRCS+= bn_kron.c
 SRCS+= bn_lib.c
 SRCS+= bn_mod.c
 SRCS+= bn_mod_sqrt.c
+SRCS+= bn_mod_words.c
 SRCS+= bn_mont.c
 SRCS+= bn_mul.c
 SRCS+= bn_prime.c
diff --git a/src/lib/libcrypto/bn/bn_internal.h b/src/lib/libcrypto/bn/bn_internal.h
index 895a194c93..b6e903553f 100644
--- a/src/lib/libcrypto/bn/bn_internal.h
+++ b/src/lib/libcrypto/bn/bn_internal.h
@@ -1,4 +1,4 @@
-/*      $OpenBSD: bn_internal.h,v 1.17 2025/05/25 04:53:05 jsing Exp $ */
+/*      $OpenBSD: bn_internal.h,v 1.18 2025/05/25 04:58:32 jsing Exp $ */
 /*
  * Copyright (c) 2023 Joel Sing <jsing@openbsd.org>
  *
@@ -35,6 +35,16 @@ BN_ULONG bn_add_words_masked(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
     BN_ULONG mask, size_t n);
 BN_ULONG bn_sub_words_masked(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
     BN_ULONG mask, size_t n);
+void bn_mod_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
+    const BN_ULONG *m, size_t n);
+void bn_mod_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
+    const BN_ULONG *m, size_t n);
+void bn_mod_mul_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
+    const BN_ULONG *m, BN_ULONG *t, BN_ULONG m0, size_t n);
+
+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);
 
 #ifndef HAVE_BN_CT_NE_ZERO
 static inline int
diff --git a/src/lib/libcrypto/bn/bn_mod_words.c b/src/lib/libcrypto/bn/bn_mod_words.c
new file mode 100644
index 0000000000..8971f9f306
--- /dev/null
+++ b/src/lib/libcrypto/bn/bn_mod_words.c
@@ -0,0 +1,78 @@
+/*      $OpenBSD: bn_mod_words.c,v 1.1 2025/05/25 04:58:32 jsing Exp $  */
+/*
+ * Copyright (c) 2024 Joel Sing <jsing@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include "bn_local.h"
+#include "bn_internal.h"
+
+/*
+ * bn_mod_add_words() computes r[] = (a[] + b[]) mod m[], where a, b, r and
+ * m are arrays of words with length n (r may be the same as a or b).
+ */
+#ifndef HAVE_BN_MOD_ADD_WORDS
+void
+bn_mod_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
+    const BN_ULONG *m, size_t n)
+{
+        BN_ULONG carry, mask;
+
+        /*
+         * Compute a + b, then compute r - m to determine if r >= m, considering
+         * any carry that resulted from the addition. Finally complete a
+         * conditional subtraction of r - m.
+         */
+        /* XXX - change bn_add_words to use size_t. */
+        carry = bn_add_words(r, a, b, n);
+        mask = ~(carry - bn_sub_words_borrow(r, m, n));
+        bn_sub_words_masked(r, r, m, mask, n);
+}
+#endif
+
+/*
+ * bn_mod_sub_words() computes r[] = (a[] - b[]) mod m[], where a, b, r and
+ * m are arrays of words with length n (r may be the same as a or b).
+ */
+#ifndef HAVE_BN_MOD_SUB_WORDS
+void
+bn_mod_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
+    const BN_ULONG *m, size_t n)
+{
+        BN_ULONG borrow, mask;
+
+        /*
+         * Compute a - b, then complete a conditional addition of r + m
+         * based on the resulting borrow.
+         */
+        /* XXX - change bn_sub_words to use size_t. */
+        borrow = bn_sub_words(r, a, b, n);
+        mask = (0 - borrow);
+        bn_add_words_masked(r, r, m, mask, n);
+}
+#endif
+
+/*
+ * bn_mod_mul_words() computes r[] = (a[] * b[]) mod m[], where a, b, r and
+ * m are arrays of words with length n (r may be the same as a or b) in the
+ * Montgomery domain. The result remains in the Montgomery domain.
+ */
+#ifndef HAVE_BN_MOD_MUL_WORDS
+void
+bn_mod_mul_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
+    const BN_ULONG *m, BN_ULONG *t, BN_ULONG m0, size_t n)
+{
+        bn_montgomery_multiply_words(r, a, b, m, t, m0, n);
+}
+#endif
diff --git a/src/lib/libcrypto/bn/bn_mont.c b/src/lib/libcrypto/bn/bn_mont.c
index edd7bcd0c8..ce88b23ca9 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.66 2025/03/09 15:22:40 tb Exp $ */
+/* $OpenBSD: bn_mont.c,v 1.67 2025/05/25 04:58:32 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -417,7 +417,7 @@ bn_mod_mul_montgomery_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
         return ret;
 }
 
-static void
+static inline void
 bn_montgomery_multiply_word(const BN_ULONG *ap, BN_ULONG b, const BN_ULONG *np,
     BN_ULONG *tp, BN_ULONG w, BN_ULONG *carry_a, BN_ULONG *carry_n, int n_len)
 {
@@ -452,7 +452,7 @@ bn_montgomery_multiply_word(const BN_ULONG *ap, BN_ULONG b, const BN_ULONG *np,
  * 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.
  */
-static void
+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)
 {