1 /* crypto/ec/ecp_smpl.c */
3 * Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
4 * for the OpenSSL project. Includes code written by Bodo Moeller for the
7 /* ====================================================================
8 * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved.
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in
19 * the documentation and/or other materials provided with the
22 * 3. All advertising materials mentioning features or use of this
23 * software must display the following acknowledgment:
24 * "This product includes software developed by the OpenSSL Project
25 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
27 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
28 * endorse or promote products derived from this software without
29 * prior written permission. For written permission, please contact
30 * openssl-core@openssl.org.
32 * 5. Products derived from this software may not be called "OpenSSL"
33 * nor may "OpenSSL" appear in their names without prior written
34 * permission of the OpenSSL Project.
36 * 6. Redistributions of any form whatsoever must retain the following
38 * "This product includes software developed by the OpenSSL Project
39 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
41 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
42 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
44 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
45 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
46 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
47 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
48 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
49 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
50 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
51 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
52 * OF THE POSSIBILITY OF SUCH DAMAGE.
53 * ====================================================================
55 * This product includes cryptographic software written by Eric Young
56 * (eay@cryptsoft.com). This product includes software written by Tim
57 * Hudson (tjh@cryptsoft.com).
60 /* ====================================================================
61 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
62 * Portions of this software developed by SUN MICROSYSTEMS, INC.,
63 * and contributed to the OpenSSL project.
66 #include <openssl/err.h>
67 #include <openssl/symhacks.h>
71 const EC_METHOD
*EC_GFp_simple_method(void)
73 static const EC_METHOD ret
= {
75 NID_X9_62_prime_field
,
76 ec_GFp_simple_group_init
,
77 ec_GFp_simple_group_finish
,
78 ec_GFp_simple_group_clear_finish
,
79 ec_GFp_simple_group_copy
,
80 ec_GFp_simple_group_set_curve
,
81 ec_GFp_simple_group_get_curve
,
82 ec_GFp_simple_group_get_degree
,
83 ec_GFp_simple_group_check_discriminant
,
84 ec_GFp_simple_point_init
,
85 ec_GFp_simple_point_finish
,
86 ec_GFp_simple_point_clear_finish
,
87 ec_GFp_simple_point_copy
,
88 ec_GFp_simple_point_set_to_infinity
,
89 ec_GFp_simple_set_Jprojective_coordinates_GFp
,
90 ec_GFp_simple_get_Jprojective_coordinates_GFp
,
91 ec_GFp_simple_point_set_affine_coordinates
,
92 ec_GFp_simple_point_get_affine_coordinates
,
97 ec_GFp_simple_is_at_infinity
,
98 ec_GFp_simple_is_on_curve
,
100 ec_GFp_simple_make_affine
,
101 ec_GFp_simple_points_make_affine
,
103 0 /* precompute_mult */ ,
104 0 /* have_precompute_mult */ ,
105 ec_GFp_simple_field_mul
,
106 ec_GFp_simple_field_sqr
,
108 0 /* field_encode */ ,
109 0 /* field_decode */ ,
110 0 /* field_set_to_one */
117 * Most method functions in this file are designed to work with
118 * non-trivial representations of field elements if necessary
119 * (see ecp_mont.c): while standard modular addition and subtraction
120 * are used, the field_mul and field_sqr methods will be used for
121 * multiplication, and field_encode and field_decode (if defined)
122 * will be used for converting between representations.
124 * Functions ec_GFp_simple_points_make_affine() and
125 * ec_GFp_simple_point_get_affine_coordinates() specifically assume
126 * that if a non-trivial representation is used, it is a Montgomery
127 * representation (i.e. 'encoding' means multiplying by some factor R).
130 int ec_GFp_simple_group_init(EC_GROUP
*group
)
132 group
->field
= BN_new();
135 if (!group
->field
|| !group
->a
|| !group
->b
) {
136 BN_free(group
->field
);
141 group
->a_is_minus3
= 0;
145 void ec_GFp_simple_group_finish(EC_GROUP
*group
)
147 BN_free(group
->field
);
152 void ec_GFp_simple_group_clear_finish(EC_GROUP
*group
)
154 BN_clear_free(group
->field
);
155 BN_clear_free(group
->a
);
156 BN_clear_free(group
->b
);
159 int ec_GFp_simple_group_copy(EC_GROUP
*dest
, const EC_GROUP
*src
)
161 if (!BN_copy(dest
->field
, src
->field
))
163 if (!BN_copy(dest
->a
, src
->a
))
165 if (!BN_copy(dest
->b
, src
->b
))
168 dest
->a_is_minus3
= src
->a_is_minus3
;
173 int ec_GFp_simple_group_set_curve(EC_GROUP
*group
,
174 const BIGNUM
*p
, const BIGNUM
*a
,
175 const BIGNUM
*b
, BN_CTX
*ctx
)
178 BN_CTX
*new_ctx
= NULL
;
181 /* p must be a prime > 3 */
182 if (BN_num_bits(p
) <= 2 || !BN_is_odd(p
)) {
183 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE
, EC_R_INVALID_FIELD
);
188 ctx
= new_ctx
= BN_CTX_new();
194 tmp_a
= BN_CTX_get(ctx
);
199 if (!BN_copy(group
->field
, p
))
201 BN_set_negative(group
->field
, 0);
204 if (!BN_nnmod(tmp_a
, a
, p
, ctx
))
206 if (group
->meth
->field_encode
) {
207 if (!group
->meth
->field_encode(group
, group
->a
, tmp_a
, ctx
))
209 } else if (!BN_copy(group
->a
, tmp_a
))
213 if (!BN_nnmod(group
->b
, b
, p
, ctx
))
215 if (group
->meth
->field_encode
)
216 if (!group
->meth
->field_encode(group
, group
->b
, group
->b
, ctx
))
219 /* group->a_is_minus3 */
220 if (!BN_add_word(tmp_a
, 3))
222 group
->a_is_minus3
= (0 == BN_cmp(tmp_a
, group
->field
));
229 BN_CTX_free(new_ctx
);
233 int ec_GFp_simple_group_get_curve(const EC_GROUP
*group
, BIGNUM
*p
, BIGNUM
*a
,
234 BIGNUM
*b
, BN_CTX
*ctx
)
237 BN_CTX
*new_ctx
= NULL
;
240 if (!BN_copy(p
, group
->field
))
244 if (a
!= NULL
|| b
!= NULL
) {
245 if (group
->meth
->field_decode
) {
247 ctx
= new_ctx
= BN_CTX_new();
252 if (!group
->meth
->field_decode(group
, a
, group
->a
, ctx
))
256 if (!group
->meth
->field_decode(group
, b
, group
->b
, ctx
))
261 if (!BN_copy(a
, group
->a
))
265 if (!BN_copy(b
, group
->b
))
275 BN_CTX_free(new_ctx
);
279 int ec_GFp_simple_group_get_degree(const EC_GROUP
*group
)
281 return BN_num_bits(group
->field
);
284 int ec_GFp_simple_group_check_discriminant(const EC_GROUP
*group
, BN_CTX
*ctx
)
287 BIGNUM
*a
, *b
, *order
, *tmp_1
, *tmp_2
;
288 const BIGNUM
*p
= group
->field
;
289 BN_CTX
*new_ctx
= NULL
;
292 ctx
= new_ctx
= BN_CTX_new();
294 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT
,
295 ERR_R_MALLOC_FAILURE
);
302 tmp_1
= BN_CTX_get(ctx
);
303 tmp_2
= BN_CTX_get(ctx
);
304 order
= BN_CTX_get(ctx
);
308 if (group
->meth
->field_decode
) {
309 if (!group
->meth
->field_decode(group
, a
, group
->a
, ctx
))
311 if (!group
->meth
->field_decode(group
, b
, group
->b
, ctx
))
314 if (!BN_copy(a
, group
->a
))
316 if (!BN_copy(b
, group
->b
))
321 * check the discriminant:
322 * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p)
328 } else if (!BN_is_zero(b
)) {
329 if (!BN_mod_sqr(tmp_1
, a
, p
, ctx
))
331 if (!BN_mod_mul(tmp_2
, tmp_1
, a
, p
, ctx
))
333 if (!BN_lshift(tmp_1
, tmp_2
, 2))
337 if (!BN_mod_sqr(tmp_2
, b
, p
, ctx
))
339 if (!BN_mul_word(tmp_2
, 27))
343 if (!BN_mod_add(a
, tmp_1
, tmp_2
, p
, ctx
))
354 BN_CTX_free(new_ctx
);
358 int ec_GFp_simple_point_init(EC_POINT
*point
)
365 if (!point
->X
|| !point
->Y
|| !point
->Z
) {
377 void ec_GFp_simple_point_finish(EC_POINT
*point
)
384 void ec_GFp_simple_point_clear_finish(EC_POINT
*point
)
386 BN_clear_free(point
->X
);
387 BN_clear_free(point
->Y
);
388 BN_clear_free(point
->Z
);
392 int ec_GFp_simple_point_copy(EC_POINT
*dest
, const EC_POINT
*src
)
394 if (!BN_copy(dest
->X
, src
->X
))
396 if (!BN_copy(dest
->Y
, src
->Y
))
398 if (!BN_copy(dest
->Z
, src
->Z
))
400 dest
->Z_is_one
= src
->Z_is_one
;
405 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP
*group
,
413 int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP
*group
,
420 BN_CTX
*new_ctx
= NULL
;
424 ctx
= new_ctx
= BN_CTX_new();
430 if (!BN_nnmod(point
->X
, x
, group
->field
, ctx
))
432 if (group
->meth
->field_encode
) {
433 if (!group
->meth
->field_encode(group
, point
->X
, point
->X
, ctx
))
439 if (!BN_nnmod(point
->Y
, y
, group
->field
, ctx
))
441 if (group
->meth
->field_encode
) {
442 if (!group
->meth
->field_encode(group
, point
->Y
, point
->Y
, ctx
))
450 if (!BN_nnmod(point
->Z
, z
, group
->field
, ctx
))
452 Z_is_one
= BN_is_one(point
->Z
);
453 if (group
->meth
->field_encode
) {
454 if (Z_is_one
&& (group
->meth
->field_set_to_one
!= 0)) {
455 if (!group
->meth
->field_set_to_one(group
, point
->Z
, ctx
))
459 meth
->field_encode(group
, point
->Z
, point
->Z
, ctx
))
463 point
->Z_is_one
= Z_is_one
;
470 BN_CTX_free(new_ctx
);
474 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP
*group
,
475 const EC_POINT
*point
,
476 BIGNUM
*x
, BIGNUM
*y
,
477 BIGNUM
*z
, BN_CTX
*ctx
)
479 BN_CTX
*new_ctx
= NULL
;
482 if (group
->meth
->field_decode
!= 0) {
484 ctx
= new_ctx
= BN_CTX_new();
490 if (!group
->meth
->field_decode(group
, x
, point
->X
, ctx
))
494 if (!group
->meth
->field_decode(group
, y
, point
->Y
, ctx
))
498 if (!group
->meth
->field_decode(group
, z
, point
->Z
, ctx
))
503 if (!BN_copy(x
, point
->X
))
507 if (!BN_copy(y
, point
->Y
))
511 if (!BN_copy(z
, point
->Z
))
520 BN_CTX_free(new_ctx
);
524 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP
*group
,
527 const BIGNUM
*y
, BN_CTX
*ctx
)
529 if (x
== NULL
|| y
== NULL
) {
531 * unlike for projective coordinates, we do not tolerate this
533 ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES
,
534 ERR_R_PASSED_NULL_PARAMETER
);
538 return EC_POINT_set_Jprojective_coordinates_GFp(group
, point
, x
, y
,
539 BN_value_one(), ctx
);
542 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP
*group
,
543 const EC_POINT
*point
,
544 BIGNUM
*x
, BIGNUM
*y
,
547 BN_CTX
*new_ctx
= NULL
;
548 BIGNUM
*Z
, *Z_1
, *Z_2
, *Z_3
;
552 if (EC_POINT_is_at_infinity(group
, point
)) {
553 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES
,
554 EC_R_POINT_AT_INFINITY
);
559 ctx
= new_ctx
= BN_CTX_new();
566 Z_1
= BN_CTX_get(ctx
);
567 Z_2
= BN_CTX_get(ctx
);
568 Z_3
= BN_CTX_get(ctx
);
572 /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */
574 if (group
->meth
->field_decode
) {
575 if (!group
->meth
->field_decode(group
, Z
, point
->Z
, ctx
))
583 if (group
->meth
->field_decode
) {
585 if (!group
->meth
->field_decode(group
, x
, point
->X
, ctx
))
589 if (!group
->meth
->field_decode(group
, y
, point
->Y
, ctx
))
594 if (!BN_copy(x
, point
->X
))
598 if (!BN_copy(y
, point
->Y
))
603 if (!BN_mod_inverse(Z_1
, Z_
, group
->field
, ctx
)) {
604 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES
,
609 if (group
->meth
->field_encode
== 0) {
610 /* field_sqr works on standard representation */
611 if (!group
->meth
->field_sqr(group
, Z_2
, Z_1
, ctx
))
614 if (!BN_mod_sqr(Z_2
, Z_1
, group
->field
, ctx
))
620 * in the Montgomery case, field_mul will cancel out Montgomery
623 if (!group
->meth
->field_mul(group
, x
, point
->X
, Z_2
, ctx
))
628 if (group
->meth
->field_encode
== 0) {
630 * field_mul works on standard representation
632 if (!group
->meth
->field_mul(group
, Z_3
, Z_2
, Z_1
, ctx
))
635 if (!BN_mod_mul(Z_3
, Z_2
, Z_1
, group
->field
, ctx
))
640 * in the Montgomery case, field_mul will cancel out Montgomery
643 if (!group
->meth
->field_mul(group
, y
, point
->Y
, Z_3
, ctx
))
653 BN_CTX_free(new_ctx
);
657 int ec_GFp_simple_add(const EC_GROUP
*group
, EC_POINT
*r
, const EC_POINT
*a
,
658 const EC_POINT
*b
, BN_CTX
*ctx
)
660 int (*field_mul
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*,
661 const BIGNUM
*, BN_CTX
*);
662 int (*field_sqr
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*, BN_CTX
*);
664 BN_CTX
*new_ctx
= NULL
;
665 BIGNUM
*n0
, *n1
, *n2
, *n3
, *n4
, *n5
, *n6
;
669 return EC_POINT_dbl(group
, r
, a
, ctx
);
670 if (EC_POINT_is_at_infinity(group
, a
))
671 return EC_POINT_copy(r
, b
);
672 if (EC_POINT_is_at_infinity(group
, b
))
673 return EC_POINT_copy(r
, a
);
675 field_mul
= group
->meth
->field_mul
;
676 field_sqr
= group
->meth
->field_sqr
;
680 ctx
= new_ctx
= BN_CTX_new();
686 n0
= BN_CTX_get(ctx
);
687 n1
= BN_CTX_get(ctx
);
688 n2
= BN_CTX_get(ctx
);
689 n3
= BN_CTX_get(ctx
);
690 n4
= BN_CTX_get(ctx
);
691 n5
= BN_CTX_get(ctx
);
692 n6
= BN_CTX_get(ctx
);
697 * Note that in this function we must not read components of 'a' or 'b'
698 * once we have written the corresponding components of 'r'. ('r' might
699 * be one of 'a' or 'b'.)
704 if (!BN_copy(n1
, a
->X
))
706 if (!BN_copy(n2
, a
->Y
))
711 if (!field_sqr(group
, n0
, b
->Z
, ctx
))
713 if (!field_mul(group
, n1
, a
->X
, n0
, ctx
))
715 /* n1 = X_a * Z_b^2 */
717 if (!field_mul(group
, n0
, n0
, b
->Z
, ctx
))
719 if (!field_mul(group
, n2
, a
->Y
, n0
, ctx
))
721 /* n2 = Y_a * Z_b^3 */
726 if (!BN_copy(n3
, b
->X
))
728 if (!BN_copy(n4
, b
->Y
))
733 if (!field_sqr(group
, n0
, a
->Z
, ctx
))
735 if (!field_mul(group
, n3
, b
->X
, n0
, ctx
))
737 /* n3 = X_b * Z_a^2 */
739 if (!field_mul(group
, n0
, n0
, a
->Z
, ctx
))
741 if (!field_mul(group
, n4
, b
->Y
, n0
, ctx
))
743 /* n4 = Y_b * Z_a^3 */
747 if (!BN_mod_sub_quick(n5
, n1
, n3
, p
))
749 if (!BN_mod_sub_quick(n6
, n2
, n4
, p
))
754 if (BN_is_zero(n5
)) {
755 if (BN_is_zero(n6
)) {
756 /* a is the same point as b */
758 ret
= EC_POINT_dbl(group
, r
, a
, ctx
);
762 /* a is the inverse of b */
771 if (!BN_mod_add_quick(n1
, n1
, n3
, p
))
773 if (!BN_mod_add_quick(n2
, n2
, n4
, p
))
779 if (a
->Z_is_one
&& b
->Z_is_one
) {
780 if (!BN_copy(r
->Z
, n5
))
784 if (!BN_copy(n0
, b
->Z
))
786 } else if (b
->Z_is_one
) {
787 if (!BN_copy(n0
, a
->Z
))
790 if (!field_mul(group
, n0
, a
->Z
, b
->Z
, ctx
))
793 if (!field_mul(group
, r
->Z
, n0
, n5
, ctx
))
797 /* Z_r = Z_a * Z_b * n5 */
800 if (!field_sqr(group
, n0
, n6
, ctx
))
802 if (!field_sqr(group
, n4
, n5
, ctx
))
804 if (!field_mul(group
, n3
, n1
, n4
, ctx
))
806 if (!BN_mod_sub_quick(r
->X
, n0
, n3
, p
))
808 /* X_r = n6^2 - n5^2 * 'n7' */
811 if (!BN_mod_lshift1_quick(n0
, r
->X
, p
))
813 if (!BN_mod_sub_quick(n0
, n3
, n0
, p
))
815 /* n9 = n5^2 * 'n7' - 2 * X_r */
818 if (!field_mul(group
, n0
, n0
, n6
, ctx
))
820 if (!field_mul(group
, n5
, n4
, n5
, ctx
))
821 goto end
; /* now n5 is n5^3 */
822 if (!field_mul(group
, n1
, n2
, n5
, ctx
))
824 if (!BN_mod_sub_quick(n0
, n0
, n1
, p
))
827 if (!BN_add(n0
, n0
, p
))
829 /* now 0 <= n0 < 2*p, and n0 is even */
830 if (!BN_rshift1(r
->Y
, n0
))
832 /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
837 if (ctx
) /* otherwise we already called BN_CTX_end */
840 BN_CTX_free(new_ctx
);
844 int ec_GFp_simple_dbl(const EC_GROUP
*group
, EC_POINT
*r
, const EC_POINT
*a
,
847 int (*field_mul
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*,
848 const BIGNUM
*, BN_CTX
*);
849 int (*field_sqr
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*, BN_CTX
*);
851 BN_CTX
*new_ctx
= NULL
;
852 BIGNUM
*n0
, *n1
, *n2
, *n3
;
855 if (EC_POINT_is_at_infinity(group
, a
)) {
861 field_mul
= group
->meth
->field_mul
;
862 field_sqr
= group
->meth
->field_sqr
;
866 ctx
= new_ctx
= BN_CTX_new();
872 n0
= BN_CTX_get(ctx
);
873 n1
= BN_CTX_get(ctx
);
874 n2
= BN_CTX_get(ctx
);
875 n3
= BN_CTX_get(ctx
);
880 * Note that in this function we must not read components of 'a' once we
881 * have written the corresponding components of 'r'. ('r' might the same
887 if (!field_sqr(group
, n0
, a
->X
, ctx
))
889 if (!BN_mod_lshift1_quick(n1
, n0
, p
))
891 if (!BN_mod_add_quick(n0
, n0
, n1
, p
))
893 if (!BN_mod_add_quick(n1
, n0
, group
->a
, p
))
895 /* n1 = 3 * X_a^2 + a_curve */
896 } else if (group
->a_is_minus3
) {
897 if (!field_sqr(group
, n1
, a
->Z
, ctx
))
899 if (!BN_mod_add_quick(n0
, a
->X
, n1
, p
))
901 if (!BN_mod_sub_quick(n2
, a
->X
, n1
, p
))
903 if (!field_mul(group
, n1
, n0
, n2
, ctx
))
905 if (!BN_mod_lshift1_quick(n0
, n1
, p
))
907 if (!BN_mod_add_quick(n1
, n0
, n1
, p
))
910 * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
911 * = 3 * X_a^2 - 3 * Z_a^4
914 if (!field_sqr(group
, n0
, a
->X
, ctx
))
916 if (!BN_mod_lshift1_quick(n1
, n0
, p
))
918 if (!BN_mod_add_quick(n0
, n0
, n1
, p
))
920 if (!field_sqr(group
, n1
, a
->Z
, ctx
))
922 if (!field_sqr(group
, n1
, n1
, ctx
))
924 if (!field_mul(group
, n1
, n1
, group
->a
, ctx
))
926 if (!BN_mod_add_quick(n1
, n1
, n0
, p
))
928 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
933 if (!BN_copy(n0
, a
->Y
))
936 if (!field_mul(group
, n0
, a
->Y
, a
->Z
, ctx
))
939 if (!BN_mod_lshift1_quick(r
->Z
, n0
, p
))
942 /* Z_r = 2 * Y_a * Z_a */
945 if (!field_sqr(group
, n3
, a
->Y
, ctx
))
947 if (!field_mul(group
, n2
, a
->X
, n3
, ctx
))
949 if (!BN_mod_lshift_quick(n2
, n2
, 2, p
))
951 /* n2 = 4 * X_a * Y_a^2 */
954 if (!BN_mod_lshift1_quick(n0
, n2
, p
))
956 if (!field_sqr(group
, r
->X
, n1
, ctx
))
958 if (!BN_mod_sub_quick(r
->X
, r
->X
, n0
, p
))
960 /* X_r = n1^2 - 2 * n2 */
963 if (!field_sqr(group
, n0
, n3
, ctx
))
965 if (!BN_mod_lshift_quick(n3
, n0
, 3, p
))
970 if (!BN_mod_sub_quick(n0
, n2
, r
->X
, p
))
972 if (!field_mul(group
, n0
, n1
, n0
, ctx
))
974 if (!BN_mod_sub_quick(r
->Y
, n0
, n3
, p
))
976 /* Y_r = n1 * (n2 - X_r) - n3 */
983 BN_CTX_free(new_ctx
);
987 int ec_GFp_simple_invert(const EC_GROUP
*group
, EC_POINT
*point
, BN_CTX
*ctx
)
989 if (EC_POINT_is_at_infinity(group
, point
) || BN_is_zero(point
->Y
))
990 /* point is its own inverse */
993 return BN_usub(point
->Y
, group
->field
, point
->Y
);
996 int ec_GFp_simple_is_at_infinity(const EC_GROUP
*group
, const EC_POINT
*point
)
998 return BN_is_zero(point
->Z
);
1001 int ec_GFp_simple_is_on_curve(const EC_GROUP
*group
, const EC_POINT
*point
,
1004 int (*field_mul
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*,
1005 const BIGNUM
*, BN_CTX
*);
1006 int (*field_sqr
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*, BN_CTX
*);
1008 BN_CTX
*new_ctx
= NULL
;
1009 BIGNUM
*rh
, *tmp
, *Z4
, *Z6
;
1012 if (EC_POINT_is_at_infinity(group
, point
))
1015 field_mul
= group
->meth
->field_mul
;
1016 field_sqr
= group
->meth
->field_sqr
;
1020 ctx
= new_ctx
= BN_CTX_new();
1026 rh
= BN_CTX_get(ctx
);
1027 tmp
= BN_CTX_get(ctx
);
1028 Z4
= BN_CTX_get(ctx
);
1029 Z6
= BN_CTX_get(ctx
);
1034 * We have a curve defined by a Weierstrass equation
1035 * y^2 = x^3 + a*x + b.
1036 * The point to consider is given in Jacobian projective coordinates
1037 * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3).
1038 * Substituting this and multiplying by Z^6 transforms the above equation into
1039 * Y^2 = X^3 + a*X*Z^4 + b*Z^6.
1040 * To test this, we add up the right-hand side in 'rh'.
1044 if (!field_sqr(group
, rh
, point
->X
, ctx
))
1047 if (!point
->Z_is_one
) {
1048 if (!field_sqr(group
, tmp
, point
->Z
, ctx
))
1050 if (!field_sqr(group
, Z4
, tmp
, ctx
))
1052 if (!field_mul(group
, Z6
, Z4
, tmp
, ctx
))
1055 /* rh := (rh + a*Z^4)*X */
1056 if (group
->a_is_minus3
) {
1057 if (!BN_mod_lshift1_quick(tmp
, Z4
, p
))
1059 if (!BN_mod_add_quick(tmp
, tmp
, Z4
, p
))
1061 if (!BN_mod_sub_quick(rh
, rh
, tmp
, p
))
1063 if (!field_mul(group
, rh
, rh
, point
->X
, ctx
))
1066 if (!field_mul(group
, tmp
, Z4
, group
->a
, ctx
))
1068 if (!BN_mod_add_quick(rh
, rh
, tmp
, p
))
1070 if (!field_mul(group
, rh
, rh
, point
->X
, ctx
))
1074 /* rh := rh + b*Z^6 */
1075 if (!field_mul(group
, tmp
, group
->b
, Z6
, ctx
))
1077 if (!BN_mod_add_quick(rh
, rh
, tmp
, p
))
1080 /* point->Z_is_one */
1082 /* rh := (rh + a)*X */
1083 if (!BN_mod_add_quick(rh
, rh
, group
->a
, p
))
1085 if (!field_mul(group
, rh
, rh
, point
->X
, ctx
))
1088 if (!BN_mod_add_quick(rh
, rh
, group
->b
, p
))
1093 if (!field_sqr(group
, tmp
, point
->Y
, ctx
))
1096 ret
= (0 == BN_ucmp(tmp
, rh
));
1100 if (new_ctx
!= NULL
)
1101 BN_CTX_free(new_ctx
);
1105 int ec_GFp_simple_cmp(const EC_GROUP
*group
, const EC_POINT
*a
,
1106 const EC_POINT
*b
, BN_CTX
*ctx
)
1111 * 0 equal (in affine coordinates)
1115 int (*field_mul
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*,
1116 const BIGNUM
*, BN_CTX
*);
1117 int (*field_sqr
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*, BN_CTX
*);
1118 BN_CTX
*new_ctx
= NULL
;
1119 BIGNUM
*tmp1
, *tmp2
, *Za23
, *Zb23
;
1120 const BIGNUM
*tmp1_
, *tmp2_
;
1123 if (EC_POINT_is_at_infinity(group
, a
)) {
1124 return EC_POINT_is_at_infinity(group
, b
) ? 0 : 1;
1127 if (EC_POINT_is_at_infinity(group
, b
))
1130 if (a
->Z_is_one
&& b
->Z_is_one
) {
1131 return ((BN_cmp(a
->X
, b
->X
) == 0) && BN_cmp(a
->Y
, b
->Y
) == 0) ? 0 : 1;
1134 field_mul
= group
->meth
->field_mul
;
1135 field_sqr
= group
->meth
->field_sqr
;
1138 ctx
= new_ctx
= BN_CTX_new();
1144 tmp1
= BN_CTX_get(ctx
);
1145 tmp2
= BN_CTX_get(ctx
);
1146 Za23
= BN_CTX_get(ctx
);
1147 Zb23
= BN_CTX_get(ctx
);
1152 * We have to decide whether
1153 * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
1154 * or equivalently, whether
1155 * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
1159 if (!field_sqr(group
, Zb23
, b
->Z
, ctx
))
1161 if (!field_mul(group
, tmp1
, a
->X
, Zb23
, ctx
))
1167 if (!field_sqr(group
, Za23
, a
->Z
, ctx
))
1169 if (!field_mul(group
, tmp2
, b
->X
, Za23
, ctx
))
1175 /* compare X_a*Z_b^2 with X_b*Z_a^2 */
1176 if (BN_cmp(tmp1_
, tmp2_
) != 0) {
1177 ret
= 1; /* points differ */
1182 if (!field_mul(group
, Zb23
, Zb23
, b
->Z
, ctx
))
1184 if (!field_mul(group
, tmp1
, a
->Y
, Zb23
, ctx
))
1190 if (!field_mul(group
, Za23
, Za23
, a
->Z
, ctx
))
1192 if (!field_mul(group
, tmp2
, b
->Y
, Za23
, ctx
))
1198 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */
1199 if (BN_cmp(tmp1_
, tmp2_
) != 0) {
1200 ret
= 1; /* points differ */
1204 /* points are equal */
1209 if (new_ctx
!= NULL
)
1210 BN_CTX_free(new_ctx
);
1214 int ec_GFp_simple_make_affine(const EC_GROUP
*group
, EC_POINT
*point
,
1217 BN_CTX
*new_ctx
= NULL
;
1221 if (point
->Z_is_one
|| EC_POINT_is_at_infinity(group
, point
))
1225 ctx
= new_ctx
= BN_CTX_new();
1231 x
= BN_CTX_get(ctx
);
1232 y
= BN_CTX_get(ctx
);
1236 if (!EC_POINT_get_affine_coordinates_GFp(group
, point
, x
, y
, ctx
))
1238 if (!EC_POINT_set_affine_coordinates_GFp(group
, point
, x
, y
, ctx
))
1240 if (!point
->Z_is_one
) {
1241 ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE
, ERR_R_INTERNAL_ERROR
);
1249 if (new_ctx
!= NULL
)
1250 BN_CTX_free(new_ctx
);
1254 int ec_GFp_simple_points_make_affine(const EC_GROUP
*group
, size_t num
,
1255 EC_POINT
*points
[], BN_CTX
*ctx
)
1257 BN_CTX
*new_ctx
= NULL
;
1258 BIGNUM
*tmp
, *tmp_Z
;
1259 BIGNUM
**prod_Z
= NULL
;
1267 ctx
= new_ctx
= BN_CTX_new();
1273 tmp
= BN_CTX_get(ctx
);
1274 tmp_Z
= BN_CTX_get(ctx
);
1275 if (tmp
== NULL
|| tmp_Z
== NULL
)
1278 prod_Z
= OPENSSL_malloc(num
* sizeof prod_Z
[0]);
1281 for (i
= 0; i
< num
; i
++) {
1282 prod_Z
[i
] = BN_new();
1283 if (prod_Z
[i
] == NULL
)
1288 * Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z,
1289 * skipping any zero-valued inputs (pretend that they're 1).
1292 if (!BN_is_zero(points
[0]->Z
)) {
1293 if (!BN_copy(prod_Z
[0], points
[0]->Z
))
1296 if (group
->meth
->field_set_to_one
!= 0) {
1297 if (!group
->meth
->field_set_to_one(group
, prod_Z
[0], ctx
))
1300 if (!BN_one(prod_Z
[0]))
1305 for (i
= 1; i
< num
; i
++) {
1306 if (!BN_is_zero(points
[i
]->Z
)) {
1308 meth
->field_mul(group
, prod_Z
[i
], prod_Z
[i
- 1], points
[i
]->Z
,
1312 if (!BN_copy(prod_Z
[i
], prod_Z
[i
- 1]))
1318 * Now use a single explicit inversion to replace every non-zero
1319 * points[i]->Z by its inverse.
1322 if (!BN_mod_inverse(tmp
, prod_Z
[num
- 1], group
->field
, ctx
)) {
1323 ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE
, ERR_R_BN_LIB
);
1326 if (group
->meth
->field_encode
!= 0) {
1328 * In the Montgomery case, we just turned R*H (representing H) into
1329 * 1/(R*H), but we need R*(1/H) (representing 1/H); i.e. we need to
1330 * multiply by the Montgomery factor twice.
1332 if (!group
->meth
->field_encode(group
, tmp
, tmp
, ctx
))
1334 if (!group
->meth
->field_encode(group
, tmp
, tmp
, ctx
))
1338 for (i
= num
- 1; i
> 0; --i
) {
1340 * Loop invariant: tmp is the product of the inverses of points[0]->Z
1341 * .. points[i]->Z (zero-valued inputs skipped).
1343 if (!BN_is_zero(points
[i
]->Z
)) {
1345 * Set tmp_Z to the inverse of points[i]->Z (as product of Z
1346 * inverses 0 .. i, Z values 0 .. i - 1).
1349 meth
->field_mul(group
, tmp_Z
, prod_Z
[i
- 1], tmp
, ctx
))
1352 * Update tmp to satisfy the loop invariant for i - 1.
1354 if (!group
->meth
->field_mul(group
, tmp
, tmp
, points
[i
]->Z
, ctx
))
1356 /* Replace points[i]->Z by its inverse. */
1357 if (!BN_copy(points
[i
]->Z
, tmp_Z
))
1362 if (!BN_is_zero(points
[0]->Z
)) {
1363 /* Replace points[0]->Z by its inverse. */
1364 if (!BN_copy(points
[0]->Z
, tmp
))
1368 /* Finally, fix up the X and Y coordinates for all points. */
1370 for (i
= 0; i
< num
; i
++) {
1371 EC_POINT
*p
= points
[i
];
1373 if (!BN_is_zero(p
->Z
)) {
1374 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */
1376 if (!group
->meth
->field_sqr(group
, tmp
, p
->Z
, ctx
))
1378 if (!group
->meth
->field_mul(group
, p
->X
, p
->X
, tmp
, ctx
))
1381 if (!group
->meth
->field_mul(group
, tmp
, tmp
, p
->Z
, ctx
))
1383 if (!group
->meth
->field_mul(group
, p
->Y
, p
->Y
, tmp
, ctx
))
1386 if (group
->meth
->field_set_to_one
!= 0) {
1387 if (!group
->meth
->field_set_to_one(group
, p
->Z
, ctx
))
1401 if (new_ctx
!= NULL
)
1402 BN_CTX_free(new_ctx
);
1403 if (prod_Z
!= NULL
) {
1404 for (i
= 0; i
< num
; i
++) {
1405 if (prod_Z
[i
] == NULL
)
1407 BN_clear_free(prod_Z
[i
]);
1409 OPENSSL_free(prod_Z
);
1414 int ec_GFp_simple_field_mul(const EC_GROUP
*group
, BIGNUM
*r
, const BIGNUM
*a
,
1415 const BIGNUM
*b
, BN_CTX
*ctx
)
1417 return BN_mod_mul(r
, a
, b
, group
->field
, ctx
);
1420 int ec_GFp_simple_field_sqr(const EC_GROUP
*group
, BIGNUM
*r
, const BIGNUM
*a
,
1423 return BN_mod_sqr(r
, a
, group
->field
, ctx
);