From 48472c192c88669e44bdba626a93217f709ca4d4 Mon Sep 17 00:00:00 2001 From: jsing <> Date: Sun, 25 May 2025 04:58:32 +0000 Subject: Provide bn_mod_{add,sub,mul}_words(). These implement constant time modular addition, subtraction and multiplication in the Montegomery domain. ok tb@ --- src/lib/libcrypto/Makefile | 3 +- src/lib/libcrypto/bn/bn_internal.h | 12 +++++- src/lib/libcrypto/bn/bn_mod_words.c | 78 +++++++++++++++++++++++++++++++++++++ src/lib/libcrypto/bn/bn_mont.c | 6 +-- 4 files changed, 94 insertions(+), 5 deletions(-) create mode 100644 src/lib/libcrypto/bn/bn_mod_words.c (limited to 'src') 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 * @@ -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 + * + * 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) { -- cgit v1.2.3-55-g6feb