Debian Codegraph @

external/boringssl/crypto/ec/simple.c

raw
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 * [email protected].
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 * ([email protected]). This product includes software written by Tim
52 * Hudson ([email protected]).
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
78
79 /* Most method functions in this file are designed to work with non-trivial
80 * representations of field elements if necessary (see ecp_mont.c): while
81 * standard modular addition and subtraction are used, the field_mul and
82 * field_sqr methods will be used for multiplication, and field_encode and
83 * field_decode (if defined) will be used for converting between
84 * representations.
85 *
86 * Functions here specifically assume that if a non-trivial representation is
87 * used, it is a Montgomery representation (i.e. 'encoding' means multiplying
88 * by some factor R). */
89
90 int ec_GFp_simple_group_init(EC_GROUP *group) {
91 BN_init(&group->field);
92 BN_init(&group->a);
93 BN_init(&group->b);
94 BN_init(&group->one);
95 group->a_is_minus3 = 0;
96 return 1;
97 }
98
99 void ec_GFp_simple_group_finish(EC_GROUP *group) {
100 BN_free(&group->field);
101 BN_free(&group->a);
102 BN_free(&group->b);
103 BN_free(&group->one);
104 }
105
106 int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) {
107 if (!BN_copy(&dest->field, &src->field) ||
108 !BN_copy(&dest->a, &src->a) ||
109 !BN_copy(&dest->b, &src->b) ||
110 !BN_copy(&dest->one, &src->one)) {
111 return 0;
112 }
113
114 dest->a_is_minus3 = src->a_is_minus3;
115 return 1;
116 }
117
118 int ec_GFp_simple_group_set_curve(EC_GROUP *group, const BIGNUM *p,
119 const BIGNUM *a, const BIGNUM *b,
120 BN_CTX *ctx) {
121 int ret = 0;
122 BN_CTX *new_ctx = NULL;
123 BIGNUM *tmp_a;
124
125 /* p must be a prime > 3 */
126 if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) {
127 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_FIELD);
128 return 0;
129 }
130
131 if (ctx == NULL) {
132 ctx = new_ctx = BN_CTX_new();
133 if (ctx == NULL) {
134 return 0;
135 }
136 }
137
138 BN_CTX_start(ctx);
139 tmp_a = BN_CTX_get(ctx);
140 if (tmp_a == NULL) {
141 goto err;
142 }
143
144 /* group->field */
145 if (!BN_copy(&group->field, p)) {
146 goto err;
147 }
148 BN_set_negative(&group->field, 0);
149
150 /* group->a */
151 if (!BN_nnmod(tmp_a, a, p, ctx)) {
152 goto err;
153 }
154 if (group->meth->field_encode) {
155 if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) {
156 goto err;
157 }
158 } else if (!BN_copy(&group->a, tmp_a)) {
159 goto err;
160 }
161
162 /* group->b */
163 if (!BN_nnmod(&group->b, b, p, ctx)) {
164 goto err;
165 }
166 if (group->meth->field_encode &&
167 !group->meth->field_encode(group, &group->b, &group->b, ctx)) {
168 goto err;
169 }
170
171 /* group->a_is_minus3 */
172 if (!BN_add_word(tmp_a, 3)) {
173 goto err;
174 }
175 group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
176
177 if (group->meth->field_encode != NULL) {
178 if (!group->meth->field_encode(group, &group->one, BN_value_one(), ctx)) {
179 goto err;
180 }
181 } else if (!BN_copy(&group->one, BN_value_one())) {
182 goto err;
183 }
184
185 ret = 1;
186
187 err:
188 BN_CTX_end(ctx);
189 BN_CTX_free(new_ctx);
190 return ret;
191 }
192
193 int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
194 BIGNUM *b, BN_CTX *ctx) {
195 int ret = 0;
196 BN_CTX *new_ctx = NULL;
197
198 if (p != NULL && !BN_copy(p, &group->field)) {
199 return 0;
200 }
201
202 if (a != NULL || b != NULL) {
203 if (group->meth->field_decode) {
204 if (ctx == NULL) {
205 ctx = new_ctx = BN_CTX_new();
206 if (ctx == NULL) {
207 return 0;
208 }
209 }
210 if (a != NULL && !group->meth->field_decode(group, a, &group->a, ctx)) {
211 goto err;
212 }
213 if (b != NULL && !group->meth->field_decode(group, b, &group->b, ctx)) {
214 goto err;
215 }
216 } else {
217 if (a != NULL && !BN_copy(a, &group->a)) {
218 goto err;
219 }
220 if (b != NULL && !BN_copy(b, &group->b)) {
221 goto err;
222 }
223 }
224 }
225
226 ret = 1;
227
228 err:
229 BN_CTX_free(new_ctx);
230 return ret;
231 }
232
233 unsigned ec_GFp_simple_group_get_degree(const EC_GROUP *group) {
234 return BN_num_bits(&group->field);
235 }
236
237 int ec_GFp_simple_point_init(EC_POINT *point) {
238 BN_init(&point->X);
239 BN_init(&point->Y);
240 BN_init(&point->Z);
241
242 return 1;
243 }
244
245 void ec_GFp_simple_point_finish(EC_POINT *point) {
246 BN_free(&point->X);
247 BN_free(&point->Y);
248 BN_free(&point->Z);
249 }
250
251 void ec_GFp_simple_point_clear_finish(EC_POINT *point) {
252 BN_clear_free(&point->X);
253 BN_clear_free(&point->Y);
254 BN_clear_free(&point->Z);
255 }
256
257 int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src) {
258 if (!BN_copy(&dest->X, &src->X) ||
259 !BN_copy(&dest->Y, &src->Y) ||
260 !BN_copy(&dest->Z, &src->Z)) {
261 return 0;
262 }
263
264 return 1;
265 }
266
267 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group,
268 EC_POINT *point) {
269 BN_zero(&point->Z);
270 return 1;
271 }
272
273 static int set_Jprojective_coordinate_GFp(const EC_GROUP *group, BIGNUM *out,
274 const BIGNUM *in, BN_CTX *ctx) {
275 if (in == NULL) {
276 return 1;
277 }
278 if (BN_is_negative(in) ||
279 BN_cmp(in, &group->field) >= 0) {
280 OPENSSL_PUT_ERROR(EC, EC_R_COORDINATES_OUT_OF_RANGE);
281 return 0;
282 }
283 if (group->meth->field_encode) {
284 return group->meth->field_encode(group, out, in, ctx);
285 }
286 return BN_copy(out, in) != NULL;
287 }
288
289 int ec_GFp_simple_set_Jprojective_coordinates_GFp(
290 const EC_GROUP *group, EC_POINT *point, const BIGNUM *x, const BIGNUM *y,
291 const BIGNUM *z, BN_CTX *ctx) {
292 BN_CTX *new_ctx = NULL;
293 int ret = 0;
294
295 if (ctx == NULL) {
296 ctx = new_ctx = BN_CTX_new();
297 if (ctx == NULL) {
298 return 0;
299 }
300 }
301
302 if (!set_Jprojective_coordinate_GFp(group, &point->X, x, ctx) ||
303 !set_Jprojective_coordinate_GFp(group, &point->Y, y, ctx) ||
304 !set_Jprojective_coordinate_GFp(group, &point->Z, z, ctx)) {
305 goto err;
306 }
307
308 ret = 1;
309
310 err:
311 BN_CTX_free(new_ctx);
312 return ret;
313 }
314
315 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group,
316 const EC_POINT *point,
317 BIGNUM *x, BIGNUM *y,
318 BIGNUM *z, BN_CTX *ctx) {
319 BN_CTX *new_ctx = NULL;
320 int ret = 0;
321
322 if (group->meth->field_decode != 0) {
323 if (ctx == NULL) {
324 ctx = new_ctx = BN_CTX_new();
325 if (ctx == NULL) {
326 return 0;
327 }
328 }
329
330 if (x != NULL && !group->meth->field_decode(group, x, &point->X, ctx)) {
331 goto err;
332 }
333 if (y != NULL && !group->meth->field_decode(group, y, &point->Y, ctx)) {
334 goto err;
335 }
336 if (z != NULL && !group->meth->field_decode(group, z, &point->Z, ctx)) {
337 goto err;
338 }
339 } else {
340 if (x != NULL && !BN_copy(x, &point->X)) {
341 goto err;
342 }
343 if (y != NULL && !BN_copy(y, &point->Y)) {
344 goto err;
345 }
346 if (z != NULL && !BN_copy(z, &point->Z)) {
347 goto err;
348 }
349 }
350
351 ret = 1;
352
353 err:
354 BN_CTX_free(new_ctx);
355 return ret;
356 }
357
358 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group,
359 EC_POINT *point, const BIGNUM *x,
360 const BIGNUM *y, BN_CTX *ctx) {
361 if (x == NULL || y == NULL) {
362 /* unlike for projective coordinates, we do not tolerate this */
363 OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER);
364 return 0;
365 }
366
367 return ec_point_set_Jprojective_coordinates_GFp(group, point, x, y,
368 BN_value_one(), ctx);
369 }
370
371 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
372 const EC_POINT *b, BN_CTX *ctx) {
373 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *,
374 BN_CTX *);
375 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
376 const BIGNUM *p;
377 BN_CTX *new_ctx = NULL;
378 BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
379 int ret = 0;
380
381 if (a == b) {
382 return EC_POINT_dbl(group, r, a, ctx);
383 }
384 if (EC_POINT_is_at_infinity(group, a)) {
385 return EC_POINT_copy(r, b);
386 }
387 if (EC_POINT_is_at_infinity(group, b)) {
388 return EC_POINT_copy(r, a);
389 }
390
391 field_mul = group->meth->field_mul;
392 field_sqr = group->meth->field_sqr;
393 p = &group->field;
394
395 if (ctx == NULL) {
396 ctx = new_ctx = BN_CTX_new();
397 if (ctx == NULL) {
398 return 0;
399 }
400 }
401
402 BN_CTX_start(ctx);
403 n0 = BN_CTX_get(ctx);
404 n1 = BN_CTX_get(ctx);
405 n2 = BN_CTX_get(ctx);
406 n3 = BN_CTX_get(ctx);
407 n4 = BN_CTX_get(ctx);
408 n5 = BN_CTX_get(ctx);
409 n6 = BN_CTX_get(ctx);
410 if (n6 == NULL) {
411 goto end;
412 }
413
414 /* Note that in this function we must not read components of 'a' or 'b'
415 * once we have written the corresponding components of 'r'.
416 * ('r' might be one of 'a' or 'b'.)
417 */
418
419 /* n1, n2 */
420 int b_Z_is_one = BN_cmp(&b->Z, &group->one) == 0;
421
422 if (b_Z_is_one) {
423 if (!BN_copy(n1, &a->X) || !BN_copy(n2, &a->Y)) {
424 goto end;
425 }
426 /* n1 = X_a */
427 /* n2 = Y_a */
428 } else {
429 if (!field_sqr(group, n0, &b->Z, ctx) ||
430 !field_mul(group, n1, &a->X, n0, ctx)) {
431 goto end;
432 }
433 /* n1 = X_a * Z_b^2 */
434
435 if (!field_mul(group, n0, n0, &b->Z, ctx) ||
436 !field_mul(group, n2, &a->Y, n0, ctx)) {
437 goto end;
438 }
439 /* n2 = Y_a * Z_b^3 */
440 }
441
442 /* n3, n4 */
443 int a_Z_is_one = BN_cmp(&a->Z, &group->one) == 0;
444 if (a_Z_is_one) {
445 if (!BN_copy(n3, &b->X) || !BN_copy(n4, &b->Y)) {
446 goto end;
447 }
448 /* n3 = X_b */
449 /* n4 = Y_b */
450 } else {
451 if (!field_sqr(group, n0, &a->Z, ctx) ||
452 !field_mul(group, n3, &b->X, n0, ctx)) {
453 goto end;
454 }
455 /* n3 = X_b * Z_a^2 */
456
457 if (!field_mul(group, n0, n0, &a->Z, ctx) ||
458 !field_mul(group, n4, &b->Y, n0, ctx)) {
459 goto end;
460 }
461 /* n4 = Y_b * Z_a^3 */
462 }
463
464 /* n5, n6 */
465 if (!BN_mod_sub_quick(n5, n1, n3, p) ||
466 !BN_mod_sub_quick(n6, n2, n4, p)) {
467 goto end;
468 }
469 /* n5 = n1 - n3 */
470 /* n6 = n2 - n4 */
471
472 if (BN_is_zero(n5)) {
473 if (BN_is_zero(n6)) {
474 /* a is the same point as b */
475 BN_CTX_end(ctx);
476 ret = EC_POINT_dbl(group, r, a, ctx);
477 ctx = NULL;
478 goto end;
479 } else {
480 /* a is the inverse of b */
481 BN_zero(&r->Z);
482 ret = 1;
483 goto end;
484 }
485 }
486
487 /* 'n7', 'n8' */
488 if (!BN_mod_add_quick(n1, n1, n3, p) ||
489 !BN_mod_add_quick(n2, n2, n4, p)) {
490 goto end;
491 }
492 /* 'n7' = n1 + n3 */
493 /* 'n8' = n2 + n4 */
494
495 /* Z_r */
496 if (a_Z_is_one && b_Z_is_one) {
497 if (!BN_copy(&r->Z, n5)) {
498 goto end;
499 }
500 } else {
501 if (a_Z_is_one) {
502 if (!BN_copy(n0, &b->Z)) {
503 goto end;
504 }
505 } else if (b_Z_is_one) {
506 if (!BN_copy(n0, &a->Z)) {
507 goto end;
508 }
509 } else if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) {
510 goto end;
511 }
512 if (!field_mul(group, &r->Z, n0, n5, ctx)) {
513 goto end;
514 }
515 }
516
517 /* Z_r = Z_a * Z_b * n5 */
518
519 /* X_r */
520 if (!field_sqr(group, n0, n6, ctx) ||
521 !field_sqr(group, n4, n5, ctx) ||
522 !field_mul(group, n3, n1, n4, ctx) ||
523 !BN_mod_sub_quick(&r->X, n0, n3, p)) {
524 goto end;
525 }
526 /* X_r = n6^2 - n5^2 * 'n7' */
527
528 /* 'n9' */
529 if (!BN_mod_lshift1_quick(n0, &r->X, p) ||
530 !BN_mod_sub_quick(n0, n3, n0, p)) {
531 goto end;
532 }
533 /* n9 = n5^2 * 'n7' - 2 * X_r */
534
535 /* Y_r */
536 if (!field_mul(group, n0, n0, n6, ctx) ||
537 !field_mul(group, n5, n4, n5, ctx)) {
538 goto end; /* now n5 is n5^3 */
539 }
540 if (!field_mul(group, n1, n2, n5, ctx) ||
541 !BN_mod_sub_quick(n0, n0, n1, p)) {
542 goto end;
543 }
544 if (BN_is_odd(n0) && !BN_add(n0, n0, p)) {
545 goto end;
546 }
547 /* now 0 <= n0 < 2*p, and n0 is even */
548 if (!BN_rshift1(&r->Y, n0)) {
549 goto end;
550 }
551 /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
552
553 ret = 1;
554
555 end:
556 if (ctx) {
557 /* otherwise we already called BN_CTX_end */
558 BN_CTX_end(ctx);
559 }
560 BN_CTX_free(new_ctx);
561 return ret;
562 }
563
564 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
565 BN_CTX *ctx) {
566 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *,
567 BN_CTX *);
568 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
569 const BIGNUM *p;
570 BN_CTX *new_ctx = NULL;
571 BIGNUM *n0, *n1, *n2, *n3;
572 int ret = 0;
573
574 if (EC_POINT_is_at_infinity(group, a)) {
575 BN_zero(&r->Z);
576 return 1;
577 }
578
579 field_mul = group->meth->field_mul;
580 field_sqr = group->meth->field_sqr;
581 p = &group->field;
582
583 if (ctx == NULL) {
584 ctx = new_ctx = BN_CTX_new();
585 if (ctx == NULL) {
586 return 0;
587 }
588 }
589
590 BN_CTX_start(ctx);
591 n0 = BN_CTX_get(ctx);
592 n1 = BN_CTX_get(ctx);
593 n2 = BN_CTX_get(ctx);
594 n3 = BN_CTX_get(ctx);
595 if (n3 == NULL) {
596 goto err;
597 }
598
599 /* Note that in this function we must not read components of 'a'
600 * once we have written the corresponding components of 'r'.
601 * ('r' might the same as 'a'.)
602 */
603
604 /* n1 */
605 if (BN_cmp(&a->Z, &group->one) == 0) {
606 if (!field_sqr(group, n0, &a->X, ctx) ||
607 !BN_mod_lshift1_quick(n1, n0, p) ||
608 !BN_mod_add_quick(n0, n0, n1, p) ||
609 !BN_mod_add_quick(n1, n0, &group->a, p)) {
610 goto err;
611 }
612 /* n1 = 3 * X_a^2 + a_curve */
613 } else if (group->a_is_minus3) {
614 if (!field_sqr(group, n1, &a->Z, ctx) ||
615 !BN_mod_add_quick(n0, &a->X, n1, p) ||
616 !BN_mod_sub_quick(n2, &a->X, n1, p) ||
617 !field_mul(group, n1, n0, n2, ctx) ||
618 !BN_mod_lshift1_quick(n0, n1, p) ||
619 !BN_mod_add_quick(n1, n0, n1, p)) {
620 goto err;
621 }
622 /* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
623 * = 3 * X_a^2 - 3 * Z_a^4 */
624 } else {
625 if (!field_sqr(group, n0, &a->X, ctx) ||
626 !BN_mod_lshift1_quick(n1, n0, p) ||
627 !BN_mod_add_quick(n0, n0, n1, p) ||
628 !field_sqr(group, n1, &a->Z, ctx) ||
629 !field_sqr(group, n1, n1, ctx) ||
630 !field_mul(group, n1, n1, &group->a, ctx) ||
631 !BN_mod_add_quick(n1, n1, n0, p)) {
632 goto err;
633 }
634 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
635 }
636
637 /* Z_r */
638 if (BN_cmp(&a->Z, &group->one) == 0) {
639 if (!BN_copy(n0, &a->Y)) {
640 goto err;
641 }
642 } else if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) {
643 goto err;
644 }
645 if (!BN_mod_lshift1_quick(&r->Z, n0, p)) {
646 goto err;
647 }
648 /* Z_r = 2 * Y_a * Z_a */
649
650 /* n2 */
651 if (!field_sqr(group, n3, &a->Y, ctx) ||
652 !field_mul(group, n2, &a->X, n3, ctx) ||
653 !BN_mod_lshift_quick(n2, n2, 2, p)) {
654 goto err;
655 }
656 /* n2 = 4 * X_a * Y_a^2 */
657
658 /* X_r */
659 if (!BN_mod_lshift1_quick(n0, n2, p) ||
660 !field_sqr(group, &r->X, n1, ctx) ||
661 !BN_mod_sub_quick(&r->X, &r->X, n0, p)) {
662 goto err;
663 }
664 /* X_r = n1^2 - 2 * n2 */
665
666 /* n3 */
667 if (!field_sqr(group, n0, n3, ctx) ||
668 !BN_mod_lshift_quick(n3, n0, 3, p)) {
669 goto err;
670 }
671 /* n3 = 8 * Y_a^4 */
672
673 /* Y_r */
674 if (!BN_mod_sub_quick(n0, n2, &r->X, p) ||
675 !field_mul(group, n0, n1, n0, ctx) ||
676 !BN_mod_sub_quick(&r->Y, n0, n3, p)) {
677 goto err;
678 }
679 /* Y_r = n1 * (n2 - X_r) - n3 */
680
681 ret = 1;
682
683 err:
684 BN_CTX_end(ctx);
685 BN_CTX_free(new_ctx);
686 return ret;
687 }
688
689 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) {
690 if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y)) {
691 /* point is its own inverse */
692 return 1;
693 }
694
695 return BN_usub(&point->Y, &group->field, &point->Y);
696 }
697
698 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) {
699 return BN_is_zero(&point->Z);
700 }
701
702 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
703 BN_CTX *ctx) {
704 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *,
705 BN_CTX *);
706 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
707 const BIGNUM *p;
708 BN_CTX *new_ctx = NULL;
709 BIGNUM *rh, *tmp, *Z4, *Z6;
710 int ret = 0;
711
712 if (EC_POINT_is_at_infinity(group, point)) {
713 return 1;
714 }
715
716 field_mul = group->meth->field_mul;
717 field_sqr = group->meth->field_sqr;
718 p = &group->field;
719
720 if (ctx == NULL) {
721 ctx = new_ctx = BN_CTX_new();
722 if (ctx == NULL) {
723 return 0;
724 }
725 }
726
727 BN_CTX_start(ctx);
728 rh = BN_CTX_get(ctx);
729 tmp = BN_CTX_get(ctx);
730 Z4 = BN_CTX_get(ctx);
731 Z6 = BN_CTX_get(ctx);
732 if (Z6 == NULL) {
733 goto err;
734 }
735
736 /* We have a curve defined by a Weierstrass equation
737 * y^2 = x^3 + a*x + b.
738 * The point to consider is given in Jacobian projective coordinates
739 * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3).
740 * Substituting this and multiplying by Z^6 transforms the above equation
741 * into
742 * Y^2 = X^3 + a*X*Z^4 + b*Z^6.
743 * To test this, we add up the right-hand side in 'rh'.
744 */
745
746 /* rh := X^2 */
747 if (!field_sqr(group, rh, &point->X, ctx)) {
748 goto err;
749 }
750
751 if (BN_cmp(&point->Z, &group->one) != 0) {
752 if (!field_sqr(group, tmp, &point->Z, ctx) ||
753 !field_sqr(group, Z4, tmp, ctx) ||
754 !field_mul(group, Z6, Z4, tmp, ctx)) {
755 goto err;
756 }
757
758 /* rh := (rh + a*Z^4)*X */
759 if (group->a_is_minus3) {
760 if (!BN_mod_lshift1_quick(tmp, Z4, p) ||
761 !BN_mod_add_quick(tmp, tmp, Z4, p) ||
762 !BN_mod_sub_quick(rh, rh, tmp, p) ||
763 !field_mul(group, rh, rh, &point->X, ctx)) {
764 goto err;
765 }
766 } else {
767 if (!field_mul(group, tmp, Z4, &group->a, ctx) ||
768 !BN_mod_add_quick(rh, rh, tmp, p) ||
769 !field_mul(group, rh, rh, &point->X, ctx)) {
770 goto err;
771 }
772 }
773
774 /* rh := rh + b*Z^6 */
775 if (!field_mul(group, tmp, &group->b, Z6, ctx) ||
776 !BN_mod_add_quick(rh, rh, tmp, p)) {
777 goto err;
778 }
779 } else {
780 /* rh := (rh + a)*X */
781 if (!BN_mod_add_quick(rh, rh, &group->a, p) ||
782 !field_mul(group, rh, rh, &point->X, ctx)) {
783 goto err;
784 }
785 /* rh := rh + b */
786 if (!BN_mod_add_quick(rh, rh, &group->b, p)) {
787 goto err;
788 }
789 }
790
791 /* 'lh' := Y^2 */
792 if (!field_sqr(group, tmp, &point->Y, ctx)) {
793 goto err;
794 }
795
796 ret = (0 == BN_ucmp(tmp, rh));
797
798 err:
799 BN_CTX_end(ctx);
800 BN_CTX_free(new_ctx);
801 return ret;
802 }
803
804 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
805 const EC_POINT *b, BN_CTX *ctx) {
806 /* return values:
807 * -1 error
808 * 0 equal (in affine coordinates)
809 * 1 not equal
810 */
811
812 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *,
813 BN_CTX *);
814 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
815 BN_CTX *new_ctx = NULL;
816 BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
817 const BIGNUM *tmp1_, *tmp2_;
818 int ret = -1;
819
820 if (EC_POINT_is_at_infinity(group, a)) {
821 return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
822 }
823
824 if (EC_POINT_is_at_infinity(group, b)) {
825 return 1;
826 }
827
828 int a_Z_is_one = BN_cmp(&a->Z, &group->one) == 0;
829 int b_Z_is_one = BN_cmp(&b->Z, &group->one) == 0;
830
831 if (a_Z_is_one && b_Z_is_one) {
832 return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
833 }
834
835 field_mul = group->meth->field_mul;
836 field_sqr = group->meth->field_sqr;
837
838 if (ctx == NULL) {
839 ctx = new_ctx = BN_CTX_new();
840 if (ctx == NULL) {
841 return -1;
842 }
843 }
844
845 BN_CTX_start(ctx);
846 tmp1 = BN_CTX_get(ctx);
847 tmp2 = BN_CTX_get(ctx);
848 Za23 = BN_CTX_get(ctx);
849 Zb23 = BN_CTX_get(ctx);
850 if (Zb23 == NULL) {
851 goto end;
852 }
853
854 /* We have to decide whether
855 * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
856 * or equivalently, whether
857 * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
858 */
859
860 if (!b_Z_is_one) {
861 if (!field_sqr(group, Zb23, &b->Z, ctx) ||
862 !field_mul(group, tmp1, &a->X, Zb23, ctx)) {
863 goto end;
864 }
865 tmp1_ = tmp1;
866 } else {
867 tmp1_ = &a->X;
868 }
869 if (!a_Z_is_one) {
870 if (!field_sqr(group, Za23, &a->Z, ctx) ||
871 !field_mul(group, tmp2, &b->X, Za23, ctx)) {
872 goto end;
873 }
874 tmp2_ = tmp2;
875 } else {
876 tmp2_ = &b->X;
877 }
878
879 /* compare X_a*Z_b^2 with X_b*Z_a^2 */
880 if (BN_cmp(tmp1_, tmp2_) != 0) {
881 ret = 1; /* points differ */
882 goto end;
883 }
884
885
886 if (!b_Z_is_one) {
887 if (!field_mul(group, Zb23, Zb23, &b->Z, ctx) ||
888 !field_mul(group, tmp1, &a->Y, Zb23, ctx)) {
889 goto end;
890 }
891 /* tmp1_ = tmp1 */
892 } else {
893 tmp1_ = &a->Y;
894 }
895 if (!a_Z_is_one) {
896 if (!field_mul(group, Za23, Za23, &a->Z, ctx) ||
897 !field_mul(group, tmp2, &b->Y, Za23, ctx)) {
898 goto end;
899 }
900 /* tmp2_ = tmp2 */
901 } else {
902 tmp2_ = &b->Y;
903 }
904
905 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */
906 if (BN_cmp(tmp1_, tmp2_) != 0) {
907 ret = 1; /* points differ */
908 goto end;
909 }
910
911 /* points are equal */
912 ret = 0;
913
914 end:
915 BN_CTX_end(ctx);
916 BN_CTX_free(new_ctx);
917 return ret;
918 }
919
920 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
921 BN_CTX *ctx) {
922 BN_CTX *new_ctx = NULL;
923 BIGNUM *x, *y;
924 int ret = 0;
925
926 if (BN_cmp(&point->Z, &group->one) == 0 ||
927 EC_POINT_is_at_infinity(group, point)) {
928 return 1;
929 }
930
931 if (ctx == NULL) {
932 ctx = new_ctx = BN_CTX_new();
933 if (ctx == NULL) {
934 return 0;
935 }
936 }
937
938 BN_CTX_start(ctx);
939 x = BN_CTX_get(ctx);
940 y = BN_CTX_get(ctx);
941 if (y == NULL) {
942 goto err;
943 }
944
945 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx) ||
946 !EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) {
947 goto err;
948 }
949 if (BN_cmp(&point->Z, &group->one) != 0) {
950 OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
951 goto err;
952 }
953
954 ret = 1;
955
956 err:
957 BN_CTX_end(ctx);
958 BN_CTX_free(new_ctx);
959 return ret;
960 }
961
962 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num,
963 EC_POINT *points[], BN_CTX *ctx) {
964 BN_CTX *new_ctx = NULL;
965 BIGNUM *tmp, *tmp_Z;
966 BIGNUM **prod_Z = NULL;
967 size_t i;
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 memset(prod_Z, 0, num * sizeof(prod_Z[0]));
993 for (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 (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
1027 * non-zero points[i]->Z by its inverse. */
1028
1029 if (!BN_mod_inverse(tmp, prod_Z[num - 1], &group->field, ctx)) {
1030 OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB);
1031 goto err;
1032 }
1033
1034 if (group->meth->field_encode != NULL) {
1035 /* In the Montgomery case, we just turned R*H (representing H)
1036 * into 1/(R*H), but we need R*(1/H) (representing 1/H);
1037 * i.e. we need to multiply by the Montgomery factor twice. */
1038 if (!group->meth->field_encode(group, tmp, tmp, ctx) ||
1039 !group->meth->field_encode(group, tmp, tmp, ctx)) {
1040 goto err;
1041 }
1042 }
1043
1044 for (i = num - 1; i > 0; --i) {
1045 /* Loop invariant: tmp is the product of the inverses of
1046 * points[0]->Z .. points[i]->Z (zero-valued inputs skipped). */
1047 if (BN_is_zero(&points[i]->Z)) {
1048 continue;
1049 }
1050
1051 /* Set tmp_Z to the inverse of points[i]->Z (as product
1052 * of Z inverses 0 .. i, Z values 0 .. i - 1). */
1053 if (!group->meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx) ||
1054 /* Update tmp to satisfy the loop invariant for i - 1. */
1055 !group->meth->field_mul(group, tmp, tmp, &points[i]->Z, ctx) ||
1056 /* Replace points[i]->Z by its inverse. */
1057 !BN_copy(&points[i]->Z, tmp_Z)) {
1058 goto err;
1059 }
1060 }
1061
1062 /* Replace points[0]->Z by its inverse. */
1063 if (!BN_is_zero(&points[0]->Z) && !BN_copy(&points[0]->Z, tmp)) {
1064 goto err;
1065 }
1066
1067 /* Finally, fix up the X and Y coordinates for all points. */
1068 for (i = 0; i < num; i++) {
1069 EC_POINT *p = points[i];
1070
1071 if (!BN_is_zero(&p->Z)) {
1072 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1). */
1073 if (!group->meth->field_sqr(group, tmp, &p->Z, ctx) ||
1074 !group->meth->field_mul(group, &p->X, &p->X, tmp, ctx) ||
1075 !group->meth->field_mul(group, tmp, tmp, &p->Z, ctx) ||
1076 !group->meth->field_mul(group, &p->Y, &p->Y, tmp, ctx)) {
1077 goto err;
1078 }
1079
1080 if (BN_copy(&p->Z, &group->one) == NULL) {
1081 goto err;
1082 }
1083 }
1084 }
1085
1086 ret = 1;
1087
1088 err:
1089 BN_CTX_end(ctx);
1090 BN_CTX_free(new_ctx);
1091 if (prod_Z != NULL) {
1092 for (i = 0; i < num; i++) {
1093 if (prod_Z[i] == NULL) {
1094 break;
1095 }
1096 BN_clear_free(prod_Z[i]);
1097 }
1098 OPENSSL_free(prod_Z);
1099 }
1100
1101 return ret;
1102 }
1103
1104 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1105 const BIGNUM *b, BN_CTX *ctx) {
1106 return BN_mod_mul(r, a, b, &group->field, ctx);
1107 }
1108
1109 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1110 BN_CTX *ctx) {
1111 return BN_mod_sqr(r, a, &group->field, ctx);
1112 }