From e977838d69c1994d3229516f8fca1fe64aafb9cb Mon Sep 17 00:00:00 2001 From: jsing <> Date: Wed, 21 Jun 2023 07:41:55 +0000 Subject: Make BN_num_bits() independent of bn->top. Provide bn_bitsize(), which performs a constant time scan of a BN in order to determine the bit size of the BN value. Use this for BN_num_bits() such that it is no longer dependent on the bn->top value. ok tb@ --- src/lib/libcrypto/bn/bn_primitives.c | 63 ++++++++++++++++++++++++++++++++++++ 1 file changed, 63 insertions(+) create mode 100644 src/lib/libcrypto/bn/bn_primitives.c (limited to 'src/lib/libcrypto/bn/bn_primitives.c') diff --git a/src/lib/libcrypto/bn/bn_primitives.c b/src/lib/libcrypto/bn/bn_primitives.c new file mode 100644 index 0000000000..e9caec4818 --- /dev/null +++ b/src/lib/libcrypto/bn/bn_primitives.c @@ -0,0 +1,63 @@ +/* $OpenBSD: bn_primitives.c,v 1.1 2023/06/21 07:41:55 jsing Exp $ */ +/* + * Copyright (c) 2023 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_arch.h" +#include "bn_internal.h" +#include "bn_local.h" + +#ifndef HAVE_BN_WORD_CLZ +int +bn_word_clz(BN_ULONG w) +{ + BN_ULONG bits, mask, shift; + + bits = shift = BN_BITS2; + mask = 0; + + while ((shift >>= 1) != 0) { + bits += (shift & mask) - (shift & ~mask); + mask = bn_ct_ne_zero_mask(w >> bits); + } + bits += 1 & mask; + + bits -= bn_ct_eq_zero(w); + + return BN_BITS2 - bits; +} +#endif + +#ifndef HAVE_BN_BITSIZE +int +bn_bitsize(const BIGNUM *bn) +{ + BN_ULONG n = 0, x = 0; + BN_ULONG mask, w; + int i = 0; + + while (i < bn->top) { + w = bn->d[i]; + mask = bn_ct_ne_zero_mask(w); + n = ((BN_ULONG)i & mask) | (n & ~mask); + x = (w & mask) | (x & ~mask); + i++; + } + + return (n + 1) * BN_BITS2 - bn_word_clz(x); +} +#endif -- cgit v1.2.3-55-g6feb