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 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 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 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 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 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 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 * 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 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 * 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 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