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