ec_mult.c 23 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910
  1. /* crypto/ec/ec_mult.c */
  2. /*
  3. * Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project.
  4. */
  5. /* ====================================================================
  6. * Copyright (c) 1998-2003 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. #include <string.h>
  64. #include <openssl/err.h>
  65. #include "ec_lcl.h"
  66. /*
  67. * This file implements the wNAF-based interleaving multi-exponentation method
  68. * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp>);
  69. * for multiplication with precomputation, we use wNAF splitting
  70. * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#fastexp>).
  71. */
  72. /* structure for precomputed multiples of the generator */
  73. typedef struct ec_pre_comp_st {
  74. const EC_GROUP *group; /* parent EC_GROUP object */
  75. size_t blocksize; /* block size for wNAF splitting */
  76. size_t numblocks; /* max. number of blocks for which we have precomputation */
  77. size_t w; /* window size */
  78. EC_POINT **points; /* array with pre-calculated multiples of generator:
  79. * 'num' pointers to EC_POINT objects followed by a NULL */
  80. size_t num; /* numblocks * 2^(w-1) */
  81. int references;
  82. } EC_PRE_COMP;
  83. /* functions to manage EC_PRE_COMP within the EC_GROUP extra_data framework */
  84. static void *ec_pre_comp_dup(void *);
  85. static void ec_pre_comp_free(void *);
  86. static void ec_pre_comp_clear_free(void *);
  87. static EC_PRE_COMP *ec_pre_comp_new(const EC_GROUP *group)
  88. {
  89. EC_PRE_COMP *ret = NULL;
  90. if (!group)
  91. return NULL;
  92. ret = (EC_PRE_COMP *)OPENSSL_malloc(sizeof(EC_PRE_COMP));
  93. if (!ret)
  94. return ret;
  95. ret->group = group;
  96. ret->blocksize = 8; /* default */
  97. ret->numblocks = 0;
  98. ret->w = 4; /* default */
  99. ret->points = NULL;
  100. ret->num = 0;
  101. ret->references = 1;
  102. return ret;
  103. }
  104. static void *ec_pre_comp_dup(void *src_)
  105. {
  106. EC_PRE_COMP *src = src_;
  107. /* no need to actually copy, these objects never change! */
  108. CRYPTO_add(&src->references, 1, CRYPTO_LOCK_EC_PRE_COMP);
  109. return src_;
  110. }
  111. static void ec_pre_comp_free(void *pre_)
  112. {
  113. int i;
  114. EC_PRE_COMP *pre = pre_;
  115. if (!pre)
  116. return;
  117. i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP);
  118. if (i > 0)
  119. return;
  120. if (pre->points)
  121. {
  122. EC_POINT **p;
  123. for (p = pre->points; *p != NULL; p++)
  124. EC_POINT_free(*p);
  125. OPENSSL_free(pre->points);
  126. }
  127. OPENSSL_free(pre);
  128. }
  129. static void ec_pre_comp_clear_free(void *pre_)
  130. {
  131. int i;
  132. EC_PRE_COMP *pre = pre_;
  133. if (!pre)
  134. return;
  135. i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP);
  136. if (i > 0)
  137. return;
  138. if (pre->points)
  139. {
  140. EC_POINT **p;
  141. for (p = pre->points; *p != NULL; p++)
  142. EC_POINT_clear_free(*p);
  143. OPENSSL_cleanse(pre->points, sizeof pre->points);
  144. OPENSSL_free(pre->points);
  145. }
  146. OPENSSL_cleanse(pre, sizeof pre);
  147. OPENSSL_free(pre);
  148. }
  149. /* Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.
  150. * This is an array r[] of values that are either zero or odd with an
  151. * absolute value less than 2^w satisfying
  152. * scalar = \sum_j r[j]*2^j
  153. * where at most one of any w+1 consecutive digits is non-zero
  154. * with the exception that the most significant digit may be only
  155. * w-1 zeros away from that next non-zero digit.
  156. */
  157. static signed char *compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len)
  158. {
  159. int window_val;
  160. int ok = 0;
  161. signed char *r = NULL;
  162. int sign = 1;
  163. int bit, next_bit, mask;
  164. size_t len = 0, j;
  165. if (w <= 0 || w > 7) /* 'signed char' can represent integers with absolute values less than 2^7 */
  166. {
  167. ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
  168. goto err;
  169. }
  170. bit = 1 << w; /* at most 128 */
  171. next_bit = bit << 1; /* at most 256 */
  172. mask = next_bit - 1; /* at most 255 */
  173. if (BN_is_negative(scalar))
  174. {
  175. sign = -1;
  176. }
  177. len = BN_num_bits(scalar);
  178. r = OPENSSL_malloc(len + 1); /* modified wNAF may be one digit longer than binary representation
  179. * (*ret_len will be set to the actual length, i.e. at most
  180. * BN_num_bits(scalar) + 1) */
  181. if (r == NULL) goto err;
  182. if (scalar->d == NULL || scalar->top == 0)
  183. {
  184. ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
  185. goto err;
  186. }
  187. window_val = scalar->d[0] & mask;
  188. j = 0;
  189. while ((window_val != 0) || (j + w + 1 < len)) /* if j+w+1 >= len, window_val will not increase */
  190. {
  191. int digit = 0;
  192. /* 0 <= window_val <= 2^(w+1) */
  193. if (window_val & 1)
  194. {
  195. /* 0 < window_val < 2^(w+1) */
  196. if (window_val & bit)
  197. {
  198. digit = window_val - next_bit; /* -2^w < digit < 0 */
  199. #if 1 /* modified wNAF */
  200. if (j + w + 1 >= len)
  201. {
  202. /* special case for generating modified wNAFs:
  203. * no new bits will be added into window_val,
  204. * so using a positive digit here will decrease
  205. * the total length of the representation */
  206. digit = window_val & (mask >> 1); /* 0 < digit < 2^w */
  207. }
  208. #endif
  209. }
  210. else
  211. {
  212. digit = window_val; /* 0 < digit < 2^w */
  213. }
  214. if (digit <= -bit || digit >= bit || !(digit & 1))
  215. {
  216. ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
  217. goto err;
  218. }
  219. window_val -= digit;
  220. /* now window_val is 0 or 2^(w+1) in standard wNAF generation;
  221. * for modified window NAFs, it may also be 2^w
  222. */
  223. if (window_val != 0 && window_val != next_bit && window_val != bit)
  224. {
  225. ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
  226. goto err;
  227. }
  228. }
  229. r[j++] = sign * digit;
  230. window_val >>= 1;
  231. window_val += bit * BN_is_bit_set(scalar, j + w);
  232. if (window_val > next_bit)
  233. {
  234. ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
  235. goto err;
  236. }
  237. }
  238. if (j > len + 1)
  239. {
  240. ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
  241. goto err;
  242. }
  243. len = j;
  244. ok = 1;
  245. err:
  246. if (!ok)
  247. {
  248. OPENSSL_free(r);
  249. r = NULL;
  250. }
  251. if (ok)
  252. *ret_len = len;
  253. return r;
  254. }
  255. /* TODO: table should be optimised for the wNAF-based implementation,
  256. * sometimes smaller windows will give better performance
  257. * (thus the boundaries should be increased)
  258. */
  259. #define EC_window_bits_for_scalar_size(b) \
  260. ((size_t) \
  261. ((b) >= 2000 ? 6 : \
  262. (b) >= 800 ? 5 : \
  263. (b) >= 300 ? 4 : \
  264. (b) >= 70 ? 3 : \
  265. (b) >= 20 ? 2 : \
  266. 1))
  267. /* Compute
  268. * \sum scalars[i]*points[i],
  269. * also including
  270. * scalar*generator
  271. * in the addition if scalar != NULL
  272. */
  273. int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
  274. size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx)
  275. {
  276. BN_CTX *new_ctx = NULL;
  277. const EC_POINT *generator = NULL;
  278. EC_POINT *tmp = NULL;
  279. size_t totalnum;
  280. size_t blocksize = 0, numblocks = 0; /* for wNAF splitting */
  281. size_t pre_points_per_block = 0;
  282. size_t i, j;
  283. int k;
  284. int r_is_inverted = 0;
  285. int r_is_at_infinity = 1;
  286. size_t *wsize = NULL; /* individual window sizes */
  287. signed char **wNAF = NULL; /* individual wNAFs */
  288. size_t *wNAF_len = NULL;
  289. size_t max_len = 0;
  290. size_t num_val;
  291. EC_POINT **val = NULL; /* precomputation */
  292. EC_POINT **v;
  293. EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' or 'pre_comp->points' */
  294. const EC_PRE_COMP *pre_comp = NULL;
  295. int num_scalar = 0; /* flag: will be set to 1 if 'scalar' must be treated like other scalars,
  296. * i.e. precomputation is not available */
  297. int ret = 0;
  298. if (group->meth != r->meth)
  299. {
  300. ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS);
  301. return 0;
  302. }
  303. if ((scalar == NULL) && (num == 0))
  304. {
  305. return EC_POINT_set_to_infinity(group, r);
  306. }
  307. for (i = 0; i < num; i++)
  308. {
  309. if (group->meth != points[i]->meth)
  310. {
  311. ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS);
  312. return 0;
  313. }
  314. }
  315. if (ctx == NULL)
  316. {
  317. ctx = new_ctx = BN_CTX_new();
  318. if (ctx == NULL)
  319. goto err;
  320. }
  321. if (scalar != NULL)
  322. {
  323. generator = EC_GROUP_get0_generator(group);
  324. if (generator == NULL)
  325. {
  326. ECerr(EC_F_EC_WNAF_MUL, EC_R_UNDEFINED_GENERATOR);
  327. goto err;
  328. }
  329. /* look if we can use precomputed multiples of generator */
  330. pre_comp = EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free);
  331. if (pre_comp && pre_comp->numblocks && (EC_POINT_cmp(group, generator, pre_comp->points[0], ctx) == 0))
  332. {
  333. blocksize = pre_comp->blocksize;
  334. /* determine maximum number of blocks that wNAF splitting may yield
  335. * (NB: maximum wNAF length is bit length plus one) */
  336. numblocks = (BN_num_bits(scalar) / blocksize) + 1;
  337. /* we cannot use more blocks than we have precomputation for */
  338. if (numblocks > pre_comp->numblocks)
  339. numblocks = pre_comp->numblocks;
  340. pre_points_per_block = 1u << (pre_comp->w - 1);
  341. /* check that pre_comp looks sane */
  342. if (pre_comp->num != (pre_comp->numblocks * pre_points_per_block))
  343. {
  344. ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
  345. goto err;
  346. }
  347. }
  348. else
  349. {
  350. /* can't use precomputation */
  351. pre_comp = NULL;
  352. numblocks = 1;
  353. num_scalar = 1; /* treat 'scalar' like 'num'-th element of 'scalars' */
  354. }
  355. }
  356. totalnum = num + numblocks;
  357. wsize = OPENSSL_malloc(totalnum * sizeof wsize[0]);
  358. wNAF_len = OPENSSL_malloc(totalnum * sizeof wNAF_len[0]);
  359. wNAF = OPENSSL_malloc((totalnum + 1) * sizeof wNAF[0]); /* includes space for pivot */
  360. val_sub = OPENSSL_malloc(totalnum * sizeof val_sub[0]);
  361. if (!wsize || !wNAF_len || !wNAF || !val_sub)
  362. goto err;
  363. wNAF[0] = NULL; /* preliminary pivot */
  364. /* num_val will be the total number of temporarily precomputed points */
  365. num_val = 0;
  366. for (i = 0; i < num + num_scalar; i++)
  367. {
  368. size_t bits;
  369. bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar);
  370. wsize[i] = EC_window_bits_for_scalar_size(bits);
  371. num_val += 1u << (wsize[i] - 1);
  372. wNAF[i + 1] = NULL; /* make sure we always have a pivot */
  373. wNAF[i] = compute_wNAF((i < num ? scalars[i] : scalar), wsize[i], &wNAF_len[i]);
  374. if (wNAF[i] == NULL)
  375. goto err;
  376. if (wNAF_len[i] > max_len)
  377. max_len = wNAF_len[i];
  378. }
  379. if (numblocks)
  380. {
  381. /* we go here iff scalar != NULL */
  382. if (pre_comp == NULL)
  383. {
  384. if (num_scalar != 1)
  385. {
  386. ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
  387. goto err;
  388. }
  389. /* we have already generated a wNAF for 'scalar' */
  390. }
  391. else
  392. {
  393. signed char *tmp_wNAF = NULL;
  394. size_t tmp_len = 0;
  395. if (num_scalar != 0)
  396. {
  397. ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
  398. goto err;
  399. }
  400. /* use the window size for which we have precomputation */
  401. wsize[num] = pre_comp->w;
  402. tmp_wNAF = compute_wNAF(scalar, wsize[num], &tmp_len);
  403. if (!tmp_wNAF)
  404. goto err;
  405. if (tmp_len <= max_len)
  406. {
  407. /* One of the other wNAFs is at least as long
  408. * as the wNAF belonging to the generator,
  409. * so wNAF splitting will not buy us anything. */
  410. numblocks = 1;
  411. totalnum = num + 1; /* don't use wNAF splitting */
  412. wNAF[num] = tmp_wNAF;
  413. wNAF[num + 1] = NULL;
  414. wNAF_len[num] = tmp_len;
  415. if (tmp_len > max_len)
  416. max_len = tmp_len;
  417. /* pre_comp->points starts with the points that we need here: */
  418. val_sub[num] = pre_comp->points;
  419. }
  420. else
  421. {
  422. /* don't include tmp_wNAF directly into wNAF array
  423. * - use wNAF splitting and include the blocks */
  424. signed char *pp;
  425. EC_POINT **tmp_points;
  426. if (tmp_len < numblocks * blocksize)
  427. {
  428. /* possibly we can do with fewer blocks than estimated */
  429. numblocks = (tmp_len + blocksize - 1) / blocksize;
  430. if (numblocks > pre_comp->numblocks)
  431. {
  432. ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
  433. goto err;
  434. }
  435. totalnum = num + numblocks;
  436. }
  437. /* split wNAF in 'numblocks' parts */
  438. pp = tmp_wNAF;
  439. tmp_points = pre_comp->points;
  440. for (i = num; i < totalnum; i++)
  441. {
  442. if (i < totalnum - 1)
  443. {
  444. wNAF_len[i] = blocksize;
  445. if (tmp_len < blocksize)
  446. {
  447. ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
  448. goto err;
  449. }
  450. tmp_len -= blocksize;
  451. }
  452. else
  453. /* last block gets whatever is left
  454. * (this could be more or less than 'blocksize'!) */
  455. wNAF_len[i] = tmp_len;
  456. wNAF[i + 1] = NULL;
  457. wNAF[i] = OPENSSL_malloc(wNAF_len[i]);
  458. if (wNAF[i] == NULL)
  459. {
  460. OPENSSL_free(tmp_wNAF);
  461. goto err;
  462. }
  463. memcpy(wNAF[i], pp, wNAF_len[i]);
  464. if (wNAF_len[i] > max_len)
  465. max_len = wNAF_len[i];
  466. if (*tmp_points == NULL)
  467. {
  468. ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
  469. OPENSSL_free(tmp_wNAF);
  470. goto err;
  471. }
  472. val_sub[i] = tmp_points;
  473. tmp_points += pre_points_per_block;
  474. pp += blocksize;
  475. }
  476. OPENSSL_free(tmp_wNAF);
  477. }
  478. }
  479. }
  480. /* All points we precompute now go into a single array 'val'.
  481. * 'val_sub[i]' is a pointer to the subarray for the i-th point,
  482. * or to a subarray of 'pre_comp->points' if we already have precomputation. */
  483. val = OPENSSL_malloc((num_val + 1) * sizeof val[0]);
  484. if (val == NULL) goto err;
  485. val[num_val] = NULL; /* pivot element */
  486. /* allocate points for precomputation */
  487. v = val;
  488. for (i = 0; i < num + num_scalar; i++)
  489. {
  490. val_sub[i] = v;
  491. for (j = 0; j < (1u << (wsize[i] - 1)); j++)
  492. {
  493. *v = EC_POINT_new(group);
  494. if (*v == NULL) goto err;
  495. v++;
  496. }
  497. }
  498. if (!(v == val + num_val))
  499. {
  500. ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
  501. goto err;
  502. }
  503. if (!(tmp = EC_POINT_new(group)))
  504. goto err;
  505. /* prepare precomputed values:
  506. * val_sub[i][0] := points[i]
  507. * val_sub[i][1] := 3 * points[i]
  508. * val_sub[i][2] := 5 * points[i]
  509. * ...
  510. */
  511. for (i = 0; i < num + num_scalar; i++)
  512. {
  513. if (i < num)
  514. {
  515. if (!EC_POINT_copy(val_sub[i][0], points[i])) goto err;
  516. }
  517. else
  518. {
  519. if (!EC_POINT_copy(val_sub[i][0], generator)) goto err;
  520. }
  521. if (wsize[i] > 1)
  522. {
  523. if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) goto err;
  524. for (j = 1; j < (1u << (wsize[i] - 1)); j++)
  525. {
  526. if (!EC_POINT_add(group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) goto err;
  527. }
  528. }
  529. }
  530. #if 1 /* optional; EC_window_bits_for_scalar_size assumes we do this step */
  531. if (!EC_POINTs_make_affine(group, num_val, val, ctx))
  532. goto err;
  533. #endif
  534. r_is_at_infinity = 1;
  535. for (k = max_len - 1; k >= 0; k--)
  536. {
  537. if (!r_is_at_infinity)
  538. {
  539. if (!EC_POINT_dbl(group, r, r, ctx)) goto err;
  540. }
  541. for (i = 0; i < totalnum; i++)
  542. {
  543. if (wNAF_len[i] > (size_t)k)
  544. {
  545. int digit = wNAF[i][k];
  546. int is_neg;
  547. if (digit)
  548. {
  549. is_neg = digit < 0;
  550. if (is_neg)
  551. digit = -digit;
  552. if (is_neg != r_is_inverted)
  553. {
  554. if (!r_is_at_infinity)
  555. {
  556. if (!EC_POINT_invert(group, r, ctx)) goto err;
  557. }
  558. r_is_inverted = !r_is_inverted;
  559. }
  560. /* digit > 0 */
  561. if (r_is_at_infinity)
  562. {
  563. if (!EC_POINT_copy(r, val_sub[i][digit >> 1])) goto err;
  564. r_is_at_infinity = 0;
  565. }
  566. else
  567. {
  568. if (!EC_POINT_add(group, r, r, val_sub[i][digit >> 1], ctx)) goto err;
  569. }
  570. }
  571. }
  572. }
  573. }
  574. if (r_is_at_infinity)
  575. {
  576. if (!EC_POINT_set_to_infinity(group, r)) goto err;
  577. }
  578. else
  579. {
  580. if (r_is_inverted)
  581. if (!EC_POINT_invert(group, r, ctx)) goto err;
  582. }
  583. ret = 1;
  584. err:
  585. if (new_ctx != NULL)
  586. BN_CTX_free(new_ctx);
  587. if (tmp != NULL)
  588. EC_POINT_free(tmp);
  589. if (wsize != NULL)
  590. OPENSSL_free(wsize);
  591. if (wNAF_len != NULL)
  592. OPENSSL_free(wNAF_len);
  593. if (wNAF != NULL)
  594. {
  595. signed char **w;
  596. for (w = wNAF; *w != NULL; w++)
  597. OPENSSL_free(*w);
  598. OPENSSL_free(wNAF);
  599. }
  600. if (val != NULL)
  601. {
  602. for (v = val; *v != NULL; v++)
  603. EC_POINT_clear_free(*v);
  604. OPENSSL_free(val);
  605. }
  606. if (val_sub != NULL)
  607. {
  608. OPENSSL_free(val_sub);
  609. }
  610. return ret;
  611. }
  612. /* ec_wNAF_precompute_mult()
  613. * creates an EC_PRE_COMP object with preprecomputed multiples of the generator
  614. * for use with wNAF splitting as implemented in ec_wNAF_mul().
  615. *
  616. * 'pre_comp->points' is an array of multiples of the generator
  617. * of the following form:
  618. * points[0] = generator;
  619. * points[1] = 3 * generator;
  620. * ...
  621. * points[2^(w-1)-1] = (2^(w-1)-1) * generator;
  622. * points[2^(w-1)] = 2^blocksize * generator;
  623. * points[2^(w-1)+1] = 3 * 2^blocksize * generator;
  624. * ...
  625. * points[2^(w-1)*(numblocks-1)-1] = (2^(w-1)) * 2^(blocksize*(numblocks-2)) * generator
  626. * points[2^(w-1)*(numblocks-1)] = 2^(blocksize*(numblocks-1)) * generator
  627. * ...
  628. * points[2^(w-1)*numblocks-1] = (2^(w-1)) * 2^(blocksize*(numblocks-1)) * generator
  629. * points[2^(w-1)*numblocks] = NULL
  630. */
  631. int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
  632. {
  633. const EC_POINT *generator;
  634. EC_POINT *tmp_point = NULL, *base = NULL, **var;
  635. BN_CTX *new_ctx = NULL;
  636. BIGNUM *order;
  637. size_t i, bits, w, pre_points_per_block, blocksize, numblocks, num;
  638. EC_POINT **points = NULL;
  639. EC_PRE_COMP *pre_comp;
  640. int ret = 0;
  641. /* if there is an old EC_PRE_COMP object, throw it away */
  642. EC_EX_DATA_free_data(&group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free);
  643. if ((pre_comp = ec_pre_comp_new(group)) == NULL)
  644. return 0;
  645. generator = EC_GROUP_get0_generator(group);
  646. if (generator == NULL)
  647. {
  648. ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNDEFINED_GENERATOR);
  649. goto err;
  650. }
  651. if (ctx == NULL)
  652. {
  653. ctx = new_ctx = BN_CTX_new();
  654. if (ctx == NULL)
  655. goto err;
  656. }
  657. BN_CTX_start(ctx);
  658. order = BN_CTX_get(ctx);
  659. if (order == NULL) goto err;
  660. if (!EC_GROUP_get_order(group, order, ctx)) goto err;
  661. if (BN_is_zero(order))
  662. {
  663. ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNKNOWN_ORDER);
  664. goto err;
  665. }
  666. bits = BN_num_bits(order);
  667. /* The following parameters mean we precompute (approximately)
  668. * one point per bit.
  669. *
  670. * TBD: The combination 8, 4 is perfect for 160 bits; for other
  671. * bit lengths, other parameter combinations might provide better
  672. * efficiency.
  673. */
  674. blocksize = 8;
  675. w = 4;
  676. if (EC_window_bits_for_scalar_size(bits) > w)
  677. {
  678. /* let's not make the window too small ... */
  679. w = EC_window_bits_for_scalar_size(bits);
  680. }
  681. numblocks = (bits + blocksize - 1) / blocksize; /* max. number of blocks to use for wNAF splitting */
  682. pre_points_per_block = 1u << (w - 1);
  683. num = pre_points_per_block * numblocks; /* number of points to compute and store */
  684. points = OPENSSL_malloc(sizeof (EC_POINT*)*(num + 1));
  685. if (!points)
  686. {
  687. ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
  688. goto err;
  689. }
  690. var = points;
  691. var[num] = NULL; /* pivot */
  692. for (i = 0; i < num; i++)
  693. {
  694. if ((var[i] = EC_POINT_new(group)) == NULL)
  695. {
  696. ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
  697. goto err;
  698. }
  699. }
  700. if (!(tmp_point = EC_POINT_new(group)) || !(base = EC_POINT_new(group)))
  701. {
  702. ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
  703. goto err;
  704. }
  705. if (!EC_POINT_copy(base, generator))
  706. goto err;
  707. /* do the precomputation */
  708. for (i = 0; i < numblocks; i++)
  709. {
  710. size_t j;
  711. if (!EC_POINT_dbl(group, tmp_point, base, ctx))
  712. goto err;
  713. if (!EC_POINT_copy(*var++, base))
  714. goto err;
  715. for (j = 1; j < pre_points_per_block; j++, var++)
  716. {
  717. /* calculate odd multiples of the current base point */
  718. if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx))
  719. goto err;
  720. }
  721. if (i < numblocks - 1)
  722. {
  723. /* get the next base (multiply current one by 2^blocksize) */
  724. size_t k;
  725. if (blocksize <= 2)
  726. {
  727. ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_INTERNAL_ERROR);
  728. goto err;
  729. }
  730. if (!EC_POINT_dbl(group, base, tmp_point, ctx))
  731. goto err;
  732. for (k = 2; k < blocksize; k++)
  733. {
  734. if (!EC_POINT_dbl(group,base,base,ctx))
  735. goto err;
  736. }
  737. }
  738. }
  739. if (!EC_POINTs_make_affine(group, num, points, ctx))
  740. goto err;
  741. pre_comp->group = group;
  742. pre_comp->blocksize = blocksize;
  743. pre_comp->numblocks = numblocks;
  744. pre_comp->w = w;
  745. pre_comp->points = points;
  746. points = NULL;
  747. pre_comp->num = num;
  748. if (!EC_EX_DATA_set_data(&group->extra_data, pre_comp,
  749. ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free))
  750. goto err;
  751. pre_comp = NULL;
  752. ret = 1;
  753. err:
  754. if (ctx != NULL)
  755. BN_CTX_end(ctx);
  756. if (new_ctx != NULL)
  757. BN_CTX_free(new_ctx);
  758. if (pre_comp)
  759. ec_pre_comp_free(pre_comp);
  760. if (points)
  761. {
  762. EC_POINT **p;
  763. for (p = points; *p != NULL; p++)
  764. EC_POINT_free(*p);
  765. OPENSSL_free(points);
  766. }
  767. if (tmp_point)
  768. EC_POINT_free(tmp_point);
  769. if (base)
  770. EC_POINT_free(base);
  771. return ret;
  772. }
  773. int ec_wNAF_have_precompute_mult(const EC_GROUP *group)
  774. {
  775. if (EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free) != NULL)
  776. return 1;
  777. else
  778. return 0;
  779. }