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