1 /* Originally written by Bodo Moeller for the OpenSSL project.
2 * ====================================================================
3 * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
15 * distribution.
16 *
17 * 3. All advertising materials mentioning features or use of this
18 * software must display the following acknowledgment:
19 * "This product includes software developed by the OpenSSL Project
20 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
21 *
22 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
23 * endorse or promote products derived from this software without
24 * prior written permission. For written permission, please contact
25 * openssl-core@openssl.org.
26 *
27 * 5. Products derived from this software may not be called "OpenSSL"
28 * nor may "OpenSSL" appear in their names without prior written
29 * permission of the OpenSSL Project.
30 *
31 * 6. Redistributions of any form whatsoever must retain the following
32 * acknowledgment:
33 * "This product includes software developed by the OpenSSL Project
34 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
35 *
36 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
37 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
38 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
39 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
40 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
42 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
43 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
44 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
45 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
46 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
47 * OF THE POSSIBILITY OF SUCH DAMAGE.
48 * ====================================================================
49 *
50 * This product includes cryptographic software written by Eric Young
51 * (eay@cryptsoft.com). This product includes software written by Tim
52 * Hudson (tjh@cryptsoft.com).
53 *
54 */
55 /* ====================================================================
56 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
57 *
58 * Portions of the attached software ("Contribution") are developed by
59 * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
60 *
61 * The Contribution is licensed pursuant to the OpenSSL open source
62 * license provided above.
63 *
64 * The elliptic curve binary polynomial software is originally written by
65 * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems
66 * Laboratories. */
67
68 #include <openssl/ec.h>
69
70 #include <string.h>
71
72 #include <openssl/bn.h>
73 #include <openssl/err.h>
74 #include <openssl/mem.h>
75
76 #include "internal.h"
77 #include "../../internal.h"
78
79
80 /* Most method functions in this file are designed to work with non-trivial
81 * representations of field elements if necessary (see ecp_mont.c): while
82 * standard modular addition and subtraction are used, the field_mul and
83 * field_sqr methods will be used for multiplication, and field_encode and
84 * field_decode (if defined) will be used for converting between
85 * representations.
86 *
87 * Functions here specifically assume that if a non-trivial representation is
88 * used, it is a Montgomery representation (i.e. 'encoding' means multiplying
89 * by some factor R). */
90
ec_GFp_simple_group_init(EC_GROUP * group)91 int ec_GFp_simple_group_init(EC_GROUP *group) {
92 BN_init(&group->field);
93 BN_init(&group->a);
94 BN_init(&group->b);
95 BN_init(&group->one);
96 group->a_is_minus3 = 0;
97 return 1;
98 }
99
ec_GFp_simple_group_finish(EC_GROUP * group)100 void ec_GFp_simple_group_finish(EC_GROUP *group) {
101 BN_free(&group->field);
102 BN_free(&group->a);
103 BN_free(&group->b);
104 BN_free(&group->one);
105 }
106
ec_GFp_simple_group_copy(EC_GROUP * dest,const EC_GROUP * src)107 int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) {
108 if (!BN_copy(&dest->field, &src->field) ||
109 !BN_copy(&dest->a, &src->a) ||
110 !BN_copy(&dest->b, &src->b) ||
111 !BN_copy(&dest->one, &src->one)) {
112 return 0;
113 }
114
115 dest->a_is_minus3 = src->a_is_minus3;
116 return 1;
117 }
118
ec_GFp_simple_group_set_curve(EC_GROUP * group,const BIGNUM * p,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)119 int ec_GFp_simple_group_set_curve(EC_GROUP *group, const BIGNUM *p,
120 const BIGNUM *a, const BIGNUM *b,
121 BN_CTX *ctx) {
122 int ret = 0;
123 BN_CTX *new_ctx = NULL;
124 BIGNUM *tmp_a;
125
126 /* p must be a prime > 3 */
127 if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) {
128 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_FIELD);
129 return 0;
130 }
131
132 if (ctx == NULL) {
133 ctx = new_ctx = BN_CTX_new();
134 if (ctx == NULL) {
135 return 0;
136 }
137 }
138
139 BN_CTX_start(ctx);
140 tmp_a = BN_CTX_get(ctx);
141 if (tmp_a == NULL) {
142 goto err;
143 }
144
145 /* group->field */
146 if (!BN_copy(&group->field, p)) {
147 goto err;
148 }
149 BN_set_negative(&group->field, 0);
150
151 /* group->a */
152 if (!BN_nnmod(tmp_a, a, p, ctx)) {
153 goto err;
154 }
155 if (group->meth->field_encode) {
156 if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) {
157 goto err;
158 }
159 } else if (!BN_copy(&group->a, tmp_a)) {
160 goto err;
161 }
162
163 /* group->b */
164 if (!BN_nnmod(&group->b, b, p, ctx)) {
165 goto err;
166 }
167 if (group->meth->field_encode &&
168 !group->meth->field_encode(group, &group->b, &group->b, ctx)) {
169 goto err;
170 }
171
172 /* group->a_is_minus3 */
173 if (!BN_add_word(tmp_a, 3)) {
174 goto err;
175 }
176 group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
177
178 if (group->meth->field_encode != NULL) {
179 if (!group->meth->field_encode(group, &group->one, BN_value_one(), ctx)) {
180 goto err;
181 }
182 } else if (!BN_copy(&group->one, BN_value_one())) {
183 goto err;
184 }
185
186 ret = 1;
187
188 err:
189 BN_CTX_end(ctx);
190 BN_CTX_free(new_ctx);
191 return ret;
192 }
193
ec_GFp_simple_group_get_curve(const EC_GROUP * group,BIGNUM * p,BIGNUM * a,BIGNUM * b,BN_CTX * ctx)194 int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
195 BIGNUM *b, BN_CTX *ctx) {
196 int ret = 0;
197 BN_CTX *new_ctx = NULL;
198
199 if (p != NULL && !BN_copy(p, &group->field)) {
200 return 0;
201 }
202
203 if (a != NULL || b != NULL) {
204 if (group->meth->field_decode) {
205 if (ctx == NULL) {
206 ctx = new_ctx = BN_CTX_new();
207 if (ctx == NULL) {
208 return 0;
209 }
210 }
211 if (a != NULL && !group->meth->field_decode(group, a, &group->a, ctx)) {
212 goto err;
213 }
214 if (b != NULL && !group->meth->field_decode(group, b, &group->b, ctx)) {
215 goto err;
216 }
217 } else {
218 if (a != NULL && !BN_copy(a, &group->a)) {
219 goto err;
220 }
221 if (b != NULL && !BN_copy(b, &group->b)) {
222 goto err;
223 }
224 }
225 }
226
227 ret = 1;
228
229 err:
230 BN_CTX_free(new_ctx);
231 return ret;
232 }
233
ec_GFp_simple_group_get_degree(const EC_GROUP * group)234 unsigned ec_GFp_simple_group_get_degree(const EC_GROUP *group) {
235 return BN_num_bits(&group->field);
236 }
237
ec_GFp_simple_point_init(EC_POINT * point)238 int ec_GFp_simple_point_init(EC_POINT *point) {
239 BN_init(&point->X);
240 BN_init(&point->Y);
241 BN_init(&point->Z);
242
243 return 1;
244 }
245
ec_GFp_simple_point_finish(EC_POINT * point)246 void ec_GFp_simple_point_finish(EC_POINT *point) {
247 BN_free(&point->X);
248 BN_free(&point->Y);
249 BN_free(&point->Z);
250 }
251
ec_GFp_simple_point_clear_finish(EC_POINT * point)252 void ec_GFp_simple_point_clear_finish(EC_POINT *point) {
253 BN_clear_free(&point->X);
254 BN_clear_free(&point->Y);
255 BN_clear_free(&point->Z);
256 }
257
ec_GFp_simple_point_copy(EC_POINT * dest,const EC_POINT * src)258 int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src) {
259 if (!BN_copy(&dest->X, &src->X) ||
260 !BN_copy(&dest->Y, &src->Y) ||
261 !BN_copy(&dest->Z, &src->Z)) {
262 return 0;
263 }
264
265 return 1;
266 }
267
ec_GFp_simple_point_set_to_infinity(const EC_GROUP * group,EC_POINT * point)268 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group,
269 EC_POINT *point) {
270 BN_zero(&point->Z);
271 return 1;
272 }
273
set_Jprojective_coordinate_GFp(const EC_GROUP * group,BIGNUM * out,const BIGNUM * in,BN_CTX * ctx)274 static int set_Jprojective_coordinate_GFp(const EC_GROUP *group, BIGNUM *out,
275 const BIGNUM *in, BN_CTX *ctx) {
276 if (in == NULL) {
277 return 1;
278 }
279 if (BN_is_negative(in) ||
280 BN_cmp(in, &group->field) >= 0) {
281 OPENSSL_PUT_ERROR(EC, EC_R_COORDINATES_OUT_OF_RANGE);
282 return 0;
283 }
284 if (group->meth->field_encode) {
285 return group->meth->field_encode(group, out, in, ctx);
286 }
287 return BN_copy(out, in) != NULL;
288 }
289
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)290 int ec_GFp_simple_set_Jprojective_coordinates_GFp(
291 const EC_GROUP *group, EC_POINT *point, const BIGNUM *x, const BIGNUM *y,
292 const BIGNUM *z, BN_CTX *ctx) {
293 BN_CTX *new_ctx = NULL;
294 int ret = 0;
295
296 if (ctx == NULL) {
297 ctx = new_ctx = BN_CTX_new();
298 if (ctx == NULL) {
299 return 0;
300 }
301 }
302
303 if (!set_Jprojective_coordinate_GFp(group, &point->X, x, ctx) ||
304 !set_Jprojective_coordinate_GFp(group, &point->Y, y, ctx) ||
305 !set_Jprojective_coordinate_GFp(group, &point->Z, z, ctx)) {
306 goto err;
307 }
308
309 ret = 1;
310
311 err:
312 BN_CTX_free(new_ctx);
313 return ret;
314 }
315
ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP * group,const EC_POINT * point,BIGNUM * x,BIGNUM * y,BIGNUM * z,BN_CTX * ctx)316 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group,
317 const EC_POINT *point,
318 BIGNUM *x, BIGNUM *y,
319 BIGNUM *z, BN_CTX *ctx) {
320 BN_CTX *new_ctx = NULL;
321 int ret = 0;
322
323 if (group->meth->field_decode != 0) {
324 if (ctx == NULL) {
325 ctx = new_ctx = BN_CTX_new();
326 if (ctx == NULL) {
327 return 0;
328 }
329 }
330
331 if (x != NULL && !group->meth->field_decode(group, x, &point->X, ctx)) {
332 goto err;
333 }
334 if (y != NULL && !group->meth->field_decode(group, y, &point->Y, ctx)) {
335 goto err;
336 }
337 if (z != NULL && !group->meth->field_decode(group, z, &point->Z, ctx)) {
338 goto err;
339 }
340 } else {
341 if (x != NULL && !BN_copy(x, &point->X)) {
342 goto err;
343 }
344 if (y != NULL && !BN_copy(y, &point->Y)) {
345 goto err;
346 }
347 if (z != NULL && !BN_copy(z, &point->Z)) {
348 goto err;
349 }
350 }
351
352 ret = 1;
353
354 err:
355 BN_CTX_free(new_ctx);
356 return ret;
357 }
358
ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x,const BIGNUM * y,BN_CTX * ctx)359 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group,
360 EC_POINT *point, const BIGNUM *x,
361 const BIGNUM *y, BN_CTX *ctx) {
362 if (x == NULL || y == NULL) {
363 /* unlike for projective coordinates, we do not tolerate this */
364 OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER);
365 return 0;
366 }
367
368 return ec_point_set_Jprojective_coordinates_GFp(group, point, x, y,
369 BN_value_one(), ctx);
370 }
371
ec_GFp_simple_add(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)372 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
373 const EC_POINT *b, BN_CTX *ctx) {
374 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *,
375 BN_CTX *);
376 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
377 const BIGNUM *p;
378 BN_CTX *new_ctx = NULL;
379 BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
380 int ret = 0;
381
382 if (a == b) {
383 return EC_POINT_dbl(group, r, a, ctx);
384 }
385 if (EC_POINT_is_at_infinity(group, a)) {
386 return EC_POINT_copy(r, b);
387 }
388 if (EC_POINT_is_at_infinity(group, b)) {
389 return EC_POINT_copy(r, a);
390 }
391
392 field_mul = group->meth->field_mul;
393 field_sqr = group->meth->field_sqr;
394 p = &group->field;
395
396 if (ctx == NULL) {
397 ctx = new_ctx = BN_CTX_new();
398 if (ctx == NULL) {
399 return 0;
400 }
401 }
402
403 BN_CTX_start(ctx);
404 n0 = BN_CTX_get(ctx);
405 n1 = BN_CTX_get(ctx);
406 n2 = BN_CTX_get(ctx);
407 n3 = BN_CTX_get(ctx);
408 n4 = BN_CTX_get(ctx);
409 n5 = BN_CTX_get(ctx);
410 n6 = BN_CTX_get(ctx);
411 if (n6 == NULL) {
412 goto end;
413 }
414
415 /* Note that in this function we must not read components of 'a' or 'b'
416 * once we have written the corresponding components of 'r'.
417 * ('r' might be one of 'a' or 'b'.)
418 */
419
420 /* n1, n2 */
421 int b_Z_is_one = BN_cmp(&b->Z, &group->one) == 0;
422
423 if (b_Z_is_one) {
424 if (!BN_copy(n1, &a->X) || !BN_copy(n2, &a->Y)) {
425 goto end;
426 }
427 /* n1 = X_a */
428 /* n2 = Y_a */
429 } else {
430 if (!field_sqr(group, n0, &b->Z, ctx) ||
431 !field_mul(group, n1, &a->X, n0, ctx)) {
432 goto end;
433 }
434 /* n1 = X_a * Z_b^2 */
435
436 if (!field_mul(group, n0, n0, &b->Z, ctx) ||
437 !field_mul(group, n2, &a->Y, n0, ctx)) {
438 goto end;
439 }
440 /* n2 = Y_a * Z_b^3 */
441 }
442
443 /* n3, n4 */
444 int a_Z_is_one = BN_cmp(&a->Z, &group->one) == 0;
445 if (a_Z_is_one) {
446 if (!BN_copy(n3, &b->X) || !BN_copy(n4, &b->Y)) {
447 goto end;
448 }
449 /* n3 = X_b */
450 /* n4 = Y_b */
451 } else {
452 if (!field_sqr(group, n0, &a->Z, ctx) ||
453 !field_mul(group, n3, &b->X, n0, ctx)) {
454 goto end;
455 }
456 /* n3 = X_b * Z_a^2 */
457
458 if (!field_mul(group, n0, n0, &a->Z, ctx) ||
459 !field_mul(group, n4, &b->Y, n0, ctx)) {
460 goto end;
461 }
462 /* n4 = Y_b * Z_a^3 */
463 }
464
465 /* n5, n6 */
466 if (!BN_mod_sub_quick(n5, n1, n3, p) ||
467 !BN_mod_sub_quick(n6, n2, n4, p)) {
468 goto end;
469 }
470 /* n5 = n1 - n3 */
471 /* n6 = n2 - n4 */
472
473 if (BN_is_zero(n5)) {
474 if (BN_is_zero(n6)) {
475 /* a is the same point as b */
476 BN_CTX_end(ctx);
477 ret = EC_POINT_dbl(group, r, a, ctx);
478 ctx = NULL;
479 goto end;
480 } else {
481 /* a is the inverse of b */
482 BN_zero(&r->Z);
483 ret = 1;
484 goto end;
485 }
486 }
487
488 /* 'n7', 'n8' */
489 if (!BN_mod_add_quick(n1, n1, n3, p) ||
490 !BN_mod_add_quick(n2, n2, n4, p)) {
491 goto end;
492 }
493 /* 'n7' = n1 + n3 */
494 /* 'n8' = n2 + n4 */
495
496 /* Z_r */
497 if (a_Z_is_one && b_Z_is_one) {
498 if (!BN_copy(&r->Z, n5)) {
499 goto end;
500 }
501 } else {
502 if (a_Z_is_one) {
503 if (!BN_copy(n0, &b->Z)) {
504 goto end;
505 }
506 } else if (b_Z_is_one) {
507 if (!BN_copy(n0, &a->Z)) {
508 goto end;
509 }
510 } else if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) {
511 goto end;
512 }
513 if (!field_mul(group, &r->Z, n0, n5, ctx)) {
514 goto end;
515 }
516 }
517
518 /* Z_r = Z_a * Z_b * n5 */
519
520 /* X_r */
521 if (!field_sqr(group, n0, n6, ctx) ||
522 !field_sqr(group, n4, n5, ctx) ||
523 !field_mul(group, n3, n1, n4, ctx) ||
524 !BN_mod_sub_quick(&r->X, n0, n3, p)) {
525 goto end;
526 }
527 /* X_r = n6^2 - n5^2 * 'n7' */
528
529 /* 'n9' */
530 if (!BN_mod_lshift1_quick(n0, &r->X, p) ||
531 !BN_mod_sub_quick(n0, n3, n0, p)) {
532 goto end;
533 }
534 /* n9 = n5^2 * 'n7' - 2 * X_r */
535
536 /* Y_r */
537 if (!field_mul(group, n0, n0, n6, ctx) ||
538 !field_mul(group, n5, n4, n5, ctx)) {
539 goto end; /* now n5 is n5^3 */
540 }
541 if (!field_mul(group, n1, n2, n5, ctx) ||
542 !BN_mod_sub_quick(n0, n0, n1, p)) {
543 goto end;
544 }
545 if (BN_is_odd(n0) && !BN_add(n0, n0, p)) {
546 goto end;
547 }
548 /* now 0 <= n0 < 2*p, and n0 is even */
549 if (!BN_rshift1(&r->Y, n0)) {
550 goto end;
551 }
552 /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
553
554 ret = 1;
555
556 end:
557 if (ctx) {
558 /* otherwise we already called BN_CTX_end */
559 BN_CTX_end(ctx);
560 }
561 BN_CTX_free(new_ctx);
562 return ret;
563 }
564
ec_GFp_simple_dbl(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,BN_CTX * ctx)565 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
566 BN_CTX *ctx) {
567 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *,
568 BN_CTX *);
569 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
570 const BIGNUM *p;
571 BN_CTX *new_ctx = NULL;
572 BIGNUM *n0, *n1, *n2, *n3;
573 int ret = 0;
574
575 if (EC_POINT_is_at_infinity(group, a)) {
576 BN_zero(&r->Z);
577 return 1;
578 }
579
580 field_mul = group->meth->field_mul;
581 field_sqr = group->meth->field_sqr;
582 p = &group->field;
583
584 if (ctx == NULL) {
585 ctx = new_ctx = BN_CTX_new();
586 if (ctx == NULL) {
587 return 0;
588 }
589 }
590
591 BN_CTX_start(ctx);
592 n0 = BN_CTX_get(ctx);
593 n1 = BN_CTX_get(ctx);
594 n2 = BN_CTX_get(ctx);
595 n3 = BN_CTX_get(ctx);
596 if (n3 == NULL) {
597 goto err;
598 }
599
600 /* Note that in this function we must not read components of 'a'
601 * once we have written the corresponding components of 'r'.
602 * ('r' might the same as 'a'.)
603 */
604
605 /* n1 */
606 if (BN_cmp(&a->Z, &group->one) == 0) {
607 if (!field_sqr(group, n0, &a->X, ctx) ||
608 !BN_mod_lshift1_quick(n1, n0, p) ||
609 !BN_mod_add_quick(n0, n0, n1, p) ||
610 !BN_mod_add_quick(n1, n0, &group->a, p)) {
611 goto err;
612 }
613 /* n1 = 3 * X_a^2 + a_curve */
614 } else if (group->a_is_minus3) {
615 if (!field_sqr(group, n1, &a->Z, ctx) ||
616 !BN_mod_add_quick(n0, &a->X, n1, p) ||
617 !BN_mod_sub_quick(n2, &a->X, n1, p) ||
618 !field_mul(group, n1, n0, n2, ctx) ||
619 !BN_mod_lshift1_quick(n0, n1, p) ||
620 !BN_mod_add_quick(n1, n0, n1, p)) {
621 goto err;
622 }
623 /* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
624 * = 3 * X_a^2 - 3 * Z_a^4 */
625 } else {
626 if (!field_sqr(group, n0, &a->X, ctx) ||
627 !BN_mod_lshift1_quick(n1, n0, p) ||
628 !BN_mod_add_quick(n0, n0, n1, p) ||
629 !field_sqr(group, n1, &a->Z, ctx) ||
630 !field_sqr(group, n1, n1, ctx) ||
631 !field_mul(group, n1, n1, &group->a, ctx) ||
632 !BN_mod_add_quick(n1, n1, n0, p)) {
633 goto err;
634 }
635 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
636 }
637
638 /* Z_r */
639 if (BN_cmp(&a->Z, &group->one) == 0) {
640 if (!BN_copy(n0, &a->Y)) {
641 goto err;
642 }
643 } else if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) {
644 goto err;
645 }
646 if (!BN_mod_lshift1_quick(&r->Z, n0, p)) {
647 goto err;
648 }
649 /* Z_r = 2 * Y_a * Z_a */
650
651 /* n2 */
652 if (!field_sqr(group, n3, &a->Y, ctx) ||
653 !field_mul(group, n2, &a->X, n3, ctx) ||
654 !BN_mod_lshift_quick(n2, n2, 2, p)) {
655 goto err;
656 }
657 /* n2 = 4 * X_a * Y_a^2 */
658
659 /* X_r */
660 if (!BN_mod_lshift1_quick(n0, n2, p) ||
661 !field_sqr(group, &r->X, n1, ctx) ||
662 !BN_mod_sub_quick(&r->X, &r->X, n0, p)) {
663 goto err;
664 }
665 /* X_r = n1^2 - 2 * n2 */
666
667 /* n3 */
668 if (!field_sqr(group, n0, n3, ctx) ||
669 !BN_mod_lshift_quick(n3, n0, 3, p)) {
670 goto err;
671 }
672 /* n3 = 8 * Y_a^4 */
673
674 /* Y_r */
675 if (!BN_mod_sub_quick(n0, n2, &r->X, p) ||
676 !field_mul(group, n0, n1, n0, ctx) ||
677 !BN_mod_sub_quick(&r->Y, n0, n3, p)) {
678 goto err;
679 }
680 /* Y_r = n1 * (n2 - X_r) - n3 */
681
682 ret = 1;
683
684 err:
685 BN_CTX_end(ctx);
686 BN_CTX_free(new_ctx);
687 return ret;
688 }
689
ec_GFp_simple_invert(const EC_GROUP * group,EC_POINT * point,BN_CTX * ctx)690 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) {
691 if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y)) {
692 /* point is its own inverse */
693 return 1;
694 }
695
696 return BN_usub(&point->Y, &group->field, &point->Y);
697 }
698
ec_GFp_simple_is_at_infinity(const EC_GROUP * group,const EC_POINT * point)699 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) {
700 return BN_is_zero(&point->Z);
701 }
702
ec_GFp_simple_is_on_curve(const EC_GROUP * group,const EC_POINT * point,BN_CTX * ctx)703 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
704 BN_CTX *ctx) {
705 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *,
706 BN_CTX *);
707 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
708 const BIGNUM *p;
709 BN_CTX *new_ctx = NULL;
710 BIGNUM *rh, *tmp, *Z4, *Z6;
711 int ret = 0;
712
713 if (EC_POINT_is_at_infinity(group, point)) {
714 return 1;
715 }
716
717 field_mul = group->meth->field_mul;
718 field_sqr = group->meth->field_sqr;
719 p = &group->field;
720
721 if (ctx == NULL) {
722 ctx = new_ctx = BN_CTX_new();
723 if (ctx == NULL) {
724 return 0;
725 }
726 }
727
728 BN_CTX_start(ctx);
729 rh = BN_CTX_get(ctx);
730 tmp = BN_CTX_get(ctx);
731 Z4 = BN_CTX_get(ctx);
732 Z6 = BN_CTX_get(ctx);
733 if (Z6 == NULL) {
734 goto err;
735 }
736
737 /* We have a curve defined by a Weierstrass equation
738 * y^2 = x^3 + a*x + b.
739 * The point to consider is given in Jacobian projective coordinates
740 * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3).
741 * Substituting this and multiplying by Z^6 transforms the above equation
742 * into
743 * Y^2 = X^3 + a*X*Z^4 + b*Z^6.
744 * To test this, we add up the right-hand side in 'rh'.
745 */
746
747 /* rh := X^2 */
748 if (!field_sqr(group, rh, &point->X, ctx)) {
749 goto err;
750 }
751
752 if (BN_cmp(&point->Z, &group->one) != 0) {
753 if (!field_sqr(group, tmp, &point->Z, ctx) ||
754 !field_sqr(group, Z4, tmp, ctx) ||
755 !field_mul(group, Z6, Z4, tmp, ctx)) {
756 goto err;
757 }
758
759 /* rh := (rh + a*Z^4)*X */
760 if (group->a_is_minus3) {
761 if (!BN_mod_lshift1_quick(tmp, Z4, p) ||
762 !BN_mod_add_quick(tmp, tmp, Z4, p) ||
763 !BN_mod_sub_quick(rh, rh, tmp, p) ||
764 !field_mul(group, rh, rh, &point->X, ctx)) {
765 goto err;
766 }
767 } else {
768 if (!field_mul(group, tmp, Z4, &group->a, ctx) ||
769 !BN_mod_add_quick(rh, rh, tmp, p) ||
770 !field_mul(group, rh, rh, &point->X, ctx)) {
771 goto err;
772 }
773 }
774
775 /* rh := rh + b*Z^6 */
776 if (!field_mul(group, tmp, &group->b, Z6, ctx) ||
777 !BN_mod_add_quick(rh, rh, tmp, p)) {
778 goto err;
779 }
780 } else {
781 /* rh := (rh + a)*X */
782 if (!BN_mod_add_quick(rh, rh, &group->a, p) ||
783 !field_mul(group, rh, rh, &point->X, ctx)) {
784 goto err;
785 }
786 /* rh := rh + b */
787 if (!BN_mod_add_quick(rh, rh, &group->b, p)) {
788 goto err;
789 }
790 }
791
792 /* 'lh' := Y^2 */
793 if (!field_sqr(group, tmp, &point->Y, ctx)) {
794 goto err;
795 }
796
797 ret = (0 == BN_ucmp(tmp, rh));
798
799 err:
800 BN_CTX_end(ctx);
801 BN_CTX_free(new_ctx);
802 return ret;
803 }
804
ec_GFp_simple_cmp(const EC_GROUP * group,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)805 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
806 const EC_POINT *b, BN_CTX *ctx) {
807 /* return values:
808 * -1 error
809 * 0 equal (in affine coordinates)
810 * 1 not equal
811 */
812
813 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *,
814 BN_CTX *);
815 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
816 BN_CTX *new_ctx = NULL;
817 BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
818 const BIGNUM *tmp1_, *tmp2_;
819 int ret = -1;
820
821 if (EC_POINT_is_at_infinity(group, a)) {
822 return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
823 }
824
825 if (EC_POINT_is_at_infinity(group, b)) {
826 return 1;
827 }
828
829 int a_Z_is_one = BN_cmp(&a->Z, &group->one) == 0;
830 int b_Z_is_one = BN_cmp(&b->Z, &group->one) == 0;
831
832 if (a_Z_is_one && b_Z_is_one) {
833 return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
834 }
835
836 field_mul = group->meth->field_mul;
837 field_sqr = group->meth->field_sqr;
838
839 if (ctx == NULL) {
840 ctx = new_ctx = BN_CTX_new();
841 if (ctx == NULL) {
842 return -1;
843 }
844 }
845
846 BN_CTX_start(ctx);
847 tmp1 = BN_CTX_get(ctx);
848 tmp2 = BN_CTX_get(ctx);
849 Za23 = BN_CTX_get(ctx);
850 Zb23 = BN_CTX_get(ctx);
851 if (Zb23 == NULL) {
852 goto end;
853 }
854
855 /* We have to decide whether
856 * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
857 * or equivalently, whether
858 * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
859 */
860
861 if (!b_Z_is_one) {
862 if (!field_sqr(group, Zb23, &b->Z, ctx) ||
863 !field_mul(group, tmp1, &a->X, Zb23, ctx)) {
864 goto end;
865 }
866 tmp1_ = tmp1;
867 } else {
868 tmp1_ = &a->X;
869 }
870 if (!a_Z_is_one) {
871 if (!field_sqr(group, Za23, &a->Z, ctx) ||
872 !field_mul(group, tmp2, &b->X, Za23, ctx)) {
873 goto end;
874 }
875 tmp2_ = tmp2;
876 } else {
877 tmp2_ = &b->X;
878 }
879
880 /* compare X_a*Z_b^2 with X_b*Z_a^2 */
881 if (BN_cmp(tmp1_, tmp2_) != 0) {
882 ret = 1; /* points differ */
883 goto end;
884 }
885
886
887 if (!b_Z_is_one) {
888 if (!field_mul(group, Zb23, Zb23, &b->Z, ctx) ||
889 !field_mul(group, tmp1, &a->Y, Zb23, ctx)) {
890 goto end;
891 }
892 /* tmp1_ = tmp1 */
893 } else {
894 tmp1_ = &a->Y;
895 }
896 if (!a_Z_is_one) {
897 if (!field_mul(group, Za23, Za23, &a->Z, ctx) ||
898 !field_mul(group, tmp2, &b->Y, Za23, ctx)) {
899 goto end;
900 }
901 /* tmp2_ = tmp2 */
902 } else {
903 tmp2_ = &b->Y;
904 }
905
906 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */
907 if (BN_cmp(tmp1_, tmp2_) != 0) {
908 ret = 1; /* points differ */
909 goto end;
910 }
911
912 /* points are equal */
913 ret = 0;
914
915 end:
916 BN_CTX_end(ctx);
917 BN_CTX_free(new_ctx);
918 return ret;
919 }
920
ec_GFp_simple_make_affine(const EC_GROUP * group,EC_POINT * point,BN_CTX * ctx)921 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
922 BN_CTX *ctx) {
923 BN_CTX *new_ctx = NULL;
924 BIGNUM *x, *y;
925 int ret = 0;
926
927 if (BN_cmp(&point->Z, &group->one) == 0 ||
928 EC_POINT_is_at_infinity(group, point)) {
929 return 1;
930 }
931
932 if (ctx == NULL) {
933 ctx = new_ctx = BN_CTX_new();
934 if (ctx == NULL) {
935 return 0;
936 }
937 }
938
939 BN_CTX_start(ctx);
940 x = BN_CTX_get(ctx);
941 y = BN_CTX_get(ctx);
942 if (y == NULL) {
943 goto err;
944 }
945
946 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx) ||
947 !EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) {
948 goto err;
949 }
950 if (BN_cmp(&point->Z, &group->one) != 0) {
951 OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
952 goto err;
953 }
954
955 ret = 1;
956
957 err:
958 BN_CTX_end(ctx);
959 BN_CTX_free(new_ctx);
960 return ret;
961 }
962
ec_GFp_simple_points_make_affine(const EC_GROUP * group,size_t num,EC_POINT * points[],BN_CTX * ctx)963 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num,
964 EC_POINT *points[], BN_CTX *ctx) {
965 BN_CTX *new_ctx = NULL;
966 BIGNUM *tmp, *tmp_Z;
967 BIGNUM **prod_Z = NULL;
968 int ret = 0;
969
970 if (num == 0) {
971 return 1;
972 }
973
974 if (ctx == NULL) {
975 ctx = new_ctx = BN_CTX_new();
976 if (ctx == NULL) {
977 return 0;
978 }
979 }
980
981 BN_CTX_start(ctx);
982 tmp = BN_CTX_get(ctx);
983 tmp_Z = BN_CTX_get(ctx);
984 if (tmp == NULL || tmp_Z == NULL) {
985 goto err;
986 }
987
988 prod_Z = OPENSSL_malloc(num * sizeof(prod_Z[0]));
989 if (prod_Z == NULL) {
990 goto err;
991 }
992 OPENSSL_memset(prod_Z, 0, num * sizeof(prod_Z[0]));
993 for (size_t i = 0; i < num; i++) {
994 prod_Z[i] = BN_new();
995 if (prod_Z[i] == NULL) {
996 goto err;
997 }
998 }
999
1000 /* Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z,
1001 * skipping any zero-valued inputs (pretend that they're 1). */
1002
1003 if (!BN_is_zero(&points[0]->Z)) {
1004 if (!BN_copy(prod_Z[0], &points[0]->Z)) {
1005 goto err;
1006 }
1007 } else {
1008 if (BN_copy(prod_Z[0], &group->one) == NULL) {
1009 goto err;
1010 }
1011 }
1012
1013 for (size_t i = 1; i < num; i++) {
1014 if (!BN_is_zero(&points[i]->Z)) {
1015 if (!group->meth->field_mul(group, prod_Z[i], prod_Z[i - 1],
1016 &points[i]->Z, ctx)) {
1017 goto err;
1018 }
1019 } else {
1020 if (!BN_copy(prod_Z[i], prod_Z[i - 1])) {
1021 goto err;
1022 }
1023 }
1024 }
1025
1026 /* Now use a single explicit inversion to replace every non-zero points[i]->Z
1027 * by its inverse. We use |BN_mod_inverse_odd| instead of doing a constant-
1028 * time inversion using Fermat's Little Theorem because this function is
1029 * usually only used for converting multiples of a public key point to
1030 * affine, and a public key point isn't secret. If we were to use Fermat's
1031 * Little Theorem then the cost of the inversion would usually be so high
1032 * that converting the multiples to affine would be counterproductive. */
1033 int no_inverse;
1034 if (!BN_mod_inverse_odd(tmp, &no_inverse, prod_Z[num - 1], &group->field,
1035 ctx)) {
1036 OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB);
1037 goto err;
1038 }
1039
1040 if (group->meth->field_encode != NULL) {
1041 /* In the Montgomery case, we just turned R*H (representing H)
1042 * into 1/(R*H), but we need R*(1/H) (representing 1/H);
1043 * i.e. we need to multiply by the Montgomery factor twice. */
1044 if (!group->meth->field_encode(group, tmp, tmp, ctx) ||
1045 !group->meth->field_encode(group, tmp, tmp, ctx)) {
1046 goto err;
1047 }
1048 }
1049
1050 for (size_t i = num - 1; i > 0; --i) {
1051 /* Loop invariant: tmp is the product of the inverses of
1052 * points[0]->Z .. points[i]->Z (zero-valued inputs skipped). */
1053 if (BN_is_zero(&points[i]->Z)) {
1054 continue;
1055 }
1056
1057 /* Set tmp_Z to the inverse of points[i]->Z (as product
1058 * of Z inverses 0 .. i, Z values 0 .. i - 1). */
1059 if (!group->meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx) ||
1060 /* Update tmp to satisfy the loop invariant for i - 1. */
1061 !group->meth->field_mul(group, tmp, tmp, &points[i]->Z, ctx) ||
1062 /* Replace points[i]->Z by its inverse. */
1063 !BN_copy(&points[i]->Z, tmp_Z)) {
1064 goto err;
1065 }
1066 }
1067
1068 /* Replace points[0]->Z by its inverse. */
1069 if (!BN_is_zero(&points[0]->Z) && !BN_copy(&points[0]->Z, tmp)) {
1070 goto err;
1071 }
1072
1073 /* Finally, fix up the X and Y coordinates for all points. */
1074 for (size_t i = 0; i < num; i++) {
1075 EC_POINT *p = points[i];
1076
1077 if (!BN_is_zero(&p->Z)) {
1078 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1). */
1079 if (!group->meth->field_sqr(group, tmp, &p->Z, ctx) ||
1080 !group->meth->field_mul(group, &p->X, &p->X, tmp, ctx) ||
1081 !group->meth->field_mul(group, tmp, tmp, &p->Z, ctx) ||
1082 !group->meth->field_mul(group, &p->Y, &p->Y, tmp, ctx)) {
1083 goto err;
1084 }
1085
1086 if (BN_copy(&p->Z, &group->one) == NULL) {
1087 goto err;
1088 }
1089 }
1090 }
1091
1092 ret = 1;
1093
1094 err:
1095 BN_CTX_end(ctx);
1096 BN_CTX_free(new_ctx);
1097 if (prod_Z != NULL) {
1098 for (size_t i = 0; i < num; i++) {
1099 if (prod_Z[i] == NULL) {
1100 break;
1101 }
1102 BN_clear_free(prod_Z[i]);
1103 }
1104 OPENSSL_free(prod_Z);
1105 }
1106
1107 return ret;
1108 }
1109
ec_GFp_simple_field_mul(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)1110 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1111 const BIGNUM *b, BN_CTX *ctx) {
1112 return BN_mod_mul(r, a, b, &group->field, ctx);
1113 }
1114
ec_GFp_simple_field_sqr(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,BN_CTX * ctx)1115 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1116 BN_CTX *ctx) {
1117 return BN_mod_sqr(r, a, &group->field, ctx);
1118 }
1119