2 * Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
3 * for the OpenSSL project. Includes code written by Bodo Moeller for the
6 /* ====================================================================
7 * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
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
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/)"
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.
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.
35 * 6. Redistributions of any form whatsoever must retain the following
37 * "This product includes software developed by the OpenSSL Project
38 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
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 * ====================================================================
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).
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.
65 #include <openssl/err.h>
66 #include <openssl/symhacks.h>
70 const EC_METHOD *EC_GFp_simple_method(void)
72 static const EC_METHOD ret = {
74 NID_X9_62_prime_field,
75 ec_GFp_simple_group_init,
76 ec_GFp_simple_group_finish,
77 ec_GFp_simple_group_clear_finish,
78 ec_GFp_simple_group_copy,
79 ec_GFp_simple_group_set_curve,
80 ec_GFp_simple_group_get_curve,
81 ec_GFp_simple_group_get_degree,
82 ec_group_simple_order_bits,
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 */
111 ec_key_simple_priv2oct,
112 ec_key_simple_oct2priv,
114 ec_key_simple_generate_key,
115 ec_key_simple_check_key,
116 ec_key_simple_generate_public_key,
119 ecdh_simple_compute_key
126 * Most method functions in this file are designed to work with
127 * non-trivial representations of field elements if necessary
128 * (see ecp_mont.c): while standard modular addition and subtraction
129 * are used, the field_mul and field_sqr methods will be used for
130 * multiplication, and field_encode and field_decode (if defined)
131 * will be used for converting between representations.
133 * Functions ec_GFp_simple_points_make_affine() and
134 * ec_GFp_simple_point_get_affine_coordinates() specifically assume
135 * that if a non-trivial representation is used, it is a Montgomery
136 * representation (i.e. 'encoding' means multiplying by some factor R).
139 int ec_GFp_simple_group_init(EC_GROUP *group)
141 group->field = BN_new();
144 if (group->field == NULL || group->a == NULL || group->b == NULL) {
145 BN_free(group->field);
150 group->a_is_minus3 = 0;
154 void ec_GFp_simple_group_finish(EC_GROUP *group)
156 BN_free(group->field);
161 void ec_GFp_simple_group_clear_finish(EC_GROUP *group)
163 BN_clear_free(group->field);
164 BN_clear_free(group->a);
165 BN_clear_free(group->b);
168 int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
170 if (!BN_copy(dest->field, src->field))
172 if (!BN_copy(dest->a, src->a))
174 if (!BN_copy(dest->b, src->b))
177 dest->a_is_minus3 = src->a_is_minus3;
182 int ec_GFp_simple_group_set_curve(EC_GROUP *group,
183 const BIGNUM *p, const BIGNUM *a,
184 const BIGNUM *b, BN_CTX *ctx)
187 BN_CTX *new_ctx = NULL;
190 /* p must be a prime > 3 */
191 if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) {
192 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD);
197 ctx = new_ctx = BN_CTX_new();
203 tmp_a = BN_CTX_get(ctx);
208 if (!BN_copy(group->field, p))
210 BN_set_negative(group->field, 0);
213 if (!BN_nnmod(tmp_a, a, p, ctx))
215 if (group->meth->field_encode) {
216 if (!group->meth->field_encode(group, group->a, tmp_a, ctx))
218 } else if (!BN_copy(group->a, tmp_a))
222 if (!BN_nnmod(group->b, b, p, ctx))
224 if (group->meth->field_encode)
225 if (!group->meth->field_encode(group, group->b, group->b, ctx))
228 /* group->a_is_minus3 */
229 if (!BN_add_word(tmp_a, 3))
231 group->a_is_minus3 = (0 == BN_cmp(tmp_a, group->field));
237 BN_CTX_free(new_ctx);
241 int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
242 BIGNUM *b, BN_CTX *ctx)
245 BN_CTX *new_ctx = NULL;
248 if (!BN_copy(p, group->field))
252 if (a != NULL || b != NULL) {
253 if (group->meth->field_decode) {
255 ctx = new_ctx = BN_CTX_new();
260 if (!group->meth->field_decode(group, a, group->a, ctx))
264 if (!group->meth->field_decode(group, b, group->b, ctx))
269 if (!BN_copy(a, group->a))
273 if (!BN_copy(b, group->b))
282 BN_CTX_free(new_ctx);
286 int ec_GFp_simple_group_get_degree(const EC_GROUP *group)
288 return BN_num_bits(group->field);
291 int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
294 BIGNUM *a, *b, *order, *tmp_1, *tmp_2;
295 const BIGNUM *p = group->field;
296 BN_CTX *new_ctx = NULL;
299 ctx = new_ctx = BN_CTX_new();
301 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT,
302 ERR_R_MALLOC_FAILURE);
309 tmp_1 = BN_CTX_get(ctx);
310 tmp_2 = BN_CTX_get(ctx);
311 order = BN_CTX_get(ctx);
315 if (group->meth->field_decode) {
316 if (!group->meth->field_decode(group, a, group->a, ctx))
318 if (!group->meth->field_decode(group, b, group->b, ctx))
321 if (!BN_copy(a, group->a))
323 if (!BN_copy(b, group->b))
328 * check the discriminant:
329 * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p)
335 } else if (!BN_is_zero(b)) {
336 if (!BN_mod_sqr(tmp_1, a, p, ctx))
338 if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx))
340 if (!BN_lshift(tmp_1, tmp_2, 2))
344 if (!BN_mod_sqr(tmp_2, b, p, ctx))
346 if (!BN_mul_word(tmp_2, 27))
350 if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx))
360 BN_CTX_free(new_ctx);
364 int ec_GFp_simple_point_init(EC_POINT *point)
371 if (point->X == NULL || point->Y == NULL || point->Z == NULL) {
380 void ec_GFp_simple_point_finish(EC_POINT *point)
387 void ec_GFp_simple_point_clear_finish(EC_POINT *point)
389 BN_clear_free(point->X);
390 BN_clear_free(point->Y);
391 BN_clear_free(point->Z);
395 int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
397 if (!BN_copy(dest->X, src->X))
399 if (!BN_copy(dest->Y, src->Y))
401 if (!BN_copy(dest->Z, src->Z))
403 dest->Z_is_one = src->Z_is_one;
408 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group,
416 int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group,
423 BN_CTX *new_ctx = NULL;
427 ctx = new_ctx = BN_CTX_new();
433 if (!BN_nnmod(point->X, x, group->field, ctx))
435 if (group->meth->field_encode) {
436 if (!group->meth->field_encode(group, point->X, point->X, ctx))
442 if (!BN_nnmod(point->Y, y, group->field, ctx))
444 if (group->meth->field_encode) {
445 if (!group->meth->field_encode(group, point->Y, point->Y, ctx))
453 if (!BN_nnmod(point->Z, z, group->field, ctx))
455 Z_is_one = BN_is_one(point->Z);
456 if (group->meth->field_encode) {
457 if (Z_is_one && (group->meth->field_set_to_one != 0)) {
458 if (!group->meth->field_set_to_one(group, point->Z, ctx))
462 meth->field_encode(group, point->Z, point->Z, ctx))
466 point->Z_is_one = Z_is_one;
472 BN_CTX_free(new_ctx);
476 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group,
477 const EC_POINT *point,
478 BIGNUM *x, BIGNUM *y,
479 BIGNUM *z, BN_CTX *ctx)
481 BN_CTX *new_ctx = NULL;
484 if (group->meth->field_decode != 0) {
486 ctx = new_ctx = BN_CTX_new();
492 if (!group->meth->field_decode(group, x, point->X, ctx))
496 if (!group->meth->field_decode(group, y, point->Y, ctx))
500 if (!group->meth->field_decode(group, z, point->Z, ctx))
505 if (!BN_copy(x, point->X))
509 if (!BN_copy(y, point->Y))
513 if (!BN_copy(z, point->Z))
521 BN_CTX_free(new_ctx);
525 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group,
528 const BIGNUM *y, BN_CTX *ctx)
530 if (x == NULL || y == NULL) {
532 * unlike for projective coordinates, we do not tolerate this
534 ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES,
535 ERR_R_PASSED_NULL_PARAMETER);
539 return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y,
540 BN_value_one(), ctx);
543 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group,
544 const EC_POINT *point,
545 BIGNUM *x, BIGNUM *y,
548 BN_CTX *new_ctx = NULL;
549 BIGNUM *Z, *Z_1, *Z_2, *Z_3;
553 if (EC_POINT_is_at_infinity(group, point)) {
554 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES,
555 EC_R_POINT_AT_INFINITY);
560 ctx = new_ctx = BN_CTX_new();
567 Z_1 = BN_CTX_get(ctx);
568 Z_2 = BN_CTX_get(ctx);
569 Z_3 = BN_CTX_get(ctx);
573 /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */
575 if (group->meth->field_decode) {
576 if (!group->meth->field_decode(group, Z, point->Z, ctx))
584 if (group->meth->field_decode) {
586 if (!group->meth->field_decode(group, x, point->X, ctx))
590 if (!group->meth->field_decode(group, y, point->Y, ctx))
595 if (!BN_copy(x, point->X))
599 if (!BN_copy(y, point->Y))
604 if (!BN_mod_inverse(Z_1, Z_, group->field, ctx)) {
605 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES,
610 if (group->meth->field_encode == 0) {
611 /* field_sqr works on standard representation */
612 if (!group->meth->field_sqr(group, Z_2, Z_1, ctx))
615 if (!BN_mod_sqr(Z_2, Z_1, group->field, ctx))
621 * in the Montgomery case, field_mul will cancel out Montgomery
624 if (!group->meth->field_mul(group, x, point->X, Z_2, ctx))
629 if (group->meth->field_encode == 0) {
631 * field_mul works on standard representation
633 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx))
636 if (!BN_mod_mul(Z_3, Z_2, Z_1, group->field, ctx))
641 * in the Montgomery case, field_mul will cancel out Montgomery
644 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 */
839 BN_CTX_free(new_ctx);
843 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
846 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
847 const BIGNUM *, BN_CTX *);
848 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
850 BN_CTX *new_ctx = NULL;
851 BIGNUM *n0, *n1, *n2, *n3;
854 if (EC_POINT_is_at_infinity(group, a)) {
860 field_mul = group->meth->field_mul;
861 field_sqr = group->meth->field_sqr;
865 ctx = new_ctx = BN_CTX_new();
871 n0 = BN_CTX_get(ctx);
872 n1 = BN_CTX_get(ctx);
873 n2 = BN_CTX_get(ctx);
874 n3 = BN_CTX_get(ctx);
879 * Note that in this function we must not read components of 'a' once we
880 * have written the corresponding components of 'r'. ('r' might the same
886 if (!field_sqr(group, n0, a->X, ctx))
888 if (!BN_mod_lshift1_quick(n1, n0, p))
890 if (!BN_mod_add_quick(n0, n0, n1, p))
892 if (!BN_mod_add_quick(n1, n0, group->a, p))
894 /* n1 = 3 * X_a^2 + a_curve */
895 } else if (group->a_is_minus3) {
896 if (!field_sqr(group, n1, a->Z, ctx))
898 if (!BN_mod_add_quick(n0, a->X, n1, p))
900 if (!BN_mod_sub_quick(n2, a->X, n1, p))
902 if (!field_mul(group, n1, n0, n2, ctx))
904 if (!BN_mod_lshift1_quick(n0, n1, p))
906 if (!BN_mod_add_quick(n1, n0, n1, p))
909 * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
910 * = 3 * X_a^2 - 3 * Z_a^4
913 if (!field_sqr(group, n0, a->X, ctx))
915 if (!BN_mod_lshift1_quick(n1, n0, p))
917 if (!BN_mod_add_quick(n0, n0, n1, p))
919 if (!field_sqr(group, n1, a->Z, ctx))
921 if (!field_sqr(group, n1, n1, ctx))
923 if (!field_mul(group, n1, n1, group->a, ctx))
925 if (!BN_mod_add_quick(n1, n1, n0, p))
927 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
932 if (!BN_copy(n0, a->Y))
935 if (!field_mul(group, n0, a->Y, a->Z, ctx))
938 if (!BN_mod_lshift1_quick(r->Z, n0, p))
941 /* Z_r = 2 * Y_a * Z_a */
944 if (!field_sqr(group, n3, a->Y, ctx))
946 if (!field_mul(group, n2, a->X, n3, ctx))
948 if (!BN_mod_lshift_quick(n2, n2, 2, p))
950 /* n2 = 4 * X_a * Y_a^2 */
953 if (!BN_mod_lshift1_quick(n0, n2, p))
955 if (!field_sqr(group, r->X, n1, ctx))
957 if (!BN_mod_sub_quick(r->X, r->X, n0, p))
959 /* X_r = n1^2 - 2 * n2 */
962 if (!field_sqr(group, n0, n3, ctx))
964 if (!BN_mod_lshift_quick(n3, n0, 3, p))
969 if (!BN_mod_sub_quick(n0, n2, r->X, p))
971 if (!field_mul(group, n0, n1, n0, ctx))
973 if (!BN_mod_sub_quick(r->Y, n0, n3, p))
975 /* Y_r = n1 * (n2 - X_r) - n3 */
981 BN_CTX_free(new_ctx);
985 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
987 if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y))
988 /* point is its own inverse */
991 return BN_usub(point->Y, group->field, point->Y);
994 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
996 return BN_is_zero(point->Z);
999 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
1002 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
1003 const BIGNUM *, BN_CTX *);
1004 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1006 BN_CTX *new_ctx = NULL;
1007 BIGNUM *rh, *tmp, *Z4, *Z6;
1010 if (EC_POINT_is_at_infinity(group, point))
1013 field_mul = group->meth->field_mul;
1014 field_sqr = group->meth->field_sqr;
1018 ctx = new_ctx = BN_CTX_new();
1024 rh = BN_CTX_get(ctx);
1025 tmp = BN_CTX_get(ctx);
1026 Z4 = BN_CTX_get(ctx);
1027 Z6 = BN_CTX_get(ctx);
1032 * We have a curve defined by a Weierstrass equation
1033 * y^2 = x^3 + a*x + b.
1034 * The point to consider is given in Jacobian projective coordinates
1035 * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3).
1036 * Substituting this and multiplying by Z^6 transforms the above equation into
1037 * Y^2 = X^3 + a*X*Z^4 + b*Z^6.
1038 * To test this, we add up the right-hand side in 'rh'.
1042 if (!field_sqr(group, rh, point->X, ctx))
1045 if (!point->Z_is_one) {
1046 if (!field_sqr(group, tmp, point->Z, ctx))
1048 if (!field_sqr(group, Z4, tmp, ctx))
1050 if (!field_mul(group, Z6, Z4, tmp, ctx))
1053 /* rh := (rh + a*Z^4)*X */
1054 if (group->a_is_minus3) {
1055 if (!BN_mod_lshift1_quick(tmp, Z4, p))
1057 if (!BN_mod_add_quick(tmp, tmp, Z4, p))
1059 if (!BN_mod_sub_quick(rh, rh, tmp, p))
1061 if (!field_mul(group, rh, rh, point->X, ctx))
1064 if (!field_mul(group, tmp, Z4, group->a, ctx))
1066 if (!BN_mod_add_quick(rh, rh, tmp, p))
1068 if (!field_mul(group, rh, rh, point->X, ctx))
1072 /* rh := rh + b*Z^6 */
1073 if (!field_mul(group, tmp, group->b, Z6, ctx))
1075 if (!BN_mod_add_quick(rh, rh, tmp, p))
1078 /* point->Z_is_one */
1080 /* rh := (rh + a)*X */
1081 if (!BN_mod_add_quick(rh, rh, group->a, p))
1083 if (!field_mul(group, rh, rh, point->X, ctx))
1086 if (!BN_mod_add_quick(rh, rh, group->b, p))
1091 if (!field_sqr(group, tmp, point->Y, ctx))
1094 ret = (0 == BN_ucmp(tmp, rh));
1098 BN_CTX_free(new_ctx);
1102 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
1103 const EC_POINT *b, BN_CTX *ctx)
1108 * 0 equal (in affine coordinates)
1112 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
1113 const BIGNUM *, BN_CTX *);
1114 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1115 BN_CTX *new_ctx = NULL;
1116 BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
1117 const BIGNUM *tmp1_, *tmp2_;
1120 if (EC_POINT_is_at_infinity(group, a)) {
1121 return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
1124 if (EC_POINT_is_at_infinity(group, b))
1127 if (a->Z_is_one && b->Z_is_one) {
1128 return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1;
1131 field_mul = group->meth->field_mul;
1132 field_sqr = group->meth->field_sqr;
1135 ctx = new_ctx = BN_CTX_new();
1141 tmp1 = BN_CTX_get(ctx);
1142 tmp2 = BN_CTX_get(ctx);
1143 Za23 = BN_CTX_get(ctx);
1144 Zb23 = BN_CTX_get(ctx);
1149 * We have to decide whether
1150 * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
1151 * or equivalently, whether
1152 * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
1156 if (!field_sqr(group, Zb23, b->Z, ctx))
1158 if (!field_mul(group, tmp1, a->X, Zb23, ctx))
1164 if (!field_sqr(group, Za23, a->Z, ctx))
1166 if (!field_mul(group, tmp2, b->X, Za23, ctx))
1172 /* compare X_a*Z_b^2 with X_b*Z_a^2 */
1173 if (BN_cmp(tmp1_, tmp2_) != 0) {
1174 ret = 1; /* points differ */
1179 if (!field_mul(group, Zb23, Zb23, b->Z, ctx))
1181 if (!field_mul(group, tmp1, a->Y, Zb23, ctx))
1187 if (!field_mul(group, Za23, Za23, a->Z, ctx))
1189 if (!field_mul(group, tmp2, b->Y, Za23, ctx))
1195 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */
1196 if (BN_cmp(tmp1_, tmp2_) != 0) {
1197 ret = 1; /* points differ */
1201 /* points are equal */
1206 BN_CTX_free(new_ctx);
1210 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
1213 BN_CTX *new_ctx = NULL;
1217 if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
1221 ctx = new_ctx = BN_CTX_new();
1227 x = BN_CTX_get(ctx);
1228 y = BN_CTX_get(ctx);
1232 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx))
1234 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
1236 if (!point->Z_is_one) {
1237 ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
1245 BN_CTX_free(new_ctx);
1249 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num,
1250 EC_POINT *points[], BN_CTX *ctx)
1252 BN_CTX *new_ctx = NULL;
1253 BIGNUM *tmp, *tmp_Z;
1254 BIGNUM **prod_Z = NULL;
1262 ctx = new_ctx = BN_CTX_new();
1268 tmp = BN_CTX_get(ctx);
1269 tmp_Z = BN_CTX_get(ctx);
1270 if (tmp == NULL || tmp_Z == NULL)
1273 prod_Z = OPENSSL_malloc(num * sizeof prod_Z[0]);
1276 for (i = 0; i < num; i++) {
1277 prod_Z[i] = BN_new();
1278 if (prod_Z[i] == NULL)
1283 * Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z,
1284 * skipping any zero-valued inputs (pretend that they're 1).
1287 if (!BN_is_zero(points[0]->Z)) {
1288 if (!BN_copy(prod_Z[0], points[0]->Z))
1291 if (group->meth->field_set_to_one != 0) {
1292 if (!group->meth->field_set_to_one(group, prod_Z[0], ctx))
1295 if (!BN_one(prod_Z[0]))
1300 for (i = 1; i < num; i++) {
1301 if (!BN_is_zero(points[i]->Z)) {
1303 meth->field_mul(group, prod_Z[i], prod_Z[i - 1], points[i]->Z,
1307 if (!BN_copy(prod_Z[i], prod_Z[i - 1]))
1313 * Now use a single explicit inversion to replace every non-zero
1314 * points[i]->Z by its inverse.
1317 if (!BN_mod_inverse(tmp, prod_Z[num - 1], group->field, ctx)) {
1318 ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
1321 if (group->meth->field_encode != 0) {
1323 * In the Montgomery case, we just turned R*H (representing H) into
1324 * 1/(R*H), but we need R*(1/H) (representing 1/H); i.e. we need to
1325 * multiply by the Montgomery factor twice.
1327 if (!group->meth->field_encode(group, tmp, tmp, ctx))
1329 if (!group->meth->field_encode(group, tmp, tmp, ctx))
1333 for (i = num - 1; i > 0; --i) {
1335 * Loop invariant: tmp is the product of the inverses of points[0]->Z
1336 * .. points[i]->Z (zero-valued inputs skipped).
1338 if (!BN_is_zero(points[i]->Z)) {
1340 * Set tmp_Z to the inverse of points[i]->Z (as product of Z
1341 * inverses 0 .. i, Z values 0 .. i - 1).
1344 meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx))
1347 * Update tmp to satisfy the loop invariant for i - 1.
1349 if (!group->meth->field_mul(group, tmp, tmp, points[i]->Z, ctx))
1351 /* Replace points[i]->Z by its inverse. */
1352 if (!BN_copy(points[i]->Z, tmp_Z))
1357 if (!BN_is_zero(points[0]->Z)) {
1358 /* Replace points[0]->Z by its inverse. */
1359 if (!BN_copy(points[0]->Z, tmp))
1363 /* Finally, fix up the X and Y coordinates for all points. */
1365 for (i = 0; i < num; i++) {
1366 EC_POINT *p = points[i];
1368 if (!BN_is_zero(p->Z)) {
1369 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */
1371 if (!group->meth->field_sqr(group, tmp, p->Z, ctx))
1373 if (!group->meth->field_mul(group, p->X, p->X, tmp, ctx))
1376 if (!group->meth->field_mul(group, tmp, tmp, p->Z, ctx))
1378 if (!group->meth->field_mul(group, p->Y, p->Y, tmp, ctx))
1381 if (group->meth->field_set_to_one != 0) {
1382 if (!group->meth->field_set_to_one(group, p->Z, ctx))
1396 BN_CTX_free(new_ctx);
1397 if (prod_Z != NULL) {
1398 for (i = 0; i < num; i++) {
1399 if (prod_Z[i] == NULL)
1401 BN_clear_free(prod_Z[i]);
1403 OPENSSL_free(prod_Z);
1408 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1409 const BIGNUM *b, BN_CTX *ctx)
1411 return BN_mod_mul(r, a, b, group->field, ctx);
1414 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1417 return BN_mod_sqr(r, a, group->field, ctx);