2 * Copyright 2001-2018 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
5 * Licensed under the Apache License 2.0 (the "License"). You may not use
6 * this file except in compliance with the License. You can obtain a copy
7 * in the file LICENSE in the source distribution or at
8 * https://www.openssl.org/source/license.html
11 #include <openssl/err.h>
12 #include <openssl/symhacks.h>
16 const EC_METHOD
*EC_GFp_simple_method(void)
18 static const EC_METHOD ret
= {
20 NID_X9_62_prime_field
,
21 ec_GFp_simple_group_init
,
22 ec_GFp_simple_group_finish
,
23 ec_GFp_simple_group_clear_finish
,
24 ec_GFp_simple_group_copy
,
25 ec_GFp_simple_group_set_curve
,
26 ec_GFp_simple_group_get_curve
,
27 ec_GFp_simple_group_get_degree
,
28 ec_group_simple_order_bits
,
29 ec_GFp_simple_group_check_discriminant
,
30 ec_GFp_simple_point_init
,
31 ec_GFp_simple_point_finish
,
32 ec_GFp_simple_point_clear_finish
,
33 ec_GFp_simple_point_copy
,
34 ec_GFp_simple_point_set_to_infinity
,
35 ec_GFp_simple_set_Jprojective_coordinates_GFp
,
36 ec_GFp_simple_get_Jprojective_coordinates_GFp
,
37 ec_GFp_simple_point_set_affine_coordinates
,
38 ec_GFp_simple_point_get_affine_coordinates
,
43 ec_GFp_simple_is_at_infinity
,
44 ec_GFp_simple_is_on_curve
,
46 ec_GFp_simple_make_affine
,
47 ec_GFp_simple_points_make_affine
,
49 0 /* precompute_mult */ ,
50 0 /* have_precompute_mult */ ,
51 ec_GFp_simple_field_mul
,
52 ec_GFp_simple_field_sqr
,
54 ec_GFp_simple_field_inv
,
55 0 /* field_encode */ ,
56 0 /* field_decode */ ,
57 0, /* field_set_to_one */
58 ec_key_simple_priv2oct
,
59 ec_key_simple_oct2priv
,
61 ec_key_simple_generate_key
,
62 ec_key_simple_check_key
,
63 ec_key_simple_generate_public_key
,
66 ecdh_simple_compute_key
,
67 ecdsa_simple_sign_setup
,
68 ecdsa_simple_sign_sig
,
69 ecdsa_simple_verify_sig
,
70 0, /* field_inverse_mod_ord */
71 ec_GFp_simple_blind_coordinates
,
72 ec_GFp_simple_ladder_pre
,
73 ec_GFp_simple_ladder_step
,
74 ec_GFp_simple_ladder_post
81 * Most method functions in this file are designed to work with
82 * non-trivial representations of field elements if necessary
83 * (see ecp_mont.c): while standard modular addition and subtraction
84 * are used, the field_mul and field_sqr methods will be used for
85 * multiplication, and field_encode and field_decode (if defined)
86 * will be used for converting between representations.
88 * Functions ec_GFp_simple_points_make_affine() and
89 * ec_GFp_simple_point_get_affine_coordinates() specifically assume
90 * that if a non-trivial representation is used, it is a Montgomery
91 * representation (i.e. 'encoding' means multiplying by some factor R).
94 int ec_GFp_simple_group_init(EC_GROUP
*group
)
96 group
->field
= BN_new();
99 if (group
->field
== NULL
|| group
->a
== NULL
|| group
->b
== NULL
) {
100 BN_free(group
->field
);
105 group
->a_is_minus3
= 0;
109 void ec_GFp_simple_group_finish(EC_GROUP
*group
)
111 BN_free(group
->field
);
116 void ec_GFp_simple_group_clear_finish(EC_GROUP
*group
)
118 BN_clear_free(group
->field
);
119 BN_clear_free(group
->a
);
120 BN_clear_free(group
->b
);
123 int ec_GFp_simple_group_copy(EC_GROUP
*dest
, const EC_GROUP
*src
)
125 if (!BN_copy(dest
->field
, src
->field
))
127 if (!BN_copy(dest
->a
, src
->a
))
129 if (!BN_copy(dest
->b
, src
->b
))
132 dest
->a_is_minus3
= src
->a_is_minus3
;
137 int ec_GFp_simple_group_set_curve(EC_GROUP
*group
,
138 const BIGNUM
*p
, const BIGNUM
*a
,
139 const BIGNUM
*b
, BN_CTX
*ctx
)
142 BN_CTX
*new_ctx
= NULL
;
145 /* p must be a prime > 3 */
146 if (BN_num_bits(p
) <= 2 || !BN_is_odd(p
)) {
147 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE
, EC_R_INVALID_FIELD
);
152 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
158 tmp_a
= BN_CTX_get(ctx
);
163 if (!BN_copy(group
->field
, p
))
165 BN_set_negative(group
->field
, 0);
168 if (!BN_nnmod(tmp_a
, a
, p
, ctx
))
170 if (group
->meth
->field_encode
) {
171 if (!group
->meth
->field_encode(group
, group
->a
, tmp_a
, ctx
))
173 } else if (!BN_copy(group
->a
, tmp_a
))
177 if (!BN_nnmod(group
->b
, b
, p
, ctx
))
179 if (group
->meth
->field_encode
)
180 if (!group
->meth
->field_encode(group
, group
->b
, group
->b
, ctx
))
183 /* group->a_is_minus3 */
184 if (!BN_add_word(tmp_a
, 3))
186 group
->a_is_minus3
= (0 == BN_cmp(tmp_a
, group
->field
));
192 BN_CTX_free(new_ctx
);
196 int ec_GFp_simple_group_get_curve(const EC_GROUP
*group
, BIGNUM
*p
, BIGNUM
*a
,
197 BIGNUM
*b
, BN_CTX
*ctx
)
200 BN_CTX
*new_ctx
= NULL
;
203 if (!BN_copy(p
, group
->field
))
207 if (a
!= NULL
|| b
!= NULL
) {
208 if (group
->meth
->field_decode
) {
210 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
215 if (!group
->meth
->field_decode(group
, a
, group
->a
, ctx
))
219 if (!group
->meth
->field_decode(group
, b
, group
->b
, ctx
))
224 if (!BN_copy(a
, group
->a
))
228 if (!BN_copy(b
, group
->b
))
237 BN_CTX_free(new_ctx
);
241 int ec_GFp_simple_group_get_degree(const EC_GROUP
*group
)
243 return BN_num_bits(group
->field
);
246 int ec_GFp_simple_group_check_discriminant(const EC_GROUP
*group
, BN_CTX
*ctx
)
249 BIGNUM
*a
, *b
, *order
, *tmp_1
, *tmp_2
;
250 const BIGNUM
*p
= group
->field
;
251 BN_CTX
*new_ctx
= NULL
;
254 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
256 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT
,
257 ERR_R_MALLOC_FAILURE
);
264 tmp_1
= BN_CTX_get(ctx
);
265 tmp_2
= BN_CTX_get(ctx
);
266 order
= BN_CTX_get(ctx
);
270 if (group
->meth
->field_decode
) {
271 if (!group
->meth
->field_decode(group
, a
, group
->a
, ctx
))
273 if (!group
->meth
->field_decode(group
, b
, group
->b
, ctx
))
276 if (!BN_copy(a
, group
->a
))
278 if (!BN_copy(b
, group
->b
))
283 * check the discriminant:
284 * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p)
290 } else if (!BN_is_zero(b
)) {
291 if (!BN_mod_sqr(tmp_1
, a
, p
, ctx
))
293 if (!BN_mod_mul(tmp_2
, tmp_1
, a
, p
, ctx
))
295 if (!BN_lshift(tmp_1
, tmp_2
, 2))
299 if (!BN_mod_sqr(tmp_2
, b
, p
, ctx
))
301 if (!BN_mul_word(tmp_2
, 27))
305 if (!BN_mod_add(a
, tmp_1
, tmp_2
, p
, ctx
))
314 BN_CTX_free(new_ctx
);
318 int ec_GFp_simple_point_init(EC_POINT
*point
)
325 if (point
->X
== NULL
|| point
->Y
== NULL
|| point
->Z
== NULL
) {
334 void ec_GFp_simple_point_finish(EC_POINT
*point
)
341 void ec_GFp_simple_point_clear_finish(EC_POINT
*point
)
343 BN_clear_free(point
->X
);
344 BN_clear_free(point
->Y
);
345 BN_clear_free(point
->Z
);
349 int ec_GFp_simple_point_copy(EC_POINT
*dest
, const EC_POINT
*src
)
351 if (!BN_copy(dest
->X
, src
->X
))
353 if (!BN_copy(dest
->Y
, src
->Y
))
355 if (!BN_copy(dest
->Z
, src
->Z
))
357 dest
->Z_is_one
= src
->Z_is_one
;
358 dest
->curve_name
= src
->curve_name
;
363 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP
*group
,
371 int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP
*group
,
378 BN_CTX
*new_ctx
= NULL
;
382 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
388 if (!BN_nnmod(point
->X
, x
, group
->field
, ctx
))
390 if (group
->meth
->field_encode
) {
391 if (!group
->meth
->field_encode(group
, point
->X
, point
->X
, ctx
))
397 if (!BN_nnmod(point
->Y
, y
, group
->field
, ctx
))
399 if (group
->meth
->field_encode
) {
400 if (!group
->meth
->field_encode(group
, point
->Y
, point
->Y
, ctx
))
408 if (!BN_nnmod(point
->Z
, z
, group
->field
, ctx
))
410 Z_is_one
= BN_is_one(point
->Z
);
411 if (group
->meth
->field_encode
) {
412 if (Z_is_one
&& (group
->meth
->field_set_to_one
!= 0)) {
413 if (!group
->meth
->field_set_to_one(group
, point
->Z
, ctx
))
417 meth
->field_encode(group
, point
->Z
, point
->Z
, ctx
))
421 point
->Z_is_one
= Z_is_one
;
427 BN_CTX_free(new_ctx
);
431 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP
*group
,
432 const EC_POINT
*point
,
433 BIGNUM
*x
, BIGNUM
*y
,
434 BIGNUM
*z
, BN_CTX
*ctx
)
436 BN_CTX
*new_ctx
= NULL
;
439 if (group
->meth
->field_decode
!= 0) {
441 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
447 if (!group
->meth
->field_decode(group
, x
, point
->X
, ctx
))
451 if (!group
->meth
->field_decode(group
, y
, point
->Y
, ctx
))
455 if (!group
->meth
->field_decode(group
, z
, point
->Z
, ctx
))
460 if (!BN_copy(x
, point
->X
))
464 if (!BN_copy(y
, point
->Y
))
468 if (!BN_copy(z
, point
->Z
))
476 BN_CTX_free(new_ctx
);
480 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP
*group
,
483 const BIGNUM
*y
, BN_CTX
*ctx
)
485 if (x
== NULL
|| y
== NULL
) {
487 * unlike for projective coordinates, we do not tolerate this
489 ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES
,
490 ERR_R_PASSED_NULL_PARAMETER
);
494 return EC_POINT_set_Jprojective_coordinates_GFp(group
, point
, x
, y
,
495 BN_value_one(), ctx
);
498 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP
*group
,
499 const EC_POINT
*point
,
500 BIGNUM
*x
, BIGNUM
*y
,
503 BN_CTX
*new_ctx
= NULL
;
504 BIGNUM
*Z
, *Z_1
, *Z_2
, *Z_3
;
508 if (EC_POINT_is_at_infinity(group
, point
)) {
509 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES
,
510 EC_R_POINT_AT_INFINITY
);
515 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
522 Z_1
= BN_CTX_get(ctx
);
523 Z_2
= BN_CTX_get(ctx
);
524 Z_3
= BN_CTX_get(ctx
);
528 /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */
530 if (group
->meth
->field_decode
) {
531 if (!group
->meth
->field_decode(group
, Z
, point
->Z
, ctx
))
539 if (group
->meth
->field_decode
) {
541 if (!group
->meth
->field_decode(group
, x
, point
->X
, ctx
))
545 if (!group
->meth
->field_decode(group
, y
, point
->Y
, ctx
))
550 if (!BN_copy(x
, point
->X
))
554 if (!BN_copy(y
, point
->Y
))
559 if (!group
->meth
->field_inv(group
, Z_1
, Z_
, ctx
)) {
560 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES
,
565 if (group
->meth
->field_encode
== 0) {
566 /* field_sqr works on standard representation */
567 if (!group
->meth
->field_sqr(group
, Z_2
, Z_1
, ctx
))
570 if (!BN_mod_sqr(Z_2
, Z_1
, group
->field
, ctx
))
576 * in the Montgomery case, field_mul will cancel out Montgomery
579 if (!group
->meth
->field_mul(group
, x
, point
->X
, Z_2
, ctx
))
584 if (group
->meth
->field_encode
== 0) {
586 * field_mul works on standard representation
588 if (!group
->meth
->field_mul(group
, Z_3
, Z_2
, Z_1
, ctx
))
591 if (!BN_mod_mul(Z_3
, Z_2
, Z_1
, group
->field
, ctx
))
596 * in the Montgomery case, field_mul will cancel out Montgomery
599 if (!group
->meth
->field_mul(group
, y
, point
->Y
, Z_3
, ctx
))
608 BN_CTX_free(new_ctx
);
612 int ec_GFp_simple_add(const EC_GROUP
*group
, EC_POINT
*r
, const EC_POINT
*a
,
613 const EC_POINT
*b
, BN_CTX
*ctx
)
615 int (*field_mul
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*,
616 const BIGNUM
*, BN_CTX
*);
617 int (*field_sqr
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*, BN_CTX
*);
619 BN_CTX
*new_ctx
= NULL
;
620 BIGNUM
*n0
, *n1
, *n2
, *n3
, *n4
, *n5
, *n6
;
624 return EC_POINT_dbl(group
, r
, a
, ctx
);
625 if (EC_POINT_is_at_infinity(group
, a
))
626 return EC_POINT_copy(r
, b
);
627 if (EC_POINT_is_at_infinity(group
, b
))
628 return EC_POINT_copy(r
, a
);
630 field_mul
= group
->meth
->field_mul
;
631 field_sqr
= group
->meth
->field_sqr
;
635 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
641 n0
= BN_CTX_get(ctx
);
642 n1
= BN_CTX_get(ctx
);
643 n2
= BN_CTX_get(ctx
);
644 n3
= BN_CTX_get(ctx
);
645 n4
= BN_CTX_get(ctx
);
646 n5
= BN_CTX_get(ctx
);
647 n6
= BN_CTX_get(ctx
);
652 * Note that in this function we must not read components of 'a' or 'b'
653 * once we have written the corresponding components of 'r'. ('r' might
654 * be one of 'a' or 'b'.)
659 if (!BN_copy(n1
, a
->X
))
661 if (!BN_copy(n2
, a
->Y
))
666 if (!field_sqr(group
, n0
, b
->Z
, ctx
))
668 if (!field_mul(group
, n1
, a
->X
, n0
, ctx
))
670 /* n1 = X_a * Z_b^2 */
672 if (!field_mul(group
, n0
, n0
, b
->Z
, ctx
))
674 if (!field_mul(group
, n2
, a
->Y
, n0
, ctx
))
676 /* n2 = Y_a * Z_b^3 */
681 if (!BN_copy(n3
, b
->X
))
683 if (!BN_copy(n4
, b
->Y
))
688 if (!field_sqr(group
, n0
, a
->Z
, ctx
))
690 if (!field_mul(group
, n3
, b
->X
, n0
, ctx
))
692 /* n3 = X_b * Z_a^2 */
694 if (!field_mul(group
, n0
, n0
, a
->Z
, ctx
))
696 if (!field_mul(group
, n4
, b
->Y
, n0
, ctx
))
698 /* n4 = Y_b * Z_a^3 */
702 if (!BN_mod_sub_quick(n5
, n1
, n3
, p
))
704 if (!BN_mod_sub_quick(n6
, n2
, n4
, p
))
709 if (BN_is_zero(n5
)) {
710 if (BN_is_zero(n6
)) {
711 /* a is the same point as b */
713 ret
= EC_POINT_dbl(group
, r
, a
, ctx
);
717 /* a is the inverse of b */
726 if (!BN_mod_add_quick(n1
, n1
, n3
, p
))
728 if (!BN_mod_add_quick(n2
, n2
, n4
, p
))
734 if (a
->Z_is_one
&& b
->Z_is_one
) {
735 if (!BN_copy(r
->Z
, n5
))
739 if (!BN_copy(n0
, b
->Z
))
741 } else if (b
->Z_is_one
) {
742 if (!BN_copy(n0
, a
->Z
))
745 if (!field_mul(group
, n0
, a
->Z
, b
->Z
, ctx
))
748 if (!field_mul(group
, r
->Z
, n0
, n5
, ctx
))
752 /* Z_r = Z_a * Z_b * n5 */
755 if (!field_sqr(group
, n0
, n6
, ctx
))
757 if (!field_sqr(group
, n4
, n5
, ctx
))
759 if (!field_mul(group
, n3
, n1
, n4
, ctx
))
761 if (!BN_mod_sub_quick(r
->X
, n0
, n3
, p
))
763 /* X_r = n6^2 - n5^2 * 'n7' */
766 if (!BN_mod_lshift1_quick(n0
, r
->X
, p
))
768 if (!BN_mod_sub_quick(n0
, n3
, n0
, p
))
770 /* n9 = n5^2 * 'n7' - 2 * X_r */
773 if (!field_mul(group
, n0
, n0
, n6
, ctx
))
775 if (!field_mul(group
, n5
, n4
, n5
, ctx
))
776 goto end
; /* now n5 is n5^3 */
777 if (!field_mul(group
, n1
, n2
, n5
, ctx
))
779 if (!BN_mod_sub_quick(n0
, n0
, n1
, p
))
782 if (!BN_add(n0
, n0
, p
))
784 /* now 0 <= n0 < 2*p, and n0 is even */
785 if (!BN_rshift1(r
->Y
, n0
))
787 /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
793 BN_CTX_free(new_ctx
);
797 int ec_GFp_simple_dbl(const EC_GROUP
*group
, EC_POINT
*r
, const EC_POINT
*a
,
800 int (*field_mul
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*,
801 const BIGNUM
*, BN_CTX
*);
802 int (*field_sqr
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*, BN_CTX
*);
804 BN_CTX
*new_ctx
= NULL
;
805 BIGNUM
*n0
, *n1
, *n2
, *n3
;
808 if (EC_POINT_is_at_infinity(group
, a
)) {
814 field_mul
= group
->meth
->field_mul
;
815 field_sqr
= group
->meth
->field_sqr
;
819 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
825 n0
= BN_CTX_get(ctx
);
826 n1
= BN_CTX_get(ctx
);
827 n2
= BN_CTX_get(ctx
);
828 n3
= BN_CTX_get(ctx
);
833 * Note that in this function we must not read components of 'a' once we
834 * have written the corresponding components of 'r'. ('r' might the same
840 if (!field_sqr(group
, n0
, a
->X
, ctx
))
842 if (!BN_mod_lshift1_quick(n1
, n0
, p
))
844 if (!BN_mod_add_quick(n0
, n0
, n1
, p
))
846 if (!BN_mod_add_quick(n1
, n0
, group
->a
, p
))
848 /* n1 = 3 * X_a^2 + a_curve */
849 } else if (group
->a_is_minus3
) {
850 if (!field_sqr(group
, n1
, a
->Z
, ctx
))
852 if (!BN_mod_add_quick(n0
, a
->X
, n1
, p
))
854 if (!BN_mod_sub_quick(n2
, a
->X
, n1
, p
))
856 if (!field_mul(group
, n1
, n0
, n2
, ctx
))
858 if (!BN_mod_lshift1_quick(n0
, n1
, p
))
860 if (!BN_mod_add_quick(n1
, n0
, n1
, p
))
863 * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
864 * = 3 * X_a^2 - 3 * Z_a^4
867 if (!field_sqr(group
, n0
, a
->X
, ctx
))
869 if (!BN_mod_lshift1_quick(n1
, n0
, p
))
871 if (!BN_mod_add_quick(n0
, n0
, n1
, p
))
873 if (!field_sqr(group
, n1
, a
->Z
, ctx
))
875 if (!field_sqr(group
, n1
, n1
, ctx
))
877 if (!field_mul(group
, n1
, n1
, group
->a
, ctx
))
879 if (!BN_mod_add_quick(n1
, n1
, n0
, p
))
881 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
886 if (!BN_copy(n0
, a
->Y
))
889 if (!field_mul(group
, n0
, a
->Y
, a
->Z
, ctx
))
892 if (!BN_mod_lshift1_quick(r
->Z
, n0
, p
))
895 /* Z_r = 2 * Y_a * Z_a */
898 if (!field_sqr(group
, n3
, a
->Y
, ctx
))
900 if (!field_mul(group
, n2
, a
->X
, n3
, ctx
))
902 if (!BN_mod_lshift_quick(n2
, n2
, 2, p
))
904 /* n2 = 4 * X_a * Y_a^2 */
907 if (!BN_mod_lshift1_quick(n0
, n2
, p
))
909 if (!field_sqr(group
, r
->X
, n1
, ctx
))
911 if (!BN_mod_sub_quick(r
->X
, r
->X
, n0
, p
))
913 /* X_r = n1^2 - 2 * n2 */
916 if (!field_sqr(group
, n0
, n3
, ctx
))
918 if (!BN_mod_lshift_quick(n3
, n0
, 3, p
))
923 if (!BN_mod_sub_quick(n0
, n2
, r
->X
, p
))
925 if (!field_mul(group
, n0
, n1
, n0
, ctx
))
927 if (!BN_mod_sub_quick(r
->Y
, n0
, n3
, p
))
929 /* Y_r = n1 * (n2 - X_r) - n3 */
935 BN_CTX_free(new_ctx
);
939 int ec_GFp_simple_invert(const EC_GROUP
*group
, EC_POINT
*point
, BN_CTX
*ctx
)
941 if (EC_POINT_is_at_infinity(group
, point
) || BN_is_zero(point
->Y
))
942 /* point is its own inverse */
945 return BN_usub(point
->Y
, group
->field
, point
->Y
);
948 int ec_GFp_simple_is_at_infinity(const EC_GROUP
*group
, const EC_POINT
*point
)
950 return BN_is_zero(point
->Z
);
953 int ec_GFp_simple_is_on_curve(const EC_GROUP
*group
, const EC_POINT
*point
,
956 int (*field_mul
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*,
957 const BIGNUM
*, BN_CTX
*);
958 int (*field_sqr
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*, BN_CTX
*);
960 BN_CTX
*new_ctx
= NULL
;
961 BIGNUM
*rh
, *tmp
, *Z4
, *Z6
;
964 if (EC_POINT_is_at_infinity(group
, point
))
967 field_mul
= group
->meth
->field_mul
;
968 field_sqr
= group
->meth
->field_sqr
;
972 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
978 rh
= BN_CTX_get(ctx
);
979 tmp
= BN_CTX_get(ctx
);
980 Z4
= BN_CTX_get(ctx
);
981 Z6
= BN_CTX_get(ctx
);
986 * We have a curve defined by a Weierstrass equation
987 * y^2 = x^3 + a*x + b.
988 * The point to consider is given in Jacobian projective coordinates
989 * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3).
990 * Substituting this and multiplying by Z^6 transforms the above equation into
991 * Y^2 = X^3 + a*X*Z^4 + b*Z^6.
992 * To test this, we add up the right-hand side in 'rh'.
996 if (!field_sqr(group
, rh
, point
->X
, ctx
))
999 if (!point
->Z_is_one
) {
1000 if (!field_sqr(group
, tmp
, point
->Z
, ctx
))
1002 if (!field_sqr(group
, Z4
, tmp
, ctx
))
1004 if (!field_mul(group
, Z6
, Z4
, tmp
, ctx
))
1007 /* rh := (rh + a*Z^4)*X */
1008 if (group
->a_is_minus3
) {
1009 if (!BN_mod_lshift1_quick(tmp
, Z4
, p
))
1011 if (!BN_mod_add_quick(tmp
, tmp
, Z4
, p
))
1013 if (!BN_mod_sub_quick(rh
, rh
, tmp
, p
))
1015 if (!field_mul(group
, rh
, rh
, point
->X
, ctx
))
1018 if (!field_mul(group
, tmp
, Z4
, group
->a
, ctx
))
1020 if (!BN_mod_add_quick(rh
, rh
, tmp
, p
))
1022 if (!field_mul(group
, rh
, rh
, point
->X
, ctx
))
1026 /* rh := rh + b*Z^6 */
1027 if (!field_mul(group
, tmp
, group
->b
, Z6
, ctx
))
1029 if (!BN_mod_add_quick(rh
, rh
, tmp
, p
))
1032 /* point->Z_is_one */
1034 /* rh := (rh + a)*X */
1035 if (!BN_mod_add_quick(rh
, rh
, group
->a
, p
))
1037 if (!field_mul(group
, rh
, rh
, point
->X
, ctx
))
1040 if (!BN_mod_add_quick(rh
, rh
, group
->b
, p
))
1045 if (!field_sqr(group
, tmp
, point
->Y
, ctx
))
1048 ret
= (0 == BN_ucmp(tmp
, rh
));
1052 BN_CTX_free(new_ctx
);
1056 int ec_GFp_simple_cmp(const EC_GROUP
*group
, const EC_POINT
*a
,
1057 const EC_POINT
*b
, BN_CTX
*ctx
)
1062 * 0 equal (in affine coordinates)
1066 int (*field_mul
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*,
1067 const BIGNUM
*, BN_CTX
*);
1068 int (*field_sqr
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*, BN_CTX
*);
1069 BN_CTX
*new_ctx
= NULL
;
1070 BIGNUM
*tmp1
, *tmp2
, *Za23
, *Zb23
;
1071 const BIGNUM
*tmp1_
, *tmp2_
;
1074 if (EC_POINT_is_at_infinity(group
, a
)) {
1075 return EC_POINT_is_at_infinity(group
, b
) ? 0 : 1;
1078 if (EC_POINT_is_at_infinity(group
, b
))
1081 if (a
->Z_is_one
&& b
->Z_is_one
) {
1082 return ((BN_cmp(a
->X
, b
->X
) == 0) && BN_cmp(a
->Y
, b
->Y
) == 0) ? 0 : 1;
1085 field_mul
= group
->meth
->field_mul
;
1086 field_sqr
= group
->meth
->field_sqr
;
1089 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
1095 tmp1
= BN_CTX_get(ctx
);
1096 tmp2
= BN_CTX_get(ctx
);
1097 Za23
= BN_CTX_get(ctx
);
1098 Zb23
= BN_CTX_get(ctx
);
1103 * We have to decide whether
1104 * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
1105 * or equivalently, whether
1106 * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
1110 if (!field_sqr(group
, Zb23
, b
->Z
, ctx
))
1112 if (!field_mul(group
, tmp1
, a
->X
, Zb23
, ctx
))
1118 if (!field_sqr(group
, Za23
, a
->Z
, ctx
))
1120 if (!field_mul(group
, tmp2
, b
->X
, Za23
, ctx
))
1126 /* compare X_a*Z_b^2 with X_b*Z_a^2 */
1127 if (BN_cmp(tmp1_
, tmp2_
) != 0) {
1128 ret
= 1; /* points differ */
1133 if (!field_mul(group
, Zb23
, Zb23
, b
->Z
, ctx
))
1135 if (!field_mul(group
, tmp1
, a
->Y
, Zb23
, ctx
))
1141 if (!field_mul(group
, Za23
, Za23
, a
->Z
, ctx
))
1143 if (!field_mul(group
, tmp2
, b
->Y
, Za23
, ctx
))
1149 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */
1150 if (BN_cmp(tmp1_
, tmp2_
) != 0) {
1151 ret
= 1; /* points differ */
1155 /* points are equal */
1160 BN_CTX_free(new_ctx
);
1164 int ec_GFp_simple_make_affine(const EC_GROUP
*group
, EC_POINT
*point
,
1167 BN_CTX
*new_ctx
= NULL
;
1171 if (point
->Z_is_one
|| EC_POINT_is_at_infinity(group
, point
))
1175 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
1181 x
= BN_CTX_get(ctx
);
1182 y
= BN_CTX_get(ctx
);
1186 if (!EC_POINT_get_affine_coordinates(group
, point
, x
, y
, ctx
))
1188 if (!EC_POINT_set_affine_coordinates(group
, point
, x
, y
, ctx
))
1190 if (!point
->Z_is_one
) {
1191 ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE
, ERR_R_INTERNAL_ERROR
);
1199 BN_CTX_free(new_ctx
);
1203 int ec_GFp_simple_points_make_affine(const EC_GROUP
*group
, size_t num
,
1204 EC_POINT
*points
[], BN_CTX
*ctx
)
1206 BN_CTX
*new_ctx
= NULL
;
1207 BIGNUM
*tmp
, *tmp_Z
;
1208 BIGNUM
**prod_Z
= NULL
;
1216 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
1222 tmp
= BN_CTX_get(ctx
);
1223 tmp_Z
= BN_CTX_get(ctx
);
1227 prod_Z
= OPENSSL_malloc(num
* sizeof(prod_Z
[0]));
1230 for (i
= 0; i
< num
; i
++) {
1231 prod_Z
[i
] = BN_new();
1232 if (prod_Z
[i
] == NULL
)
1237 * Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z,
1238 * skipping any zero-valued inputs (pretend that they're 1).
1241 if (!BN_is_zero(points
[0]->Z
)) {
1242 if (!BN_copy(prod_Z
[0], points
[0]->Z
))
1245 if (group
->meth
->field_set_to_one
!= 0) {
1246 if (!group
->meth
->field_set_to_one(group
, prod_Z
[0], ctx
))
1249 if (!BN_one(prod_Z
[0]))
1254 for (i
= 1; i
< num
; i
++) {
1255 if (!BN_is_zero(points
[i
]->Z
)) {
1257 meth
->field_mul(group
, prod_Z
[i
], prod_Z
[i
- 1], points
[i
]->Z
,
1261 if (!BN_copy(prod_Z
[i
], prod_Z
[i
- 1]))
1267 * Now use a single explicit inversion to replace every non-zero
1268 * points[i]->Z by its inverse.
1271 if (!group
->meth
->field_inv(group
, tmp
, prod_Z
[num
- 1], ctx
)) {
1272 ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE
, ERR_R_BN_LIB
);
1275 if (group
->meth
->field_encode
!= 0) {
1277 * In the Montgomery case, we just turned R*H (representing H) into
1278 * 1/(R*H), but we need R*(1/H) (representing 1/H); i.e. we need to
1279 * multiply by the Montgomery factor twice.
1281 if (!group
->meth
->field_encode(group
, tmp
, tmp
, ctx
))
1283 if (!group
->meth
->field_encode(group
, tmp
, tmp
, ctx
))
1287 for (i
= num
- 1; i
> 0; --i
) {
1289 * Loop invariant: tmp is the product of the inverses of points[0]->Z
1290 * .. points[i]->Z (zero-valued inputs skipped).
1292 if (!BN_is_zero(points
[i
]->Z
)) {
1294 * Set tmp_Z to the inverse of points[i]->Z (as product of Z
1295 * inverses 0 .. i, Z values 0 .. i - 1).
1298 meth
->field_mul(group
, tmp_Z
, prod_Z
[i
- 1], tmp
, ctx
))
1301 * Update tmp to satisfy the loop invariant for i - 1.
1303 if (!group
->meth
->field_mul(group
, tmp
, tmp
, points
[i
]->Z
, ctx
))
1305 /* Replace points[i]->Z by its inverse. */
1306 if (!BN_copy(points
[i
]->Z
, tmp_Z
))
1311 if (!BN_is_zero(points
[0]->Z
)) {
1312 /* Replace points[0]->Z by its inverse. */
1313 if (!BN_copy(points
[0]->Z
, tmp
))
1317 /* Finally, fix up the X and Y coordinates for all points. */
1319 for (i
= 0; i
< num
; i
++) {
1320 EC_POINT
*p
= points
[i
];
1322 if (!BN_is_zero(p
->Z
)) {
1323 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */
1325 if (!group
->meth
->field_sqr(group
, tmp
, p
->Z
, ctx
))
1327 if (!group
->meth
->field_mul(group
, p
->X
, p
->X
, tmp
, ctx
))
1330 if (!group
->meth
->field_mul(group
, tmp
, tmp
, p
->Z
, ctx
))
1332 if (!group
->meth
->field_mul(group
, p
->Y
, p
->Y
, tmp
, ctx
))
1335 if (group
->meth
->field_set_to_one
!= 0) {
1336 if (!group
->meth
->field_set_to_one(group
, p
->Z
, ctx
))
1350 BN_CTX_free(new_ctx
);
1351 if (prod_Z
!= NULL
) {
1352 for (i
= 0; i
< num
; i
++) {
1353 if (prod_Z
[i
] == NULL
)
1355 BN_clear_free(prod_Z
[i
]);
1357 OPENSSL_free(prod_Z
);
1362 int ec_GFp_simple_field_mul(const EC_GROUP
*group
, BIGNUM
*r
, const BIGNUM
*a
,
1363 const BIGNUM
*b
, BN_CTX
*ctx
)
1365 return BN_mod_mul(r
, a
, b
, group
->field
, ctx
);
1368 int ec_GFp_simple_field_sqr(const EC_GROUP
*group
, BIGNUM
*r
, const BIGNUM
*a
,
1371 return BN_mod_sqr(r
, a
, group
->field
, ctx
);
1375 * Computes the multiplicative inverse of a in GF(p), storing the result in r.
1376 * If a is zero (or equivalent), you'll get a EC_R_CANNOT_INVERT error.
1377 * Since we don't have a Mont structure here, SCA hardening is with blinding.
1379 int ec_GFp_simple_field_inv(const EC_GROUP
*group
, BIGNUM
*r
, const BIGNUM
*a
,
1383 BN_CTX
*new_ctx
= NULL
;
1387 && (ctx
= new_ctx
= BN_CTX_secure_new_ex(group
->libctx
)) == NULL
)
1391 if ((e
= BN_CTX_get(ctx
)) == NULL
)
1395 if (!BN_priv_rand_range_ex(e
, group
->field
, ctx
))
1397 } while (BN_is_zero(e
));
1400 if (!group
->meth
->field_mul(group
, r
, a
, e
, ctx
))
1402 /* r := 1/(a * e) */
1403 if (!BN_mod_inverse(r
, r
, group
->field
, ctx
)) {
1404 ECerr(EC_F_EC_GFP_SIMPLE_FIELD_INV
, EC_R_CANNOT_INVERT
);
1407 /* r := e/(a * e) = 1/a */
1408 if (!group
->meth
->field_mul(group
, r
, r
, e
, ctx
))
1415 BN_CTX_free(new_ctx
);
1420 * Apply randomization of EC point projective coordinates:
1422 * (X, Y ,Z ) = (lambda^2*X, lambda^3*Y, lambda*Z)
1423 * lambda = [1,group->field)
1426 int ec_GFp_simple_blind_coordinates(const EC_GROUP
*group
, EC_POINT
*p
,
1430 BIGNUM
*lambda
= NULL
;
1431 BIGNUM
*temp
= NULL
;
1434 lambda
= BN_CTX_get(ctx
);
1435 temp
= BN_CTX_get(ctx
);
1437 ECerr(EC_F_EC_GFP_SIMPLE_BLIND_COORDINATES
, ERR_R_MALLOC_FAILURE
);
1441 /* make sure lambda is not zero */
1443 if (!BN_priv_rand_range_ex(lambda
, group
->field
, ctx
)) {
1444 ECerr(EC_F_EC_GFP_SIMPLE_BLIND_COORDINATES
, ERR_R_BN_LIB
);
1447 } while (BN_is_zero(lambda
));
1449 /* if field_encode defined convert between representations */
1450 if (group
->meth
->field_encode
!= NULL
1451 && !group
->meth
->field_encode(group
, lambda
, lambda
, ctx
))
1453 if (!group
->meth
->field_mul(group
, p
->Z
, p
->Z
, lambda
, ctx
))
1455 if (!group
->meth
->field_sqr(group
, temp
, lambda
, ctx
))
1457 if (!group
->meth
->field_mul(group
, p
->X
, p
->X
, temp
, ctx
))
1459 if (!group
->meth
->field_mul(group
, temp
, temp
, lambda
, ctx
))
1461 if (!group
->meth
->field_mul(group
, p
->Y
, p
->Y
, temp
, ctx
))
1473 * Set s := p, r := 2p.
1475 * For doubling we use Formula 3 from Izu-Takagi "A fast parallel elliptic curve
1476 * multiplication resistant against side channel attacks" appendix, as described
1478 * https://hyperelliptic.org/EFD/g1p/auto-shortw-xz.html#doubling-dbl-2002-it-2
1480 * The input point p will be in randomized Jacobian projective coords:
1481 * x = X/Z**2, y=Y/Z**3
1483 * The output points p, s, and r are converted to standard (homogeneous)
1484 * projective coords:
1487 int ec_GFp_simple_ladder_pre(const EC_GROUP
*group
,
1488 EC_POINT
*r
, EC_POINT
*s
,
1489 EC_POINT
*p
, BN_CTX
*ctx
)
1491 BIGNUM
*t1
, *t2
, *t3
, *t4
, *t5
, *t6
= NULL
;
1500 /* convert p: (X,Y,Z) -> (XZ,Y,Z**3) */
1501 if (!group
->meth
->field_mul(group
, p
->X
, p
->X
, p
->Z
, ctx
)
1502 || !group
->meth
->field_sqr(group
, t1
, p
->Z
, ctx
)
1503 || !group
->meth
->field_mul(group
, p
->Z
, p
->Z
, t1
, ctx
)
1505 || !group
->meth
->field_sqr(group
, t2
, p
->X
, ctx
)
1506 || !group
->meth
->field_sqr(group
, t3
, p
->Z
, ctx
)
1507 || !group
->meth
->field_mul(group
, t4
, t3
, group
->a
, ctx
)
1508 || !BN_mod_sub_quick(t5
, t2
, t4
, group
->field
)
1509 || !BN_mod_add_quick(t2
, t2
, t4
, group
->field
)
1510 || !group
->meth
->field_sqr(group
, t5
, t5
, ctx
)
1511 || !group
->meth
->field_mul(group
, t6
, t3
, group
->b
, ctx
)
1512 || !group
->meth
->field_mul(group
, t1
, p
->X
, p
->Z
, ctx
)
1513 || !group
->meth
->field_mul(group
, t4
, t1
, t6
, ctx
)
1514 || !BN_mod_lshift_quick(t4
, t4
, 3, group
->field
)
1515 /* r->X coord output */
1516 || !BN_mod_sub_quick(r
->X
, t5
, t4
, group
->field
)
1517 || !group
->meth
->field_mul(group
, t1
, t1
, t2
, ctx
)
1518 || !group
->meth
->field_mul(group
, t2
, t3
, t6
, ctx
)
1519 || !BN_mod_add_quick(t1
, t1
, t2
, group
->field
)
1520 /* r->Z coord output */
1521 || !BN_mod_lshift_quick(r
->Z
, t1
, 2, group
->field
)
1522 || !EC_POINT_copy(s
, p
))
1533 * Differential addition-and-doubling using Eq. (9) and (10) from Izu-Takagi
1534 * "A fast parallel elliptic curve multiplication resistant against side channel
1535 * attacks", as described at
1536 * https://hyperelliptic.org/EFD/g1p/auto-shortw-xz.html#ladder-ladd-2002-it-4
1538 int ec_GFp_simple_ladder_step(const EC_GROUP
*group
,
1539 EC_POINT
*r
, EC_POINT
*s
,
1540 EC_POINT
*p
, BN_CTX
*ctx
)
1543 BIGNUM
*t0
, *t1
, *t2
, *t3
, *t4
, *t5
, *t6
, *t7
= NULL
;
1546 t0
= BN_CTX_get(ctx
);
1547 t1
= BN_CTX_get(ctx
);
1548 t2
= BN_CTX_get(ctx
);
1549 t3
= BN_CTX_get(ctx
);
1550 t4
= BN_CTX_get(ctx
);
1551 t5
= BN_CTX_get(ctx
);
1552 t6
= BN_CTX_get(ctx
);
1553 t7
= BN_CTX_get(ctx
);
1556 || !group
->meth
->field_mul(group
, t0
, r
->X
, s
->X
, ctx
)
1557 || !group
->meth
->field_mul(group
, t1
, r
->Z
, s
->Z
, ctx
)
1558 || !group
->meth
->field_mul(group
, t2
, r
->X
, s
->Z
, ctx
)
1559 || !group
->meth
->field_mul(group
, t3
, r
->Z
, s
->X
, ctx
)
1560 || !group
->meth
->field_mul(group
, t4
, group
->a
, t1
, ctx
)
1561 || !BN_mod_add_quick(t0
, t0
, t4
, group
->field
)
1562 || !BN_mod_add_quick(t4
, t3
, t2
, group
->field
)
1563 || !group
->meth
->field_mul(group
, t0
, t4
, t0
, ctx
)
1564 || !group
->meth
->field_sqr(group
, t1
, t1
, ctx
)
1565 || !BN_mod_lshift_quick(t7
, group
->b
, 2, group
->field
)
1566 || !group
->meth
->field_mul(group
, t1
, t7
, t1
, ctx
)
1567 || !BN_mod_lshift1_quick(t0
, t0
, group
->field
)
1568 || !BN_mod_add_quick(t0
, t1
, t0
, group
->field
)
1569 || !BN_mod_sub_quick(t1
, t2
, t3
, group
->field
)
1570 || !group
->meth
->field_sqr(group
, t1
, t1
, ctx
)
1571 || !group
->meth
->field_mul(group
, t3
, t1
, p
->X
, ctx
)
1572 || !group
->meth
->field_mul(group
, t0
, p
->Z
, t0
, ctx
)
1573 /* s->X coord output */
1574 || !BN_mod_sub_quick(s
->X
, t0
, t3
, group
->field
)
1575 /* s->Z coord output */
1576 || !group
->meth
->field_mul(group
, s
->Z
, p
->Z
, t1
, ctx
)
1577 || !group
->meth
->field_sqr(group
, t3
, r
->X
, ctx
)
1578 || !group
->meth
->field_sqr(group
, t2
, r
->Z
, ctx
)
1579 || !group
->meth
->field_mul(group
, t4
, t2
, group
->a
, ctx
)
1580 || !BN_mod_add_quick(t5
, r
->X
, r
->Z
, group
->field
)
1581 || !group
->meth
->field_sqr(group
, t5
, t5
, ctx
)
1582 || !BN_mod_sub_quick(t5
, t5
, t3
, group
->field
)
1583 || !BN_mod_sub_quick(t5
, t5
, t2
, group
->field
)
1584 || !BN_mod_sub_quick(t6
, t3
, t4
, group
->field
)
1585 || !group
->meth
->field_sqr(group
, t6
, t6
, ctx
)
1586 || !group
->meth
->field_mul(group
, t0
, t2
, t5
, ctx
)
1587 || !group
->meth
->field_mul(group
, t0
, t7
, t0
, ctx
)
1588 /* r->X coord output */
1589 || !BN_mod_sub_quick(r
->X
, t6
, t0
, group
->field
)
1590 || !BN_mod_add_quick(t6
, t3
, t4
, group
->field
)
1591 || !group
->meth
->field_sqr(group
, t3
, t2
, ctx
)
1592 || !group
->meth
->field_mul(group
, t7
, t3
, t7
, ctx
)
1593 || !group
->meth
->field_mul(group
, t5
, t5
, t6
, ctx
)
1594 || !BN_mod_lshift1_quick(t5
, t5
, group
->field
)
1595 /* r->Z coord output */
1596 || !BN_mod_add_quick(r
->Z
, t7
, t5
, group
->field
))
1607 * Recovers the y-coordinate of r using Eq. (8) from Brier-Joye, "Weierstrass
1608 * Elliptic Curves and Side-Channel Attacks", modified to work in projective
1609 * coordinates and return r in Jacobian projective coordinates.
1611 * X4 = two*Y1*X2*Z3*Z2*Z1;
1612 * Y4 = two*b*Z3*SQR(Z2*Z1) + Z3*(a*Z2*Z1+X1*X2)*(X1*Z2+X2*Z1) - X3*SQR(X1*Z2-X2*Z1);
1613 * Z4 = two*Y1*Z3*SQR(Z2)*Z1;
1616 * - Z1==0 implies p is at infinity, which would have caused an early exit in
1618 * - Z2==0 implies r is at infinity (handled by the BN_is_zero(r->Z) branch);
1619 * - Z3==0 implies s is at infinity (handled by the BN_is_zero(s->Z) branch);
1620 * - Y1==0 implies p has order 2, so either r or s are infinity and handled by
1621 * one of the BN_is_zero(...) branches.
1623 int ec_GFp_simple_ladder_post(const EC_GROUP
*group
,
1624 EC_POINT
*r
, EC_POINT
*s
,
1625 EC_POINT
*p
, BN_CTX
*ctx
)
1628 BIGNUM
*t0
, *t1
, *t2
, *t3
, *t4
, *t5
, *t6
= NULL
;
1630 if (BN_is_zero(r
->Z
))
1631 return EC_POINT_set_to_infinity(group
, r
);
1633 if (BN_is_zero(s
->Z
)) {
1634 /* (X,Y,Z) -> (XZ,YZ**2,Z) */
1635 if (!group
->meth
->field_mul(group
, r
->X
, p
->X
, p
->Z
, ctx
)
1636 || !group
->meth
->field_sqr(group
, r
->Z
, p
->Z
, ctx
)
1637 || !group
->meth
->field_mul(group
, r
->Y
, p
->Y
, r
->Z
, ctx
)
1638 || !BN_copy(r
->Z
, p
->Z
)
1639 || !EC_POINT_invert(group
, r
, ctx
))
1645 t0
= BN_CTX_get(ctx
);
1646 t1
= BN_CTX_get(ctx
);
1647 t2
= BN_CTX_get(ctx
);
1648 t3
= BN_CTX_get(ctx
);
1649 t4
= BN_CTX_get(ctx
);
1650 t5
= BN_CTX_get(ctx
);
1651 t6
= BN_CTX_get(ctx
);
1654 || !BN_mod_lshift1_quick(t0
, p
->Y
, group
->field
)
1655 || !group
->meth
->field_mul(group
, t1
, r
->X
, p
->Z
, ctx
)
1656 || !group
->meth
->field_mul(group
, t2
, r
->Z
, s
->Z
, ctx
)
1657 || !group
->meth
->field_mul(group
, t2
, t1
, t2
, ctx
)
1658 || !group
->meth
->field_mul(group
, t3
, t2
, t0
, ctx
)
1659 || !group
->meth
->field_mul(group
, t2
, r
->Z
, p
->Z
, ctx
)
1660 || !group
->meth
->field_sqr(group
, t4
, t2
, ctx
)
1661 || !BN_mod_lshift1_quick(t5
, group
->b
, group
->field
)
1662 || !group
->meth
->field_mul(group
, t4
, t4
, t5
, ctx
)
1663 || !group
->meth
->field_mul(group
, t6
, t2
, group
->a
, ctx
)
1664 || !group
->meth
->field_mul(group
, t5
, r
->X
, p
->X
, ctx
)
1665 || !BN_mod_add_quick(t5
, t6
, t5
, group
->field
)
1666 || !group
->meth
->field_mul(group
, t6
, r
->Z
, p
->X
, ctx
)
1667 || !BN_mod_add_quick(t2
, t6
, t1
, group
->field
)
1668 || !group
->meth
->field_mul(group
, t5
, t5
, t2
, ctx
)
1669 || !BN_mod_sub_quick(t6
, t6
, t1
, group
->field
)
1670 || !group
->meth
->field_sqr(group
, t6
, t6
, ctx
)
1671 || !group
->meth
->field_mul(group
, t6
, t6
, s
->X
, ctx
)
1672 || !BN_mod_add_quick(t4
, t5
, t4
, group
->field
)
1673 || !group
->meth
->field_mul(group
, t4
, t4
, s
->Z
, ctx
)
1674 || !BN_mod_sub_quick(t4
, t4
, t6
, group
->field
)
1675 || !group
->meth
->field_sqr(group
, t5
, r
->Z
, ctx
)
1676 || !group
->meth
->field_mul(group
, r
->Z
, p
->Z
, s
->Z
, ctx
)
1677 || !group
->meth
->field_mul(group
, r
->Z
, t5
, r
->Z
, ctx
)
1678 || !group
->meth
->field_mul(group
, r
->Z
, r
->Z
, t0
, ctx
)
1679 /* t3 := X, t4 := Y */
1680 /* (X,Y,Z) -> (XZ,YZ**2,Z) */
1681 || !group
->meth
->field_mul(group
, r
->X
, t3
, r
->Z
, ctx
)
1682 || !group
->meth
->field_sqr(group
, t3
, r
->Z
, ctx
)
1683 || !group
->meth
->field_mul(group
, r
->Y
, t4
, t3
, ctx
))