]> git.ipfire.org Git - thirdparty/openssl.git/blob - crypto/ec/ecp_smpl.c
projects / thirdparty / openssl.git / blob
? search:


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