diff options
| -rw-r--r-- | lib/libcrypto/ec/ec_mult.c | 27 |
1 files changed, 23 insertions, 4 deletions
diff --git a/lib/libcrypto/ec/ec_mult.c b/lib/libcrypto/ec/ec_mult.c index 546a74c5906..4dc5e12a46c 100644 --- a/lib/libcrypto/ec/ec_mult.c +++ b/lib/libcrypto/ec/ec_mult.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ec_mult.c,v 1.45 2024/11/22 16:27:46 tb Exp $ */ +/* $OpenBSD: ec_mult.c,v 1.46 2024/11/22 17:08:13 tb Exp $ */ /* * Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project. */ @@ -67,7 +67,6 @@ #include <openssl/ec.h> #include <openssl/err.h> -#include "bn_local.h" #include "ec_local.h" static int @@ -89,6 +88,10 @@ ec_window_bits(const BIGNUM *bn) return 1; } +/* + * Modified width-(w+1) non-adjacent form of bn. + */ + static int ec_compute_wNAF(const BIGNUM *bn, signed char **out_wNAF, size_t *out_wNAF_len, size_t *out_len) @@ -108,6 +111,8 @@ ec_compute_wNAF(const BIGNUM *bn, signed char **out_wNAF, size_t *out_wNAF_len, goto done; } + sign = BN_is_negative(bn) ? -1 : 1; + wNAF_len = BN_num_bits(bn); if ((wNAF = calloc(1, wNAF_len + 1)) == NULL) { ECerror(ERR_R_MALLOC_FAILURE); @@ -121,13 +126,25 @@ ec_compute_wNAF(const BIGNUM *bn, signed char **out_wNAF, size_t *out_wNAF_len, next = bit << 1; mask = next - 1; - sign = BN_is_negative(bn) ? -1 : 1; - window = bn->d[0] & mask; + /* Extract the wbits + 1 lowest bits without using BIGNUM internals. */ + window = 0; + for (i = 0; i < wbits + 1; i++) { + if (BN_is_bit_set(bn, i)) + window |= (1 << i); + } + /* Instead of bn >>= 1 in each iteration, slide window to the left. */ for (i = 0; i + wbits + 1 < wNAF_len || window != 0; i++) { digit = 0; + /* + * If window is odd, the i-th wNAF digit is window (mods 2^w), + * where mods is the signed modulo in (-2^w-1, 2^w-1]. In the + * last iterations the digits are grouped slightly differently. + * Subtract the digit from window, so window is 0, next, or bit, + * and add the digit to the wNAF digits. + */ if ((window & 1) != 0) { digit = window; if ((window & bit) != 0) { @@ -140,6 +157,8 @@ ec_compute_wNAF(const BIGNUM *bn, signed char **out_wNAF, size_t *out_wNAF_len, } wNAF[i] = sign * digit; + + /* Slide the window to the left. */ window >>= 1; window += bit * BN_is_bit_set(bn, i + wbits + 1); } |