Stop using BIGNUM internals, add some clarifying comments

ok jsing

1 files changed, 23 insertions, 4 deletions

diff --git a/src/lib/libcrypto/ec/ec_mult.c b/src/lib/libcrypto/ec/ec_mult.c
index 546a74c590..4dc5e12a46 100644
--- a/src/lib/libcrypto/ec/ec_mult.c
+++ b/src/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);
         }