summaryrefslogtreecommitdiff
path: root/src/lib
diff options
context:
space:
mode:
authorjsing <>2023-06-21 07:41:55 +0000
committerjsing <>2023-06-21 07:41:55 +0000
commite977838d69c1994d3229516f8fca1fe64aafb9cb (patch)
treefd160d47e7a4a56b7a1cb2b7a25b722886a6a475 /src/lib
parent66de59424a5c1e76a91fc81a1b29df9eb1801d46 (diff)
downloadopenbsd-e977838d69c1994d3229516f8fca1fe64aafb9cb.tar.gz
openbsd-e977838d69c1994d3229516f8fca1fe64aafb9cb.tar.bz2
openbsd-e977838d69c1994d3229516f8fca1fe64aafb9cb.zip
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@
Diffstat (limited to 'src/lib')
-rw-r--r--src/lib/libcrypto/Makefile3
-rw-r--r--src/lib/libcrypto/bn/bn_internal.h6
-rw-r--r--src/lib/libcrypto/bn/bn_lib.c31
-rw-r--r--src/lib/libcrypto/bn/bn_local.h4
-rw-r--r--src/lib/libcrypto/bn/bn_primitives.c63
5 files changed, 74 insertions, 33 deletions
diff --git a/src/lib/libcrypto/Makefile b/src/lib/libcrypto/Makefile
index 89bd94d79a..6fe129bcdd 100644
--- a/src/lib/libcrypto/Makefile
+++ b/src/lib/libcrypto/Makefile
@@ -1,4 +1,4 @@
1# $OpenBSD: Makefile,v 1.130 2023/06/11 05:35:43 tb Exp $ 1# $OpenBSD: Makefile,v 1.131 2023/06/21 07:41:55 jsing Exp $
2 2
3LIB= crypto 3LIB= crypto
4LIBREBUILD=y 4LIBREBUILD=y
@@ -195,6 +195,7 @@ SRCS+= bn_mod_sqrt.c
195SRCS+= bn_mont.c 195SRCS+= bn_mont.c
196SRCS+= bn_mul.c 196SRCS+= bn_mul.c
197SRCS+= bn_prime.c 197SRCS+= bn_prime.c
198SRCS+= bn_primitives.c
198SRCS+= bn_rand.c 199SRCS+= bn_rand.c
199SRCS+= bn_recp.c 200SRCS+= bn_recp.c
200SRCS+= bn_shift.c 201SRCS+= bn_shift.c
diff --git a/src/lib/libcrypto/bn/bn_internal.h b/src/lib/libcrypto/bn/bn_internal.h
index 5f86e21330..f5c69c5d77 100644
--- a/src/lib/libcrypto/bn/bn_internal.h
+++ b/src/lib/libcrypto/bn/bn_internal.h
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_internal.h,v 1.12 2023/06/12 16:17:24 jsing Exp $ */ 1/* $OpenBSD: bn_internal.h,v 1.13 2023/06/21 07:41:55 jsing Exp $ */
2/* 2/*
3 * Copyright (c) 2023 Joel Sing <jsing@openbsd.org> 3 * Copyright (c) 2023 Joel Sing <jsing@openbsd.org>
4 * 4 *
@@ -22,6 +22,10 @@
22#ifndef HEADER_BN_INTERNAL_H 22#ifndef HEADER_BN_INTERNAL_H
23#define HEADER_BN_INTERNAL_H 23#define HEADER_BN_INTERNAL_H
24 24
25int bn_word_clz(BN_ULONG w);
26
27int bn_bitsize(const BIGNUM *bn);
28
25#ifndef HAVE_BN_CT_NE_ZERO 29#ifndef HAVE_BN_CT_NE_ZERO
26static inline int 30static inline int
27bn_ct_ne_zero(BN_ULONG w) 31bn_ct_ne_zero(BN_ULONG w)
diff --git a/src/lib/libcrypto/bn/bn_lib.c b/src/lib/libcrypto/bn/bn_lib.c
index 389dd3ff3e..b8eb565497 100644
--- a/src/lib/libcrypto/bn/bn_lib.c
+++ b/src/lib/libcrypto/bn/bn_lib.c
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_lib.c,v 1.86 2023/04/30 19:15:48 tb Exp $ */ 1/* $OpenBSD: bn_lib.c,v 1.87 2023/06/21 07:41:55 jsing Exp $ */
2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved. 3 * All rights reserved.
4 * 4 *
@@ -159,27 +159,6 @@ BN_value_one(void)
159 return &bn_value_one; 159 return &bn_value_one;
160} 160}
161 161
162#ifndef HAVE_BN_WORD_CLZ
163int
164bn_word_clz(BN_ULONG w)
165{
166 BN_ULONG bits, mask, shift;
167
168 bits = shift = BN_BITS2;
169 mask = 0;
170
171 while ((shift >>= 1) != 0) {
172 bits += (shift & mask) - (shift & ~mask);
173 mask = bn_ct_ne_zero_mask(w >> bits);
174 }
175 bits += 1 & mask;
176
177 bits -= bn_ct_eq_zero(w);
178
179 return BN_BITS2 - bits;
180}
181#endif
182
183int 162int
184BN_num_bits_word(BN_ULONG w) 163BN_num_bits_word(BN_ULONG w)
185{ 164{
@@ -187,13 +166,9 @@ BN_num_bits_word(BN_ULONG w)
187} 166}
188 167
189int 168int
190BN_num_bits(const BIGNUM *a) 169BN_num_bits(const BIGNUM *bn)
191{ 170{
192 int i = a->top - 1; 171 return bn_bitsize(bn);
193
194 if (BN_is_zero(a))
195 return 0;
196 return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
197} 172}
198 173
199void 174void
diff --git a/src/lib/libcrypto/bn/bn_local.h b/src/lib/libcrypto/bn/bn_local.h
index 78b4157d12..c86e4d032b 100644
--- a/src/lib/libcrypto/bn/bn_local.h
+++ b/src/lib/libcrypto/bn/bn_local.h
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_local.h,v 1.22 2023/05/10 12:21:55 tb Exp $ */ 1/* $OpenBSD: bn_local.h,v 1.23 2023/06/21 07:41:55 jsing Exp $ */
2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved. 3 * All rights reserved.
4 * 4 *
@@ -259,8 +259,6 @@ void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a);
259int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp, 259int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
260 const BN_ULONG *np, const BN_ULONG *n0, int num); 260 const BN_ULONG *np, const BN_ULONG *n0, int num);
261 261
262int bn_word_clz(BN_ULONG w);
263
264void bn_correct_top(BIGNUM *a); 262void bn_correct_top(BIGNUM *a);
265int bn_expand(BIGNUM *a, int bits); 263int bn_expand(BIGNUM *a, int bits);
266int bn_wexpand(BIGNUM *a, int words); 264int bn_wexpand(BIGNUM *a, int words);
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 @@
1/* $OpenBSD: bn_primitives.c,v 1.1 2023/06/21 07:41:55 jsing Exp $ */
2/*
3 * Copyright (c) 2023 Joel Sing <jsing@openbsd.org>
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */
17
18#include <openssl/bn.h>
19
20#include "bn_arch.h"
21#include "bn_internal.h"
22#include "bn_local.h"
23
24#ifndef HAVE_BN_WORD_CLZ
25int
26bn_word_clz(BN_ULONG w)
27{
28 BN_ULONG bits, mask, shift;
29
30 bits = shift = BN_BITS2;
31 mask = 0;
32
33 while ((shift >>= 1) != 0) {
34 bits += (shift & mask) - (shift & ~mask);
35 mask = bn_ct_ne_zero_mask(w >> bits);
36 }
37 bits += 1 & mask;
38
39 bits -= bn_ct_eq_zero(w);
40
41 return BN_BITS2 - bits;
42}
43#endif
44
45#ifndef HAVE_BN_BITSIZE
46int
47bn_bitsize(const BIGNUM *bn)
48{
49 BN_ULONG n = 0, x = 0;
50 BN_ULONG mask, w;
51 int i = 0;
52
53 while (i < bn->top) {
54 w = bn->d[i];
55 mask = bn_ct_ne_zero_mask(w);
56 n = ((BN_ULONG)i & mask) | (n & ~mask);
57 x = (w & mask) | (x & ~mask);
58 i++;
59 }
60
61 return (n + 1) * BN_BITS2 - bn_word_clz(x);
62}
63#endif
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-24 15:21:39 +0000