summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/ec/ecp_smpl.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/ec/ecp_smpl.c')
-rw-r--r--src/lib/libcrypto/ec/ecp_smpl.c1410
1 files changed, 0 insertions, 1410 deletions
diff --git a/src/lib/libcrypto/ec/ecp_smpl.c b/src/lib/libcrypto/ec/ecp_smpl.c
deleted file mode 100644
index f6db4dc9b1..0000000000
--- a/src/lib/libcrypto/ec/ecp_smpl.c
+++ /dev/null
@@ -1,1410 +0,0 @@
1/* $OpenBSD: ecp_smpl.c,v 1.15 2015/02/09 15:49:22 jsing Exp $ */
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 */
64
65#include <openssl/err.h>
66
67#include "ec_lcl.h"
68
69const EC_METHOD *
70EC_GFp_simple_method(void)
71{
72 static const EC_METHOD ret = {
73 .flags = EC_FLAGS_DEFAULT_OCT,
74 .field_type = NID_X9_62_prime_field,
75 .group_init = ec_GFp_simple_group_init,
76 .group_finish = ec_GFp_simple_group_finish,
77 .group_clear_finish = ec_GFp_simple_group_clear_finish,
78 .group_copy = ec_GFp_simple_group_copy,
79 .group_set_curve = ec_GFp_simple_group_set_curve,
80 .group_get_curve = ec_GFp_simple_group_get_curve,
81 .group_get_degree = ec_GFp_simple_group_get_degree,
82 .group_check_discriminant =
83 ec_GFp_simple_group_check_discriminant,
84 .point_init = ec_GFp_simple_point_init,
85 .point_finish = ec_GFp_simple_point_finish,
86 .point_clear_finish = ec_GFp_simple_point_clear_finish,
87 .point_copy = ec_GFp_simple_point_copy,
88 .point_set_to_infinity = ec_GFp_simple_point_set_to_infinity,
89 .point_set_Jprojective_coordinates_GFp =
90 ec_GFp_simple_set_Jprojective_coordinates_GFp,
91 .point_get_Jprojective_coordinates_GFp =
92 ec_GFp_simple_get_Jprojective_coordinates_GFp,
93 .point_set_affine_coordinates =
94 ec_GFp_simple_point_set_affine_coordinates,
95 .point_get_affine_coordinates =
96 ec_GFp_simple_point_get_affine_coordinates,
97 .add = ec_GFp_simple_add,
98 .dbl = ec_GFp_simple_dbl,
99 .invert = ec_GFp_simple_invert,
100 .is_at_infinity = ec_GFp_simple_is_at_infinity,
101 .is_on_curve = ec_GFp_simple_is_on_curve,
102 .point_cmp = ec_GFp_simple_cmp,
103 .make_affine = ec_GFp_simple_make_affine,
104 .points_make_affine = ec_GFp_simple_points_make_affine,
105 .field_mul = ec_GFp_simple_field_mul,
106 .field_sqr = ec_GFp_simple_field_sqr
107 };
108
109 return &ret;
110}
111
112
113/* Most method functions in this file are designed to work with
114 * non-trivial representations of field elements if necessary
115 * (see ecp_mont.c): while standard modular addition and subtraction
116 * are used, the field_mul and field_sqr methods will be used for
117 * multiplication, and field_encode and field_decode (if defined)
118 * will be used for converting between representations.
119
120 * Functions ec_GFp_simple_points_make_affine() and
121 * ec_GFp_simple_point_get_affine_coordinates() specifically assume
122 * that if a non-trivial representation is used, it is a Montgomery
123 * representation (i.e. 'encoding' means multiplying by some factor R).
124 */
125
126
127int
128ec_GFp_simple_group_init(EC_GROUP * group)
129{
130 BN_init(&group->field);
131 BN_init(&group->a);
132 BN_init(&group->b);
133 group->a_is_minus3 = 0;
134 return 1;
135}
136
137
138void
139ec_GFp_simple_group_finish(EC_GROUP * group)
140{
141 BN_free(&group->field);
142 BN_free(&group->a);
143 BN_free(&group->b);
144}
145
146
147void
148ec_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}
154
155
156int
157ec_GFp_simple_group_copy(EC_GROUP * dest, const EC_GROUP * src)
158{
159 if (!BN_copy(&dest->field, &src->field))
160 return 0;
161 if (!BN_copy(&dest->a, &src->a))
162 return 0;
163 if (!BN_copy(&dest->b, &src->b))
164 return 0;
165
166 dest->a_is_minus3 = src->a_is_minus3;
167
168 return 1;
169}
170
171
172int
173ec_GFp_simple_group_set_curve(EC_GROUP * group,
174 const BIGNUM * p, const BIGNUM * a, const BIGNUM * b, BN_CTX * ctx)
175{
176 int ret = 0;
177 BN_CTX *new_ctx = NULL;
178 BIGNUM *tmp_a;
179
180 /* p must be a prime > 3 */
181 if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) {
182 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD);
183 return 0;
184 }
185 if (ctx == NULL) {
186 ctx = new_ctx = BN_CTX_new();
187 if (ctx == NULL)
188 return 0;
189 }
190 BN_CTX_start(ctx);
191 if ((tmp_a = BN_CTX_get(ctx)) == NULL)
192 goto err;
193
194 /* group->field */
195 if (!BN_copy(&group->field, p))
196 goto err;
197 BN_set_negative(&group->field, 0);
198
199 /* group->a */
200 if (!BN_nnmod(tmp_a, a, p, ctx))
201 goto err;
202 if (group->meth->field_encode) {
203 if (!group->meth->field_encode(group, &group->a, tmp_a, ctx))
204 goto err;
205 } else if (!BN_copy(&group->a, tmp_a))
206 goto err;
207
208 /* group->b */
209 if (!BN_nnmod(&group->b, b, p, ctx))
210 goto err;
211 if (group->meth->field_encode)
212 if (!group->meth->field_encode(group, &group->b, &group->b, ctx))
213 goto err;
214
215 /* group->a_is_minus3 */
216 if (!BN_add_word(tmp_a, 3))
217 goto err;
218 group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
219
220 ret = 1;
221
222err:
223 BN_CTX_end(ctx);
224 BN_CTX_free(new_ctx);
225 return ret;
226}
227
228
229int
230ec_GFp_simple_group_get_curve(const EC_GROUP * group, BIGNUM * p, BIGNUM * a, BIGNUM * b, BN_CTX * ctx)
231{
232 int ret = 0;
233 BN_CTX *new_ctx = NULL;
234
235 if (p != NULL) {
236 if (!BN_copy(p, &group->field))
237 return 0;
238 }
239 if (a != NULL || b != NULL) {
240 if (group->meth->field_decode) {
241 if (ctx == NULL) {
242 ctx = new_ctx = BN_CTX_new();
243 if (ctx == NULL)
244 return 0;
245 }
246 if (a != NULL) {
247 if (!group->meth->field_decode(group, a, &group->a, ctx))
248 goto err;
249 }
250 if (b != NULL) {
251 if (!group->meth->field_decode(group, b, &group->b, ctx))
252 goto err;
253 }
254 } else {
255 if (a != NULL) {
256 if (!BN_copy(a, &group->a))
257 goto err;
258 }
259 if (b != NULL) {
260 if (!BN_copy(b, &group->b))
261 goto err;
262 }
263 }
264 }
265 ret = 1;
266
267err:
268 BN_CTX_free(new_ctx);
269 return ret;
270}
271
272
273int
274ec_GFp_simple_group_get_degree(const EC_GROUP * group)
275{
276 return BN_num_bits(&group->field);
277}
278
279
280int
281ec_GFp_simple_group_check_discriminant(const EC_GROUP * group, BN_CTX * ctx)
282{
283 int ret = 0;
284 BIGNUM *a, *b, *order, *tmp_1, *tmp_2;
285 const BIGNUM *p = &group->field;
286 BN_CTX *new_ctx = NULL;
287
288 if (ctx == NULL) {
289 ctx = new_ctx = BN_CTX_new();
290 if (ctx == NULL) {
291 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, ERR_R_MALLOC_FAILURE);
292 goto err;
293 }
294 }
295 BN_CTX_start(ctx);
296 if ((a = BN_CTX_get(ctx)) == NULL)
297 goto err;
298 if ((b = BN_CTX_get(ctx)) == NULL)
299 goto err;
300 if ((tmp_1 = BN_CTX_get(ctx)) == NULL)
301 goto err;
302 if ((tmp_2 = BN_CTX_get(ctx)) == NULL)
303 goto err;
304 if ((order = BN_CTX_get(ctx)) == NULL)
305 goto err;
306
307 if (group->meth->field_decode) {
308 if (!group->meth->field_decode(group, a, &group->a, ctx))
309 goto err;
310 if (!group->meth->field_decode(group, b, &group->b, ctx))
311 goto err;
312 } else {
313 if (!BN_copy(a, &group->a))
314 goto err;
315 if (!BN_copy(b, &group->b))
316 goto err;
317 }
318
319 /*
320 * check the discriminant: y^2 = x^3 + a*x + b is an elliptic curve
321 * <=> 4*a^3 + 27*b^2 != 0 (mod p) 0 =< a, b < p
322 */
323 if (BN_is_zero(a)) {
324 if (BN_is_zero(b))
325 goto err;
326 } else if (!BN_is_zero(b)) {
327 if (!BN_mod_sqr(tmp_1, a, p, ctx))
328 goto err;
329 if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx))
330 goto err;
331 if (!BN_lshift(tmp_1, tmp_2, 2))
332 goto err;
333 /* tmp_1 = 4*a^3 */
334
335 if (!BN_mod_sqr(tmp_2, b, p, ctx))
336 goto err;
337 if (!BN_mul_word(tmp_2, 27))
338 goto err;
339 /* tmp_2 = 27*b^2 */
340
341 if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx))
342 goto err;
343 if (BN_is_zero(a))
344 goto err;
345 }
346 ret = 1;
347
348err:
349 if (ctx != NULL)
350 BN_CTX_end(ctx);
351 BN_CTX_free(new_ctx);
352 return ret;
353}
354
355
356int
357ec_GFp_simple_point_init(EC_POINT * point)
358{
359 BN_init(&point->X);
360 BN_init(&point->Y);
361 BN_init(&point->Z);
362 point->Z_is_one = 0;
363
364 return 1;
365}
366
367
368void
369ec_GFp_simple_point_finish(EC_POINT * point)
370{
371 BN_free(&point->X);
372 BN_free(&point->Y);
373 BN_free(&point->Z);
374}
375
376
377void
378ec_GFp_simple_point_clear_finish(EC_POINT * point)
379{
380 BN_clear_free(&point->X);
381 BN_clear_free(&point->Y);
382 BN_clear_free(&point->Z);
383 point->Z_is_one = 0;
384}
385
386
387int
388ec_GFp_simple_point_copy(EC_POINT * dest, const EC_POINT * src)
389{
390 if (!BN_copy(&dest->X, &src->X))
391 return 0;
392 if (!BN_copy(&dest->Y, &src->Y))
393 return 0;
394 if (!BN_copy(&dest->Z, &src->Z))
395 return 0;
396 dest->Z_is_one = src->Z_is_one;
397
398 return 1;
399}
400
401
402int
403ec_GFp_simple_point_set_to_infinity(const EC_GROUP * group, EC_POINT * point)
404{
405 point->Z_is_one = 0;
406 BN_zero(&point->Z);
407 return 1;
408}
409
410
411int
412ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP * group, EC_POINT * point,
413 const BIGNUM * x, const BIGNUM * y, const BIGNUM * z, BN_CTX * ctx)
414{
415 BN_CTX *new_ctx = NULL;
416 int ret = 0;
417
418 if (ctx == NULL) {
419 ctx = new_ctx = BN_CTX_new();
420 if (ctx == NULL)
421 return 0;
422 }
423 if (x != NULL) {
424 if (!BN_nnmod(&point->X, x, &group->field, ctx))
425 goto err;
426 if (group->meth->field_encode) {
427 if (!group->meth->field_encode(group, &point->X, &point->X, ctx))
428 goto err;
429 }
430 }
431 if (y != NULL) {
432 if (!BN_nnmod(&point->Y, y, &group->field, ctx))
433 goto err;
434 if (group->meth->field_encode) {
435 if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx))
436 goto err;
437 }
438 }
439 if (z != NULL) {
440 int Z_is_one;
441
442 if (!BN_nnmod(&point->Z, z, &group->field, ctx))
443 goto err;
444 Z_is_one = BN_is_one(&point->Z);
445 if (group->meth->field_encode) {
446 if (Z_is_one && (group->meth->field_set_to_one != 0)) {
447 if (!group->meth->field_set_to_one(group, &point->Z, ctx))
448 goto err;
449 } else {
450 if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx))
451 goto err;
452 }
453 }
454 point->Z_is_one = Z_is_one;
455 }
456 ret = 1;
457
458err:
459 BN_CTX_free(new_ctx);
460 return ret;
461}
462
463
464int
465ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP * group, const EC_POINT * point,
466 BIGNUM * x, BIGNUM * y, BIGNUM * z, BN_CTX * ctx)
467{
468 BN_CTX *new_ctx = NULL;
469 int ret = 0;
470
471 if (group->meth->field_decode != 0) {
472 if (ctx == NULL) {
473 ctx = new_ctx = BN_CTX_new();
474 if (ctx == NULL)
475 return 0;
476 }
477 if (x != NULL) {
478 if (!group->meth->field_decode(group, x, &point->X, ctx))
479 goto err;
480 }
481 if (y != NULL) {
482 if (!group->meth->field_decode(group, y, &point->Y, ctx))
483 goto err;
484 }
485 if (z != NULL) {
486 if (!group->meth->field_decode(group, z, &point->Z, ctx))
487 goto err;
488 }
489 } else {
490 if (x != NULL) {
491 if (!BN_copy(x, &point->X))
492 goto err;
493 }
494 if (y != NULL) {
495 if (!BN_copy(y, &point->Y))
496 goto err;
497 }
498 if (z != NULL) {
499 if (!BN_copy(z, &point->Z))
500 goto err;
501 }
502 }
503
504 ret = 1;
505
506err:
507 BN_CTX_free(new_ctx);
508 return ret;
509}
510
511
512int
513ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP * group, EC_POINT * point,
514 const BIGNUM * x, const BIGNUM * y, BN_CTX * ctx)
515{
516 if (x == NULL || y == NULL) {
517 /* unlike for projective coordinates, we do not tolerate this */
518 ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PASSED_NULL_PARAMETER);
519 return 0;
520 }
521 return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, BN_value_one(), ctx);
522}
523
524
525int
526ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP * group, const EC_POINT * point,
527 BIGNUM * x, BIGNUM * y, BN_CTX * ctx)
528{
529 BN_CTX *new_ctx = NULL;
530 BIGNUM *Z, *Z_1, *Z_2, *Z_3;
531 const BIGNUM *Z_;
532 int ret = 0;
533
534 if (EC_POINT_is_at_infinity(group, point) > 0) {
535 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POINT_AT_INFINITY);
536 return 0;
537 }
538 if (ctx == NULL) {
539 ctx = new_ctx = BN_CTX_new();
540 if (ctx == NULL)
541 return 0;
542 }
543 BN_CTX_start(ctx);
544 if ((Z = BN_CTX_get(ctx)) == NULL)
545 goto err;
546 if ((Z_1 = BN_CTX_get(ctx)) == NULL)
547 goto err;
548 if ((Z_2 = BN_CTX_get(ctx)) == NULL)
549 goto err;
550 if ((Z_3 = BN_CTX_get(ctx)) == NULL)
551 goto err;
552
553 /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */
554
555 if (group->meth->field_decode) {
556 if (!group->meth->field_decode(group, Z, &point->Z, ctx))
557 goto err;
558 Z_ = Z;
559 } else {
560 Z_ = &point->Z;
561 }
562
563 if (BN_is_one(Z_)) {
564 if (group->meth->field_decode) {
565 if (x != NULL) {
566 if (!group->meth->field_decode(group, x, &point->X, ctx))
567 goto err;
568 }
569 if (y != NULL) {
570 if (!group->meth->field_decode(group, y, &point->Y, ctx))
571 goto err;
572 }
573 } else {
574 if (x != NULL) {
575 if (!BN_copy(x, &point->X))
576 goto err;
577 }
578 if (y != NULL) {
579 if (!BN_copy(y, &point->Y))
580 goto err;
581 }
582 }
583 } else {
584 if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx)) {
585 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_BN_LIB);
586 goto err;
587 }
588 if (group->meth->field_encode == 0) {
589 /* field_sqr works on standard representation */
590 if (!group->meth->field_sqr(group, Z_2, Z_1, ctx))
591 goto err;
592 } else {
593 if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx))
594 goto err;
595 }
596
597 if (x != NULL) {
598 /*
599 * in the Montgomery case, field_mul will cancel out
600 * Montgomery factor in X:
601 */
602 if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx))
603 goto err;
604 }
605 if (y != NULL) {
606 if (group->meth->field_encode == 0) {
607 /* field_mul works on standard representation */
608 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx))
609 goto err;
610 } else {
611 if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx))
612 goto err;
613 }
614
615 /*
616 * in the Montgomery case, field_mul will cancel out
617 * Montgomery factor in Y:
618 */
619 if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx))
620 goto err;
621 }
622 }
623
624 ret = 1;
625
626err:
627 BN_CTX_end(ctx);
628 BN_CTX_free(new_ctx);
629 return ret;
630}
631
632int
633ec_GFp_simple_add(const EC_GROUP * group, EC_POINT * r, const EC_POINT * a, const EC_POINT * b, BN_CTX * ctx)
634{
635 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
636 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
637 const BIGNUM *p;
638 BN_CTX *new_ctx = NULL;
639 BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
640 int ret = 0;
641
642 if (a == b)
643 return EC_POINT_dbl(group, r, a, ctx);
644 if (EC_POINT_is_at_infinity(group, a) > 0)
645 return EC_POINT_copy(r, b);
646 if (EC_POINT_is_at_infinity(group, b) > 0)
647 return EC_POINT_copy(r, a);
648
649 field_mul = group->meth->field_mul;
650 field_sqr = group->meth->field_sqr;
651 p = &group->field;
652
653 if (ctx == NULL) {
654 ctx = new_ctx = BN_CTX_new();
655 if (ctx == NULL)
656 return 0;
657 }
658 BN_CTX_start(ctx);
659 if ((n0 = BN_CTX_get(ctx)) == NULL)
660 goto end;
661 if ((n1 = BN_CTX_get(ctx)) == NULL)
662 goto end;
663 if ((n2 = BN_CTX_get(ctx)) == NULL)
664 goto end;
665 if ((n3 = BN_CTX_get(ctx)) == NULL)
666 goto end;
667 if ((n4 = BN_CTX_get(ctx)) == NULL)
668 goto end;
669 if ((n5 = BN_CTX_get(ctx)) == NULL)
670 goto end;
671 if ((n6 = BN_CTX_get(ctx)) == NULL)
672 goto end;
673
674 /*
675 * Note that in this function we must not read components of 'a' or
676 * 'b' once we have written the corresponding components of 'r'. ('r'
677 * might be one of 'a' or 'b'.)
678 */
679
680 /* n1, n2 */
681 if (b->Z_is_one) {
682 if (!BN_copy(n1, &a->X))
683 goto end;
684 if (!BN_copy(n2, &a->Y))
685 goto end;
686 /* n1 = X_a */
687 /* n2 = Y_a */
688 } else {
689 if (!field_sqr(group, n0, &b->Z, ctx))
690 goto end;
691 if (!field_mul(group, n1, &a->X, n0, ctx))
692 goto end;
693 /* n1 = X_a * Z_b^2 */
694
695 if (!field_mul(group, n0, n0, &b->Z, ctx))
696 goto end;
697 if (!field_mul(group, n2, &a->Y, n0, ctx))
698 goto end;
699 /* n2 = Y_a * Z_b^3 */
700 }
701
702 /* n3, n4 */
703 if (a->Z_is_one) {
704 if (!BN_copy(n3, &b->X))
705 goto end;
706 if (!BN_copy(n4, &b->Y))
707 goto end;
708 /* n3 = X_b */
709 /* n4 = Y_b */
710 } else {
711 if (!field_sqr(group, n0, &a->Z, ctx))
712 goto end;
713 if (!field_mul(group, n3, &b->X, n0, ctx))
714 goto end;
715 /* n3 = X_b * Z_a^2 */
716
717 if (!field_mul(group, n0, n0, &a->Z, ctx))
718 goto end;
719 if (!field_mul(group, n4, &b->Y, n0, ctx))
720 goto end;
721 /* n4 = Y_b * Z_a^3 */
722 }
723
724 /* n5, n6 */
725 if (!BN_mod_sub_quick(n5, n1, n3, p))
726 goto end;
727 if (!BN_mod_sub_quick(n6, n2, n4, p))
728 goto end;
729 /* n5 = n1 - n3 */
730 /* n6 = n2 - n4 */
731
732 if (BN_is_zero(n5)) {
733 if (BN_is_zero(n6)) {
734 /* a is the same point as b */
735 BN_CTX_end(ctx);
736 ret = EC_POINT_dbl(group, r, a, ctx);
737 ctx = NULL;
738 goto end;
739 } else {
740 /* a is the inverse of b */
741 BN_zero(&r->Z);
742 r->Z_is_one = 0;
743 ret = 1;
744 goto end;
745 }
746 }
747 /* 'n7', 'n8' */
748 if (!BN_mod_add_quick(n1, n1, n3, p))
749 goto end;
750 if (!BN_mod_add_quick(n2, n2, n4, p))
751 goto end;
752 /* 'n7' = n1 + n3 */
753 /* 'n8' = n2 + n4 */
754
755 /* Z_r */
756 if (a->Z_is_one && b->Z_is_one) {
757 if (!BN_copy(&r->Z, n5))
758 goto end;
759 } else {
760 if (a->Z_is_one) {
761 if (!BN_copy(n0, &b->Z))
762 goto end;
763 } else if (b->Z_is_one) {
764 if (!BN_copy(n0, &a->Z))
765 goto end;
766 } else {
767 if (!field_mul(group, n0, &a->Z, &b->Z, ctx))
768 goto end;
769 }
770 if (!field_mul(group, &r->Z, n0, n5, ctx))
771 goto end;
772 }
773 r->Z_is_one = 0;
774 /* Z_r = Z_a * Z_b * n5 */
775
776 /* X_r */
777 if (!field_sqr(group, n0, n6, ctx))
778 goto end;
779 if (!field_sqr(group, n4, n5, ctx))
780 goto end;
781 if (!field_mul(group, n3, n1, n4, ctx))
782 goto end;
783 if (!BN_mod_sub_quick(&r->X, n0, n3, p))
784 goto end;
785 /* X_r = n6^2 - n5^2 * 'n7' */
786
787 /* 'n9' */
788 if (!BN_mod_lshift1_quick(n0, &r->X, p))
789 goto end;
790 if (!BN_mod_sub_quick(n0, n3, n0, p))
791 goto end;
792 /* n9 = n5^2 * 'n7' - 2 * X_r */
793
794 /* Y_r */
795 if (!field_mul(group, n0, n0, n6, ctx))
796 goto end;
797 if (!field_mul(group, n5, n4, n5, ctx))
798 goto end; /* now n5 is n5^3 */
799 if (!field_mul(group, n1, n2, n5, ctx))
800 goto end;
801 if (!BN_mod_sub_quick(n0, n0, n1, p))
802 goto end;
803 if (BN_is_odd(n0))
804 if (!BN_add(n0, n0, p))
805 goto end;
806 /* now 0 <= n0 < 2*p, and n0 is even */
807 if (!BN_rshift1(&r->Y, n0))
808 goto end;
809 /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
810
811 ret = 1;
812
813end:
814 if (ctx) /* otherwise we already called BN_CTX_end */
815 BN_CTX_end(ctx);
816 BN_CTX_free(new_ctx);
817 return ret;
818}
819
820
821int
822ec_GFp_simple_dbl(const EC_GROUP * group, EC_POINT * r, const EC_POINT * a, BN_CTX * ctx)
823{
824 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
825 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
826 const BIGNUM *p;
827 BN_CTX *new_ctx = NULL;
828 BIGNUM *n0, *n1, *n2, *n3;
829 int ret = 0;
830
831 if (EC_POINT_is_at_infinity(group, a) > 0) {
832 BN_zero(&r->Z);
833 r->Z_is_one = 0;
834 return 1;
835 }
836 field_mul = group->meth->field_mul;
837 field_sqr = group->meth->field_sqr;
838 p = &group->field;
839
840 if (ctx == NULL) {
841 ctx = new_ctx = BN_CTX_new();
842 if (ctx == NULL)
843 return 0;
844 }
845 BN_CTX_start(ctx);
846 if ((n0 = BN_CTX_get(ctx)) == NULL)
847 goto err;
848 if ((n1 = BN_CTX_get(ctx)) == NULL)
849 goto err;
850 if ((n2 = BN_CTX_get(ctx)) == NULL)
851 goto err;
852 if ((n3 = BN_CTX_get(ctx)) == NULL)
853 goto err;
854
855 /*
856 * Note that in this function we must not read components of 'a' once
857 * we have written the corresponding components of 'r'. ('r' might
858 * the same as 'a'.)
859 */
860
861 /* n1 */
862 if (a->Z_is_one) {
863 if (!field_sqr(group, n0, &a->X, ctx))
864 goto err;
865 if (!BN_mod_lshift1_quick(n1, n0, p))
866 goto err;
867 if (!BN_mod_add_quick(n0, n0, n1, p))
868 goto err;
869 if (!BN_mod_add_quick(n1, n0, &group->a, p))
870 goto err;
871 /* n1 = 3 * X_a^2 + a_curve */
872 } else if (group->a_is_minus3) {
873 if (!field_sqr(group, n1, &a->Z, ctx))
874 goto err;
875 if (!BN_mod_add_quick(n0, &a->X, n1, p))
876 goto err;
877 if (!BN_mod_sub_quick(n2, &a->X, n1, p))
878 goto err;
879 if (!field_mul(group, n1, n0, n2, ctx))
880 goto err;
881 if (!BN_mod_lshift1_quick(n0, n1, p))
882 goto err;
883 if (!BN_mod_add_quick(n1, n0, n1, p))
884 goto err;
885 /*
886 * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) = 3 * X_a^2 - 3 *
887 * Z_a^4
888 */
889 } else {
890 if (!field_sqr(group, n0, &a->X, ctx))
891 goto err;
892 if (!BN_mod_lshift1_quick(n1, n0, p))
893 goto err;
894 if (!BN_mod_add_quick(n0, n0, n1, p))
895 goto err;
896 if (!field_sqr(group, n1, &a->Z, ctx))
897 goto err;
898 if (!field_sqr(group, n1, n1, ctx))
899 goto err;
900 if (!field_mul(group, n1, n1, &group->a, ctx))
901 goto err;
902 if (!BN_mod_add_quick(n1, n1, n0, p))
903 goto err;
904 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
905 }
906
907 /* Z_r */
908 if (a->Z_is_one) {
909 if (!BN_copy(n0, &a->Y))
910 goto err;
911 } else {
912 if (!field_mul(group, n0, &a->Y, &a->Z, ctx))
913 goto err;
914 }
915 if (!BN_mod_lshift1_quick(&r->Z, n0, p))
916 goto err;
917 r->Z_is_one = 0;
918 /* Z_r = 2 * Y_a * Z_a */
919
920 /* n2 */
921 if (!field_sqr(group, n3, &a->Y, ctx))
922 goto err;
923 if (!field_mul(group, n2, &a->X, n3, ctx))
924 goto err;
925 if (!BN_mod_lshift_quick(n2, n2, 2, p))
926 goto err;
927 /* n2 = 4 * X_a * Y_a^2 */
928
929 /* X_r */
930 if (!BN_mod_lshift1_quick(n0, n2, p))
931 goto err;
932 if (!field_sqr(group, &r->X, n1, ctx))
933 goto err;
934 if (!BN_mod_sub_quick(&r->X, &r->X, n0, p))
935 goto err;
936 /* X_r = n1^2 - 2 * n2 */
937
938 /* n3 */
939 if (!field_sqr(group, n0, n3, ctx))
940 goto err;
941 if (!BN_mod_lshift_quick(n3, n0, 3, p))
942 goto err;
943 /* n3 = 8 * Y_a^4 */
944
945 /* Y_r */
946 if (!BN_mod_sub_quick(n0, n2, &r->X, p))
947 goto err;
948 if (!field_mul(group, n0, n1, n0, ctx))
949 goto err;
950 if (!BN_mod_sub_quick(&r->Y, n0, n3, p))
951 goto err;
952 /* Y_r = n1 * (n2 - X_r) - n3 */
953
954 ret = 1;
955
956err:
957 BN_CTX_end(ctx);
958 BN_CTX_free(new_ctx);
959 return ret;
960}
961
962
963int
964ec_GFp_simple_invert(const EC_GROUP * group, EC_POINT * point, BN_CTX * ctx)
965{
966 if (EC_POINT_is_at_infinity(group, point) > 0 || BN_is_zero(&point->Y))
967 /* point is its own inverse */
968 return 1;
969
970 return BN_usub(&point->Y, &group->field, &point->Y);
971}
972
973
974int
975ec_GFp_simple_is_at_infinity(const EC_GROUP * group, const EC_POINT * point)
976{
977 return BN_is_zero(&point->Z);
978}
979
980
981int
982ec_GFp_simple_is_on_curve(const EC_GROUP * group, const EC_POINT * point, BN_CTX * ctx)
983{
984 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
985 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
986 const BIGNUM *p;
987 BN_CTX *new_ctx = NULL;
988 BIGNUM *rh, *tmp, *Z4, *Z6;
989 int ret = -1;
990
991 if (EC_POINT_is_at_infinity(group, point) > 0)
992 return 1;
993
994 field_mul = group->meth->field_mul;
995 field_sqr = group->meth->field_sqr;
996 p = &group->field;
997
998 if (ctx == NULL) {
999 ctx = new_ctx = BN_CTX_new();
1000 if (ctx == NULL)
1001 return -1;
1002 }
1003 BN_CTX_start(ctx);
1004 if ((rh = BN_CTX_get(ctx)) == NULL)
1005 goto err;
1006 if ((tmp = BN_CTX_get(ctx)) == NULL)
1007 goto err;
1008 if ((Z4 = BN_CTX_get(ctx)) == NULL)
1009 goto err;
1010 if ((Z6 = BN_CTX_get(ctx)) == NULL)
1011 goto err;
1012
1013 /*
1014 * We have a curve defined by a Weierstrass equation y^2 = x^3 + a*x
1015 * + b. The point to consider is given in Jacobian projective
1016 * coordinates where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3).
1017 * Substituting this and multiplying by Z^6 transforms the above
1018 * equation into Y^2 = X^3 + a*X*Z^4 + b*Z^6. To test this, we add up
1019 * the right-hand side in 'rh'.
1020 */
1021
1022 /* rh := X^2 */
1023 if (!field_sqr(group, rh, &point->X, ctx))
1024 goto err;
1025
1026 if (!point->Z_is_one) {
1027 if (!field_sqr(group, tmp, &point->Z, ctx))
1028 goto err;
1029 if (!field_sqr(group, Z4, tmp, ctx))
1030 goto err;
1031 if (!field_mul(group, Z6, Z4, tmp, ctx))
1032 goto err;
1033
1034 /* rh := (rh + a*Z^4)*X */
1035 if (group->a_is_minus3) {
1036 if (!BN_mod_lshift1_quick(tmp, Z4, p))
1037 goto err;
1038 if (!BN_mod_add_quick(tmp, tmp, Z4, p))
1039 goto err;
1040 if (!BN_mod_sub_quick(rh, rh, tmp, p))
1041 goto err;
1042 if (!field_mul(group, rh, rh, &point->X, ctx))
1043 goto err;
1044 } else {
1045 if (!field_mul(group, tmp, Z4, &group->a, ctx))
1046 goto err;
1047 if (!BN_mod_add_quick(rh, rh, tmp, p))
1048 goto err;
1049 if (!field_mul(group, rh, rh, &point->X, ctx))
1050 goto err;
1051 }
1052
1053 /* rh := rh + b*Z^6 */
1054 if (!field_mul(group, tmp, &group->b, Z6, ctx))
1055 goto err;
1056 if (!BN_mod_add_quick(rh, rh, tmp, p))
1057 goto err;
1058 } else {
1059 /* point->Z_is_one */
1060
1061 /* rh := (rh + a)*X */
1062 if (!BN_mod_add_quick(rh, rh, &group->a, p))
1063 goto err;
1064 if (!field_mul(group, rh, rh, &point->X, ctx))
1065 goto err;
1066 /* rh := rh + b */
1067 if (!BN_mod_add_quick(rh, rh, &group->b, p))
1068 goto err;
1069 }
1070
1071 /* 'lh' := Y^2 */
1072 if (!field_sqr(group, tmp, &point->Y, ctx))
1073 goto err;
1074
1075 ret = (0 == BN_ucmp(tmp, rh));
1076
1077err:
1078 BN_CTX_end(ctx);
1079 BN_CTX_free(new_ctx);
1080 return ret;
1081}
1082
1083
1084int
1085ec_GFp_simple_cmp(const EC_GROUP * group, const EC_POINT * a, const EC_POINT * b, BN_CTX * ctx)
1086{
1087 /*
1088 * return values: -1 error 0 equal (in affine coordinates) 1
1089 * not equal
1090 */
1091
1092 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1093 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1094 BN_CTX *new_ctx = NULL;
1095 BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
1096 const BIGNUM *tmp1_, *tmp2_;
1097 int ret = -1;
1098
1099 if (EC_POINT_is_at_infinity(group, a) > 0) {
1100 return EC_POINT_is_at_infinity(group, b) > 0 ? 0 : 1;
1101 }
1102 if (EC_POINT_is_at_infinity(group, b) > 0)
1103 return 1;
1104
1105 if (a->Z_is_one && b->Z_is_one) {
1106 return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
1107 }
1108 field_mul = group->meth->field_mul;
1109 field_sqr = group->meth->field_sqr;
1110
1111 if (ctx == NULL) {
1112 ctx = new_ctx = BN_CTX_new();
1113 if (ctx == NULL)
1114 return -1;
1115 }
1116 BN_CTX_start(ctx);
1117 if ((tmp1 = BN_CTX_get(ctx)) == NULL)
1118 goto end;
1119 if ((tmp2 = BN_CTX_get(ctx)) == NULL)
1120 goto end;
1121 if ((Za23 = BN_CTX_get(ctx)) == NULL)
1122 goto end;
1123 if ((Zb23 = BN_CTX_get(ctx)) == NULL)
1124 goto end;
1125
1126 /*
1127 * We have to decide whether (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2,
1128 * Y_b/Z_b^3), or equivalently, whether (X_a*Z_b^2, Y_a*Z_b^3) =
1129 * (X_b*Z_a^2, Y_b*Z_a^3).
1130 */
1131
1132 if (!b->Z_is_one) {
1133 if (!field_sqr(group, Zb23, &b->Z, ctx))
1134 goto end;
1135 if (!field_mul(group, tmp1, &a->X, Zb23, ctx))
1136 goto end;
1137 tmp1_ = tmp1;
1138 } else
1139 tmp1_ = &a->X;
1140 if (!a->Z_is_one) {
1141 if (!field_sqr(group, Za23, &a->Z, ctx))
1142 goto end;
1143 if (!field_mul(group, tmp2, &b->X, Za23, ctx))
1144 goto end;
1145 tmp2_ = tmp2;
1146 } else
1147 tmp2_ = &b->X;
1148
1149 /* compare X_a*Z_b^2 with X_b*Z_a^2 */
1150 if (BN_cmp(tmp1_, tmp2_) != 0) {
1151 ret = 1; /* points differ */
1152 goto end;
1153 }
1154 if (!b->Z_is_one) {
1155 if (!field_mul(group, Zb23, Zb23, &b->Z, ctx))
1156 goto end;
1157 if (!field_mul(group, tmp1, &a->Y, Zb23, ctx))
1158 goto end;
1159 /* tmp1_ = tmp1 */
1160 } else
1161 tmp1_ = &a->Y;
1162 if (!a->Z_is_one) {
1163 if (!field_mul(group, Za23, Za23, &a->Z, ctx))
1164 goto end;
1165 if (!field_mul(group, tmp2, &b->Y, Za23, ctx))
1166 goto end;
1167 /* tmp2_ = tmp2 */
1168 } else
1169 tmp2_ = &b->Y;
1170
1171 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */
1172 if (BN_cmp(tmp1_, tmp2_) != 0) {
1173 ret = 1; /* points differ */
1174 goto end;
1175 }
1176 /* points are equal */
1177 ret = 0;
1178
1179end:
1180 BN_CTX_end(ctx);
1181 BN_CTX_free(new_ctx);
1182 return ret;
1183}
1184
1185
1186int
1187ec_GFp_simple_make_affine(const EC_GROUP * group, EC_POINT * point, BN_CTX * ctx)
1188{
1189 BN_CTX *new_ctx = NULL;
1190 BIGNUM *x, *y;
1191 int ret = 0;
1192
1193 if (point->Z_is_one || EC_POINT_is_at_infinity(group, point) > 0)
1194 return 1;
1195
1196 if (ctx == NULL) {
1197 ctx = new_ctx = BN_CTX_new();
1198 if (ctx == NULL)
1199 return 0;
1200 }
1201 BN_CTX_start(ctx);
1202 if ((x = BN_CTX_get(ctx)) == NULL)
1203 goto err;
1204 if ((y = BN_CTX_get(ctx)) == NULL)
1205 goto err;
1206
1207 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx))
1208 goto err;
1209 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
1210 goto err;
1211 if (!point->Z_is_one) {
1212 ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
1213 goto err;
1214 }
1215 ret = 1;
1216
1217err:
1218 BN_CTX_end(ctx);
1219 BN_CTX_free(new_ctx);
1220 return ret;
1221}
1222
1223
1224int
1225ec_GFp_simple_points_make_affine(const EC_GROUP * group, size_t num, EC_POINT * points[], BN_CTX * ctx)
1226{
1227 BN_CTX *new_ctx = NULL;
1228 BIGNUM *tmp0, *tmp1;
1229 size_t pow2 = 0;
1230 BIGNUM **heap = NULL;
1231 size_t i;
1232 int ret = 0;
1233
1234 if (num == 0)
1235 return 1;
1236
1237 if (ctx == NULL) {
1238 ctx = new_ctx = BN_CTX_new();
1239 if (ctx == NULL)
1240 return 0;
1241 }
1242 BN_CTX_start(ctx);
1243 if ((tmp0 = BN_CTX_get(ctx)) == NULL)
1244 goto err;
1245 if ((tmp1 = BN_CTX_get(ctx)) == NULL)
1246 goto err;
1247
1248 /*
1249 * Before converting the individual points, compute inverses of all Z
1250 * values. Modular inversion is rather slow, but luckily we can do
1251 * with a single explicit inversion, plus about 3 multiplications per
1252 * input value.
1253 */
1254
1255 pow2 = 1;
1256 while (num > pow2)
1257 pow2 <<= 1;
1258 /*
1259 * Now pow2 is the smallest power of 2 satifsying pow2 >= num. We
1260 * need twice that.
1261 */
1262 pow2 <<= 1;
1263
1264 heap = reallocarray(NULL, pow2, sizeof heap[0]);
1265 if (heap == NULL)
1266 goto err;
1267
1268 /*
1269 * The array is used as a binary tree, exactly as in heapsort:
1270 *
1271 * heap[1] heap[2] heap[3] heap[4] heap[5]
1272 * heap[6] heap[7] heap[8]heap[9] heap[10]heap[11]
1273 * heap[12]heap[13] heap[14] heap[15]
1274 *
1275 * We put the Z's in the last line; then we set each other node to the
1276 * product of its two child-nodes (where empty or 0 entries are
1277 * treated as ones); then we invert heap[1]; then we invert each
1278 * other node by replacing it by the product of its parent (after
1279 * inversion) and its sibling (before inversion).
1280 */
1281 heap[0] = NULL;
1282 for (i = pow2 / 2 - 1; i > 0; i--)
1283 heap[i] = NULL;
1284 for (i = 0; i < num; i++)
1285 heap[pow2 / 2 + i] = &points[i]->Z;
1286 for (i = pow2 / 2 + num; i < pow2; i++)
1287 heap[i] = NULL;
1288
1289 /* set each node to the product of its children */
1290 for (i = pow2 / 2 - 1; i > 0; i--) {
1291 heap[i] = BN_new();
1292 if (heap[i] == NULL)
1293 goto err;
1294
1295 if (heap[2 * i] != NULL) {
1296 if ((heap[2 * i + 1] == NULL) || BN_is_zero(heap[2 * i + 1])) {
1297 if (!BN_copy(heap[i], heap[2 * i]))
1298 goto err;
1299 } else {
1300 if (BN_is_zero(heap[2 * i])) {
1301 if (!BN_copy(heap[i], heap[2 * i + 1]))
1302 goto err;
1303 } else {
1304 if (!group->meth->field_mul(group, heap[i],
1305 heap[2 * i], heap[2 * i + 1], ctx))
1306 goto err;
1307 }
1308 }
1309 }
1310 }
1311
1312 /* invert heap[1] */
1313 if (!BN_is_zero(heap[1])) {
1314 if (!BN_mod_inverse(heap[1], heap[1], &group->field, ctx)) {
1315 ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
1316 goto err;
1317 }
1318 }
1319 if (group->meth->field_encode != 0) {
1320 /*
1321 * in the Montgomery case, we just turned R*H (representing
1322 * H) into 1/(R*H), but we need R*(1/H) (representing
1323 * 1/H); i.e. we have need to multiply by the Montgomery
1324 * factor twice
1325 */
1326 if (!group->meth->field_encode(group, heap[1], heap[1], ctx))
1327 goto err;
1328 if (!group->meth->field_encode(group, heap[1], heap[1], ctx))
1329 goto err;
1330 }
1331 /* set other heap[i]'s to their inverses */
1332 for (i = 2; i < pow2 / 2 + num; i += 2) {
1333 /* i is even */
1334 if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1])) {
1335 if (!group->meth->field_mul(group, tmp0, heap[i / 2], heap[i + 1], ctx))
1336 goto err;
1337 if (!group->meth->field_mul(group, tmp1, heap[i / 2], heap[i], ctx))
1338 goto err;
1339 if (!BN_copy(heap[i], tmp0))
1340 goto err;
1341 if (!BN_copy(heap[i + 1], tmp1))
1342 goto err;
1343 } else {
1344 if (!BN_copy(heap[i], heap[i / 2]))
1345 goto err;
1346 }
1347 }
1348
1349 /*
1350 * we have replaced all non-zero Z's by their inverses, now fix up
1351 * all the points
1352 */
1353 for (i = 0; i < num; i++) {
1354 EC_POINT *p = points[i];
1355
1356 if (!BN_is_zero(&p->Z)) {
1357 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */
1358
1359 if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx))
1360 goto err;
1361 if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx))
1362 goto err;
1363
1364 if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx))
1365 goto err;
1366 if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx))
1367 goto err;
1368
1369 if (group->meth->field_set_to_one != 0) {
1370 if (!group->meth->field_set_to_one(group, &p->Z, ctx))
1371 goto err;
1372 } else {
1373 if (!BN_one(&p->Z))
1374 goto err;
1375 }
1376 p->Z_is_one = 1;
1377 }
1378 }
1379
1380 ret = 1;
1381
1382err:
1383 BN_CTX_end(ctx);
1384 BN_CTX_free(new_ctx);
1385 if (heap != NULL) {
1386 /*
1387 * heap[pow2/2] .. heap[pow2-1] have not been allocated
1388 * locally!
1389 */
1390 for (i = pow2 / 2 - 1; i > 0; i--) {
1391 BN_clear_free(heap[i]);
1392 }
1393 free(heap);
1394 }
1395 return ret;
1396}
1397
1398
1399int
1400ec_GFp_simple_field_mul(const EC_GROUP * group, BIGNUM * r, const BIGNUM * a, const BIGNUM * b, BN_CTX * ctx)
1401{
1402 return BN_mod_mul(r, a, b, &group->field, ctx);
1403}
1404
1405
1406int
1407ec_GFp_simple_field_sqr(const EC_GROUP * group, BIGNUM * r, const BIGNUM * a, BN_CTX * ctx)
1408{
1409 return BN_mod_sqr(r, a, &group->field, ctx);
1410}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-05-07 21:41:02 +0000