开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 游戏 > 其他游戏 > 查看源码
ec_mult.c
资源名称：wow-313-source.rar　[点击查看]
上传用户：yisoukefu
上传日期：2020-08-09
资源大小：39506k
文件大小：23k
源码类别：

其他游戏

开发平台：

Visual C++

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