From ee7498205ca9a9c113be85f42342dfd4565d0953 Mon Sep 17 00:00:00 2001 From: jsing Date: Thu, 16 Feb 2023 04:42:20 +0000 Subject: [PATCH] Reimplement bn_add_words() and bn_sub_words() using bignum primitives. This removes the effectively duplicate BN_LLONG version of bn_add_words() and simplifies the code considerably. ok tb@ --- lib/libcrypto/bn/bn_add.c | 140 +++++++-------------------------- lib/libcrypto/bn/bn_internal.h | 59 +++++++++++++- 2 files changed, 88 insertions(+), 111 deletions(-) diff --git a/lib/libcrypto/bn/bn_add.c b/lib/libcrypto/bn/bn_add.c index 8ae9bbe8546..51b87104cf8 100644 --- a/lib/libcrypto/bn/bn_add.c +++ b/lib/libcrypto/bn/bn_add.c @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_add.c,v 1.22 2023/02/13 04:25:37 jsing Exp $ */ +/* $OpenBSD: bn_add.c,v 1.23 2023/02/16 04:42:20 jsing Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -64,89 +64,31 @@ #include "bn_arch.h" #include "bn_local.h" +#include "bn_internal.h" BN_ULONG bn_add(BIGNUM *r, int rn, const BIGNUM *a, const BIGNUM *b); BN_ULONG bn_sub(BIGNUM *r, int rn, const BIGNUM *a, const BIGNUM *b); +/* + * 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 -#ifdef BN_LLONG BN_ULONG bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) { - BN_ULLONG ll = 0; + BN_ULONG carry = 0; assert(n >= 0); if (n <= 0) - return ((BN_ULONG)0); - -#ifndef OPENSSL_SMALL_FOOTPRINT - while (n & ~3) { - ll += (BN_ULLONG)a[0] + b[0]; - r[0] = (BN_ULONG)ll & BN_MASK2; - ll >>= BN_BITS2; - ll += (BN_ULLONG)a[1] + b[1]; - r[1] = (BN_ULONG)ll & BN_MASK2; - ll >>= BN_BITS2; - ll += (BN_ULLONG)a[2] + b[2]; - r[2] = (BN_ULONG)ll & BN_MASK2; - ll >>= BN_BITS2; - ll += (BN_ULLONG)a[3] + b[3]; - r[3] = (BN_ULONG)ll & BN_MASK2; - ll >>= BN_BITS2; - a += 4; - b += 4; - r += 4; - n -= 4; - } -#endif - while (n) { - ll += (BN_ULLONG)a[0] + b[0]; - r[0] = (BN_ULONG)ll & BN_MASK2; - ll >>= BN_BITS2; - a++; - b++; - r++; - n--; - } - return ((BN_ULONG)ll); -} -#else /* !BN_LLONG */ -BN_ULONG -bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) -{ - BN_ULONG c, l, t; - - assert(n >= 0); - if (n <= 0) - return ((BN_ULONG)0); + return 0; - c = 0; #ifndef OPENSSL_SMALL_FOOTPRINT while (n & ~3) { - t = a[0]; - t = (t + c) & BN_MASK2; - c = (t < c); - l = (t + b[0]) & BN_MASK2; - c += (l < t); - r[0] = l; - t = a[1]; - t = (t + c) & BN_MASK2; - c = (t < c); - l = (t + b[1]) & BN_MASK2; - c += (l < t); - r[1] = l; - t = a[2]; - t = (t + c) & BN_MASK2; - c = (t < c); - l = (t + b[2]) & BN_MASK2; - c += (l < t); - r[2] = l; - t = a[3]; - t = (t + c) & BN_MASK2; - c = (t < c); - l = (t + b[3]) & BN_MASK2; - c += (l < t); - r[3] = l; + bn_addw_addw(a[0], b[0], carry, &carry, &r[0]); + bn_addw_addw(a[1], b[1], carry, &carry, &r[1]); + bn_addw_addw(a[2], b[2], carry, &carry, &r[2]); + bn_addw_addw(a[3], b[3], carry, &carry, &r[3]); a += 4; b += 4; r += 4; @@ -154,55 +96,37 @@ bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) } #endif while (n) { - t = a[0]; - t = (t + c) & BN_MASK2; - c = (t < c); - l = (t + b[0]) & BN_MASK2; - c += (l < t); - r[0] = l; + bn_addw_addw(a[0], b[0], carry, &carry, &r[0]); a++; b++; r++; n--; } - return ((BN_ULONG)c); + return carry; } -#endif /* !BN_LLONG */ #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 t1, t2; - int c = 0; + BN_ULONG borrow = 0; assert(n >= 0); if (n <= 0) - return ((BN_ULONG)0); + return 0; #ifndef OPENSSL_SMALL_FOOTPRINT - while (n&~3) { - t1 = a[0]; - t2 = b[0]; - r[0] = (t1 - t2 - c) & BN_MASK2; - if (t1 != t2) - c = (t1 < t2); - t1 = a[1]; - t2 = b[1]; - r[1] = (t1 - t2 - c) & BN_MASK2; - if (t1 != t2) - c = (t1 < t2); - t1 = a[2]; - t2 = b[2]; - r[2] = (t1 - t2 - c) & BN_MASK2; - if (t1 != t2) - c = (t1 < t2); - t1 = a[3]; - t2 = b[3]; - r[3] = (t1 - t2 - c) & BN_MASK2; - if (t1 != t2) - c = (t1 < t2); + while (n & ~3) { + bn_subw_subw(a[0], b[0], borrow, &borrow, &r[0]); + bn_subw_subw(a[1], b[1], borrow, &borrow, &r[1]); + bn_subw_subw(a[2], b[2], borrow, &borrow, &r[2]); + bn_subw_subw(a[3], b[3], borrow, &borrow, &r[3]); a += 4; b += 4; r += 4; @@ -210,26 +134,22 @@ bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) } #endif while (n) { - t1 = a[0]; - t2 = b[0]; - r[0] = (t1 - t2 - c) & BN_MASK2; - if (t1 != t2) - c = (t1 < t2); + bn_subw_subw(a[0], b[0], borrow, &borrow, &r[0]); a++; b++; r++; n--; } - return (c); + return borrow; } #endif -#ifndef HAVE_BN_ADD /* * bn_add() computes a + b, storing the result in r (which may be the same as a * or b). The caller must ensure that r has been expanded to max(a->top, b->top) * words. Any carry resulting from the addition is returned. */ +#ifndef HAVE_BN_ADD BN_ULONG bn_add(BIGNUM *r, int rn, const BIGNUM *a, const BIGNUM *b) { @@ -268,13 +188,13 @@ bn_add(BIGNUM *r, int rn, const BIGNUM *a, const BIGNUM *b) } #endif -#ifndef HAVE_BN_SUB /* * bn_sub() computes a - b, storing the result in r (which may be the same as a * or b). The caller must ensure that the number of words in a is greater than * or equal to the number of words in b and that r has been expanded to * a->top words. Any borrow resulting from the subtraction is returned. */ +#ifndef HAVE_BN_SUB BN_ULONG bn_sub(BIGNUM *r, int rn, const BIGNUM *a, const BIGNUM *b) { diff --git a/lib/libcrypto/bn/bn_internal.h b/lib/libcrypto/bn/bn_internal.h index 12ea3641e62..1b5ab9c42c1 100644 --- a/lib/libcrypto/bn/bn_internal.h +++ b/lib/libcrypto/bn/bn_internal.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_internal.h,v 1.4 2023/02/15 04:46:49 tb Exp $ */ +/* $OpenBSD: bn_internal.h,v 1.5 2023/02/16 04:42:20 jsing Exp $ */ /* * Copyright (c) 2023 Joel Sing * @@ -102,6 +102,63 @@ bn_addw(BN_ULONG a, BN_ULONG b, BN_ULONG *out_r1, BN_ULONG *out_r0) #endif #endif +/* + * bn_addw_addw() computes (r1:r0) = a + b + c, where all inputs are single + * words, producing a double word result. + */ +#ifndef HAVE_BN_ADDW_ADDW +static inline void +bn_addw_addw(BN_ULONG a, BN_ULONG b, BN_ULONG c, BN_ULONG *out_r1, + BN_ULONG *out_r0) +{ + BN_ULONG carry, r1, r0; + + bn_addw(a, b, &r1, &r0); + bn_addw(r0, c, &carry, &r0); + r1 += carry; + + *out_r1 = r1; + *out_r0 = r0; +} +#endif + +/* + * bn_subw() computes r0 = a - b, where both inputs are single words, + * producing a single word result and borrow. + */ +#ifndef HAVE_BN_SUBW +static inline void +bn_subw(BN_ULONG a, BN_ULONG b, BN_ULONG *out_borrow, BN_ULONG *out_r0) +{ + BN_ULONG borrow, r0; + + r0 = a - b; + borrow = ((r0 | (b & ~a)) & (b | ~a)) >> (BN_BITS2 - 1); + + *out_borrow = borrow; + *out_r0 = r0; +} +#endif + +/* + * bn_subw_subw() computes r0 = a - b - c, where all inputs are single words, + * producing a single word result and borrow. + */ +#ifndef HAVE_BN_SUBW_SUBW +static inline void +bn_subw_subw(BN_ULONG a, BN_ULONG b, BN_ULONG c, BN_ULONG *out_borrow, + BN_ULONG *out_r0) +{ + BN_ULONG b1, b2, r0; + + bn_subw(a, b, &b1, &r0); + bn_subw(r0, c, &b2, &r0); + + *out_borrow = b1 + b2; + *out_r0 = r0; +} +#endif + #ifndef HAVE_BN_UMUL_HILO #ifdef BN_LLONG static inline void -- 2.20.1