From cbdbb6515eba8411eeb6f22618e029f1a461aa60 Mon Sep 17 00:00:00 2001 From: jsing <> Date: Sun, 25 May 2025 04:30:55 +0000 Subject: Provide additional variants of bn_add_words()/bn_sub_words(). Move bn_add_words() and bn_sub_words() from bn_add.c to bn_add_sub.c. These have effectively been replaced in the previous rewrites. Remove the asserts - if bad lengths are passed the results will be incorrect and things will fail (these should use size_t instead of int, but that is a problem for another day). Provide bn_sub_words_borrow(), which computes a subtraction but only returns the resulting borrow. Provide bn_add_words_masked() and bn_sub_words_masked(), which perform an masked addition or subtraction. These can also be used to implement constant time addition and subtraction, especially for reduction. ok beck@ tb@ --- src/lib/libcrypto/bn/bn_add_sub.c | 178 +++++++++++++++++++++++++++++++++++++ src/lib/libcrypto/bn/bn_internal.h | 12 ++- src/lib/libcrypto/bn/bn_local.h | 6 +- 3 files changed, 190 insertions(+), 6 deletions(-) create mode 100644 src/lib/libcrypto/bn/bn_add_sub.c (limited to 'src') diff --git a/src/lib/libcrypto/bn/bn_add_sub.c b/src/lib/libcrypto/bn/bn_add_sub.c new file mode 100644 index 0000000000..5c9d5a2b1a --- /dev/null +++ b/src/lib/libcrypto/bn/bn_add_sub.c @@ -0,0 +1,178 @@ +/* $OpenBSD: bn_add_sub.c,v 1.1 2025/05/25 04:30:55 jsing Exp $ */ +/* + * Copyright (c) 2023,2024,2025 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 + +#include "bn_internal.h" + +/* + * bn_add_words() computes (carry:r[i]) = a[i] + b[i] + carry, where a and b + * are both arrays of words. Any carry resulting from the addition is returned. + */ +#ifndef HAVE_BN_ADD_WORDS +BN_ULONG +bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) +{ + BN_ULONG carry = 0; + + while (n >= 4) { + bn_qwaddqw(a[3], a[2], a[1], a[0], b[3], b[2], b[1], b[0], + carry, &carry, &r[3], &r[2], &r[1], &r[0]); + a += 4; + b += 4; + r += 4; + n -= 4; + } + while (n > 0) { + bn_addw_addw(a[0], b[0], carry, &carry, &r[0]); + a++; + b++; + r++; + n--; + } + + return carry; +} +#endif + +/* + * bn_sub_words() computes (borrow:r[i]) = a[i] - b[i] - borrow, where a and b + * are both arrays of words. Any borrow resulting from the subtraction is + * returned. + */ +#ifndef HAVE_BN_SUB_WORDS +BN_ULONG +bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) +{ + BN_ULONG borrow = 0; + + while (n >= 4) { + bn_qwsubqw(a[3], a[2], a[1], a[0], b[3], b[2], b[1], b[0], + borrow, &borrow, &r[3], &r[2], &r[1], &r[0]); + a += 4; + b += 4; + r += 4; + n -= 4; + } + while (n > 0) { + bn_subw_subw(a[0], b[0], borrow, &borrow, &r[0]); + a++; + b++; + r++; + n--; + } + + return borrow; +} +#endif + +/* + * bn_sub_borrow() computes a[i] - b[i], returning the resulting borrow only. + */ +#ifndef HAVE_BN_SUB_WORDS_BORROW +BN_ULONG +bn_sub_words_borrow(const BN_ULONG *a, const BN_ULONG *b, size_t n) +{ + BN_ULONG borrow = 0; + BN_ULONG r; + + while (n >= 4) { + bn_qwsubqw(a[3], a[2], a[1], a[0], b[3], b[2], b[1], b[0], + borrow, &borrow, &r, &r, &r, &r); + a += 4; + b += 4; + n -= 4; + } + while (n > 0) { + bn_subw_subw(a[0], b[0], borrow, &borrow, &r); + a++; + b++; + n--; + } + + return borrow; +} +#endif + +/* + * bn_add_words_masked() computes r[] = a[] + (b[] & mask), where a, b and r are + * arrays of words with length n (r may be the same as a or b). + */ +#ifndef HAVE_BN_ADD_WORDS_MASKED +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 carry = 0; + + /* XXX - consider conditional/masked versions of bn_addw_addw/bn_qwaddqw. */ + + while (n >= 4) { + bn_qwaddqw(a[3], a[2], a[1], a[0], b[3] & mask, b[2] & mask, + b[1] & mask, b[0] & mask, carry, &carry, &r[3], &r[2], + &r[1], &r[0]); + a += 4; + b += 4; + r += 4; + n -= 4; + } + while (n > 0) { + bn_addw_addw(a[0], b[0] & mask, carry, &carry, &r[0]); + a++; + b++; + r++; + n--; + } + + return carry; +} +#endif + +/* + * bn_sub_words_masked() computes r[] = a[] - (b[] & mask), where a, b and r are + * arrays of words with length n (r may be the same as a or b). + */ +#ifndef HAVE_BN_SUB_WORDS_MASKED +BN_ULONG +bn_sub_words_masked(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, + BN_ULONG mask, size_t n) +{ + BN_ULONG borrow = 0; + + /* XXX - consider conditional/masked versions of bn_subw_subw/bn_qwsubqw. */ + + /* Compute conditional r[i] = a[i] - b[i]. */ + while (n >= 4) { + bn_qwsubqw(a[3], a[2], a[1], a[0], b[3] & mask, b[2] & mask, + b[1] & mask, b[0] & mask, borrow, &borrow, &r[3], &r[2], + &r[1], &r[0]); + a += 4; + b += 4; + r += 4; + n -= 4; + } + while (n > 0) { + bn_subw_subw(a[0], b[0] & mask, borrow, &borrow, &r[0]); + a++; + b++; + r++; + n--; + } + + return borrow; +} +#endif diff --git a/src/lib/libcrypto/bn/bn_internal.h b/src/lib/libcrypto/bn/bn_internal.h index fd04bc9f8a..18fd7550a6 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.15 2023/06/25 11:42:26 jsing Exp $ */ +/* $OpenBSD: bn_internal.h,v 1.16 2025/05/25 04:30:55 jsing Exp $ */ /* * Copyright (c) 2023 Joel Sing * @@ -26,6 +26,16 @@ int bn_word_clz(BN_ULONG w); int bn_bitsize(const BIGNUM *bn); +BN_ULONG bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, + int num); +BN_ULONG bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, + int num); +BN_ULONG bn_sub_words_borrow(const BN_ULONG *a, const BN_ULONG *b, size_t n); +void bn_add_words_masked(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, + BN_ULONG mask, size_t n); +void bn_sub_words_masked(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, + BN_ULONG mask, size_t n); + #ifndef HAVE_BN_CT_NE_ZERO static inline int bn_ct_ne_zero(BN_ULONG w) diff --git a/src/lib/libcrypto/bn/bn_local.h b/src/lib/libcrypto/bn/bn_local.h index 067ffab3d9..0eb9a7a745 100644 --- a/src/lib/libcrypto/bn/bn_local.h +++ b/src/lib/libcrypto/bn/bn_local.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_local.h,v 1.50 2025/02/13 11:04:20 tb Exp $ */ +/* $OpenBSD: bn_local.h,v 1.51 2025/05/25 04:30:55 jsing Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -254,10 +254,6 @@ int bn_expand_bits(BIGNUM *a, size_t bits); int bn_expand_bytes(BIGNUM *a, size_t bytes); int bn_wexpand(BIGNUM *a, int words); -BN_ULONG bn_add_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp, - int num); -BN_ULONG bn_sub_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp, - int num); BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w); BN_ULONG bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w); void bn_sqr_words(BN_ULONG *rp, const BN_ULONG *ap, int num); -- cgit v1.2.3-55-g6feb