]> git.ipfire.org Git - thirdparty/openssl.git/blob - crypto/ec/ecp_smpl.c
projects / thirdparty / openssl.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Make ec_GFp_simple_point_get_affine_coordinates() faster
[thirdparty/openssl.git] / crypto / ec / ecp_smpl.c
1 /* crypto/ec/ecp_smpl.c */
2 /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
3 * for the OpenSSL project.
4 * Includes code written by Bodo Moeller for the OpenSSL project.
5 */
6 /* ====================================================================
7 * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 *
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in
18 * the documentation and/or other materials provided with the
19 * distribution.
20 *
21 * 3. All advertising materials mentioning features or use of this
22 * software must display the following acknowledgment:
23 * "This product includes software developed by the OpenSSL Project
24 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
25 *
26 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
27 * endorse or promote products derived from this software without
28 * prior written permission. For written permission, please contact
29 * openssl-core@openssl.org.
30 *
31 * 5. Products derived from this software may not be called "OpenSSL"
32 * nor may "OpenSSL" appear in their names without prior written
33 * permission of the OpenSSL Project.
34 *
35 * 6. Redistributions of any form whatsoever must retain the following
36 * acknowledgment:
37 * "This product includes software developed by the OpenSSL Project
38 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
39 *
40 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
41 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
43 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
44 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
45 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
46 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
47 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
49 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
50 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
51 * OF THE POSSIBILITY OF SUCH DAMAGE.
52 * ====================================================================
53 *
54 * This product includes cryptographic software written by Eric Young
55 * (eay@cryptsoft.com). This product includes software written by Tim
56 * Hudson (tjh@cryptsoft.com).
57 *
58 */
59 /* ====================================================================
60 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
61 * Portions of this software developed by SUN MICROSYSTEMS, INC.,
62 * and contributed to the OpenSSL project.
63 */
64
65 #include <openssl/err.h>
66 #include <openssl/symhacks.h>
67
68 #include "ec_lcl.h"
69
70 const EC_METHOD *EC_GFp_simple_method(void)
71 {
72 static const EC_METHOD ret = {
73 NID_X9_62_prime_field,
74 ec_GFp_simple_group_init,
75 ec_GFp_simple_group_finish,
76 ec_GFp_simple_group_clear_finish,
77 ec_GFp_simple_group_copy,
78 ec_GFp_simple_group_set_curve,
79 ec_GFp_simple_group_get_curve,
80 ec_GFp_simple_group_get_degree,
81 ec_GFp_simple_group_check_discriminant,
82 ec_GFp_simple_point_init,
83 ec_GFp_simple_point_finish,
84 ec_GFp_simple_point_clear_finish,
85 ec_GFp_simple_point_copy,
86 ec_GFp_simple_point_set_to_infinity,
87 ec_GFp_simple_set_Jprojective_coordinates_GFp,
88 ec_GFp_simple_get_Jprojective_coordinates_GFp,
89 ec_GFp_simple_point_set_affine_coordinates,
90 ec_GFp_simple_point_get_affine_coordinates,
91 ec_GFp_simple_set_compressed_coordinates,
92 ec_GFp_simple_point2oct,
93 ec_GFp_simple_oct2point,
94 ec_GFp_simple_add,
95 ec_GFp_simple_dbl,
96 ec_GFp_simple_invert,
97 0 /* mul */,
98 0 /* precompute_mult */,
99 ec_GFp_simple_is_at_infinity,
100 ec_GFp_simple_is_on_curve,
101 ec_GFp_simple_cmp,
102 ec_GFp_simple_make_affine,
103 ec_GFp_simple_points_make_affine,
104 ec_GFp_simple_field_mul,
105 ec_GFp_simple_field_sqr,
106 0 /* field_div */,
107 0 /* field_encode */,
108 0 /* field_decode */,
109 0 /* field_set_to_one */ };
110
111 return &ret;
112 }
113
114
115 int ec_GFp_simple_group_init(EC_GROUP *group)
116 {
117 BN_init(&group->field);
118 BN_init(&group->a);
119 BN_init(&group->b);
120 group->a_is_minus3 = 0;
121 return 1;
122 }
123
124
125 void ec_GFp_simple_group_finish(EC_GROUP *group)
126 {
127 BN_free(&group->field);
128 BN_free(&group->a);
129 BN_free(&group->b);
130 }
131
132
133 void ec_GFp_simple_group_clear_finish(EC_GROUP *group)
134 {
135 BN_clear_free(&group->field);
136 BN_clear_free(&group->a);
137 BN_clear_free(&group->b);
138 }
139
140
141 int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
142 {
143 if (!BN_copy(&dest->field, &src->field)) return 0;
144 if (!BN_copy(&dest->a, &src->a)) return 0;
145 if (!BN_copy(&dest->b, &src->b)) return 0;
146
147 dest->a_is_minus3 = src->a_is_minus3;
148
149 return 1;
150 }
151
152
153 int ec_GFp_simple_group_set_curve(EC_GROUP *group,
154 const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
155 {
156 int ret = 0;
157 BN_CTX *new_ctx = NULL;
158 BIGNUM *tmp_a;
159
160 /* p must be a prime > 3 */
161 if (BN_num_bits(p) <= 2 || !BN_is_odd(p))
162 {
163 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD);
164 return 0;
165 }
166
167 if (ctx == NULL)
168 {
169 ctx = new_ctx = BN_CTX_new();
170 if (ctx == NULL)
171 return 0;
172 }
173
174 BN_CTX_start(ctx);
175 tmp_a = BN_CTX_get(ctx);
176 if (tmp_a == NULL) goto err;
177
178 /* group->field */
179 if (!BN_copy(&group->field, p)) goto err;
180 BN_set_sign(&group->field, 0);
181
182 /* group->a */
183 if (!BN_nnmod(tmp_a, a, p, ctx)) goto err;
184 if (group->meth->field_encode)
185 { if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) goto err; }
186 else
187 if (!BN_copy(&group->a, tmp_a)) goto err;
188
189 /* group->b */
190 if (!BN_nnmod(&group->b, b, p, ctx)) goto err;
191 if (group->meth->field_encode)
192 if (!group->meth->field_encode(group, &group->b, &group->b, ctx)) goto err;
193
194 /* group->a_is_minus3 */
195 if (!BN_add_word(tmp_a, 3)) goto err;
196 group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
197
198 ret = 1;
199
200 err:
201 BN_CTX_end(ctx);
202 if (new_ctx != NULL)
203 BN_CTX_free(new_ctx);
204 return ret;
205 }
206
207
208 int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
209 {
210 int ret = 0;
211 BN_CTX *new_ctx = NULL;
212
213 if (p != NULL)
214 {
215 if (!BN_copy(p, &group->field)) return 0;
216 }
217
218 if (a != NULL || b != NULL)
219 {
220 if (group->meth->field_decode)
221 {
222 if (ctx == NULL)
223 {
224 ctx = new_ctx = BN_CTX_new();
225 if (ctx == NULL)
226 return 0;
227 }
228 if (a != NULL)
229 {
230 if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err;
231 }
232 if (b != NULL)
233 {
234 if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err;
235 }
236 }
237 else
238 {
239 if (a != NULL)
240 {
241 if (!BN_copy(a, &group->a)) goto err;
242 }
243 if (b != NULL)
244 {
245 if (!BN_copy(b, &group->b)) goto err;
246 }
247 }
248 }
249
250 ret = 1;
251
252 err:
253 if (new_ctx)
254 BN_CTX_free(new_ctx);
255 return ret;
256 }
257
258
259 int ec_GFp_simple_group_get_degree(const EC_GROUP *group)
260 {
261 return BN_num_bits(&group->field);
262 }
263
264
265 int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
266 {
267 int ret = 0;
268 BIGNUM *a,*b,*order,*tmp_1,*tmp_2;
269 const BIGNUM *p = &group->field;
270 BN_CTX *new_ctx = NULL;
271
272 if (ctx == NULL)
273 {
274 ctx = new_ctx = BN_CTX_new();
275 if (ctx == NULL)
276 {
277 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, ERR_R_MALLOC_FAILURE);
278 goto err;
279 }
280 }
281 BN_CTX_start(ctx);
282 a = BN_CTX_get(ctx);
283 b = BN_CTX_get(ctx);
284 tmp_1 = BN_CTX_get(ctx);
285 tmp_2 = BN_CTX_get(ctx);
286 order = BN_CTX_get(ctx);
287 if (order == NULL) goto err;
288
289 if (group->meth->field_decode)
290 {
291 if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err;
292 if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err;
293 }
294 else
295 {
296 if (!BN_copy(a, &group->a)) goto err;
297 if (!BN_copy(b, &group->b)) goto err;
298 }
299
300 /* check the discriminant:
301 * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p)
302 * 0 =< a, b < p */
303 if (BN_is_zero(a))
304 {
305 if (BN_is_zero(b)) goto err;
306 }
307 else if (!BN_is_zero(b))
308 {
309 if (!BN_mod_sqr(tmp_1, a, p, ctx)) goto err;
310 if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx)) goto err;
311 if (!BN_lshift(tmp_1, tmp_2, 2)) goto err;
312 /* tmp_1 = 4*a^3 */
313
314 if (!BN_mod_sqr(tmp_2, b, p, ctx)) goto err;
315 if (!BN_mul_word(tmp_2, 27)) goto err;
316 /* tmp_2 = 27*b^2 */
317
318 if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx)) goto err;
319 if (BN_is_zero(a)) goto err;
320 }
321 ret = 1;
322
323 err:
324 BN_CTX_end(ctx);
325 if (new_ctx != NULL)
326 BN_CTX_free(new_ctx);
327 return ret;
328 }
329
330
331 int ec_GFp_simple_point_init(EC_POINT *point)
332 {
333 BN_init(&point->X);
334 BN_init(&point->Y);
335 BN_init(&point->Z);
336 point->Z_is_one = 0;
337
338 return 1;
339 }
340
341
342 void ec_GFp_simple_point_finish(EC_POINT *point)
343 {
344 BN_free(&point->X);
345 BN_free(&point->Y);
346 BN_free(&point->Z);
347 }
348
349
350 void ec_GFp_simple_point_clear_finish(EC_POINT *point)
351 {
352 BN_clear_free(&point->X);
353 BN_clear_free(&point->Y);
354 BN_clear_free(&point->Z);
355 point->Z_is_one = 0;
356 }
357
358
359 int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
360 {
361 if (!BN_copy(&dest->X, &src->X)) return 0;
362 if (!BN_copy(&dest->Y, &src->Y)) return 0;
363 if (!BN_copy(&dest->Z, &src->Z)) return 0;
364 dest->Z_is_one = src->Z_is_one;
365
366 return 1;
367 }
368
369
370 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
371 {
372 point->Z_is_one = 0;
373 return (BN_zero(&point->Z));
374 }
375
376
377 int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
378 const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx)
379 {
380 BN_CTX *new_ctx = NULL;
381 int ret = 0;
382
383 if (ctx == NULL)
384 {
385 ctx = new_ctx = BN_CTX_new();
386 if (ctx == NULL)
387 return 0;
388 }
389
390 if (x != NULL)
391 {
392 if (!BN_nnmod(&point->X, x, &group->field, ctx)) goto err;
393 if (group->meth->field_encode)
394 {
395 if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) goto err;
396 }
397 }
398
399 if (y != NULL)
400 {
401 if (!BN_nnmod(&point->Y, y, &group->field, ctx)) goto err;
402 if (group->meth->field_encode)
403 {
404 if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) goto err;
405 }
406 }
407
408 if (z != NULL)
409 {
410 int Z_is_one;
411
412 if (!BN_nnmod(&point->Z, z, &group->field, ctx)) goto err;
413 Z_is_one = BN_is_one(&point->Z);
414 if (group->meth->field_encode)
415 {
416 if (Z_is_one && (group->meth->field_set_to_one != 0))
417 {
418 if (!group->meth->field_set_to_one(group, &point->Z, ctx)) goto err;
419 }
420 else
421 {
422 if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err;
423 }
424 }
425 point->Z_is_one = Z_is_one;
426 }
427
428 ret = 1;
429
430 err:
431 if (new_ctx != NULL)
432 BN_CTX_free(new_ctx);
433 return ret;
434 }
435
436
437 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point,
438 BIGNUM *x, BIGNUM *y, 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 {
445 if (ctx == NULL)
446 {
447 ctx = new_ctx = BN_CTX_new();
448 if (ctx == NULL)
449 return 0;
450 }
451
452 if (x != NULL)
453 {
454 if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err;
455 }
456 if (y != NULL)
457 {
458 if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err;
459 }
460 if (z != NULL)
461 {
462 if (!group->meth->field_decode(group, z, &point->Z, ctx)) goto err;
463 }
464 }
465 else
466 {
467 if (x != NULL)
468 {
469 if (!BN_copy(x, &point->X)) goto err;
470 }
471 if (y != NULL)
472 {
473 if (!BN_copy(y, &point->Y)) goto err;
474 }
475 if (z != NULL)
476 {
477 if (!BN_copy(z, &point->Z)) goto err;
478 }
479 }
480
481 ret = 1;
482
483 err:
484 if (new_ctx != NULL)
485 BN_CTX_free(new_ctx);
486 return ret;
487 }
488
489
490 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point,
491 const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
492 {
493 if (x == NULL || y == NULL)
494 {
495 /* unlike for projective coordinates, we do not tolerate this */
496 ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PASSED_NULL_PARAMETER);
497 return 0;
498 }
499
500 return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, BN_value_one(), ctx);
501 }
502
503
504 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point,
505 BIGNUM *x, BIGNUM *y, 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 {
514 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POINT_AT_INFINITY);
515 return 0;
516 }
517
518 if (ctx == NULL)
519 {
520 ctx = new_ctx = BN_CTX_new();
521 if (ctx == NULL)
522 return 0;
523 }
524
525 BN_CTX_start(ctx);
526 Z = BN_CTX_get(ctx);
527 Z_1 = BN_CTX_get(ctx);
528 Z_2 = BN_CTX_get(ctx);
529 Z_3 = BN_CTX_get(ctx);
530 if (Z_3 == NULL) 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 {
536 if (!group->meth->field_decode(group, Z, &point->Z, ctx)) goto err;
537 Z_ = Z;
538 }
539 else
540 {
541 Z_ = &point->Z;
542 }
543
544 if (BN_is_one(Z_))
545 {
546 if (group->meth->field_decode)
547 {
548 if (x != NULL)
549 {
550 if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err;
551 }
552 if (y != NULL)
553 {
554 if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err;
555 }
556 }
557 else
558 {
559 if (x != NULL)
560 {
561 if (!BN_copy(x, &point->X)) goto err;
562 }
563 if (y != NULL)
564 {
565 if (!BN_copy(y, &point->Y)) goto err;
566 }
567 }
568 }
569 else
570 {
571 if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx))
572 {
573 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_BN_LIB);
574 goto err;
575 }
576
577 if (group->meth->field_encode == 0)
578 {
579 /* field_sqr works on standard representation */
580 if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) goto err;
581 }
582 else
583 {
584 if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err;
585 }
586
587 if (x != NULL)
588 {
589 /* in the Montgomery case, field_mul will cancel out Montgomery factor in X: */
590 if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx)) goto err;
591 }
592
593 if (y != NULL)
594 {
595 if (group->meth->field_encode == 0)
596 {
597 /* field_mul works on standard representation */
598 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) goto err;
599 }
600 else
601 {
602 if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto err;
603 }
604
605 /* in the Montgomery case, field_mul will cancel out Montgomery factor in Y: */
606 if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) goto err;
607 }
608 }
609
610 ret = 1;
611
612 err:
613 BN_CTX_end(ctx);
614 if (new_ctx != NULL)
615 BN_CTX_free(new_ctx);
616 return ret;
617 }
618
619
620 int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, EC_POINT *point,
621 const BIGNUM *x_, int y_bit, BN_CTX *ctx)
622 {
623 BN_CTX *new_ctx = NULL;
624 BIGNUM *tmp1, *tmp2, *x, *y;
625 int ret = 0;
626
627 if (ctx == NULL)
628 {
629 ctx = new_ctx = BN_CTX_new();
630 if (ctx == NULL)
631 return 0;
632 }
633
634 y_bit = (y_bit != 0);
635
636 BN_CTX_start(ctx);
637 tmp1 = BN_CTX_get(ctx);
638 tmp2 = BN_CTX_get(ctx);
639 x = BN_CTX_get(ctx);
640 y = BN_CTX_get(ctx);
641 if (y == NULL) goto err;
642
643 /* Recover y. We have a Weierstrass equation
644 * y^2 = x^3 + a*x + b,
645 * so y is one of the square roots of x^3 + a*x + b.
646 */
647
648 /* tmp1 := x^3 */
649 if (!BN_nnmod(x, x_, &group->field,ctx)) goto err;
650 if (group->meth->field_decode == 0)
651 {
652 /* field_{sqr,mul} work on standard representation */
653 if (!group->meth->field_sqr(group, tmp2, x_, ctx)) goto err;
654 if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) goto err;
655 }
656 else
657 {
658 if (!BN_mod_sqr(tmp2, x_, &group->field, ctx)) goto err;
659 if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) goto err;
660 }
661
662 /* tmp1 := tmp1 + a*x */
663 if (group->a_is_minus3)
664 {
665 if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) goto err;
666 if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) goto err;
667 if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
668 }
669 else
670 {
671 if (group->meth->field_decode)
672 {
673 if (!group->meth->field_decode(group, tmp2, &group->a, ctx)) goto err;
674 if (!BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) goto err;
675 }
676 else
677 {
678 /* field_mul works on standard representation */
679 if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) goto err;
680 }
681
682 if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
683 }
684
685 /* tmp1 := tmp1 + b */
686 if (group->meth->field_decode)
687 {
688 if (!group->meth->field_decode(group, tmp2, &group->b, ctx)) goto err;
689 if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
690 }
691 else
692 {
693 if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) goto err;
694 }
695
696 if (!BN_mod_sqrt(y, tmp1, &group->field, ctx))
697 {
698 unsigned long err = ERR_peek_error();
699
700 if (ERR_GET_LIB(err) == ERR_LIB_BN && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE)
701 {
702 (void)ERR_get_error();
703 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
704 }
705 else
706 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_BN_LIB);
707 goto err;
708 }
709
710 if (y_bit != BN_is_odd(y))
711 {
712 if (BN_is_zero(y))
713 {
714 int kron;
715
716 kron = BN_kronecker(x, &group->field, ctx);
717 if (kron == -2) goto err;
718
719 if (kron == 1)
720 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSION_BIT);
721 else
722 /* BN_mod_sqrt() should have cought this error (not a square) */
723 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
724 goto err;
725 }
726 if (!BN_usub(y, &group->field, y)) goto err;
727 }
728 if (y_bit != BN_is_odd(y))
729 {
730 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_INTERNAL_ERROR);
731 goto err;
732 }
733
734 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
735
736 ret = 1;
737
738 err:
739 BN_CTX_end(ctx);
740 if (new_ctx != NULL)
741 BN_CTX_free(new_ctx);
742 return ret;
743 }
744
745
746 size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, point_conversion_form_t form,
747 unsigned char *buf, size_t len, BN_CTX *ctx)
748 {
749 size_t ret;
750 BN_CTX *new_ctx = NULL;
751 int used_ctx = 0;
752 BIGNUM *x, *y;
753 size_t field_len, i, skip;
754
755 if ((form != POINT_CONVERSION_COMPRESSED)
756 && (form != POINT_CONVERSION_UNCOMPRESSED)
757 && (form != POINT_CONVERSION_HYBRID))
758 {
759 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
760 goto err;
761 }
762
763 if (EC_POINT_is_at_infinity(group, point))
764 {
765 /* encodes to a single 0 octet */
766 if (buf != NULL)
767 {
768 if (len < 1)
769 {
770 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
771 return 0;
772 }
773 buf[0] = 0;
774 }
775 return 1;
776 }
777
778
779 /* ret := required output buffer length */
780 field_len = BN_num_bytes(&group->field);
781 ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
782
783 /* if 'buf' is NULL, just return required length */
784 if (buf != NULL)
785 {
786 if (len < ret)
787 {
788 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
789 goto err;
790 }
791
792 if (ctx == NULL)
793 {
794 ctx = new_ctx = BN_CTX_new();
795 if (ctx == NULL)
796 return 0;
797 }
798
799 BN_CTX_start(ctx);
800 used_ctx = 1;
801 x = BN_CTX_get(ctx);
802 y = BN_CTX_get(ctx);
803 if (y == NULL) goto err;
804
805 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
806
807 if ((form == POINT_CONVERSION_COMPRESSED || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y))
808 buf[0] = form + 1;
809 else
810 buf[0] = form;
811
812 i = 1;
813
814 skip = field_len - BN_num_bytes(x);
815 if (skip > field_len)
816 {
817 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
818 goto err;
819 }
820 while (skip > 0)
821 {
822 buf[i++] = 0;
823 skip--;
824 }
825 skip = BN_bn2bin(x, buf + i);
826 i += skip;
827 if (i != 1 + field_len)
828 {
829 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
830 goto err;
831 }
832
833 if (form == POINT_CONVERSION_UNCOMPRESSED || form == POINT_CONVERSION_HYBRID)
834 {
835 skip = field_len - BN_num_bytes(y);
836 if (skip > field_len)
837 {
838 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
839 goto err;
840 }
841 while (skip > 0)
842 {
843 buf[i++] = 0;
844 skip--;
845 }
846 skip = BN_bn2bin(y, buf + i);
847 i += skip;
848 }
849
850 if (i != ret)
851 {
852 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
853 goto err;
854 }
855 }
856
857 if (used_ctx)
858 BN_CTX_end(ctx);
859 if (new_ctx != NULL)
860 BN_CTX_free(new_ctx);
861 return ret;
862
863 err:
864 if (used_ctx)
865 BN_CTX_end(ctx);
866 if (new_ctx != NULL)
867 BN_CTX_free(new_ctx);
868 return 0;
869 }
870
871
872 int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
873 const unsigned char *buf, size_t len, BN_CTX *ctx)
874 {
875 point_conversion_form_t form;
876 int y_bit;
877 BN_CTX *new_ctx = NULL;
878 BIGNUM *x, *y;
879 size_t field_len, enc_len;
880 int ret = 0;
881
882 if (len == 0)
883 {
884 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
885 return 0;
886 }
887 form = buf[0];
888 y_bit = form & 1;
889 form = form & ~1;
890 if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
891 && (form != POINT_CONVERSION_UNCOMPRESSED)
892 && (form != POINT_CONVERSION_HYBRID))
893 {
894 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
895 return 0;
896 }
897 if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit)
898 {
899 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
900 return 0;
901 }
902
903 if (form == 0)
904 {
905 if (len != 1)
906 {
907 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
908 return 0;
909 }
910
911 return EC_POINT_set_to_infinity(group, point);
912 }
913
914 field_len = BN_num_bytes(&group->field);
915 enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
916
917 if (len != enc_len)
918 {
919 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
920 return 0;
921 }
922
923 if (ctx == NULL)
924 {
925 ctx = new_ctx = BN_CTX_new();
926 if (ctx == NULL)
927 return 0;
928 }
929
930 BN_CTX_start(ctx);
931 x = BN_CTX_get(ctx);
932 y = BN_CTX_get(ctx);
933 if (y == NULL) goto err;
934
935 if (!BN_bin2bn(buf + 1, field_len, x)) goto err;
936 if (BN_ucmp(x, &group->field) >= 0)
937 {
938 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
939 goto err;
940 }
941
942 if (form == POINT_CONVERSION_COMPRESSED)
943 {
944 if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) goto err;
945 }
946 else
947 {
948 if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) goto err;
949 if (BN_ucmp(y, &group->field) >= 0)
950 {
951 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
952 goto err;
953 }
954 if (form == POINT_CONVERSION_HYBRID)
955 {
956 if (y_bit != BN_is_odd(y))
957 {
958 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
959 goto err;
960 }
961 }
962
963 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
964 }
965
966 if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */
967 {
968 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
969 goto err;
970 }
971
972 ret = 1;
973
974 err:
975 BN_CTX_end(ctx);
976 if (new_ctx != NULL)
977 BN_CTX_free(new_ctx);
978 return ret;
979 }
980
981
982 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
983 {
984 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
985 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
986 const BIGNUM *p;
987 BN_CTX *new_ctx = NULL;
988 BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
989 int ret = 0;
990
991 if (a == b)
992 return EC_POINT_dbl(group, r, a, ctx);
993 if (EC_POINT_is_at_infinity(group, a))
994 return EC_POINT_copy(r, b);
995 if (EC_POINT_is_at_infinity(group, b))
996 return EC_POINT_copy(r, a);
997
998 field_mul = group->meth->field_mul;
999 field_sqr = group->meth->field_sqr;
1000 p = &group->field;
1001
1002 if (ctx == NULL)
1003 {
1004 ctx = new_ctx = BN_CTX_new();
1005 if (ctx == NULL)
1006 return 0;
1007 }
1008
1009 BN_CTX_start(ctx);
1010 n0 = BN_CTX_get(ctx);
1011 n1 = BN_CTX_get(ctx);
1012 n2 = BN_CTX_get(ctx);
1013 n3 = BN_CTX_get(ctx);
1014 n4 = BN_CTX_get(ctx);
1015 n5 = BN_CTX_get(ctx);
1016 n6 = BN_CTX_get(ctx);
1017 if (n6 == NULL) goto end;
1018
1019 /* Note that in this function we must not read components of 'a' or 'b'
1020 * once we have written the corresponding components of 'r'.
1021 * ('r' might be one of 'a' or 'b'.)
1022 */
1023
1024 /* n1, n2 */
1025 if (b->Z_is_one)
1026 {
1027 if (!BN_copy(n1, &a->X)) goto end;
1028 if (!BN_copy(n2, &a->Y)) goto end;
1029 /* n1 = X_a */
1030 /* n2 = Y_a */
1031 }
1032 else
1033 {
1034 if (!field_sqr(group, n0, &b->Z, ctx)) goto end;
1035 if (!field_mul(group, n1, &a->X, n0, ctx)) goto end;
1036 /* n1 = X_a * Z_b^2 */
1037
1038 if (!field_mul(group, n0, n0, &b->Z, ctx)) goto end;
1039 if (!field_mul(group, n2, &a->Y, n0, ctx)) goto end;
1040 /* n2 = Y_a * Z_b^3 */
1041 }
1042
1043 /* n3, n4 */
1044 if (a->Z_is_one)
1045 {
1046 if (!BN_copy(n3, &b->X)) goto end;
1047 if (!BN_copy(n4, &b->Y)) goto end;
1048 /* n3 = X_b */
1049 /* n4 = Y_b */
1050 }
1051 else
1052 {
1053 if (!field_sqr(group, n0, &a->Z, ctx)) goto end;
1054 if (!field_mul(group, n3, &b->X, n0, ctx)) goto end;
1055 /* n3 = X_b * Z_a^2 */
1056
1057 if (!field_mul(group, n0, n0, &a->Z, ctx)) goto end;
1058 if (!field_mul(group, n4, &b->Y, n0, ctx)) goto end;
1059 /* n4 = Y_b * Z_a^3 */
1060 }
1061
1062 /* n5, n6 */
1063 if (!BN_mod_sub_quick(n5, n1, n3, p)) goto end;
1064 if (!BN_mod_sub_quick(n6, n2, n4, p)) goto end;
1065 /* n5 = n1 - n3 */
1066 /* n6 = n2 - n4 */
1067
1068 if (BN_is_zero(n5))
1069 {
1070 if (BN_is_zero(n6))
1071 {
1072 /* a is the same point as b */
1073 BN_CTX_end(ctx);
1074 ret = EC_POINT_dbl(group, r, a, ctx);
1075 ctx = NULL;
1076 goto end;
1077 }
1078 else
1079 {
1080 /* a is the inverse of b */
1081 if (!BN_zero(&r->Z)) goto end;
1082 r->Z_is_one = 0;
1083 ret = 1;
1084 goto end;
1085 }
1086 }
1087
1088 /* 'n7', 'n8' */
1089 if (!BN_mod_add_quick(n1, n1, n3, p)) goto end;
1090 if (!BN_mod_add_quick(n2, n2, n4, p)) goto end;
1091 /* 'n7' = n1 + n3 */
1092 /* 'n8' = n2 + n4 */
1093
1094 /* Z_r */
1095 if (a->Z_is_one && b->Z_is_one)
1096 {
1097 if (!BN_copy(&r->Z, n5)) goto end;
1098 }
1099 else
1100 {
1101 if (a->Z_is_one)
1102 { if (!BN_copy(n0, &b->Z)) goto end; }
1103 else if (b->Z_is_one)
1104 { if (!BN_copy(n0, &a->Z)) goto end; }
1105 else
1106 { if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) goto end; }
1107 if (!field_mul(group, &r->Z, n0, n5, ctx)) goto end;
1108 }
1109 r->Z_is_one = 0;
1110 /* Z_r = Z_a * Z_b * n5 */
1111
1112 /* X_r */
1113 if (!field_sqr(group, n0, n6, ctx)) goto end;
1114 if (!field_sqr(group, n4, n5, ctx)) goto end;
1115 if (!field_mul(group, n3, n1, n4, ctx)) goto end;
1116 if (!BN_mod_sub_quick(&r->X, n0, n3, p)) goto end;
1117 /* X_r = n6^2 - n5^2 * 'n7' */
1118
1119 /* 'n9' */
1120 if (!BN_mod_lshift1_quick(n0, &r->X, p)) goto end;
1121 if (!BN_mod_sub_quick(n0, n3, n0, p)) goto end;
1122 /* n9 = n5^2 * 'n7' - 2 * X_r */
1123
1124 /* Y_r */
1125 if (!field_mul(group, n0, n0, n6, ctx)) goto end;
1126 if (!field_mul(group, n5, n4, n5, ctx)) goto end; /* now n5 is n5^3 */
1127 if (!field_mul(group, n1, n2, n5, ctx)) goto end;
1128 if (!BN_mod_sub_quick(n0, n0, n1, p)) goto end;
1129 if (BN_is_odd(n0))
1130 if (!BN_add(n0, n0, p)) goto end;
1131 /* now 0 <= n0 < 2*p, and n0 is even */
1132 if (!BN_rshift1(&r->Y, n0)) goto end;
1133 /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
1134
1135 ret = 1;
1136
1137 end:
1138 if (ctx) /* otherwise we already called BN_CTX_end */
1139 BN_CTX_end(ctx);
1140 if (new_ctx != NULL)
1141 BN_CTX_free(new_ctx);
1142 return ret;
1143 }
1144
1145
1146 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
1147 {
1148 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1149 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1150 const BIGNUM *p;
1151 BN_CTX *new_ctx = NULL;
1152 BIGNUM *n0, *n1, *n2, *n3;
1153 int ret = 0;
1154
1155 if (EC_POINT_is_at_infinity(group, a))
1156 {
1157 if (!BN_zero(&r->Z)) return 0;
1158 r->Z_is_one = 0;
1159 return 1;
1160 }
1161
1162 field_mul = group->meth->field_mul;
1163 field_sqr = group->meth->field_sqr;
1164 p = &group->field;
1165
1166 if (ctx == NULL)
1167 {
1168 ctx = new_ctx = BN_CTX_new();
1169 if (ctx == NULL)
1170 return 0;
1171 }
1172
1173 BN_CTX_start(ctx);
1174 n0 = BN_CTX_get(ctx);
1175 n1 = BN_CTX_get(ctx);
1176 n2 = BN_CTX_get(ctx);
1177 n3 = BN_CTX_get(ctx);
1178 if (n3 == NULL) goto err;
1179
1180 /* Note that in this function we must not read components of 'a'
1181 * once we have written the corresponding components of 'r'.
1182 * ('r' might the same as 'a'.)
1183 */
1184
1185 /* n1 */
1186 if (a->Z_is_one)
1187 {
1188 if (!field_sqr(group, n0, &a->X, ctx)) goto err;
1189 if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
1190 if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
1191 if (!BN_mod_add_quick(n1, n0, &group->a, p)) goto err;
1192 /* n1 = 3 * X_a^2 + a_curve */
1193 }
1194 else if (group->a_is_minus3)
1195 {
1196 if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
1197 if (!BN_mod_add_quick(n0, &a->X, n1, p)) goto err;
1198 if (!BN_mod_sub_quick(n2, &a->X, n1, p)) goto err;
1199 if (!field_mul(group, n1, n0, n2, ctx)) goto err;
1200 if (!BN_mod_lshift1_quick(n0, n1, p)) goto err;
1201 if (!BN_mod_add_quick(n1, n0, n1, p)) goto err;
1202 /* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
1203 * = 3 * X_a^2 - 3 * Z_a^4 */
1204 }
1205 else
1206 {
1207 if (!field_sqr(group, n0, &a->X, ctx)) goto err;
1208 if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
1209 if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
1210 if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
1211 if (!field_sqr(group, n1, n1, ctx)) goto err;
1212 if (!field_mul(group, n1, n1, &group->a, ctx)) goto err;
1213 if (!BN_mod_add_quick(n1, n1, n0, p)) goto err;
1214 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
1215 }
1216
1217 /* Z_r */
1218 if (a->Z_is_one)
1219 {
1220 if (!BN_copy(n0, &a->Y)) goto err;
1221 }
1222 else
1223 {
1224 if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) goto err;
1225 }
1226 if (!BN_mod_lshift1_quick(&r->Z, n0, p)) goto err;
1227 r->Z_is_one = 0;
1228 /* Z_r = 2 * Y_a * Z_a */
1229
1230 /* n2 */
1231 if (!field_sqr(group, n3, &a->Y, ctx)) goto err;
1232 if (!field_mul(group, n2, &a->X, n3, ctx)) goto err;
1233 if (!BN_mod_lshift_quick(n2, n2, 2, p)) goto err;
1234 /* n2 = 4 * X_a * Y_a^2 */
1235
1236 /* X_r */
1237 if (!BN_mod_lshift1_quick(n0, n2, p)) goto err;
1238 if (!field_sqr(group, &r->X, n1, ctx)) goto err;
1239 if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) goto err;
1240 /* X_r = n1^2 - 2 * n2 */
1241
1242 /* n3 */
1243 if (!field_sqr(group, n0, n3, ctx)) goto err;
1244 if (!BN_mod_lshift_quick(n3, n0, 3, p)) goto err;
1245 /* n3 = 8 * Y_a^4 */
1246
1247 /* Y_r */
1248 if (!BN_mod_sub_quick(n0, n2, &r->X, p)) goto err;
1249 if (!field_mul(group, n0, n1, n0, ctx)) goto err;
1250 if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) goto err;
1251 /* Y_r = n1 * (n2 - X_r) - n3 */
1252
1253 ret = 1;
1254
1255 err:
1256 BN_CTX_end(ctx);
1257 if (new_ctx != NULL)
1258 BN_CTX_free(new_ctx);
1259 return ret;
1260 }
1261
1262
1263 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1264 {
1265 if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y))
1266 /* point is its own inverse */
1267 return 1;
1268
1269 return BN_usub(&point->Y, &group->field, &point->Y);
1270 }
1271
1272
1273 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
1274 {
1275 return BN_is_zero(&point->Z);
1276 }
1277
1278
1279 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
1280 {
1281 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1282 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1283 const BIGNUM *p;
1284 BN_CTX *new_ctx = NULL;
1285 BIGNUM *rh, *tmp1, *tmp2, *Z4, *Z6;
1286 int ret = -1;
1287
1288 if (EC_POINT_is_at_infinity(group, point))
1289 return 1;
1290
1291 field_mul = group->meth->field_mul;
1292 field_sqr = group->meth->field_sqr;
1293 p = &group->field;
1294
1295 if (ctx == NULL)
1296 {
1297 ctx = new_ctx = BN_CTX_new();
1298 if (ctx == NULL)
1299 return -1;
1300 }
1301
1302 BN_CTX_start(ctx);
1303 rh = BN_CTX_get(ctx);
1304 tmp1 = BN_CTX_get(ctx);
1305 tmp2 = BN_CTX_get(ctx);
1306 Z4 = BN_CTX_get(ctx);
1307 Z6 = BN_CTX_get(ctx);
1308 if (Z6 == NULL) goto err;
1309
1310 /* We have a curve defined by a Weierstrass equation
1311 * y^2 = x^3 + a*x + b.
1312 * The point to consider is given in Jacobian projective coordinates
1313 * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3).
1314 * Substituting this and multiplying by Z^6 transforms the above equation into
1315 * Y^2 = X^3 + a*X*Z^4 + b*Z^6.
1316 * To test this, we add up the right-hand side in 'rh'.
1317 */
1318
1319 /* rh := X^3 */
1320 if (!field_sqr(group, rh, &point->X, ctx)) goto err;
1321 if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1322
1323 if (!point->Z_is_one)
1324 {
1325 if (!field_sqr(group, tmp1, &point->Z, ctx)) goto err;
1326 if (!field_sqr(group, Z4, tmp1, ctx)) goto err;
1327 if (!field_mul(group, Z6, Z4, tmp1, ctx)) goto err;
1328
1329 /* rh := rh + a*X*Z^4 */
1330 if (!field_mul(group, tmp1, &point->X, Z4, ctx)) goto err;
1331 if (group->a_is_minus3)
1332 {
1333 if (!BN_mod_lshift1_quick(tmp2, tmp1, p)) goto err;
1334 if (!BN_mod_add_quick(tmp2, tmp2, tmp1, p)) goto err;
1335 if (!BN_mod_sub_quick(rh, rh, tmp2, p)) goto err;
1336 }
1337 else
1338 {
1339 if (!field_mul(group, tmp2, tmp1, &group->a, ctx)) goto err;
1340 if (!BN_mod_add_quick(rh, rh, tmp2, p)) goto err;
1341 }
1342
1343 /* rh := rh + b*Z^6 */
1344 if (!field_mul(group, tmp1, &group->b, Z6, ctx)) goto err;
1345 if (!BN_mod_add_quick(rh, rh, tmp1, p)) goto err;
1346 }
1347 else
1348 {
1349 /* point->Z_is_one */
1350
1351 /* rh := rh + a*X */
1352 if (group->a_is_minus3)
1353 {
1354 if (!BN_mod_lshift1_quick(tmp2, &point->X, p)) goto err;
1355 if (!BN_mod_add_quick(tmp2, tmp2, &point->X, p)) goto err;
1356 if (!BN_mod_sub_quick(rh, rh, tmp2, p)) goto err;
1357 }
1358 else
1359 {
1360 if (!field_mul(group, tmp2, &point->X, &group->a, ctx)) goto err;
1361 if (!BN_mod_add_quick(rh, rh, tmp2, p)) goto err;
1362 }
1363
1364 /* rh := rh + b */
1365 if (!BN_mod_add_quick(rh, rh, &group->b, p)) goto err;
1366 }
1367
1368 /* 'lh' := Y^2 */
1369 if (!field_sqr(group, tmp1, &point->Y, ctx)) goto err;
1370
1371 ret = (0 == BN_cmp(tmp1, rh));
1372
1373 err:
1374 BN_CTX_end(ctx);
1375 if (new_ctx != NULL)
1376 BN_CTX_free(new_ctx);
1377 return ret;
1378 }
1379
1380
1381 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
1382 {
1383 /* return values:
1384 * -1 error
1385 * 0 equal (in affine coordinates)
1386 * 1 not equal
1387 */
1388
1389 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1390 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1391 BN_CTX *new_ctx = NULL;
1392 BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
1393 const BIGNUM *tmp1_, *tmp2_;
1394 int ret = -1;
1395
1396 if (EC_POINT_is_at_infinity(group, a))
1397 {
1398 return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
1399 }
1400
1401 if (a->Z_is_one && b->Z_is_one)
1402 {
1403 return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
1404 }
1405
1406 field_mul = group->meth->field_mul;
1407 field_sqr = group->meth->field_sqr;
1408
1409 if (ctx == NULL)
1410 {
1411 ctx = new_ctx = BN_CTX_new();
1412 if (ctx == NULL)
1413 return -1;
1414 }
1415
1416 BN_CTX_start(ctx);
1417 tmp1 = BN_CTX_get(ctx);
1418 tmp2 = BN_CTX_get(ctx);
1419 Za23 = BN_CTX_get(ctx);
1420 Zb23 = BN_CTX_get(ctx);
1421 if (Zb23 == NULL) goto end;
1422
1423 /* We have to decide whether
1424 * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
1425 * or equivalently, whether
1426 * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
1427 */
1428
1429 if (!b->Z_is_one)
1430 {
1431 if (!field_sqr(group, Zb23, &b->Z, ctx)) goto end;
1432 if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) goto end;
1433 tmp1_ = tmp1;
1434 }
1435 else
1436 tmp1_ = &a->X;
1437 if (!a->Z_is_one)
1438 {
1439 if (!field_sqr(group, Za23, &a->Z, ctx)) goto end;
1440 if (!field_mul(group, tmp2, &b->X, Za23, ctx)) goto end;
1441 tmp2_ = tmp2;
1442 }
1443 else
1444 tmp2_ = &b->X;
1445
1446 /* compare X_a*Z_b^2 with X_b*Z_a^2 */
1447 if (BN_cmp(tmp1_, tmp2_) != 0)
1448 {
1449 ret = 1; /* points differ */
1450 goto end;
1451 }
1452
1453
1454 if (!b->Z_is_one)
1455 {
1456 if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) goto end;
1457 if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) goto end;
1458 /* tmp1_ = tmp1 */
1459 }
1460 else
1461 tmp1_ = &a->Y;
1462 if (!a->Z_is_one)
1463 {
1464 if (!field_mul(group, Za23, Za23, &a->Z, ctx)) goto end;
1465 if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) goto end;
1466 /* tmp2_ = tmp2 */
1467 }
1468 else
1469 tmp2_ = &b->Y;
1470
1471 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */
1472 if (BN_cmp(tmp1_, tmp2_) != 0)
1473 {
1474 ret = 1; /* points differ */
1475 goto end;
1476 }
1477
1478 /* points are equal */
1479 ret = 0;
1480
1481 end:
1482 BN_CTX_end(ctx);
1483 if (new_ctx != NULL)
1484 BN_CTX_free(new_ctx);
1485 return ret;
1486 }
1487
1488
1489 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1490 {
1491 BN_CTX *new_ctx = NULL;
1492 BIGNUM *x, *y;
1493 int ret = 0;
1494
1495 if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
1496 return 1;
1497
1498 if (ctx == NULL)
1499 {
1500 ctx = new_ctx = BN_CTX_new();
1501 if (ctx == NULL)
1502 return 0;
1503 }
1504
1505 BN_CTX_start(ctx);
1506 x = BN_CTX_get(ctx);
1507 y = BN_CTX_get(ctx);
1508 if (y == NULL) goto err;
1509
1510 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
1511 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
1512 if (!point->Z_is_one)
1513 {
1514 ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
1515 goto err;
1516 }
1517
1518 ret = 1;
1519
1520 err:
1521 BN_CTX_end(ctx);
1522 if (new_ctx != NULL)
1523 BN_CTX_free(new_ctx);
1524 return ret;
1525 }
1526
1527
1528 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
1529 {
1530 BN_CTX *new_ctx = NULL;
1531 BIGNUM *tmp0, *tmp1;
1532 size_t pow2 = 0;
1533 BIGNUM **heap = NULL;
1534 size_t i;
1535 int ret = 0;
1536
1537 if (num == 0)
1538 return 1;
1539
1540 if (ctx == NULL)
1541 {
1542 ctx = new_ctx = BN_CTX_new();
1543 if (ctx == NULL)
1544 return 0;
1545 }
1546
1547 BN_CTX_start(ctx);
1548 tmp0 = BN_CTX_get(ctx);
1549 tmp1 = BN_CTX_get(ctx);
1550 if (tmp0 == NULL || tmp1 == NULL) goto err;
1551
1552 /* Before converting the individual points, compute inverses of all Z values.
1553 * Modular inversion is rather slow, but luckily we can do with a single
1554 * explicit inversion, plus about 3 multiplications per input value.
1555 */
1556
1557 pow2 = 1;
1558 while (num > pow2)
1559 pow2 <<= 1;
1560 /* Now pow2 is the smallest power of 2 satifsying pow2 >= num.
1561 * We need twice that. */
1562 pow2 <<= 1;
1563
1564 heap = OPENSSL_malloc(pow2 * sizeof heap[0]);
1565 if (heap == NULL) goto err;
1566
1567 /* The array is used as a binary tree, exactly as in heapsort:
1568 *
1569 * heap[1]
1570 * heap[2] heap[3]
1571 * heap[4] heap[5] heap[6] heap[7]
1572 * heap[8]heap[9] heap[10]heap[11] heap[12]heap[13] heap[14] heap[15]
1573 *
1574 * We put the Z's in the last line;
1575 * then we set each other node to the product of its two child-nodes (where
1576 * empty or 0 entries are treated as ones);
1577 * then we invert heap[1];
1578 * then we invert each other node by replacing it by the product of its
1579 * parent (after inversion) and its sibling (before inversion).
1580 */
1581 heap[0] = NULL;
1582 for (i = pow2/2 - 1; i > 0; i--)
1583 heap[i] = NULL;
1584 for (i = 0; i < num; i++)
1585 heap[pow2/2 + i] = &points[i]->Z;
1586 for (i = pow2/2 + num; i < pow2; i++)
1587 heap[i] = NULL;
1588
1589 /* set each node to the product of its children */
1590 for (i = pow2/2 - 1; i > 0; i--)
1591 {
1592 heap[i] = BN_new();
1593 if (heap[i] == NULL) goto err;
1594
1595 if (heap[2*i] != NULL)
1596 {
1597 if ((heap[2*i + 1] == NULL) || BN_is_zero(heap[2*i + 1]))
1598 {
1599 if (!BN_copy(heap[i], heap[2*i])) goto err;
1600 }
1601 else
1602 {
1603 if (BN_is_zero(heap[2*i]))
1604 {
1605 if (!BN_copy(heap[i], heap[2*i + 1])) goto err;
1606 }
1607 else
1608 {
1609 if (!group->meth->field_mul(group, heap[i],
1610 heap[2*i], heap[2*i + 1], ctx)) goto err;
1611 }
1612 }
1613 }
1614 }
1615
1616 /* invert heap[1] */
1617 if (!BN_is_zero(heap[1]))
1618 {
1619 if (!BN_mod_inverse(heap[1], heap[1], &group->field, ctx))
1620 {
1621 ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
1622 goto err;
1623 }
1624 }
1625 if (group->meth->field_encode != 0)
1626 {
1627 /* in the Montgomery case, we just turned R*H (representing H)
1628 * into 1/(R*H), but we need R*(1/H) (representing 1/H);
1629 * i.e. we have need to multiply by the Montgomery factor twice */
1630 if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
1631 if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
1632 }
1633
1634 /* set other heap[i]'s to their inverses */
1635 for (i = 2; i < pow2/2 + num; i += 2)
1636 {
1637 /* i is even */
1638 if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1]))
1639 {
1640 if (!group->meth->field_mul(group, tmp0, heap[i/2], heap[i + 1], ctx)) goto err;
1641 if (!group->meth->field_mul(group, tmp1, heap[i/2], heap[i], ctx)) goto err;
1642 if (!BN_copy(heap[i], tmp0)) goto err;
1643 if (!BN_copy(heap[i + 1], tmp1)) goto err;
1644 }
1645 else
1646 {
1647 if (!BN_copy(heap[i], heap[i/2])) goto err;
1648 }
1649 }
1650
1651 /* we have replaced all non-zero Z's by their inverses, now fix up all the points */
1652 for (i = 0; i < num; i++)
1653 {
1654 EC_POINT *p = points[i];
1655
1656 if (!BN_is_zero(&p->Z))
1657 {
1658 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */
1659
1660 if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx)) goto err;
1661 if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx)) goto err;
1662
1663 if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx)) goto err;
1664 if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx)) goto err;
1665
1666 if (group->meth->field_set_to_one != 0)
1667 {
1668 if (!group->meth->field_set_to_one(group, &p->Z, ctx)) goto err;
1669 }
1670 else
1671 {
1672 if (!BN_one(&p->Z)) goto err;
1673 }
1674 p->Z_is_one = 1;
1675 }
1676 }
1677
1678 ret = 1;
1679
1680 err:
1681 BN_CTX_end(ctx);
1682 if (new_ctx != NULL)
1683 BN_CTX_free(new_ctx);
1684 if (heap != NULL)
1685 {
1686 /* heap[pow2/2] .. heap[pow2-1] have not been allocated locally! */
1687 for (i = pow2/2 - 1; i > 0; i--)
1688 {
1689 if (heap[i] != NULL)
1690 BN_clear_free(heap[i]);
1691 }
1692 OPENSSL_free(heap);
1693 }
1694 return ret;
1695 }
1696
1697
1698 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
1699 {
1700 return BN_mod_mul(r, a, b, &group->field, ctx);
1701 }
1702
1703
1704 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
1705 {
1706 return BN_mod_sqr(r, a, &group->field, ctx);
1707 }
A mirror of the official openssl repository