1 /* $OpenBSD: ec_mult.c,v 1.57 2025/01/11 13:58:31 tb Exp $ */
2 /*
3 * Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project.
4 */
5 /* ====================================================================
6 * Copyright (c) 1998-2007 The OpenSSL Project. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 *
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
18 * distribution.
19 *
20 * 3. All advertising materials mentioning features or use of this
21 * software must display the following acknowledgment:
22 * "This product includes software developed by the OpenSSL Project
23 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
24 *
25 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
26 * endorse or promote products derived from this software without
27 * prior written permission. For written permission, please contact
28 * openssl-core@openssl.org.
29 *
30 * 5. Products derived from this software may not be called "OpenSSL"
31 * nor may "OpenSSL" appear in their names without prior written
32 * permission of the OpenSSL Project.
33 *
34 * 6. Redistributions of any form whatsoever must retain the following
35 * acknowledgment:
36 * "This product includes software developed by the OpenSSL Project
37 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
38 *
39 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
40 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
41 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
42 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
43 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
44 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
45 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
46 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
48 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
49 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
50 * OF THE POSSIBILITY OF SUCH DAMAGE.
51 * ====================================================================
52 *
53 * This product includes cryptographic software written by Eric Young
54 * (eay@cryptsoft.com). This product includes software written by Tim
55 * Hudson (tjh@cryptsoft.com).
56 *
57 */
58 /* ====================================================================
59 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
60 * Portions of this software developed by SUN MICROSYSTEMS, INC.,
61 * and contributed to the OpenSSL project.
62 */
63
64 #include <stdint.h>
65 #include <stdlib.h>
66 #include <string.h>
67
68 #include <openssl/bn.h>
69 #include <openssl/ec.h>
70 #include <openssl/err.h>
71
72 #include "ec_local.h"
73
74 /* Holds the wNAF digits of bn and the corresponding odd multiples of point. */
75 struct ec_wnaf {
76 signed char *digits;
77 size_t num_digits;
78 EC_POINT **multiples;
79 size_t num_multiples;
80 };
81
82 static int
ec_window_bits(const BIGNUM * bn)83 ec_window_bits(const BIGNUM *bn)
84 {
85 int bits = BN_num_bits(bn);
86
87 if (bits >= 2000)
88 return 6;
89 if (bits >= 800)
90 return 5;
91 if (bits >= 300)
92 return 4;
93 if (bits >= 70)
94 return 3;
95 if (bits >= 20)
96 return 2;
97
98 return 1;
99 }
100
101 /*
102 * Width-(w+1) non-adjacent form of bn = \sum_j n_j 2^j, with odd n_j,
103 * where at most one of any (w+1) consecutive digits is non-zero.
104 */
105
106 static int
ec_compute_wnaf(const BIGNUM * bn,signed char * digits,size_t num_digits)107 ec_compute_wnaf(const BIGNUM *bn, signed char *digits, size_t num_digits)
108 {
109 int digit, bit, next, sign, wbits, window;
110 size_t i;
111 int ret = 0;
112
113 if (num_digits != BN_num_bits(bn) + 1) {
114 ECerror(ERR_R_INTERNAL_ERROR);
115 goto err;
116 }
117
118 sign = BN_is_negative(bn) ? -1 : 1;
119
120 wbits = ec_window_bits(bn);
121
122 bit = 1 << wbits;
123 next = bit << 1;
124
125 /* Extract the wbits + 1 lowest bits from bn into window. */
126 window = 0;
127 for (i = 0; i < wbits + 1; i++) {
128 if (BN_is_bit_set(bn, i))
129 window |= (1 << i);
130 }
131
132 /* Instead of bn >>= 1 in each iteration, slide window to the left. */
133 for (i = 0; i < num_digits; i++) {
134 digit = 0;
135
136 /*
137 * If window is odd, the i-th wNAF digit is window (mods 2^w),
138 * where mods is the signed modulo in (-2^w-1, 2^w-1]. Subtract
139 * the digit from window, so window is 0 or next, and add the
140 * digit to the wNAF digits.
141 */
142 if ((window & 1) != 0) {
143 digit = window;
144 if ((window & bit) != 0)
145 digit = window - next;
146 window -= digit;
147 }
148
149 digits[i] = sign * digit;
150
151 /* Slide the window to the left. */
152 window >>= 1;
153 window += bit * BN_is_bit_set(bn, i + wbits + 1);
154 }
155
156 ret = 1;
157
158 err:
159 return ret;
160 }
161
162 static int
ec_compute_odd_multiples(const EC_GROUP * group,const EC_POINT * point,EC_POINT ** multiples,size_t num_multiples,BN_CTX * ctx)163 ec_compute_odd_multiples(const EC_GROUP *group, const EC_POINT *point,
164 EC_POINT **multiples, size_t num_multiples, BN_CTX *ctx)
165 {
166 EC_POINT *doubled = NULL;
167 size_t i;
168 int ret = 0;
169
170 if (num_multiples < 1)
171 goto err;
172
173 if ((multiples[0] = EC_POINT_dup(point, group)) == NULL)
174 goto err;
175
176 if ((doubled = EC_POINT_new(group)) == NULL)
177 goto err;
178 if (!EC_POINT_dbl(group, doubled, point, ctx))
179 goto err;
180 for (i = 1; i < num_multiples; i++) {
181 if ((multiples[i] = EC_POINT_new(group)) == NULL)
182 goto err;
183 if (!EC_POINT_add(group, multiples[i], multiples[i - 1], doubled,
184 ctx))
185 goto err;
186 }
187
188 ret = 1;
189
190 err:
191 EC_POINT_free(doubled);
192
193 return ret;
194 }
195
196 /*
197 * Bring multiples held in wnaf0 and wnaf1 simultaneously into affine form
198 * so that the operations in the loop in ec_wnaf_mul() can take fast paths.
199 */
200
201 static int
ec_normalize_points(const EC_GROUP * group,struct ec_wnaf * wnaf0,struct ec_wnaf * wnaf1,BN_CTX * ctx)202 ec_normalize_points(const EC_GROUP *group, struct ec_wnaf *wnaf0,
203 struct ec_wnaf *wnaf1, BN_CTX *ctx)
204 {
205 EC_POINT **points0 = wnaf0->multiples, **points1 = wnaf1->multiples;
206 size_t len0 = wnaf0->num_multiples, len1 = wnaf1->num_multiples;
207 EC_POINT **val = NULL;
208 size_t len = 0;
209 int ret = 0;
210
211 if (len1 > SIZE_MAX - len0)
212 goto err;
213 len = len0 + len1;
214
215 if ((val = calloc(len, sizeof(*val))) == NULL) {
216 ECerror(ERR_R_MALLOC_FAILURE);
217 goto err;
218 }
219 memcpy(&val[0], points0, sizeof(*val) * len0);
220 memcpy(&val[len0], points1, sizeof(*val) * len1);
221
222 if (!group->meth->points_make_affine(group, len, val, ctx))
223 goto err;
224
225 ret = 1;
226
227 err:
228 free(val);
229
230 return ret;
231 }
232
233 static void
ec_points_free(EC_POINT ** points,size_t num_points)234 ec_points_free(EC_POINT **points, size_t num_points)
235 {
236 size_t i;
237
238 if (points == NULL)
239 return;
240
241 for (i = 0; i < num_points; i++)
242 EC_POINT_free(points[i]);
243 free(points);
244 }
245
246 static void
ec_wnaf_free(struct ec_wnaf * wnaf)247 ec_wnaf_free(struct ec_wnaf *wnaf)
248 {
249 if (wnaf == NULL)
250 return;
251
252 free(wnaf->digits);
253 ec_points_free(wnaf->multiples, wnaf->num_multiples);
254 free(wnaf);
255 }
256
257 /*
258 * Calculate wNAF splitting of bn and the corresponding odd multiples of point.
259 */
260
261 static struct ec_wnaf *
ec_wnaf_new(const EC_GROUP * group,const EC_POINT * point,const BIGNUM * bn,BN_CTX * ctx)262 ec_wnaf_new(const EC_GROUP *group, const EC_POINT *point, const BIGNUM *bn,
263 BN_CTX *ctx)
264 {
265 struct ec_wnaf *wnaf;
266
267 if ((wnaf = calloc(1, sizeof(*wnaf))) == NULL)
268 goto err;
269
270 wnaf->num_digits = BN_num_bits(bn) + 1;
271 if ((wnaf->digits = calloc(wnaf->num_digits,
272 sizeof(*wnaf->digits))) == NULL)
273 goto err;
274
275 if (!ec_compute_wnaf(bn, wnaf->digits, wnaf->num_digits))
276 goto err;
277
278 wnaf->num_multiples = 1ULL << (ec_window_bits(bn) - 1);
279 if ((wnaf->multiples = calloc(wnaf->num_multiples,
280 sizeof(*wnaf->multiples))) == NULL)
281 goto err;
282
283 if (!ec_compute_odd_multiples(group, point, wnaf->multiples,
284 wnaf->num_multiples, ctx))
285 goto err;
286
287 return wnaf;
288
289 err:
290 ec_wnaf_free(wnaf);
291
292 return NULL;
293 }
294
295 static signed char
ec_wnaf_digit(struct ec_wnaf * wnaf,size_t idx)296 ec_wnaf_digit(struct ec_wnaf *wnaf, size_t idx)
297 {
298 if (idx >= wnaf->num_digits)
299 return 0;
300
301 return wnaf->digits[idx];
302 }
303
304 static const EC_POINT *
ec_wnaf_multiple(struct ec_wnaf * wnaf,signed char digit)305 ec_wnaf_multiple(struct ec_wnaf *wnaf, signed char digit)
306 {
307 if (digit < 0)
308 return NULL;
309 if (digit >= 2 * wnaf->num_multiples)
310 return NULL;
311
312 return wnaf->multiples[digit >> 1];
313 }
314
315 /*
316 * Compute r = generator * m + point * n in non-constant time.
317 */
318
319 int
ec_wnaf_mul(const EC_GROUP * group,EC_POINT * r,const BIGNUM * m,const EC_POINT * point,const BIGNUM * n,BN_CTX * ctx)320 ec_wnaf_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *m,
321 const EC_POINT *point, const BIGNUM *n, BN_CTX *ctx)
322 {
323 struct ec_wnaf *wnaf[2] = { NULL, NULL };
324 const EC_POINT *generator;
325 size_t i;
326 int k;
327 int r_is_inverted = 0;
328 size_t num_digits;
329 int ret = 0;
330
331 if (m == NULL || n == NULL) {
332 ECerror(ERR_R_PASSED_NULL_PARAMETER);
333 goto err;
334 }
335 if (group->meth != r->meth || group->meth != point->meth) {
336 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
337 goto err;
338 }
339
340 if ((generator = EC_GROUP_get0_generator(group)) == NULL) {
341 ECerror(EC_R_UNDEFINED_GENERATOR);
342 goto err;
343 }
344
345 if ((wnaf[0] = ec_wnaf_new(group, generator, m, ctx)) == NULL)
346 goto err;
347 if ((wnaf[1] = ec_wnaf_new(group, point, n, ctx)) == NULL)
348 goto err;
349
350 if (!ec_normalize_points(group, wnaf[0], wnaf[1], ctx))
351 goto err;
352
353 num_digits = wnaf[0]->num_digits;
354 if (wnaf[1]->num_digits > num_digits)
355 num_digits = wnaf[1]->num_digits;
356
357 /*
358 * Set r to the neutral element. Scan through the wNAF representations
359 * of m and n, starting at the most significant digit. Double r and for
360 * each wNAF digit of m add the digit times the generator, and for each
361 * wNAF digit of n add the digit times the point, adjusting the signs
362 * as appropriate.
363 */
364
365 if (!EC_POINT_set_to_infinity(group, r))
366 goto err;
367
368 for (k = num_digits - 1; k >= 0; k--) {
369 if (!EC_POINT_dbl(group, r, r, ctx))
370 goto err;
371
372 for (i = 0; i < 2; i++) {
373 const EC_POINT *multiple;
374 signed char digit;
375 int is_neg = 0;
376
377 if ((digit = ec_wnaf_digit(wnaf[i], k)) == 0)
378 continue;
379
380 if (digit < 0) {
381 is_neg = 1;
382 digit = -digit;
383 }
384
385 if (is_neg != r_is_inverted) {
386 if (!EC_POINT_invert(group, r, ctx))
387 goto err;
388 r_is_inverted = !r_is_inverted;
389 }
390
391 if ((multiple = ec_wnaf_multiple(wnaf[i], digit)) == NULL)
392 goto err;
393
394 if (!EC_POINT_add(group, r, r, multiple, ctx))
395 goto err;
396 }
397 }
398
399 if (r_is_inverted) {
400 if (!EC_POINT_invert(group, r, ctx))
401 goto err;
402 }
403
404 ret = 1;
405
406 err:
407 ec_wnaf_free(wnaf[0]);
408 ec_wnaf_free(wnaf[1]);
409
410 return ret;
411 }
412