summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/lib/libcrypto/ec/ec_mult.c225
1 files changed, 80 insertions, 145 deletions
diff --git a/src/lib/libcrypto/ec/ec_mult.c b/src/lib/libcrypto/ec/ec_mult.c
index 1b7eb4ec1b..c119410e4a 100644
--- a/src/lib/libcrypto/ec/ec_mult.c
+++ b/src/lib/libcrypto/ec/ec_mult.c
@@ -1,4 +1,4 @@
1/* $OpenBSD: ec_mult.c,v 1.43 2024/11/22 15:21:14 tb Exp $ */ 1/* $OpenBSD: ec_mult.c,v 1.44 2024/11/22 16:17:36 tb Exp $ */
2/* 2/*
3 * Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project. 3 * Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project.
4 */ 4 */
@@ -70,154 +70,95 @@
70#include "bn_local.h" 70#include "bn_local.h"
71#include "ec_local.h" 71#include "ec_local.h"
72 72
73/* 73static int
74 * This file implements the wNAF-based interleaving multi-exponentation method 74ec_window_bits(const BIGNUM *bn)
75 * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp>); 75{
76 * for multiplication with precomputation, we use wNAF splitting 76 int bits = BN_num_bits(bn);
77 * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#fastexp>). 77
78 */ 78 if (bits >= 2000)
79 return 6;
80 if (bits >= 800)
81 return 5;
82 if (bits >= 300)
83 return 4;
84 if (bits >= 70)
85 return 3;
86 if (bits >= 20)
87 return 2;
88
89 return 1;
90}
79 91
80/* Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'. 92static int
81 * This is an array r[] of values that are either zero or odd with an 93ec_compute_wNAF(const BIGNUM *bn, signed char **out_wNAF, size_t *out_wNAF_len,
82 * absolute value less than 2^w satisfying 94 size_t *out_len)
83 * scalar = \sum_j r[j]*2^j
84 * where at most one of any w+1 consecutive digits is non-zero
85 * with the exception that the most significant digit may be only
86 * w-1 zeros away from that next non-zero digit.
87 */
88static signed char *
89compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len)
90{ 95{
91 int window_val; 96 signed char *wNAF = NULL;
92 int ok = 0; 97 size_t wNAF_len = 1, len = 1;
93 signed char *r = NULL; 98 int digit, bit, next, mask, sign, wbits, window;
94 int sign = 1; 99 size_t i;
95 int bit, next_bit, mask; 100 int ret = 0;
96 size_t len = 0, j; 101
97 102 if (BN_is_zero(bn)) {
98 if (BN_is_zero(scalar)) { 103 if ((wNAF = calloc(1, 1)) == NULL) {
99 r = malloc(1);
100 if (!r) {
101 ECerror(ERR_R_MALLOC_FAILURE); 104 ECerror(ERR_R_MALLOC_FAILURE);
102 goto err; 105 goto err;
103 } 106 }
104 r[0] = 0;
105 *ret_len = 1;
106 return r;
107 }
108 if (w <= 0 || w > 7) {
109 /* 'signed char' can represent integers with
110 * absolute values less than 2^7 */
111 ECerror(ERR_R_INTERNAL_ERROR);
112 goto err;
113 }
114 bit = 1 << w; /* at most 128 */
115 next_bit = bit << 1; /* at most 256 */
116 mask = next_bit - 1; /* at most 255 */
117 107
118 if (BN_is_negative(scalar)) { 108 goto done;
119 sign = -1;
120 } 109 }
121 if (scalar->d == NULL || scalar->top == 0) { 110
122 ECerror(ERR_R_INTERNAL_ERROR); 111 wNAF_len = BN_num_bits(bn);
123 goto err; 112 if ((wNAF = calloc(1, wNAF_len + 1)) == NULL) {
124 }
125 len = BN_num_bits(scalar);
126 r = malloc(len + 1); /* modified wNAF may be one digit longer than
127 * binary representation (*ret_len will be
128 * set to the actual length, i.e. at most
129 * BN_num_bits(scalar) + 1) */
130 if (r == NULL) {
131 ECerror(ERR_R_MALLOC_FAILURE); 113 ECerror(ERR_R_MALLOC_FAILURE);
132 goto err; 114 goto err;
133 } 115 }
134 window_val = scalar->d[0] & mask;
135 j = 0;
136 while ((window_val != 0) || (j + w + 1 < len)) {
137 /* if j+w+1 >= len, window_val will not increase */
138 int digit = 0;
139
140 /* 0 <= window_val <= 2^(w+1) */
141 if (window_val & 1) {
142 /* 0 < window_val < 2^(w+1) */
143 if (window_val & bit) {
144 digit = window_val - next_bit; /* -2^w < digit < 0 */
145
146#if 1 /* modified wNAF */
147 if (j + w + 1 >= len) {
148 /*
149 * special case for generating
150 * modified wNAFs: no new bits will
151 * be added into window_val, so using
152 * a positive digit here will
153 * decrease the total length of the
154 * representation
155 */
156
157 digit = window_val & (mask >> 1); /* 0 < digit < 2^w */
158 }
159#endif
160 } else {
161 digit = window_val; /* 0 < digit < 2^w */
162 }
163 116
164 if (digit <= -bit || digit >= bit || !(digit & 1)) { 117 wbits = ec_window_bits(bn);
165 ECerror(ERR_R_INTERNAL_ERROR); 118 len = 1 << (wbits - 1);
166 goto err;
167 }
168 window_val -= digit;
169
170 /*
171 * now window_val is 0 or 2^(w+1) in standard wNAF
172 * generation; for modified window NAFs, it may also
173 * be 2^w
174 */
175 if (window_val != 0 && window_val != next_bit && window_val != bit) {
176 ECerror(ERR_R_INTERNAL_ERROR);
177 goto err;
178 }
179 }
180 r[j++] = sign * digit;
181 119
182 window_val >>= 1; 120 bit = 1 << wbits;
183 window_val += bit * BN_is_bit_set(scalar, j + w); 121 next = bit << 1;
122 mask = next - 1;
184 123
185 if (window_val > next_bit) { 124 sign = BN_is_negative(bn) ? -1 : 1;
186 ECerror(ERR_R_INTERNAL_ERROR); 125
187 goto err; 126 window = bn->d[0] & mask;
127 i = 0;
128 while (window != 0 || i + wbits + 1 < wNAF_len) {
129 digit = 0;
130
131 if ((window & 1) != 0) {
132 digit = window;
133 if ((window & bit) != 0) {
134 digit = window - next;
135
136 if (i + wbits + 1 >= wNAF_len)
137 digit = window & (mask >> 1);
138 }
139 window -= digit;
188 } 140 }
189 }
190 141
191 if (j > len + 1) { 142 wNAF[i++] = sign * digit;
192 ECerror(ERR_R_INTERNAL_ERROR); 143 window >>= 1;
193 goto err; 144 window += bit * BN_is_bit_set(bn, i + wbits);
194 } 145 }
195 len = j;
196 ok = 1;
197 146
198 err: 147 wNAF_len = i;
199 if (!ok) {
200 free(r);
201 r = NULL;
202 }
203 if (ok)
204 *ret_len = len;
205 return r;
206}
207 148
149 done:
150 *out_wNAF = wNAF;
151 wNAF = NULL;
152 *out_wNAF_len = wNAF_len;
153 *out_len = len;
208 154
209/* TODO: table should be optimised for the wNAF-based implementation, 155 ret = 1;
210 * sometimes smaller windows will give better performance 156
211 * (thus the boundaries should be increased) 157 err:
212 */ 158 free(wNAF);
213#define EC_window_bits_for_scalar_size(b) \ 159
214 ((size_t) \ 160 return ret;
215 ((b) >= 2000 ? 6 : \ 161}
216 (b) >= 800 ? 5 : \
217 (b) >= 300 ? 4 : \
218 (b) >= 70 ? 3 : \
219 (b) >= 20 ? 2 : \
220 1))
221 162
222static int 163static int
223ec_compute_odd_multiples(const EC_GROUP *group, const EC_POINT *point, 164ec_compute_odd_multiples(const EC_GROUP *group, const EC_POINT *point,
@@ -270,8 +211,8 @@ ec_wNAF_precompute(const EC_GROUP *group, const BIGNUM *m, const EC_POINT *point
270 EC_POINT **val = NULL; 211 EC_POINT **val = NULL;
271 size_t val_len = 0; 212 size_t val_len = 0;
272 const EC_POINT *generator; 213 const EC_POINT *generator;
273 size_t wsize[2] = { 0 }; 214 size_t len[2] = { 0 };
274 size_t i, len0, len1; 215 size_t i;
275 int ret = 0; 216 int ret = 0;
276 217
277 *out_val = NULL; 218 *out_val = NULL;
@@ -282,29 +223,23 @@ ec_wNAF_precompute(const EC_GROUP *group, const BIGNUM *m, const EC_POINT *point
282 goto err; 223 goto err;
283 } 224 }
284 225
285 wsize[0] = EC_window_bits_for_scalar_size(BN_num_bits(m)); 226 if (!ec_compute_wNAF(m, &wNAF[0], &wNAF_len[0], &len[0]))
286 if ((wNAF[0] = compute_wNAF(m, wsize[0], &wNAF_len[0])) == NULL)
287 goto err; 227 goto err;
288 228 if (!ec_compute_wNAF(n, &wNAF[1], &wNAF_len[1], &len[1]))
289 wsize[1] = EC_window_bits_for_scalar_size(BN_num_bits(n));
290 if ((wNAF[1] = compute_wNAF(n, wsize[1], &wNAF_len[1])) == NULL)
291 goto err; 229 goto err;
292 230
293 len0 = 1 << (wsize[0] - 1); 231 if ((val = calloc(len[0] + len[1], sizeof(*val))) == NULL) {
294 len1 = 1 << (wsize[1] - 1);
295
296 if ((val = calloc(len0 + len1, sizeof(*val))) == NULL) {
297 ECerror(ERR_R_MALLOC_FAILURE); 232 ECerror(ERR_R_MALLOC_FAILURE);
298 goto err; 233 goto err;
299 } 234 }
300 val_len = len0 + len1; 235 val_len = len[0] + len[1];
301 236
302 row[0] = &val[0]; 237 row[0] = &val[0];
303 row[1] = &val[len0]; 238 row[1] = &val[len[0]];
304 239
305 if (!ec_compute_odd_multiples(group, generator, row[0], len0, ctx)) 240 if (!ec_compute_odd_multiples(group, generator, row[0], len[0], ctx))
306 goto err; 241 goto err;
307 if (!ec_compute_odd_multiples(group, point, row[1], len1, ctx)) 242 if (!ec_compute_odd_multiples(group, point, row[1], len[1], ctx))
308 goto err; 243 goto err;
309 244
310 if (!EC_POINTs_make_affine(group, val_len, val, ctx)) 245 if (!EC_POINTs_make_affine(group, val_len, val, ctx))
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-22 02:48:59 +0000