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