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 if (ctx != NULL)
340 BN_CTX_end(ctx);
341 if (new_ctx != NULL)
342 BN_CTX_free(new_ctx);
343 return ret;
344 }
345
346
ec_GFp_simple_point_init(EC_POINT * point)347 int ec_GFp_simple_point_init(EC_POINT *point)
348 {
349 BN_init(&point->X);
350 BN_init(&point->Y);
351 BN_init(&point->Z);
352 point->Z_is_one = 0;
353
354 return 1;
355 }
356
357
ec_GFp_simple_point_finish(EC_POINT * point)358 void ec_GFp_simple_point_finish(EC_POINT *point)
359 {
360 BN_free(&point->X);
361 BN_free(&point->Y);
362 BN_free(&point->Z);
363 }
364
365
ec_GFp_simple_point_clear_finish(EC_POINT * point)366 void ec_GFp_simple_point_clear_finish(EC_POINT *point)
367 {
368 BN_clear_free(&point->X);
369 BN_clear_free(&point->Y);
370 BN_clear_free(&point->Z);
371 point->Z_is_one = 0;
372 }
373
374
ec_GFp_simple_point_copy(EC_POINT * dest,const EC_POINT * src)375 int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
376 {
377 if (!BN_copy(&dest->X, &src->X)) return 0;
378 if (!BN_copy(&dest->Y, &src->Y)) return 0;
379 if (!BN_copy(&dest->Z, &src->Z)) return 0;
380 dest->Z_is_one = src->Z_is_one;
381
382 return 1;
383 }
384
385
ec_GFp_simple_point_set_to_infinity(const EC_GROUP * group,EC_POINT * point)386 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
387 {
388 point->Z_is_one = 0;
389 BN_zero(&point->Z);
390 return 1;
391 }
392
393
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)394 int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
395 const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx)
396 {
397 BN_CTX *new_ctx = NULL;
398 int ret = 0;
399
400 if (ctx == NULL)
401 {
402 ctx = new_ctx = BN_CTX_new();
403 if (ctx == NULL)
404 return 0;
405 }
406
407 if (x != NULL)
408 {
409 if (!BN_nnmod(&point->X, x, &group->field, ctx)) goto err;
410 if (group->meth->field_encode)
411 {
412 if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) goto err;
413 }
414 }
415
416 if (y != NULL)
417 {
418 if (!BN_nnmod(&point->Y, y, &group->field, ctx)) goto err;
419 if (group->meth->field_encode)
420 {
421 if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) goto err;
422 }
423 }
424
425 if (z != NULL)
426 {
427 int Z_is_one;
428
429 if (!BN_nnmod(&point->Z, z, &group->field, ctx)) goto err;
430 Z_is_one = BN_is_one(&point->Z);
431 if (group->meth->field_encode)
432 {
433 if (Z_is_one && (group->meth->field_set_to_one != 0))
434 {
435 if (!group->meth->field_set_to_one(group, &point->Z, ctx)) goto err;
436 }
437 else
438 {
439 if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err;
440 }
441 }
442 point->Z_is_one = Z_is_one;
443 }
444
445 ret = 1;
446
447 err:
448 if (new_ctx != NULL)
449 BN_CTX_free(new_ctx);
450 return ret;
451 }
452
453
ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP * group,const EC_POINT * point,BIGNUM * x,BIGNUM * y,BIGNUM * z,BN_CTX * ctx)454 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point,
455 BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx)
456 {
457 BN_CTX *new_ctx = NULL;
458 int ret = 0;
459
460 if (group->meth->field_decode != 0)
461 {
462 if (ctx == NULL)
463 {
464 ctx = new_ctx = BN_CTX_new();
465 if (ctx == NULL)
466 return 0;
467 }
468
469 if (x != NULL)
470 {
471 if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err;
472 }
473 if (y != NULL)
474 {
475 if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err;
476 }
477 if (z != NULL)
478 {
479 if (!group->meth->field_decode(group, z, &point->Z, ctx)) goto err;
480 }
481 }
482 else
483 {
484 if (x != NULL)
485 {
486 if (!BN_copy(x, &point->X)) goto err;
487 }
488 if (y != NULL)
489 {
490 if (!BN_copy(y, &point->Y)) goto err;
491 }
492 if (z != NULL)
493 {
494 if (!BN_copy(z, &point->Z)) goto err;
495 }
496 }
497
498 ret = 1;
499
500 err:
501 if (new_ctx != NULL)
502 BN_CTX_free(new_ctx);
503 return ret;
504 }
505
506
ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x,const BIGNUM * y,BN_CTX * ctx)507 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point,
508 const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
509 {
510 if (x == NULL || y == NULL)
511 {
512 /* unlike for projective coordinates, we do not tolerate this */
513 ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PASSED_NULL_PARAMETER);
514 return 0;
515 }
516
517 return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, BN_value_one(), ctx);
518 }
519
520
ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP * group,const EC_POINT * point,BIGNUM * x,BIGNUM * y,BN_CTX * ctx)521 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point,
522 BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
523 {
524 BN_CTX *new_ctx = NULL;
525 BIGNUM *Z, *Z_1, *Z_2, *Z_3;
526 const BIGNUM *Z_;
527 int ret = 0;
528
529 if (EC_POINT_is_at_infinity(group, point))
530 {
531 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POINT_AT_INFINITY);
532 return 0;
533 }
534
535 if (ctx == NULL)
536 {
537 ctx = new_ctx = BN_CTX_new();
538 if (ctx == NULL)
539 return 0;
540 }
541
542 BN_CTX_start(ctx);
543 Z = BN_CTX_get(ctx);
544 Z_1 = BN_CTX_get(ctx);
545 Z_2 = BN_CTX_get(ctx);
546 Z_3 = BN_CTX_get(ctx);
547 if (Z_3 == NULL) goto err;
548
549 /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */
550
551 if (group->meth->field_decode)
552 {
553 if (!group->meth->field_decode(group, Z, &point->Z, ctx)) goto err;
554 Z_ = Z;
555 }
556 else
557 {
558 Z_ = &point->Z;
559 }
560
561 if (BN_is_one(Z_))
562 {
563 if (group->meth->field_decode)
564 {
565 if (x != NULL)
566 {
567 if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err;
568 }
569 if (y != NULL)
570 {
571 if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err;
572 }
573 }
574 else
575 {
576 if (x != NULL)
577 {
578 if (!BN_copy(x, &point->X)) goto err;
579 }
580 if (y != NULL)
581 {
582 if (!BN_copy(y, &point->Y)) goto err;
583 }
584 }
585 }
586 else
587 {
588 if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx))
589 {
590 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_BN_LIB);
591 goto err;
592 }
593
594 if (group->meth->field_encode == 0)
595 {
596 /* field_sqr works on standard representation */
597 if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) goto err;
598 }
599 else
600 {
601 if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err;
602 }
603
604 if (x != NULL)
605 {
606 /* in the Montgomery case, field_mul will cancel out Montgomery factor in X: */
607 if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx)) goto err;
608 }
609
610 if (y != NULL)
611 {
612 if (group->meth->field_encode == 0)
613 {
614 /* field_mul works on standard representation */
615 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) goto err;
616 }
617 else
618 {
619 if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto err;
620 }
621
622 /* in the Montgomery case, field_mul will cancel out Montgomery factor in Y: */
623 if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) goto err;
624 }
625 }
626
627 ret = 1;
628
629 err:
630 BN_CTX_end(ctx);
631 if (new_ctx != NULL)
632 BN_CTX_free(new_ctx);
633 return ret;
634 }
635
636
ec_GFp_simple_set_compressed_coordinates(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x_,int y_bit,BN_CTX * ctx)637 int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, EC_POINT *point,
638 const BIGNUM *x_, int y_bit, BN_CTX *ctx)
639 {
640 BN_CTX *new_ctx = NULL;
641 BIGNUM *tmp1, *tmp2, *x, *y;
642 int ret = 0;
643
644 /* clear error queue*/
645 ERR_clear_error();
646
647 if (ctx == NULL)
648 {
649 ctx = new_ctx = BN_CTX_new();
650 if (ctx == NULL)
651 return 0;
652 }
653
654 y_bit = (y_bit != 0);
655
656 BN_CTX_start(ctx);
657 tmp1 = BN_CTX_get(ctx);
658 tmp2 = BN_CTX_get(ctx);
659 x = BN_CTX_get(ctx);
660 y = BN_CTX_get(ctx);
661 if (y == NULL) goto err;
662
663 /* Recover y. We have a Weierstrass equation
664 * y^2 = x^3 + a*x + b,
665 * so y is one of the square roots of x^3 + a*x + b.
666 */
667
668 /* tmp1 := x^3 */
669 if (!BN_nnmod(x, x_, &group->field,ctx)) goto err;
670 if (group->meth->field_decode == 0)
671 {
672 /* field_{sqr,mul} work on standard representation */
673 if (!group->meth->field_sqr(group, tmp2, x_, ctx)) goto err;
674 if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) goto err;
675 }
676 else
677 {
678 if (!BN_mod_sqr(tmp2, x_, &group->field, ctx)) goto err;
679 if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) goto err;
680 }
681
682 /* tmp1 := tmp1 + a*x */
683 if (group->a_is_minus3)
684 {
685 if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) goto err;
686 if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) goto err;
687 if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
688 }
689 else
690 {
691 if (group->meth->field_decode)
692 {
693 if (!group->meth->field_decode(group, tmp2, &group->a, ctx)) goto err;
694 if (!BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) goto err;
695 }
696 else
697 {
698 /* field_mul works on standard representation */
699 if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) goto err;
700 }
701
702 if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
703 }
704
705 /* tmp1 := tmp1 + b */
706 if (group->meth->field_decode)
707 {
708 if (!group->meth->field_decode(group, tmp2, &group->b, ctx)) goto err;
709 if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
710 }
711 else
712 {
713 if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) goto err;
714 }
715
716 if (!BN_mod_sqrt(y, tmp1, &group->field, ctx))
717 {
718 unsigned long err = ERR_peek_last_error();
719
720 if (ERR_GET_LIB(err) == ERR_LIB_BN && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE)
721 {
722 ERR_clear_error();
723 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
724 }
725 else
726 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_BN_LIB);
727 goto err;
728 }
729
730 if (y_bit != BN_is_odd(y))
731 {
732 if (BN_is_zero(y))
733 {
734 int kron;
735
736 kron = BN_kronecker(x, &group->field, ctx);
737 if (kron == -2) goto err;
738
739 if (kron == 1)
740 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSION_BIT);
741 else
742 /* BN_mod_sqrt() should have cought this error (not a square) */
743 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
744 goto err;
745 }
746 if (!BN_usub(y, &group->field, y)) goto err;
747 }
748 if (y_bit != BN_is_odd(y))
749 {
750 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_INTERNAL_ERROR);
751 goto err;
752 }
753
754 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
755
756 ret = 1;
757
758 err:
759 BN_CTX_end(ctx);
760 if (new_ctx != NULL)
761 BN_CTX_free(new_ctx);
762 return ret;
763 }
764
765
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)766 size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, point_conversion_form_t form,
767 unsigned char *buf, size_t len, BN_CTX *ctx)
768 {
769 size_t ret;
770 BN_CTX *new_ctx = NULL;
771 int used_ctx = 0;
772 BIGNUM *x, *y;
773 size_t field_len, i, skip;
774
775 if ((form != POINT_CONVERSION_COMPRESSED)
776 && (form != POINT_CONVERSION_UNCOMPRESSED)
777 && (form != POINT_CONVERSION_HYBRID))
778 {
779 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
780 goto err;
781 }
782
783 if (EC_POINT_is_at_infinity(group, point))
784 {
785 /* encodes to a single 0 octet */
786 if (buf != NULL)
787 {
788 if (len < 1)
789 {
790 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
791 return 0;
792 }
793 buf[0] = 0;
794 }
795 return 1;
796 }
797
798
799 /* ret := required output buffer length */
800 field_len = BN_num_bytes(&group->field);
801 ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
802
803 /* if 'buf' is NULL, just return required length */
804 if (buf != NULL)
805 {
806 if (len < ret)
807 {
808 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
809 goto err;
810 }
811
812 if (ctx == NULL)
813 {
814 ctx = new_ctx = BN_CTX_new();
815 if (ctx == NULL)
816 return 0;
817 }
818
819 BN_CTX_start(ctx);
820 used_ctx = 1;
821 x = BN_CTX_get(ctx);
822 y = BN_CTX_get(ctx);
823 if (y == NULL) goto err;
824
825 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
826
827 if ((form == POINT_CONVERSION_COMPRESSED || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y))
828 buf[0] = form + 1;
829 else
830 buf[0] = form;
831
832 i = 1;
833
834 skip = field_len - BN_num_bytes(x);
835 if (skip > field_len)
836 {
837 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
838 goto err;
839 }
840 while (skip > 0)
841 {
842 buf[i++] = 0;
843 skip--;
844 }
845 skip = BN_bn2bin(x, buf + i);
846 i += skip;
847 if (i != 1 + field_len)
848 {
849 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
850 goto err;
851 }
852
853 if (form == POINT_CONVERSION_UNCOMPRESSED || form == POINT_CONVERSION_HYBRID)
854 {
855 skip = field_len - BN_num_bytes(y);
856 if (skip > field_len)
857 {
858 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
859 goto err;
860 }
861 while (skip > 0)
862 {
863 buf[i++] = 0;
864 skip--;
865 }
866 skip = BN_bn2bin(y, buf + i);
867 i += skip;
868 }
869
870 if (i != ret)
871 {
872 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
873 goto err;
874 }
875 }
876
877 if (used_ctx)
878 BN_CTX_end(ctx);
879 if (new_ctx != NULL)
880 BN_CTX_free(new_ctx);
881 return ret;
882
883 err:
884 if (used_ctx)
885 BN_CTX_end(ctx);
886 if (new_ctx != NULL)
887 BN_CTX_free(new_ctx);
888 return 0;
889 }
890
891
ec_GFp_simple_oct2point(const EC_GROUP * group,EC_POINT * point,const unsigned char * buf,size_t len,BN_CTX * ctx)892 int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
893 const unsigned char *buf, size_t len, BN_CTX *ctx)
894 {
895 point_conversion_form_t form;
896 int y_bit;
897 BN_CTX *new_ctx = NULL;
898 BIGNUM *x, *y;
899 size_t field_len, enc_len;
900 int ret = 0;
901
902 if (len == 0)
903 {
904 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
905 return 0;
906 }
907 form = buf[0];
908 y_bit = form & 1;
909 form = form & ~1U;
910 if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
911 && (form != POINT_CONVERSION_UNCOMPRESSED)
912 && (form != POINT_CONVERSION_HYBRID))
913 {
914 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
915 return 0;
916 }
917 if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit)
918 {
919 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
920 return 0;
921 }
922
923 if (form == 0)
924 {
925 if (len != 1)
926 {
927 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
928 return 0;
929 }
930
931 return EC_POINT_set_to_infinity(group, point);
932 }
933
934 field_len = BN_num_bytes(&group->field);
935 enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
936
937 if (len != enc_len)
938 {
939 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
940 return 0;
941 }
942
943 if (ctx == NULL)
944 {
945 ctx = new_ctx = BN_CTX_new();
946 if (ctx == NULL)
947 return 0;
948 }
949
950 BN_CTX_start(ctx);
951 x = BN_CTX_get(ctx);
952 y = BN_CTX_get(ctx);
953 if (y == NULL) goto err;
954
955 if (!BN_bin2bn(buf + 1, field_len, x)) goto err;
956 if (BN_ucmp(x, &group->field) >= 0)
957 {
958 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
959 goto err;
960 }
961
962 if (form == POINT_CONVERSION_COMPRESSED)
963 {
964 if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) goto err;
965 }
966 else
967 {
968 if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) goto err;
969 if (BN_ucmp(y, &group->field) >= 0)
970 {
971 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
972 goto err;
973 }
974 if (form == POINT_CONVERSION_HYBRID)
975 {
976 if (y_bit != BN_is_odd(y))
977 {
978 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
979 goto err;
980 }
981 }
982
983 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
984 }
985
986 if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */
987 {
988 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
989 goto err;
990 }
991
992 ret = 1;
993
994 err:
995 BN_CTX_end(ctx);
996 if (new_ctx != NULL)
997 BN_CTX_free(new_ctx);
998 return ret;
999 }
1000
1001
ec_GFp_simple_add(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)1002 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
1003 {
1004 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1005 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1006 const BIGNUM *p;
1007 BN_CTX *new_ctx = NULL;
1008 BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
1009 int ret = 0;
1010
1011 if (a == b)
1012 return EC_POINT_dbl(group, r, a, ctx);
1013 if (EC_POINT_is_at_infinity(group, a))
1014 return EC_POINT_copy(r, b);
1015 if (EC_POINT_is_at_infinity(group, b))
1016 return EC_POINT_copy(r, a);
1017
1018 field_mul = group->meth->field_mul;
1019 field_sqr = group->meth->field_sqr;
1020 p = &group->field;
1021
1022 if (ctx == NULL)
1023 {
1024 ctx = new_ctx = BN_CTX_new();
1025 if (ctx == NULL)
1026 return 0;
1027 }
1028
1029 BN_CTX_start(ctx);
1030 n0 = BN_CTX_get(ctx);
1031 n1 = BN_CTX_get(ctx);
1032 n2 = BN_CTX_get(ctx);
1033 n3 = BN_CTX_get(ctx);
1034 n4 = BN_CTX_get(ctx);
1035 n5 = BN_CTX_get(ctx);
1036 n6 = BN_CTX_get(ctx);
1037 if (n6 == NULL) goto end;
1038
1039 /* Note that in this function we must not read components of 'a' or 'b'
1040 * once we have written the corresponding components of 'r'.
1041 * ('r' might be one of 'a' or 'b'.)
1042 */
1043
1044 /* n1, n2 */
1045 if (b->Z_is_one)
1046 {
1047 if (!BN_copy(n1, &a->X)) goto end;
1048 if (!BN_copy(n2, &a->Y)) goto end;
1049 /* n1 = X_a */
1050 /* n2 = Y_a */
1051 }
1052 else
1053 {
1054 if (!field_sqr(group, n0, &b->Z, ctx)) goto end;
1055 if (!field_mul(group, n1, &a->X, n0, ctx)) goto end;
1056 /* n1 = X_a * Z_b^2 */
1057
1058 if (!field_mul(group, n0, n0, &b->Z, ctx)) goto end;
1059 if (!field_mul(group, n2, &a->Y, n0, ctx)) goto end;
1060 /* n2 = Y_a * Z_b^3 */
1061 }
1062
1063 /* n3, n4 */
1064 if (a->Z_is_one)
1065 {
1066 if (!BN_copy(n3, &b->X)) goto end;
1067 if (!BN_copy(n4, &b->Y)) goto end;
1068 /* n3 = X_b */
1069 /* n4 = Y_b */
1070 }
1071 else
1072 {
1073 if (!field_sqr(group, n0, &a->Z, ctx)) goto end;
1074 if (!field_mul(group, n3, &b->X, n0, ctx)) goto end;
1075 /* n3 = X_b * Z_a^2 */
1076
1077 if (!field_mul(group, n0, n0, &a->Z, ctx)) goto end;
1078 if (!field_mul(group, n4, &b->Y, n0, ctx)) goto end;
1079 /* n4 = Y_b * Z_a^3 */
1080 }
1081
1082 /* n5, n6 */
1083 if (!BN_mod_sub_quick(n5, n1, n3, p)) goto end;
1084 if (!BN_mod_sub_quick(n6, n2, n4, p)) goto end;
1085 /* n5 = n1 - n3 */
1086 /* n6 = n2 - n4 */
1087
1088 if (BN_is_zero(n5))
1089 {
1090 if (BN_is_zero(n6))
1091 {
1092 /* a is the same point as b */
1093 BN_CTX_end(ctx);
1094 ret = EC_POINT_dbl(group, r, a, ctx);
1095 ctx = NULL;
1096 goto end;
1097 }
1098 else
1099 {
1100 /* a is the inverse of b */
1101 BN_zero(&r->Z);
1102 r->Z_is_one = 0;
1103 ret = 1;
1104 goto end;
1105 }
1106 }
1107
1108 /* 'n7', 'n8' */
1109 if (!BN_mod_add_quick(n1, n1, n3, p)) goto end;
1110 if (!BN_mod_add_quick(n2, n2, n4, p)) goto end;
1111 /* 'n7' = n1 + n3 */
1112 /* 'n8' = n2 + n4 */
1113
1114 /* Z_r */
1115 if (a->Z_is_one && b->Z_is_one)
1116 {
1117 if (!BN_copy(&r->Z, n5)) goto end;
1118 }
1119 else
1120 {
1121 if (a->Z_is_one)
1122 { if (!BN_copy(n0, &b->Z)) goto end; }
1123 else if (b->Z_is_one)
1124 { if (!BN_copy(n0, &a->Z)) goto end; }
1125 else
1126 { if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) goto end; }
1127 if (!field_mul(group, &r->Z, n0, n5, ctx)) goto end;
1128 }
1129 r->Z_is_one = 0;
1130 /* Z_r = Z_a * Z_b * n5 */
1131
1132 /* X_r */
1133 if (!field_sqr(group, n0, n6, ctx)) goto end;
1134 if (!field_sqr(group, n4, n5, ctx)) goto end;
1135 if (!field_mul(group, n3, n1, n4, ctx)) goto end;
1136 if (!BN_mod_sub_quick(&r->X, n0, n3, p)) goto end;
1137 /* X_r = n6^2 - n5^2 * 'n7' */
1138
1139 /* 'n9' */
1140 if (!BN_mod_lshift1_quick(n0, &r->X, p)) goto end;
1141 if (!BN_mod_sub_quick(n0, n3, n0, p)) goto end;
1142 /* n9 = n5^2 * 'n7' - 2 * X_r */
1143
1144 /* Y_r */
1145 if (!field_mul(group, n0, n0, n6, ctx)) goto end;
1146 if (!field_mul(group, n5, n4, n5, ctx)) goto end; /* now n5 is n5^3 */
1147 if (!field_mul(group, n1, n2, n5, ctx)) goto end;
1148 if (!BN_mod_sub_quick(n0, n0, n1, p)) goto end;
1149 if (BN_is_odd(n0))
1150 if (!BN_add(n0, n0, p)) goto end;
1151 /* now 0 <= n0 < 2*p, and n0 is even */
1152 if (!BN_rshift1(&r->Y, n0)) goto end;
1153 /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
1154
1155 ret = 1;
1156
1157 end:
1158 if (ctx) /* otherwise we already called BN_CTX_end */
1159 BN_CTX_end(ctx);
1160 if (new_ctx != NULL)
1161 BN_CTX_free(new_ctx);
1162 return ret;
1163 }
1164
1165
ec_GFp_simple_dbl(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,BN_CTX * ctx)1166 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
1167 {
1168 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1169 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1170 const BIGNUM *p;
1171 BN_CTX *new_ctx = NULL;
1172 BIGNUM *n0, *n1, *n2, *n3;
1173 int ret = 0;
1174
1175 if (EC_POINT_is_at_infinity(group, a))
1176 {
1177 BN_zero(&r->Z);
1178 r->Z_is_one = 0;
1179 return 1;
1180 }
1181
1182 field_mul = group->meth->field_mul;
1183 field_sqr = group->meth->field_sqr;
1184 p = &group->field;
1185
1186 if (ctx == NULL)
1187 {
1188 ctx = new_ctx = BN_CTX_new();
1189 if (ctx == NULL)
1190 return 0;
1191 }
1192
1193 BN_CTX_start(ctx);
1194 n0 = BN_CTX_get(ctx);
1195 n1 = BN_CTX_get(ctx);
1196 n2 = BN_CTX_get(ctx);
1197 n3 = BN_CTX_get(ctx);
1198 if (n3 == NULL) goto err;
1199
1200 /* Note that in this function we must not read components of 'a'
1201 * once we have written the corresponding components of 'r'.
1202 * ('r' might the same as 'a'.)
1203 */
1204
1205 /* n1 */
1206 if (a->Z_is_one)
1207 {
1208 if (!field_sqr(group, n0, &a->X, ctx)) goto err;
1209 if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
1210 if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
1211 if (!BN_mod_add_quick(n1, n0, &group->a, p)) goto err;
1212 /* n1 = 3 * X_a^2 + a_curve */
1213 }
1214 else if (group->a_is_minus3)
1215 {
1216 if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
1217 if (!BN_mod_add_quick(n0, &a->X, n1, p)) goto err;
1218 if (!BN_mod_sub_quick(n2, &a->X, n1, p)) goto err;
1219 if (!field_mul(group, n1, n0, n2, ctx)) goto err;
1220 if (!BN_mod_lshift1_quick(n0, n1, p)) goto err;
1221 if (!BN_mod_add_quick(n1, n0, n1, p)) goto err;
1222 /* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
1223 * = 3 * X_a^2 - 3 * Z_a^4 */
1224 }
1225 else
1226 {
1227 if (!field_sqr(group, n0, &a->X, ctx)) goto err;
1228 if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
1229 if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
1230 if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
1231 if (!field_sqr(group, n1, n1, ctx)) goto err;
1232 if (!field_mul(group, n1, n1, &group->a, ctx)) goto err;
1233 if (!BN_mod_add_quick(n1, n1, n0, p)) goto err;
1234 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
1235 }
1236
1237 /* Z_r */
1238 if (a->Z_is_one)
1239 {
1240 if (!BN_copy(n0, &a->Y)) goto err;
1241 }
1242 else
1243 {
1244 if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) goto err;
1245 }
1246 if (!BN_mod_lshift1_quick(&r->Z, n0, p)) goto err;
1247 r->Z_is_one = 0;
1248 /* Z_r = 2 * Y_a * Z_a */
1249
1250 /* n2 */
1251 if (!field_sqr(group, n3, &a->Y, ctx)) goto err;
1252 if (!field_mul(group, n2, &a->X, n3, ctx)) goto err;
1253 if (!BN_mod_lshift_quick(n2, n2, 2, p)) goto err;
1254 /* n2 = 4 * X_a * Y_a^2 */
1255
1256 /* X_r */
1257 if (!BN_mod_lshift1_quick(n0, n2, p)) goto err;
1258 if (!field_sqr(group, &r->X, n1, ctx)) goto err;
1259 if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) goto err;
1260 /* X_r = n1^2 - 2 * n2 */
1261
1262 /* n3 */
1263 if (!field_sqr(group, n0, n3, ctx)) goto err;
1264 if (!BN_mod_lshift_quick(n3, n0, 3, p)) goto err;
1265 /* n3 = 8 * Y_a^4 */
1266
1267 /* Y_r */
1268 if (!BN_mod_sub_quick(n0, n2, &r->X, p)) goto err;
1269 if (!field_mul(group, n0, n1, n0, ctx)) goto err;
1270 if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) goto err;
1271 /* Y_r = n1 * (n2 - X_r) - n3 */
1272
1273 ret = 1;
1274
1275 err:
1276 BN_CTX_end(ctx);
1277 if (new_ctx != NULL)
1278 BN_CTX_free(new_ctx);
1279 return ret;
1280 }
1281
1282
ec_GFp_simple_invert(const EC_GROUP * group,EC_POINT * point,BN_CTX * ctx)1283 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1284 {
1285 if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y))
1286 /* point is its own inverse */
1287 return 1;
1288
1289 return BN_usub(&point->Y, &group->field, &point->Y);
1290 }
1291
1292
ec_GFp_simple_is_at_infinity(const EC_GROUP * group,const EC_POINT * point)1293 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
1294 {
1295 return BN_is_zero(&point->Z);
1296 }
1297
1298
ec_GFp_simple_is_on_curve(const EC_GROUP * group,const EC_POINT * point,BN_CTX * ctx)1299 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
1300 {
1301 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1302 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1303 const BIGNUM *p;
1304 BN_CTX *new_ctx = NULL;
1305 BIGNUM *rh, *tmp, *Z4, *Z6;
1306 int ret = -1;
1307
1308 if (EC_POINT_is_at_infinity(group, point))
1309 return 1;
1310
1311 field_mul = group->meth->field_mul;
1312 field_sqr = group->meth->field_sqr;
1313 p = &group->field;
1314
1315 if (ctx == NULL)
1316 {
1317 ctx = new_ctx = BN_CTX_new();
1318 if (ctx == NULL)
1319 return -1;
1320 }
1321
1322 BN_CTX_start(ctx);
1323 rh = BN_CTX_get(ctx);
1324 tmp = BN_CTX_get(ctx);
1325 Z4 = BN_CTX_get(ctx);
1326 Z6 = BN_CTX_get(ctx);
1327 if (Z6 == NULL) goto err;
1328
1329 /* We have a curve defined by a Weierstrass equation
1330 * y^2 = x^3 + a*x + b.
1331 * The point to consider is given in Jacobian projective coordinates
1332 * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3).
1333 * Substituting this and multiplying by Z^6 transforms the above equation into
1334 * Y^2 = X^3 + a*X*Z^4 + b*Z^6.
1335 * To test this, we add up the right-hand side in 'rh'.
1336 */
1337
1338 /* rh := X^2 */
1339 if (!field_sqr(group, rh, &point->X, ctx)) goto err;
1340
1341 if (!point->Z_is_one)
1342 {
1343 if (!field_sqr(group, tmp, &point->Z, ctx)) goto err;
1344 if (!field_sqr(group, Z4, tmp, ctx)) goto err;
1345 if (!field_mul(group, Z6, Z4, tmp, ctx)) goto err;
1346
1347 /* rh := (rh + a*Z^4)*X */
1348 if (group->a_is_minus3)
1349 {
1350 if (!BN_mod_lshift1_quick(tmp, Z4, p)) goto err;
1351 if (!BN_mod_add_quick(tmp, tmp, Z4, p)) goto err;
1352 if (!BN_mod_sub_quick(rh, rh, tmp, p)) goto err;
1353 if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1354 }
1355 else
1356 {
1357 if (!field_mul(group, tmp, Z4, &group->a, ctx)) goto err;
1358 if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err;
1359 if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1360 }
1361
1362 /* rh := rh + b*Z^6 */
1363 if (!field_mul(group, tmp, &group->b, Z6, ctx)) goto err;
1364 if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err;
1365 }
1366 else
1367 {
1368 /* point->Z_is_one */
1369
1370 /* rh := (rh + a)*X */
1371 if (!BN_mod_add_quick(rh, rh, &group->a, p)) goto err;
1372 if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1373 /* rh := rh + b */
1374 if (!BN_mod_add_quick(rh, rh, &group->b, p)) goto err;
1375 }
1376
1377 /* 'lh' := Y^2 */
1378 if (!field_sqr(group, tmp, &point->Y, ctx)) goto err;
1379
1380 ret = (0 == BN_ucmp(tmp, rh));
1381
1382 err:
1383 BN_CTX_end(ctx);
1384 if (new_ctx != NULL)
1385 BN_CTX_free(new_ctx);
1386 return ret;
1387 }
1388
1389
ec_GFp_simple_cmp(const EC_GROUP * group,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)1390 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
1391 {
1392 /* return values:
1393 * -1 error
1394 * 0 equal (in affine coordinates)
1395 * 1 not equal
1396 */
1397
1398 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1399 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1400 BN_CTX *new_ctx = NULL;
1401 BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
1402 const BIGNUM *tmp1_, *tmp2_;
1403 int ret = -1;
1404
1405 if (EC_POINT_is_at_infinity(group, a))
1406 {
1407 return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
1408 }
1409
1410 if (a->Z_is_one && b->Z_is_one)
1411 {
1412 return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
1413 }
1414
1415 field_mul = group->meth->field_mul;
1416 field_sqr = group->meth->field_sqr;
1417
1418 if (ctx == NULL)
1419 {
1420 ctx = new_ctx = BN_CTX_new();
1421 if (ctx == NULL)
1422 return -1;
1423 }
1424
1425 BN_CTX_start(ctx);
1426 tmp1 = BN_CTX_get(ctx);
1427 tmp2 = BN_CTX_get(ctx);
1428 Za23 = BN_CTX_get(ctx);
1429 Zb23 = BN_CTX_get(ctx);
1430 if (Zb23 == NULL) goto end;
1431
1432 /* We have to decide whether
1433 * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
1434 * or equivalently, whether
1435 * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
1436 */
1437
1438 if (!b->Z_is_one)
1439 {
1440 if (!field_sqr(group, Zb23, &b->Z, ctx)) goto end;
1441 if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) goto end;
1442 tmp1_ = tmp1;
1443 }
1444 else
1445 tmp1_ = &a->X;
1446 if (!a->Z_is_one)
1447 {
1448 if (!field_sqr(group, Za23, &a->Z, ctx)) goto end;
1449 if (!field_mul(group, tmp2, &b->X, Za23, ctx)) goto end;
1450 tmp2_ = tmp2;
1451 }
1452 else
1453 tmp2_ = &b->X;
1454
1455 /* compare X_a*Z_b^2 with X_b*Z_a^2 */
1456 if (BN_cmp(tmp1_, tmp2_) != 0)
1457 {
1458 ret = 1; /* points differ */
1459 goto end;
1460 }
1461
1462
1463 if (!b->Z_is_one)
1464 {
1465 if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) goto end;
1466 if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) goto end;
1467 /* tmp1_ = tmp1 */
1468 }
1469 else
1470 tmp1_ = &a->Y;
1471 if (!a->Z_is_one)
1472 {
1473 if (!field_mul(group, Za23, Za23, &a->Z, ctx)) goto end;
1474 if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) goto end;
1475 /* tmp2_ = tmp2 */
1476 }
1477 else
1478 tmp2_ = &b->Y;
1479
1480 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */
1481 if (BN_cmp(tmp1_, tmp2_) != 0)
1482 {
1483 ret = 1; /* points differ */
1484 goto end;
1485 }
1486
1487 /* points are equal */
1488 ret = 0;
1489
1490 end:
1491 BN_CTX_end(ctx);
1492 if (new_ctx != NULL)
1493 BN_CTX_free(new_ctx);
1494 return ret;
1495 }
1496
1497
ec_GFp_simple_make_affine(const EC_GROUP * group,EC_POINT * point,BN_CTX * ctx)1498 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1499 {
1500 BN_CTX *new_ctx = NULL;
1501 BIGNUM *x, *y;
1502 int ret = 0;
1503
1504 if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
1505 return 1;
1506
1507 if (ctx == NULL)
1508 {
1509 ctx = new_ctx = BN_CTX_new();
1510 if (ctx == NULL)
1511 return 0;
1512 }
1513
1514 BN_CTX_start(ctx);
1515 x = BN_CTX_get(ctx);
1516 y = BN_CTX_get(ctx);
1517 if (y == NULL) goto err;
1518
1519 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
1520 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
1521 if (!point->Z_is_one)
1522 {
1523 ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
1524 goto err;
1525 }
1526
1527 ret = 1;
1528
1529 err:
1530 BN_CTX_end(ctx);
1531 if (new_ctx != NULL)
1532 BN_CTX_free(new_ctx);
1533 return ret;
1534 }
1535
1536
ec_GFp_simple_points_make_affine(const EC_GROUP * group,size_t num,EC_POINT * points[],BN_CTX * ctx)1537 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
1538 {
1539 BN_CTX *new_ctx = NULL;
1540 BIGNUM *tmp0, *tmp1;
1541 size_t pow2 = 0;
1542 BIGNUM **heap = NULL;
1543 size_t i;
1544 int ret = 0;
1545
1546 if (num == 0)
1547 return 1;
1548
1549 if (ctx == NULL)
1550 {
1551 ctx = new_ctx = BN_CTX_new();
1552 if (ctx == NULL)
1553 return 0;
1554 }
1555
1556 BN_CTX_start(ctx);
1557 tmp0 = BN_CTX_get(ctx);
1558 tmp1 = BN_CTX_get(ctx);
1559 if (tmp0 == NULL || tmp1 == NULL) goto err;
1560
1561 /* Before converting the individual points, compute inverses of all Z values.
1562 * Modular inversion is rather slow, but luckily we can do with a single
1563 * explicit inversion, plus about 3 multiplications per input value.
1564 */
1565
1566 pow2 = 1;
1567 while (num > pow2)
1568 pow2 <<= 1;
1569 /* Now pow2 is the smallest power of 2 satifsying pow2 >= num.
1570 * We need twice that. */
1571 pow2 <<= 1;
1572
1573 heap = OPENSSL_malloc(pow2 * sizeof heap[0]);
1574 if (heap == NULL) goto err;
1575
1576 /* The array is used as a binary tree, exactly as in heapsort:
1577 *
1578 * heap[1]
1579 * heap[2] heap[3]
1580 * heap[4] heap[5] heap[6] heap[7]
1581 * heap[8]heap[9] heap[10]heap[11] heap[12]heap[13] heap[14] heap[15]
1582 *
1583 * We put the Z's in the last line;
1584 * then we set each other node to the product of its two child-nodes (where
1585 * empty or 0 entries are treated as ones);
1586 * then we invert heap[1];
1587 * then we invert each other node by replacing it by the product of its
1588 * parent (after inversion) and its sibling (before inversion).
1589 */
1590 heap[0] = NULL;
1591 for (i = pow2/2 - 1; i > 0; i--)
1592 heap[i] = NULL;
1593 for (i = 0; i < num; i++)
1594 heap[pow2/2 + i] = &points[i]->Z;
1595 for (i = pow2/2 + num; i < pow2; i++)
1596 heap[i] = NULL;
1597
1598 /* set each node to the product of its children */
1599 for (i = pow2/2 - 1; i > 0; i--)
1600 {
1601 heap[i] = BN_new();
1602 if (heap[i] == NULL) goto err;
1603
1604 if (heap[2*i] != NULL)
1605 {
1606 if ((heap[2*i + 1] == NULL) || BN_is_zero(heap[2*i + 1]))
1607 {
1608 if (!BN_copy(heap[i], heap[2*i])) goto err;
1609 }
1610 else
1611 {
1612 if (BN_is_zero(heap[2*i]))
1613 {
1614 if (!BN_copy(heap[i], heap[2*i + 1])) goto err;
1615 }
1616 else
1617 {
1618 if (!group->meth->field_mul(group, heap[i],
1619 heap[2*i], heap[2*i + 1], ctx)) goto err;
1620 }
1621 }
1622 }
1623 }
1624
1625 /* invert heap[1] */
1626 if (!BN_is_zero(heap[1]))
1627 {
1628 if (!BN_mod_inverse(heap[1], heap[1], &group->field, ctx))
1629 {
1630 ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
1631 goto err;
1632 }
1633 }
1634 if (group->meth->field_encode != 0)
1635 {
1636 /* in the Montgomery case, we just turned R*H (representing H)
1637 * into 1/(R*H), but we need R*(1/H) (representing 1/H);
1638 * i.e. we have need to multiply by the Montgomery factor twice */
1639 if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
1640 if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
1641 }
1642
1643 /* set other heap[i]'s to their inverses */
1644 for (i = 2; i < pow2/2 + num; i += 2)
1645 {
1646 /* i is even */
1647 if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1]))
1648 {
1649 if (!group->meth->field_mul(group, tmp0, heap[i/2], heap[i + 1], ctx)) goto err;
1650 if (!group->meth->field_mul(group, tmp1, heap[i/2], heap[i], ctx)) goto err;
1651 if (!BN_copy(heap[i], tmp0)) goto err;
1652 if (!BN_copy(heap[i + 1], tmp1)) goto err;
1653 }
1654 else
1655 {
1656 if (!BN_copy(heap[i], heap[i/2])) goto err;
1657 }
1658 }
1659
1660 /* we have replaced all non-zero Z's by their inverses, now fix up all the points */
1661 for (i = 0; i < num; i++)
1662 {
1663 EC_POINT *p = points[i];
1664
1665 if (!BN_is_zero(&p->Z))
1666 {
1667 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */
1668
1669 if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx)) goto err;
1670 if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx)) goto err;
1671
1672 if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx)) goto err;
1673 if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx)) goto err;
1674
1675 if (group->meth->field_set_to_one != 0)
1676 {
1677 if (!group->meth->field_set_to_one(group, &p->Z, ctx)) goto err;
1678 }
1679 else
1680 {
1681 if (!BN_one(&p->Z)) goto err;
1682 }
1683 p->Z_is_one = 1;
1684 }
1685 }
1686
1687 ret = 1;
1688
1689 err:
1690 BN_CTX_end(ctx);
1691 if (new_ctx != NULL)
1692 BN_CTX_free(new_ctx);
1693 if (heap != NULL)
1694 {
1695 /* heap[pow2/2] .. heap[pow2-1] have not been allocated locally! */
1696 for (i = pow2/2 - 1; i > 0; i--)
1697 {
1698 if (heap[i] != NULL)
1699 BN_clear_free(heap[i]);
1700 }
1701 OPENSSL_free(heap);
1702 }
1703 return ret;
1704 }
1705
1706
ec_GFp_simple_field_mul(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)1707 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
1708 {
1709 return BN_mod_mul(r, a, b, &group->field, ctx);
1710 }
1711
1712
ec_GFp_simple_field_sqr(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,BN_CTX * ctx)1713 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
1714 {
1715 return BN_mod_sqr(r, a, &group->field, ctx);
1716 }
1717