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

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

其他游戏

开发平台：

Visual C++

ecp_smpl.c：源码内容
  1. /* crypto/ec/ecp_smpl.c */
  2. /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
  3.  * for the OpenSSL project. 
  4.  * Includes code written by Bodo Moeller for the OpenSSL project.
  5. */
  6. /* ====================================================================
  7.  * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
  8.  *
  9.  * Redistribution and use in source and binary forms, with or without
  10.  * modification, are permitted provided that the following conditions
  11.  * are met:
  12.  *
  13.  * 1. Redistributions of source code must retain the above copyright
  14.  *    notice, this list of conditions and the following disclaimer. 
  15.  *
  16.  * 2. Redistributions in binary form must reproduce the above copyright
  17.  *    notice, this list of conditions and the following disclaimer in
  18.  *    the documentation and/or other materials provided with the
  19.  *    distribution.
  20.  *
  21.  * 3. All advertising materials mentioning features or use of this
  22.  *    software must display the following acknowledgment:
  23.  *    "This product includes software developed by the OpenSSL Project
  24.  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  25.  *
  26.  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  27.  *    endorse or promote products derived from this software without
  28.  *    prior written permission. For written permission, please contact
  29.  *    openssl-core@openssl.org.
  30.  *
  31.  * 5. Products derived from this software may not be called "OpenSSL"
  32.  *    nor may "OpenSSL" appear in their names without prior written
  33.  *    permission of the OpenSSL Project.
  34.  *
  35.  * 6. Redistributions of any form whatsoever must retain the following
  36.  *    acknowledgment:
  37.  *    "This product includes software developed by the OpenSSL Project
  38.  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  39.  *
  40.  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  41.  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  43.  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  44.  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  45.  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  46.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  47.  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  49.  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  50.  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  51.  * OF THE POSSIBILITY OF SUCH DAMAGE.
  52.  * ====================================================================
  53.  *
  54.  * This product includes cryptographic software written by Eric Young
  55.  * (eay@cryptsoft.com).  This product includes software written by Tim
  56.  * Hudson (tjh@cryptsoft.com).
  57.  *
  58.  */
  59. /* ====================================================================
  60.  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
  61.  * Portions of this software developed by SUN MICROSYSTEMS, INC.,
  62.  * and contributed to the OpenSSL project.
  63.  */
  65. #include <openssl/err.h>
  66. #include <openssl/symhacks.h>
  68. #include "ec_lcl.h"
  70. const EC_METHOD *EC_GFp_simple_method(void)
  71. {
  72. static const EC_METHOD ret = {
  73. NID_X9_62_prime_field,
  74. ec_GFp_simple_group_init,
  75. ec_GFp_simple_group_finish,
  76. ec_GFp_simple_group_clear_finish,
  77. ec_GFp_simple_group_copy,
  78. ec_GFp_simple_group_set_curve,
  79. ec_GFp_simple_group_get_curve,
  80. ec_GFp_simple_group_get_degree,
  81. ec_GFp_simple_group_check_discriminant,
  82. ec_GFp_simple_point_init,
  83. ec_GFp_simple_point_finish,
  84. ec_GFp_simple_point_clear_finish,
  85. ec_GFp_simple_point_copy,
  86. ec_GFp_simple_point_set_to_infinity,
  87. ec_GFp_simple_set_Jprojective_coordinates_GFp,
  88. ec_GFp_simple_get_Jprojective_coordinates_GFp,
  89. ec_GFp_simple_point_set_affine_coordinates,
  90. ec_GFp_simple_point_get_affine_coordinates,
  91. ec_GFp_simple_set_compressed_coordinates,
  92. ec_GFp_simple_point2oct,
  93. ec_GFp_simple_oct2point,
  94. ec_GFp_simple_add,
  95. ec_GFp_simple_dbl,
  96. ec_GFp_simple_invert,
  97. ec_GFp_simple_is_at_infinity,
  98. ec_GFp_simple_is_on_curve,
  99. ec_GFp_simple_cmp,
  100. ec_GFp_simple_make_affine,
  101. ec_GFp_simple_points_make_affine,
  102. 0 /* mul */,
  103. 0 /* precompute_mult */,
  104. 0 /* have_precompute_mult */,
  105. ec_GFp_simple_field_mul,
  106. ec_GFp_simple_field_sqr,
  107. 0 /* field_div */,
  108. 0 /* field_encode */,
  109. 0 /* field_decode */,
  110. 0 /* field_set_to_one */ };
  112. return &ret;
  113. }
  116. /* Most method functions in this file are designed to work with
  117.  * non-trivial representations of field elements if necessary
  118.  * (see ecp_mont.c): while standard modular addition and subtraction
  119.  * are used, the field_mul and field_sqr methods will be used for
  120.  * multiplication, and field_encode and field_decode (if defined)
  121.  * will be used for converting between representations.
  123.  * Functions ec_GFp_simple_points_make_affine() and
  124.  * ec_GFp_simple_point_get_affine_coordinates() specifically assume
  125.  * that if a non-trivial representation is used, it is a Montgomery
  126.  * representation (i.e. 'encoding' means multiplying by some factor R).
  127.  */
  130. int ec_GFp_simple_group_init(EC_GROUP *group)
  131. {
  132. BN_init(&group->field);
  133. BN_init(&group->a);
  134. BN_init(&group->b);
  135. group->a_is_minus3 = 0;
  136. return 1;
  137. }
  140. void ec_GFp_simple_group_finish(EC_GROUP *group)
  141. {
  142. BN_free(&group->field);
  143. BN_free(&group->a);
  144. BN_free(&group->b);
  145. }
  148. void ec_GFp_simple_group_clear_finish(EC_GROUP *group)
  149. {
  150. BN_clear_free(&group->field);
  151. BN_clear_free(&group->a);
  152. BN_clear_free(&group->b);
  153. }
  156. int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
  157. {
  158. if (!BN_copy(&dest->field, &src->field)) return 0;
  159. if (!BN_copy(&dest->a, &src->a)) return 0;
  160. if (!BN_copy(&dest->b, &src->b)) return 0;
  162. dest->a_is_minus3 = src->a_is_minus3;
  164. return 1;
  165. }
  168. int ec_GFp_simple_group_set_curve(EC_GROUP *group,
  169. const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
  170. {
  171. int ret = 0;
  172. BN_CTX *new_ctx = NULL;
  173. BIGNUM *tmp_a;
  175. /* p must be a prime > 3 */
  176. if (BN_num_bits(p) <= 2 || !BN_is_odd(p))
  177. {
  178. ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD);
  179. return 0;
  180. }
  182. if (ctx == NULL)
  183. {
  184. ctx = new_ctx = BN_CTX_new();
  185. if (ctx == NULL)
  186. return 0;
  187. }
  189. BN_CTX_start(ctx);
  190. tmp_a = BN_CTX_get(ctx);
  191. if (tmp_a == NULL) goto err;
  193. /* group->field */
  194. if (!BN_copy(&group->field, p)) goto err;
  195. BN_set_negative(&group->field, 0);
  197. /* group->a */
  198. if (!BN_nnmod(tmp_a, a, p, ctx)) goto err;
  199. if (group->meth->field_encode)
  200. { if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) goto err; }
  201. else
  202. if (!BN_copy(&group->a, tmp_a)) goto err;
  204. /* group->b */
  205. if (!BN_nnmod(&group->b, b, p, ctx)) goto err;
  206. if (group->meth->field_encode)
  207. if (!group->meth->field_encode(group, &group->b, &group->b, ctx)) goto err;
  209. /* group->a_is_minus3 */
  210. if (!BN_add_word(tmp_a, 3)) goto err;
  211. group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
  213. ret = 1;
  215.  err:
  216. BN_CTX_end(ctx);
  217. if (new_ctx != NULL)
  218. BN_CTX_free(new_ctx);
  219. return ret;
  220. }
  223. int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
  224. {
  225. int ret = 0;
  226. BN_CTX *new_ctx = NULL;
  228. if (p != NULL)
  229. {
  230. if (!BN_copy(p, &group->field)) return 0;
  231. }
  233. if (a != NULL || b != NULL)
  234. {
  235. if (group->meth->field_decode)
  236. {
  237. if (ctx == NULL)
  238. {
  239. ctx = new_ctx = BN_CTX_new();
  240. if (ctx == NULL)
  241. return 0;
  242. }
  243. if (a != NULL)
  244. {
  245. if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err;
  246. }
  247. if (b != NULL)
  248. {
  249. if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err;
  250. }
  251. }
  252. else
  253. {
  254. if (a != NULL)
  255. {
  256. if (!BN_copy(a, &group->a)) goto err;
  257. }
  258. if (b != NULL)
  259. {
  260. if (!BN_copy(b, &group->b)) goto err;
  261. }
  262. }
  263. }
  265. ret = 1;
  267.  err:
  268. if (new_ctx)
  269. BN_CTX_free(new_ctx);
  270. return ret;
  271. }
  274. int ec_GFp_simple_group_get_degree(const EC_GROUP *group)
  275. {
  276. return BN_num_bits(&group->field);
  277. }
  280. int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
  281. {
  282. int ret = 0;
  283. BIGNUM *a,*b,*order,*tmp_1,*tmp_2;
  284. const BIGNUM *p = &group->field;
  285. BN_CTX *new_ctx = NULL;
  287. if (ctx == NULL)
  288. {
  289. ctx = new_ctx = BN_CTX_new();
  290. if (ctx == NULL)
  291. {
  292. ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, ERR_R_MALLOC_FAILURE);
  293. goto err;
  294. }
  295. }
  296. BN_CTX_start(ctx);
  297. a = BN_CTX_get(ctx);
  298. b = BN_CTX_get(ctx);
  299. tmp_1 = BN_CTX_get(ctx);
  300. tmp_2 = BN_CTX_get(ctx);
  301. order = BN_CTX_get(ctx);
  302. if (order == NULL) goto err;
  304. if (group->meth->field_decode)
  305. {
  306. if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err;
  307. if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err;
  308. }
  309. else
  310. {
  311. if (!BN_copy(a, &group->a)) goto err;
  312. if (!BN_copy(b, &group->b)) goto err;
  313. }
  315. /* check the discriminant:
  316.  * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p) 
  317.          * 0 =< a, b < p */
  318. if (BN_is_zero(a))
  319. {
  320. if (BN_is_zero(b)) goto err;
  321. }
  322. else if (!BN_is_zero(b))
  323. {
  324. if (!BN_mod_sqr(tmp_1, a, p, ctx)) goto err;
  325. if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx)) goto err;
  326. if (!BN_lshift(tmp_1, tmp_2, 2)) goto err;
  327. /* tmp_1 = 4*a^3 */
  329. if (!BN_mod_sqr(tmp_2, b, p, ctx)) goto err;
  330. if (!BN_mul_word(tmp_2, 27)) goto err;
  331. /* tmp_2 = 27*b^2 */
  333. if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx)) goto err;
  334. if (BN_is_zero(a)) goto err;
  335. }
  336. ret = 1;
  338. err:
  339. if (ctx != NULL)
  340. BN_CTX_end(ctx);
  341. if (new_ctx != NULL)
  342. BN_CTX_free(new_ctx);
  343. return ret;
  344. }
  347. int ec_GFp_simple_point_init(EC_POINT *point)
  348. {
  349. BN_init(&point->X);
  350. BN_init(&point->Y);
  351. BN_init(&point->Z);
  352. point->Z_is_one = 0;
  354. return 1;
  355. }
  358. void ec_GFp_simple_point_finish(EC_POINT *point)
  359. {
  360. BN_free(&point->X);
  361. BN_free(&point->Y);
  362. BN_free(&point->Z);
  363. }
  366. void ec_GFp_simple_point_clear_finish(EC_POINT *point)
  367. {
  368. BN_clear_free(&point->X);
  369. BN_clear_free(&point->Y);
  370. BN_clear_free(&point->Z);
  371. point->Z_is_one = 0;
  372. }
  375. int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
  376. {
  377. if (!BN_copy(&dest->X, &src->X)) return 0;
  378. if (!BN_copy(&dest->Y, &src->Y)) return 0;
  379. if (!BN_copy(&dest->Z, &src->Z)) return 0;
  380. dest->Z_is_one = src->Z_is_one;
  382. return 1;
  383. }
  386. int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
  387. {
  388. point->Z_is_one = 0;
  389. BN_zero(&point->Z);
  390. return 1;
  391. }
  394. int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
  395. const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx)
  396. {
  397. BN_CTX *new_ctx = NULL;
  398. int ret = 0;
  400. if (ctx == NULL)
  401. {
  402. ctx = new_ctx = BN_CTX_new();
  403. if (ctx == NULL)
  404. return 0;
  405. }
  407. if (x != NULL)
  408. {
  409. if (!BN_nnmod(&point->X, x, &group->field, ctx)) goto err;
  410. if (group->meth->field_encode)
  411. {
  412. if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) goto err;
  413. }
  414. }
  416. if (y != NULL)
  417. {
  418. if (!BN_nnmod(&point->Y, y, &group->field, ctx)) goto err;
  419. if (group->meth->field_encode)
  420. {
  421. if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) goto err;
  422. }
  423. }
  425. if (z != NULL)
  426. {
  427. int Z_is_one;
  429. if (!BN_nnmod(&point->Z, z, &group->field, ctx)) goto err;
  430. Z_is_one = BN_is_one(&point->Z);
  431. if (group->meth->field_encode)
  432. {
  433. if (Z_is_one && (group->meth->field_set_to_one != 0))
  434. {
  435. if (!group->meth->field_set_to_one(group, &point->Z, ctx)) goto err;
  436. }
  437. else
  438. {
  439. if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err;
  440. }
  441. }
  442. point->Z_is_one = Z_is_one;
  443. }
  445. ret = 1;
  447.  err:
  448. if (new_ctx != NULL)
  449. BN_CTX_free(new_ctx);
  450. return ret;
  451. }
  454. int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point,
  455. BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx)
  456. {
  457. BN_CTX *new_ctx = NULL;
  458. int ret = 0;
  460. if (group->meth->field_decode != 0)
  461. {
  462. if (ctx == NULL)
  463. {
  464. ctx = new_ctx = BN_CTX_new();
  465. if (ctx == NULL)
  466. return 0;
  467. }
  469. if (x != NULL)
  470. {
  471. if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err;
  472. }
  473. if (y != NULL)
  474. {
  475. if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err;
  476. }
  477. if (z != NULL)
  478. {
  479. if (!group->meth->field_decode(group, z, &point->Z, ctx)) goto err;
  480. }
  481. }
  482. else
  483. {
  484. if (x != NULL)
  485. {
  486. if (!BN_copy(x, &point->X)) goto err;
  487. }
  488. if (y != NULL)
  489. {
  490. if (!BN_copy(y, &point->Y)) goto err;
  491. }
  492. if (z != NULL)
  493. {
  494. if (!BN_copy(z, &point->Z)) goto err;
  495. }
  496. }
  498. ret = 1;
  500.  err:
  501. if (new_ctx != NULL)
  502. BN_CTX_free(new_ctx);
  503. return ret;
  504. }
  507. int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point,
  508. const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
  509. {
  510. if (x == NULL || y == NULL)
  511. {
  512. /* unlike for projective coordinates, we do not tolerate this */
  513. ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PASSED_NULL_PARAMETER);
  514. return 0;
  515. }
  517. return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, BN_value_one(), ctx);
  518. }
  521. int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point,
  522. BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
  523. {
  524. BN_CTX *new_ctx = NULL;
  525. BIGNUM *Z, *Z_1, *Z_2, *Z_3;
  526. const BIGNUM *Z_;
  527. int ret = 0;
  529. if (EC_POINT_is_at_infinity(group, point))
  530. {
  531. ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POINT_AT_INFINITY);
  532. return 0;
  533. }
  535. if (ctx == NULL)
  536. {
  537. ctx = new_ctx = BN_CTX_new();
  538. if (ctx == NULL)
  539. return 0;
  540. }
  542. BN_CTX_start(ctx);
  543. Z = BN_CTX_get(ctx);
  544. Z_1 = BN_CTX_get(ctx);
  545. Z_2 = BN_CTX_get(ctx);
  546. Z_3 = BN_CTX_get(ctx);
  547. if (Z_3 == NULL) goto err;
  549. /* transform  (X, Y, Z)  into  (x, y) := (X/Z^2, Y/Z^3) */
  551. if (group->meth->field_decode)
  552. {
  553. if (!group->meth->field_decode(group, Z, &point->Z, ctx)) goto err;
  554. Z_ = Z;
  555. }
  556. else
  557. {
  558. Z_ = &point->Z;
  559. }
  561. if (BN_is_one(Z_))
  562. {
  563. if (group->meth->field_decode)
  564. {
  565. if (x != NULL)
  566. {
  567. if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err;
  568. }
  569. if (y != NULL)
  570. {
  571. if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err;
  572. }
  573. }
  574. else
  575. {
  576. if (x != NULL)
  577. {
  578. if (!BN_copy(x, &point->X)) goto err;
  579. }
  580. if (y != NULL)
  581. {
  582. if (!BN_copy(y, &point->Y)) goto err;
  583. }
  584. }
  585. }
  586. else
  587. {
  588. if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx))
  589. {
  590. ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_BN_LIB);
  591. goto err;
  592. }
  594. if (group->meth->field_encode == 0)
  595. {
  596. /* field_sqr works on standard representation */
  597. if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) goto err;
  598. }
  599. else
  600. {
  601. if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err;
  602. }
  604. if (x != NULL)
  605. {
  606. /* in the Montgomery case, field_mul will cancel out Montgomery factor in X: */
  607. if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx)) goto err;
  608. }
  610. if (y != NULL)
  611. {
  612. if (group->meth->field_encode == 0)
  613. {
  614. /* field_mul works on standard representation */
  615. if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) goto err;
  616. }
  617. else
  618. {
  619. if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto err;
  620. }
  622. /* in the Montgomery case, field_mul will cancel out Montgomery factor in Y: */
  623. if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) goto err;
  624. }
  625. }
  627. ret = 1;
  629.  err:
  630. BN_CTX_end(ctx);
  631. if (new_ctx != NULL)
  632. BN_CTX_free(new_ctx);
  633. return ret;
  634. }
  637. int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, EC_POINT *point,
  638. const BIGNUM *x_, int y_bit, BN_CTX *ctx)
  639. {
  640. BN_CTX *new_ctx = NULL;
  641. BIGNUM *tmp1, *tmp2, *x, *y;
  642. int ret = 0;
  644. /* clear error queue*/
  645. ERR_clear_error();
  647. if (ctx == NULL)
  648. {
  649. ctx = new_ctx = BN_CTX_new();
  650. if (ctx == NULL)
  651. return 0;
  652. }
  654. y_bit = (y_bit != 0);
  656. BN_CTX_start(ctx);
  657. tmp1 = BN_CTX_get(ctx);
  658. tmp2 = BN_CTX_get(ctx);
  659. x = BN_CTX_get(ctx);
  660. y = BN_CTX_get(ctx);
  661. if (y == NULL) goto err;
  663. /* Recover y.  We have a Weierstrass equation
  664.  *     y^2 = x^3 + a*x + b,
  665.  * so  y  is one of the square roots of  x^3 + a*x + b.
  666.  */
  668. /* tmp1 := x^3 */
  669. if (!BN_nnmod(x, x_, &group->field,ctx)) goto err;
  670. if (group->meth->field_decode == 0)
  671. {
  672. /* field_{sqr,mul} work on standard representation */
  673. if (!group->meth->field_sqr(group, tmp2, x_, ctx)) goto err;
  674. if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) goto err;
  675. }
  676. else
  677. {
  678. if (!BN_mod_sqr(tmp2, x_, &group->field, ctx)) goto err;
  679. if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) goto err;
  680. }
  682. /* tmp1 := tmp1 + a*x */
  683. if (group->a_is_minus3)
  684. {
  685. if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) goto err;
  686. if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) goto err;
  687. if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
  688. }
  689. else
  690. {
  691. if (group->meth->field_decode)
  692. {
  693. if (!group->meth->field_decode(group, tmp2, &group->a, ctx)) goto err;
  694. if (!BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) goto err;
  695. }
  696. else
  697. {
  698. /* field_mul works on standard representation */
  699. if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) goto err;
  700. }
  702. if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
  703. }
  705. /* tmp1 := tmp1 + b */
  706. if (group->meth->field_decode)
  707. {
  708. if (!group->meth->field_decode(group, tmp2, &group->b, ctx)) goto err;
  709. if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
  710. }
  711. else
  712. {
  713. if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) goto err;
  714. }
  716. if (!BN_mod_sqrt(y, tmp1, &group->field, ctx))
  717. {
  718. unsigned long err = ERR_peek_last_error();
  720. if (ERR_GET_LIB(err) == ERR_LIB_BN && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE)
  721. {
  722. ERR_clear_error();
  723. ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
  724. }
  725. else
  726. ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_BN_LIB);
  727. goto err;
  728. }
  730. if (y_bit != BN_is_odd(y))
  731. {
  732. if (BN_is_zero(y))
  733. {
  734. int kron;
  736. kron = BN_kronecker(x, &group->field, ctx);
  737. if (kron == -2) goto err;
  739. if (kron == 1)
  740. ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSION_BIT);
  741. else
  742. /* BN_mod_sqrt() should have cought this error (not a square) */
  743. ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
  744. goto err;
  745. }
  746. if (!BN_usub(y, &group->field, y)) goto err;
  747. }
  748. if (y_bit != BN_is_odd(y))
  749. {
  750. ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_INTERNAL_ERROR);
  751. goto err;
  752. }
  754. if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
  756. ret = 1;
  758.  err:
  759. BN_CTX_end(ctx);
  760. if (new_ctx != NULL)
  761. BN_CTX_free(new_ctx);
  762. return ret;
  763. }
  766. size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, point_conversion_form_t form,
  767. unsigned char *buf, size_t len, BN_CTX *ctx)
  768. {
  769. size_t ret;
  770. BN_CTX *new_ctx = NULL;
  771. int used_ctx = 0;
  772. BIGNUM *x, *y;
  773. size_t field_len, i, skip;
  775. if ((form != POINT_CONVERSION_COMPRESSED)
  776. && (form != POINT_CONVERSION_UNCOMPRESSED)
  777. && (form != POINT_CONVERSION_HYBRID))
  778. {
  779. ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
  780. goto err;
  781. }
  783. if (EC_POINT_is_at_infinity(group, point))
  784. {
  785. /* encodes to a single 0 octet */
  786. if (buf != NULL)
  787. {
  788. if (len < 1)
  789. {
  790. ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
  791. return 0;
  792. }
  793. buf[0] = 0;
  794. }
  795. return 1;
  796. }
  799. /* ret := required output buffer length */
  800. field_len = BN_num_bytes(&group->field);
  801. ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
  803. /* if 'buf' is NULL, just return required length */
  804. if (buf != NULL)
  805. {
  806. if (len < ret)
  807. {
  808. ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
  809. goto err;
  810. }
  812. if (ctx == NULL)
  813. {
  814. ctx = new_ctx = BN_CTX_new();
  815. if (ctx == NULL)
  816. return 0;
  817. }
  819. BN_CTX_start(ctx);
  820. used_ctx = 1;
  821. x = BN_CTX_get(ctx);
  822. y = BN_CTX_get(ctx);
  823. if (y == NULL) goto err;
  825. if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
  827. if ((form == POINT_CONVERSION_COMPRESSED || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y))
  828. buf[0] = form + 1;
  829. else
  830. buf[0] = form;
  832. i = 1;
  834. skip = field_len - BN_num_bytes(x);
  835. if (skip > field_len)
  836. {
  837. ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
  838. goto err;
  839. }
  840. while (skip > 0)
  841. {
  842. buf[i++] = 0;
  843. skip--;
  844. }
  845. skip = BN_bn2bin(x, buf + i);
  846. i += skip;
  847. if (i != 1 + field_len)
  848. {
  849. ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
  850. goto err;
  851. }
  853. if (form == POINT_CONVERSION_UNCOMPRESSED || form == POINT_CONVERSION_HYBRID)
  854. {
  855. skip = field_len - BN_num_bytes(y);
  856. if (skip > field_len)
  857. {
  858. ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
  859. goto err;
  860. }
  861. while (skip > 0)
  862. {
  863. buf[i++] = 0;
  864. skip--;
  865. }
  866. skip = BN_bn2bin(y, buf + i);
  867. i += skip;
  868. }
  870. if (i != ret)
  871. {
  872. ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
  873. goto err;
  874. }
  875. }
  877. if (used_ctx)
  878. BN_CTX_end(ctx);
  879. if (new_ctx != NULL)
  880. BN_CTX_free(new_ctx);
  881. return ret;
  883.  err:
  884. if (used_ctx)
  885. BN_CTX_end(ctx);
  886. if (new_ctx != NULL)
  887. BN_CTX_free(new_ctx);
  888. return 0;
  889. }
  892. int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
  893. const unsigned char *buf, size_t len, BN_CTX *ctx)
  894. {
  895. point_conversion_form_t form;
  896. int y_bit;
  897. BN_CTX *new_ctx = NULL;
  898. BIGNUM *x, *y;
  899. size_t field_len, enc_len;
  900. int ret = 0;
  902. if (len == 0)
  903. {
  904. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
  905. return 0;
  906. }
  907. form = buf[0];
  908. y_bit = form & 1;
  909. form = form & ~1U;
  910. if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
  911. && (form != POINT_CONVERSION_UNCOMPRESSED)
  912. && (form != POINT_CONVERSION_HYBRID))
  913. {
  914. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
  915. return 0;
  916. }
  917. if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit)
  918. {
  919. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
  920. return 0;
  921. }
  923. if (form == 0)
  924. {
  925. if (len != 1)
  926. {
  927. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
  928. return 0;
  929. }
  931. return EC_POINT_set_to_infinity(group, point);
  932. }
  934. field_len = BN_num_bytes(&group->field);
  935. enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
  937. if (len != enc_len)
  938. {
  939. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
  940. return 0;
  941. }
  943. if (ctx == NULL)
  944. {
  945. ctx = new_ctx = BN_CTX_new();
  946. if (ctx == NULL)
  947. return 0;
  948. }
  950. BN_CTX_start(ctx);
  951. x = BN_CTX_get(ctx);
  952. y = BN_CTX_get(ctx);
  953. if (y == NULL) goto err;
  955. if (!BN_bin2bn(buf + 1, field_len, x)) goto err;
  956. if (BN_ucmp(x, &group->field) >= 0)
  957. {
  958. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
  959. goto err;
  960. }
  962. if (form == POINT_CONVERSION_COMPRESSED)
  963. {
  964. if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) goto err;
  965. }
  966. else
  967. {
  968. if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) goto err;
  969. if (BN_ucmp(y, &group->field) >= 0)
  970. {
  971. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
  972. goto err;
  973. }
  974. if (form == POINT_CONVERSION_HYBRID)
  975. {
  976. if (y_bit != BN_is_odd(y))
  977. {
  978. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
  979. goto err;
  980. }
  981. }
  983. if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
  984. }
  986. if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */
  987. {
  988. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
  989. goto err;
  990. }
  992. ret = 1;
  994.  err:
  995. BN_CTX_end(ctx);
  996. if (new_ctx != NULL)
  997. BN_CTX_free(new_ctx);
  998. return ret;
  999. }
  1002. int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
  1003. {
  1004. int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  1005. int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
  1006. const BIGNUM *p;
  1007. BN_CTX *new_ctx = NULL;
  1008. BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
  1009. int ret = 0;
  1011. if (a == b)
  1012. return EC_POINT_dbl(group, r, a, ctx);
  1013. if (EC_POINT_is_at_infinity(group, a))
  1014. return EC_POINT_copy(r, b);
  1015. if (EC_POINT_is_at_infinity(group, b))
  1016. return EC_POINT_copy(r, a);
  1018. field_mul = group->meth->field_mul;
  1019. field_sqr = group->meth->field_sqr;
  1020. p = &group->field;
  1022. if (ctx == NULL)
  1023. {
  1024. ctx = new_ctx = BN_CTX_new();
  1025. if (ctx == NULL)
  1026. return 0;
  1027. }
  1029. BN_CTX_start(ctx);
  1030. n0 = BN_CTX_get(ctx);
  1031. n1 = BN_CTX_get(ctx);
  1032. n2 = BN_CTX_get(ctx);
  1033. n3 = BN_CTX_get(ctx);
  1034. n4 = BN_CTX_get(ctx);
  1035. n5 = BN_CTX_get(ctx);
  1036. n6 = BN_CTX_get(ctx);
  1037. if (n6 == NULL) goto end;
  1039. /* Note that in this function we must not read components of 'a' or 'b'
  1040.  * once we have written the corresponding components of 'r'.
  1041.  * ('r' might be one of 'a' or 'b'.)
  1042.  */
  1044. /* n1, n2 */
  1045. if (b->Z_is_one)
  1046. {
  1047. if (!BN_copy(n1, &a->X)) goto end;
  1048. if (!BN_copy(n2, &a->Y)) goto end;
  1049. /* n1 = X_a */
  1050. /* n2 = Y_a */
  1051. }
  1052. else
  1053. {
  1054. if (!field_sqr(group, n0, &b->Z, ctx)) goto end;
  1055. if (!field_mul(group, n1, &a->X, n0, ctx)) goto end;
  1056. /* n1 = X_a * Z_b^2 */
  1058. if (!field_mul(group, n0, n0, &b->Z, ctx)) goto end;
  1059. if (!field_mul(group, n2, &a->Y, n0, ctx)) goto end;
  1060. /* n2 = Y_a * Z_b^3 */
  1061. }
  1063. /* n3, n4 */
  1064. if (a->Z_is_one)
  1065. {
  1066. if (!BN_copy(n3, &b->X)) goto end;
  1067. if (!BN_copy(n4, &b->Y)) goto end;
  1068. /* n3 = X_b */
  1069. /* n4 = Y_b */
  1070. }
  1071. else
  1072. {
  1073. if (!field_sqr(group, n0, &a->Z, ctx)) goto end;
  1074. if (!field_mul(group, n3, &b->X, n0, ctx)) goto end;
  1075. /* n3 = X_b * Z_a^2 */
  1077. if (!field_mul(group, n0, n0, &a->Z, ctx)) goto end;
  1078. if (!field_mul(group, n4, &b->Y, n0, ctx)) goto end;
  1079. /* n4 = Y_b * Z_a^3 */
  1080. }
  1082. /* n5, n6 */
  1083. if (!BN_mod_sub_quick(n5, n1, n3, p)) goto end;
  1084. if (!BN_mod_sub_quick(n6, n2, n4, p)) goto end;
  1085. /* n5 = n1 - n3 */
  1086. /* n6 = n2 - n4 */
  1088. if (BN_is_zero(n5))
  1089. {
  1090. if (BN_is_zero(n6))
  1091. {
  1092. /* a is the same point as b */
  1093. BN_CTX_end(ctx);
  1094. ret = EC_POINT_dbl(group, r, a, ctx);
  1095. ctx = NULL;
  1096. goto end;
  1097. }
  1098. else
  1099. {
  1100. /* a is the inverse of b */
  1101. BN_zero(&r->Z);
  1102. r->Z_is_one = 0;
  1103. ret = 1;
  1104. goto end;
  1105. }
  1106. }
  1108. /* 'n7', 'n8' */
  1109. if (!BN_mod_add_quick(n1, n1, n3, p)) goto end;
  1110. if (!BN_mod_add_quick(n2, n2, n4, p)) goto end;
  1111. /* 'n7' = n1 + n3 */
  1112. /* 'n8' = n2 + n4 */
  1114. /* Z_r */
  1115. if (a->Z_is_one && b->Z_is_one)
  1116. {
  1117. if (!BN_copy(&r->Z, n5)) goto end;
  1118. }
  1119. else
  1120. {
  1121. if (a->Z_is_one)
  1122. { if (!BN_copy(n0, &b->Z)) goto end; }
  1123. else if (b->Z_is_one)
  1124. { if (!BN_copy(n0, &a->Z)) goto end; }
  1125. else
  1126. { if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) goto end; }
  1127. if (!field_mul(group, &r->Z, n0, n5, ctx)) goto end;
  1128. }
  1129. r->Z_is_one = 0;
  1130. /* Z_r = Z_a * Z_b * n5 */
  1132. /* X_r */
  1133. if (!field_sqr(group, n0, n6, ctx)) goto end;
  1134. if (!field_sqr(group, n4, n5, ctx)) goto end;
  1135. if (!field_mul(group, n3, n1, n4, ctx)) goto end;
  1136. if (!BN_mod_sub_quick(&r->X, n0, n3, p)) goto end;
  1137. /* X_r = n6^2 - n5^2 * 'n7' */
  1139. /* 'n9' */
  1140. if (!BN_mod_lshift1_quick(n0, &r->X, p)) goto end;
  1141. if (!BN_mod_sub_quick(n0, n3, n0, p)) goto end;
  1142. /* n9 = n5^2 * 'n7' - 2 * X_r */
  1144. /* Y_r */
  1145. if (!field_mul(group, n0, n0, n6, ctx)) goto end;
  1146. if (!field_mul(group, n5, n4, n5, ctx)) goto end; /* now n5 is n5^3 */
  1147. if (!field_mul(group, n1, n2, n5, ctx)) goto end;
  1148. if (!BN_mod_sub_quick(n0, n0, n1, p)) goto end;
  1149. if (BN_is_odd(n0))
  1150. if (!BN_add(n0, n0, p)) goto end;
  1151. /* now  0 <= n0 < 2*p,  and n0 is even */
  1152. if (!BN_rshift1(&r->Y, n0)) goto end;
  1153. /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
  1155. ret = 1;
  1157.  end:
  1158. if (ctx) /* otherwise we already called BN_CTX_end */
  1159. BN_CTX_end(ctx);
  1160. if (new_ctx != NULL)
  1161. BN_CTX_free(new_ctx);
  1162. return ret;
  1163. }
  1166. int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
  1167. {
  1168. int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  1169. int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
  1170. const BIGNUM *p;
  1171. BN_CTX *new_ctx = NULL;
  1172. BIGNUM *n0, *n1, *n2, *n3;
  1173. int ret = 0;
  1175. if (EC_POINT_is_at_infinity(group, a))
  1176. {
  1177. BN_zero(&r->Z);
  1178. r->Z_is_one = 0;
  1179. return 1;
  1180. }
  1182. field_mul = group->meth->field_mul;
  1183. field_sqr = group->meth->field_sqr;
  1184. p = &group->field;
  1186. if (ctx == NULL)
  1187. {
  1188. ctx = new_ctx = BN_CTX_new();
  1189. if (ctx == NULL)
  1190. return 0;
  1191. }
  1193. BN_CTX_start(ctx);
  1194. n0 = BN_CTX_get(ctx);
  1195. n1 = BN_CTX_get(ctx);
  1196. n2 = BN_CTX_get(ctx);
  1197. n3 = BN_CTX_get(ctx);
  1198. if (n3 == NULL) goto err;
  1200. /* Note that in this function we must not read components of 'a'
  1201.  * once we have written the corresponding components of 'r'.
  1202.  * ('r' might the same as 'a'.)
  1203.  */
  1205. /* n1 */
  1206. if (a->Z_is_one)
  1207. {
  1208. if (!field_sqr(group, n0, &a->X, ctx)) goto err;
  1209. if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
  1210. if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
  1211. if (!BN_mod_add_quick(n1, n0, &group->a, p)) goto err;
  1212. /* n1 = 3 * X_a^2 + a_curve */
  1213. }
  1214. else if (group->a_is_minus3)
  1215. {
  1216. if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
  1217. if (!BN_mod_add_quick(n0, &a->X, n1, p)) goto err;
  1218. if (!BN_mod_sub_quick(n2, &a->X, n1, p)) goto err;
  1219. if (!field_mul(group, n1, n0, n2, ctx)) goto err;
  1220. if (!BN_mod_lshift1_quick(n0, n1, p)) goto err;
  1221. if (!BN_mod_add_quick(n1, n0, n1, p)) goto err;
  1222. /* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
  1223.  *    = 3 * X_a^2 - 3 * Z_a^4 */
  1224. }
  1225. else
  1226. {
  1227. if (!field_sqr(group, n0, &a->X, ctx)) goto err;
  1228. if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
  1229. if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
  1230. if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
  1231. if (!field_sqr(group, n1, n1, ctx)) goto err;
  1232. if (!field_mul(group, n1, n1, &group->a, ctx)) goto err;
  1233. if (!BN_mod_add_quick(n1, n1, n0, p)) goto err;
  1234. /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
  1235. }
  1237. /* Z_r */
  1238. if (a->Z_is_one)
  1239. {
  1240. if (!BN_copy(n0, &a->Y)) goto err;
  1241. }
  1242. else
  1243. {
  1244. if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) goto err;
  1245. }
  1246. if (!BN_mod_lshift1_quick(&r->Z, n0, p)) goto err;
  1247. r->Z_is_one = 0;
  1248. /* Z_r = 2 * Y_a * Z_a */
  1250. /* n2 */
  1251. if (!field_sqr(group, n3, &a->Y, ctx)) goto err;
  1252. if (!field_mul(group, n2, &a->X, n3, ctx)) goto err;
  1253. if (!BN_mod_lshift_quick(n2, n2, 2, p)) goto err;
  1254. /* n2 = 4 * X_a * Y_a^2 */
  1256. /* X_r */
  1257. if (!BN_mod_lshift1_quick(n0, n2, p)) goto err;
  1258. if (!field_sqr(group, &r->X, n1, ctx)) goto err;
  1259. if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) goto err;
  1260. /* X_r = n1^2 - 2 * n2 */
  1262. /* n3 */
  1263. if (!field_sqr(group, n0, n3, ctx)) goto err;
  1264. if (!BN_mod_lshift_quick(n3, n0, 3, p)) goto err;
  1265. /* n3 = 8 * Y_a^4 */
  1267. /* Y_r */
  1268. if (!BN_mod_sub_quick(n0, n2, &r->X, p)) goto err;
  1269. if (!field_mul(group, n0, n1, n0, ctx)) goto err;
  1270. if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) goto err;
  1271. /* Y_r = n1 * (n2 - X_r) - n3 */
  1273. ret = 1;
  1275.  err:
  1276. BN_CTX_end(ctx);
  1277. if (new_ctx != NULL)
  1278. BN_CTX_free(new_ctx);
  1279. return ret;
  1280. }
  1283. int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
  1284. {
  1285. if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y))
  1286. /* point is its own inverse */
  1287. return 1;
  1289. return BN_usub(&point->Y, &group->field, &point->Y);
  1290. }
  1293. int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
  1294. {
  1295. return BN_is_zero(&point->Z);
  1296. }
  1299. int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
  1300. {
  1301. int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  1302. int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
  1303. const BIGNUM *p;
  1304. BN_CTX *new_ctx = NULL;
  1305. BIGNUM *rh, *tmp, *Z4, *Z6;
  1306. int ret = -1;
  1308. if (EC_POINT_is_at_infinity(group, point))
  1309. return 1;
  1311. field_mul = group->meth->field_mul;
  1312. field_sqr = group->meth->field_sqr;
  1313. p = &group->field;
  1315. if (ctx == NULL)
  1316. {
  1317. ctx = new_ctx = BN_CTX_new();
  1318. if (ctx == NULL)
  1319. return -1;
  1320. }
  1322. BN_CTX_start(ctx);
  1323. rh = BN_CTX_get(ctx);
  1324. tmp = BN_CTX_get(ctx);
  1325. Z4 = BN_CTX_get(ctx);
  1326. Z6 = BN_CTX_get(ctx);
  1327. if (Z6 == NULL) goto err;
  1329. /* We have a curve defined by a Weierstrass equation
  1330.  *      y^2 = x^3 + a*x + b.
  1331.  * The point to consider is given in Jacobian projective coordinates
  1332.  * where  (X, Y, Z)  represents  (x, y) = (X/Z^2, Y/Z^3).
  1333.  * Substituting this and multiplying by  Z^6  transforms the above equation into
  1334.  *      Y^2 = X^3 + a*X*Z^4 + b*Z^6.
  1335.  * To test this, we add up the right-hand side in 'rh'.
  1336.  */
  1338. /* rh := X^2 */
  1339. if (!field_sqr(group, rh, &point->X, ctx)) goto err;
  1341. if (!point->Z_is_one)
  1342. {
  1343. if (!field_sqr(group, tmp, &point->Z, ctx)) goto err;
  1344. if (!field_sqr(group, Z4, tmp, ctx)) goto err;
  1345. if (!field_mul(group, Z6, Z4, tmp, ctx)) goto err;
  1347. /* rh := (rh + a*Z^4)*X */
  1348. if (group->a_is_minus3)
  1349. {
  1350. if (!BN_mod_lshift1_quick(tmp, Z4, p)) goto err;
  1351. if (!BN_mod_add_quick(tmp, tmp, Z4, p)) goto err;
  1352. if (!BN_mod_sub_quick(rh, rh, tmp, p)) goto err;
  1353. if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
  1354. }
  1355. else
  1356. {
  1357. if (!field_mul(group, tmp, Z4, &group->a, ctx)) goto err;
  1358. if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err;
  1359. if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
  1360. }
  1362. /* rh := rh + b*Z^6 */
  1363. if (!field_mul(group, tmp, &group->b, Z6, ctx)) goto err;
  1364. if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err;
  1365. }
  1366. else
  1367. {
  1368. /* point->Z_is_one */
  1370. /* rh := (rh + a)*X */
  1371. if (!BN_mod_add_quick(rh, rh, &group->a, p)) goto err;
  1372. if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
  1373. /* rh := rh + b */
  1374. if (!BN_mod_add_quick(rh, rh, &group->b, p)) goto err;
  1375. }
  1377. /* 'lh' := Y^2 */
  1378. if (!field_sqr(group, tmp, &point->Y, ctx)) goto err;
  1380. ret = (0 == BN_ucmp(tmp, rh));
  1382.  err:
  1383. BN_CTX_end(ctx);
  1384. if (new_ctx != NULL)
  1385. BN_CTX_free(new_ctx);
  1386. return ret;
  1387. }
  1390. int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
  1391. {
  1392. /* return values:
  1393.  *  -1   error
  1394.  *   0   equal (in affine coordinates)
  1395.  *   1   not equal
  1396.  */
  1398. int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  1399. int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
  1400. BN_CTX *new_ctx = NULL;
  1401. BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
  1402. const BIGNUM *tmp1_, *tmp2_;
  1403. int ret = -1;
  1405. if (EC_POINT_is_at_infinity(group, a))
  1406. {
  1407. return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
  1408. }
  1410. if (a->Z_is_one && b->Z_is_one)
  1411. {
  1412. return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
  1413. }
  1415. field_mul = group->meth->field_mul;
  1416. field_sqr = group->meth->field_sqr;
  1418. if (ctx == NULL)
  1419. {
  1420. ctx = new_ctx = BN_CTX_new();
  1421. if (ctx == NULL)
  1422. return -1;
  1423. }
  1425. BN_CTX_start(ctx);
  1426. tmp1 = BN_CTX_get(ctx);
  1427. tmp2 = BN_CTX_get(ctx);
  1428. Za23 = BN_CTX_get(ctx);
  1429. Zb23 = BN_CTX_get(ctx);
  1430. if (Zb23 == NULL) goto end;
  1432. /* We have to decide whether
  1433.  *     (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
  1434.  * or equivalently, whether
  1435.  *     (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
  1436.  */
  1438. if (!b->Z_is_one)
  1439. {
  1440. if (!field_sqr(group, Zb23, &b->Z, ctx)) goto end;
  1441. if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) goto end;
  1442. tmp1_ = tmp1;
  1443. }
  1444. else
  1445. tmp1_ = &a->X;
  1446. if (!a->Z_is_one)
  1447. {
  1448. if (!field_sqr(group, Za23, &a->Z, ctx)) goto end;
  1449. if (!field_mul(group, tmp2, &b->X, Za23, ctx)) goto end;
  1450. tmp2_ = tmp2;
  1451. }
  1452. else
  1453. tmp2_ = &b->X;
  1455. /* compare  X_a*Z_b^2  with  X_b*Z_a^2 */
  1456. if (BN_cmp(tmp1_, tmp2_) != 0)
  1457. {
  1458. ret = 1; /* points differ */
  1459. goto end;
  1460. }
  1463. if (!b->Z_is_one)
  1464. {
  1465. if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) goto end;
  1466. if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) goto end;
  1467. /* tmp1_ = tmp1 */
  1468. }
  1469. else
  1470. tmp1_ = &a->Y;
  1471. if (!a->Z_is_one)
  1472. {
  1473. if (!field_mul(group, Za23, Za23, &a->Z, ctx)) goto end;
  1474. if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) goto end;
  1475. /* tmp2_ = tmp2 */
  1476. }
  1477. else
  1478. tmp2_ = &b->Y;
  1480. /* compare  Y_a*Z_b^3  with  Y_b*Z_a^3 */
  1481. if (BN_cmp(tmp1_, tmp2_) != 0)
  1482. {
  1483. ret = 1; /* points differ */
  1484. goto end;
  1485. }
  1487. /* points are equal */
  1488. ret = 0;
  1490.  end:
  1491. BN_CTX_end(ctx);
  1492. if (new_ctx != NULL)
  1493. BN_CTX_free(new_ctx);
  1494. return ret;
  1495. }
  1498. int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
  1499. {
  1500. BN_CTX *new_ctx = NULL;
  1501. BIGNUM *x, *y;
  1502. int ret = 0;
  1504. if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
  1505. return 1;
  1507. if (ctx == NULL)
  1508. {
  1509. ctx = new_ctx = BN_CTX_new();
  1510. if (ctx == NULL)
  1511. return 0;
  1512. }
  1514. BN_CTX_start(ctx);
  1515. x = BN_CTX_get(ctx);
  1516. y = BN_CTX_get(ctx);
  1517. if (y == NULL) goto err;
  1519. if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
  1520. if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
  1521. if (!point->Z_is_one)
  1522. {
  1523. ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
  1524. goto err;
  1525. }
  1527. ret = 1;
  1529.  err:
  1530. BN_CTX_end(ctx);
  1531. if (new_ctx != NULL)
  1532. BN_CTX_free(new_ctx);
  1533. return ret;
  1534. }
  1537. int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
  1538. {
  1539. BN_CTX *new_ctx = NULL;
  1540. BIGNUM *tmp0, *tmp1;
  1541. size_t pow2 = 0;
  1542. BIGNUM **heap = NULL;
  1543. size_t i;
  1544. int ret = 0;
  1546. if (num == 0)
  1547. return 1;
  1549. if (ctx == NULL)
  1550. {
  1551. ctx = new_ctx = BN_CTX_new();
  1552. if (ctx == NULL)
  1553. return 0;
  1554. }
  1556. BN_CTX_start(ctx);
  1557. tmp0 = BN_CTX_get(ctx);
  1558. tmp1 = BN_CTX_get(ctx);
  1559. if (tmp0  == NULL || tmp1 == NULL) goto err;
  1561. /* Before converting the individual points, compute inverses of all Z values.
  1562.  * Modular inversion is rather slow, but luckily we can do with a single
  1563.  * explicit inversion, plus about 3 multiplications per input value.
  1564.  */
  1566. pow2 = 1;
  1567. while (num > pow2)
  1568. pow2 <<= 1;
  1569. /* Now pow2 is the smallest power of 2 satifsying pow2 >= num.
  1570.  * We need twice that. */
  1571. pow2 <<= 1;
  1573. heap = OPENSSL_malloc(pow2 * sizeof heap[0]);
  1574. if (heap == NULL) goto err;
  1576. /* The array is used as a binary tree, exactly as in heapsort:
  1577.  *
  1578.  *                               heap[1]
  1579.  *                 heap[2]                     heap[3]
  1580.  *          heap[4]       heap[5]       heap[6]       heap[7]
  1581.  *   heap[8]heap[9] heap[10]heap[11] heap[12]heap[13] heap[14] heap[15]
  1582.  *
  1583.  * We put the Z's in the last line;
  1584.  * then we set each other node to the product of its two child-nodes (where
  1585.  * empty or 0 entries are treated as ones);
  1586.  * then we invert heap[1];
  1587.  * then we invert each other node by replacing it by the product of its
  1588.  * parent (after inversion) and its sibling (before inversion).
  1589.  */
  1590. heap[0] = NULL;
  1591. for (i = pow2/2 - 1; i > 0; i--)
  1592. heap[i] = NULL;
  1593. for (i = 0; i < num; i++)
  1594. heap[pow2/2 + i] = &points[i]->Z;
  1595. for (i = pow2/2 + num; i < pow2; i++)
  1596. heap[i] = NULL;
  1598. /* set each node to the product of its children */
  1599. for (i = pow2/2 - 1; i > 0; i--)
  1600. {
  1601. heap[i] = BN_new();
  1602. if (heap[i] == NULL) goto err;
  1604. if (heap[2*i] != NULL)
  1605. {
  1606. if ((heap[2*i + 1] == NULL) || BN_is_zero(heap[2*i + 1]))
  1607. {
  1608. if (!BN_copy(heap[i], heap[2*i])) goto err;
  1609. }
  1610. else
  1611. {
  1612. if (BN_is_zero(heap[2*i]))
  1613. {
  1614. if (!BN_copy(heap[i], heap[2*i + 1])) goto err;
  1615. }
  1616. else
  1617. {
  1618. if (!group->meth->field_mul(group, heap[i],
  1619. heap[2*i], heap[2*i + 1], ctx)) goto err;
  1620. }
  1621. }
  1622. }
  1623. }
  1625. /* invert heap[1] */
  1626. if (!BN_is_zero(heap[1]))
  1627. {
  1628. if (!BN_mod_inverse(heap[1], heap[1], &group->field, ctx))
  1629. {
  1630. ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
  1631. goto err;
  1632. }
  1633. }
  1634. if (group->meth->field_encode != 0)
  1635. {
  1636. /* in the Montgomery case, we just turned  R*H  (representing H)
  1637.  * into  1/(R*H),  but we need  R*(1/H)  (representing 1/H);
  1638.  * i.e. we have need to multiply by the Montgomery factor twice */
  1639. if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
  1640. if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
  1641. }
  1643. /* set other heap[i]'s to their inverses */
  1644. for (i = 2; i < pow2/2 + num; i += 2)
  1645. {
  1646. /* i is even */
  1647. if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1]))
  1648. {
  1649. if (!group->meth->field_mul(group, tmp0, heap[i/2], heap[i + 1], ctx)) goto err;
  1650. if (!group->meth->field_mul(group, tmp1, heap[i/2], heap[i], ctx)) goto err;
  1651. if (!BN_copy(heap[i], tmp0)) goto err;
  1652. if (!BN_copy(heap[i + 1], tmp1)) goto err;
  1653. }
  1654. else
  1655. {
  1656. if (!BN_copy(heap[i], heap[i/2])) goto err;
  1657. }
  1658. }
  1660. /* we have replaced all non-zero Z's by their inverses, now fix up all the points */
  1661. for (i = 0; i < num; i++)
  1662. {
  1663. EC_POINT *p = points[i];
  1665. if (!BN_is_zero(&p->Z))
  1666. {
  1667. /* turn  (X, Y, 1/Z)  into  (X/Z^2, Y/Z^3, 1) */
  1669. if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx)) goto err;
  1670. if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx)) goto err;
  1672. if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx)) goto err;
  1673. if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx)) goto err;
  1675. if (group->meth->field_set_to_one != 0)
  1676. {
  1677. if (!group->meth->field_set_to_one(group, &p->Z, ctx)) goto err;
  1678. }
  1679. else
  1680. {
  1681. if (!BN_one(&p->Z)) goto err;
  1682. }
  1683. p->Z_is_one = 1;
  1684. }
  1685. }
  1687. ret = 1;
  1689.  err:
  1690. BN_CTX_end(ctx);
  1691. if (new_ctx != NULL)
  1692. BN_CTX_free(new_ctx);
  1693. if (heap != NULL)
  1694. {
  1695. /* heap[pow2/2] .. heap[pow2-1] have not been allocated locally! */
  1696. for (i = pow2/2 - 1; i > 0; i--)
  1697. {
  1698. if (heap[i] != NULL)
  1699. BN_clear_free(heap[i]);
  1700. }
  1701. OPENSSL_free(heap);
  1702. }
  1703. return ret;
  1704. }
  1707. int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
  1708. {
  1709. return BN_mod_mul(r, a, b, &group->field, ctx);
  1710. }
  1713. int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
  1714. {
  1715. return BN_mod_sqr(r, a, &group->field, ctx);
  1716. }