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