2 * Copyright 2001-2021 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
12 * ECDSA low-level APIs are deprecated for public use, but still ok for
15 #include "internal/deprecated.h"
17 #include <openssl/err.h>
18 #include <openssl/symhacks.h>
22 const EC_METHOD
*EC_GFp_simple_method(void)
24 static const EC_METHOD ret
= {
26 NID_X9_62_prime_field
,
27 ossl_ec_GFp_simple_group_init
,
28 ossl_ec_GFp_simple_group_finish
,
29 ossl_ec_GFp_simple_group_clear_finish
,
30 ossl_ec_GFp_simple_group_copy
,
31 ossl_ec_GFp_simple_group_set_curve
,
32 ossl_ec_GFp_simple_group_get_curve
,
33 ossl_ec_GFp_simple_group_get_degree
,
34 ossl_ec_group_simple_order_bits
,
35 ossl_ec_GFp_simple_group_check_discriminant
,
36 ossl_ec_GFp_simple_point_init
,
37 ossl_ec_GFp_simple_point_finish
,
38 ossl_ec_GFp_simple_point_clear_finish
,
39 ossl_ec_GFp_simple_point_copy
,
40 ossl_ec_GFp_simple_point_set_to_infinity
,
41 ossl_ec_GFp_simple_point_set_affine_coordinates
,
42 ossl_ec_GFp_simple_point_get_affine_coordinates
,
44 ossl_ec_GFp_simple_add
,
45 ossl_ec_GFp_simple_dbl
,
46 ossl_ec_GFp_simple_invert
,
47 ossl_ec_GFp_simple_is_at_infinity
,
48 ossl_ec_GFp_simple_is_on_curve
,
49 ossl_ec_GFp_simple_cmp
,
50 ossl_ec_GFp_simple_make_affine
,
51 ossl_ec_GFp_simple_points_make_affine
,
53 0 /* precompute_mult */ ,
54 0 /* have_precompute_mult */ ,
55 ossl_ec_GFp_simple_field_mul
,
56 ossl_ec_GFp_simple_field_sqr
,
58 ossl_ec_GFp_simple_field_inv
,
59 0 /* field_encode */ ,
60 0 /* field_decode */ ,
61 0, /* field_set_to_one */
62 ossl_ec_key_simple_priv2oct
,
63 ossl_ec_key_simple_oct2priv
,
65 ossl_ec_key_simple_generate_key
,
66 ossl_ec_key_simple_check_key
,
67 ossl_ec_key_simple_generate_public_key
,
70 ossl_ecdh_simple_compute_key
,
71 ossl_ecdsa_simple_sign_setup
,
72 ossl_ecdsa_simple_sign_sig
,
73 ossl_ecdsa_simple_verify_sig
,
74 0, /* field_inverse_mod_ord */
75 ossl_ec_GFp_simple_blind_coordinates
,
76 ossl_ec_GFp_simple_ladder_pre
,
77 ossl_ec_GFp_simple_ladder_step
,
78 ossl_ec_GFp_simple_ladder_post
85 * Most method functions in this file are designed to work with
86 * non-trivial representations of field elements if necessary
87 * (see ecp_mont.c): while standard modular addition and subtraction
88 * are used, the field_mul and field_sqr methods will be used for
89 * multiplication, and field_encode and field_decode (if defined)
90 * will be used for converting between representations.
92 * Functions ec_GFp_simple_points_make_affine() and
93 * ec_GFp_simple_point_get_affine_coordinates() specifically assume
94 * that if a non-trivial representation is used, it is a Montgomery
95 * representation (i.e. 'encoding' means multiplying by some factor R).
98 int ossl_ec_GFp_simple_group_init(EC_GROUP
*group
)
100 group
->field
= BN_new();
103 if (group
->field
== NULL
|| group
->a
== NULL
|| group
->b
== NULL
) {
104 BN_free(group
->field
);
109 group
->a_is_minus3
= 0;
113 void ossl_ec_GFp_simple_group_finish(EC_GROUP
*group
)
115 BN_free(group
->field
);
120 void ossl_ec_GFp_simple_group_clear_finish(EC_GROUP
*group
)
122 BN_clear_free(group
->field
);
123 BN_clear_free(group
->a
);
124 BN_clear_free(group
->b
);
127 int ossl_ec_GFp_simple_group_copy(EC_GROUP
*dest
, const EC_GROUP
*src
)
129 if (!BN_copy(dest
->field
, src
->field
))
131 if (!BN_copy(dest
->a
, src
->a
))
133 if (!BN_copy(dest
->b
, src
->b
))
136 dest
->a_is_minus3
= src
->a_is_minus3
;
141 int ossl_ec_GFp_simple_group_set_curve(EC_GROUP
*group
,
142 const BIGNUM
*p
, const BIGNUM
*a
,
143 const BIGNUM
*b
, BN_CTX
*ctx
)
146 BN_CTX
*new_ctx
= NULL
;
149 /* p must be a prime > 3 */
150 if (BN_num_bits(p
) <= 2 || !BN_is_odd(p
)) {
151 ERR_raise(ERR_LIB_EC
, EC_R_INVALID_FIELD
);
156 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
162 tmp_a
= BN_CTX_get(ctx
);
167 if (!BN_copy(group
->field
, p
))
169 BN_set_negative(group
->field
, 0);
172 if (!BN_nnmod(tmp_a
, a
, p
, ctx
))
174 if (group
->meth
->field_encode
) {
175 if (!group
->meth
->field_encode(group
, group
->a
, tmp_a
, ctx
))
177 } else if (!BN_copy(group
->a
, tmp_a
))
181 if (!BN_nnmod(group
->b
, b
, p
, ctx
))
183 if (group
->meth
->field_encode
)
184 if (!group
->meth
->field_encode(group
, group
->b
, group
->b
, ctx
))
187 /* group->a_is_minus3 */
188 if (!BN_add_word(tmp_a
, 3))
190 group
->a_is_minus3
= (0 == BN_cmp(tmp_a
, group
->field
));
196 BN_CTX_free(new_ctx
);
200 int ossl_ec_GFp_simple_group_get_curve(const EC_GROUP
*group
, BIGNUM
*p
,
201 BIGNUM
*a
, BIGNUM
*b
, BN_CTX
*ctx
)
204 BN_CTX
*new_ctx
= NULL
;
207 if (!BN_copy(p
, group
->field
))
211 if (a
!= NULL
|| b
!= NULL
) {
212 if (group
->meth
->field_decode
) {
214 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
219 if (!group
->meth
->field_decode(group
, a
, group
->a
, ctx
))
223 if (!group
->meth
->field_decode(group
, b
, group
->b
, ctx
))
228 if (!BN_copy(a
, group
->a
))
232 if (!BN_copy(b
, group
->b
))
241 BN_CTX_free(new_ctx
);
245 int ossl_ec_GFp_simple_group_get_degree(const EC_GROUP
*group
)
247 return BN_num_bits(group
->field
);
250 int ossl_ec_GFp_simple_group_check_discriminant(const EC_GROUP
*group
,
254 BIGNUM
*a
, *b
, *order
, *tmp_1
, *tmp_2
;
255 const BIGNUM
*p
= group
->field
;
256 BN_CTX
*new_ctx
= NULL
;
259 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
261 ERR_raise(ERR_LIB_EC
, ERR_R_BN_LIB
);
268 tmp_1
= BN_CTX_get(ctx
);
269 tmp_2
= BN_CTX_get(ctx
);
270 order
= BN_CTX_get(ctx
);
274 if (group
->meth
->field_decode
) {
275 if (!group
->meth
->field_decode(group
, a
, group
->a
, ctx
))
277 if (!group
->meth
->field_decode(group
, b
, group
->b
, ctx
))
280 if (!BN_copy(a
, group
->a
))
282 if (!BN_copy(b
, group
->b
))
287 * check the discriminant:
288 * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p)
294 } else if (!BN_is_zero(b
)) {
295 if (!BN_mod_sqr(tmp_1
, a
, p
, ctx
))
297 if (!BN_mod_mul(tmp_2
, tmp_1
, a
, p
, ctx
))
299 if (!BN_lshift(tmp_1
, tmp_2
, 2))
303 if (!BN_mod_sqr(tmp_2
, b
, p
, ctx
))
305 if (!BN_mul_word(tmp_2
, 27))
309 if (!BN_mod_add(a
, tmp_1
, tmp_2
, p
, ctx
))
318 BN_CTX_free(new_ctx
);
322 int ossl_ec_GFp_simple_point_init(EC_POINT
*point
)
329 if (point
->X
== NULL
|| point
->Y
== NULL
|| point
->Z
== NULL
) {
338 void ossl_ec_GFp_simple_point_finish(EC_POINT
*point
)
345 void ossl_ec_GFp_simple_point_clear_finish(EC_POINT
*point
)
347 BN_clear_free(point
->X
);
348 BN_clear_free(point
->Y
);
349 BN_clear_free(point
->Z
);
353 int ossl_ec_GFp_simple_point_copy(EC_POINT
*dest
, const EC_POINT
*src
)
355 if (!BN_copy(dest
->X
, src
->X
))
357 if (!BN_copy(dest
->Y
, src
->Y
))
359 if (!BN_copy(dest
->Z
, src
->Z
))
361 dest
->Z_is_one
= src
->Z_is_one
;
362 dest
->curve_name
= src
->curve_name
;
367 int ossl_ec_GFp_simple_point_set_to_infinity(const EC_GROUP
*group
,
375 int ossl_ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP
*group
,
382 BN_CTX
*new_ctx
= NULL
;
386 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
392 if (!BN_nnmod(point
->X
, x
, group
->field
, ctx
))
394 if (group
->meth
->field_encode
) {
395 if (!group
->meth
->field_encode(group
, point
->X
, point
->X
, ctx
))
401 if (!BN_nnmod(point
->Y
, y
, group
->field
, ctx
))
403 if (group
->meth
->field_encode
) {
404 if (!group
->meth
->field_encode(group
, point
->Y
, point
->Y
, ctx
))
412 if (!BN_nnmod(point
->Z
, z
, group
->field
, ctx
))
414 Z_is_one
= BN_is_one(point
->Z
);
415 if (group
->meth
->field_encode
) {
416 if (Z_is_one
&& (group
->meth
->field_set_to_one
!= 0)) {
417 if (!group
->meth
->field_set_to_one(group
, point
->Z
, ctx
))
421 meth
->field_encode(group
, point
->Z
, point
->Z
, ctx
))
425 point
->Z_is_one
= Z_is_one
;
431 BN_CTX_free(new_ctx
);
435 int ossl_ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP
*group
,
436 const EC_POINT
*point
,
437 BIGNUM
*x
, BIGNUM
*y
,
438 BIGNUM
*z
, BN_CTX
*ctx
)
440 BN_CTX
*new_ctx
= NULL
;
443 if (group
->meth
->field_decode
!= 0) {
445 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
451 if (!group
->meth
->field_decode(group
, x
, point
->X
, ctx
))
455 if (!group
->meth
->field_decode(group
, y
, point
->Y
, ctx
))
459 if (!group
->meth
->field_decode(group
, z
, point
->Z
, ctx
))
464 if (!BN_copy(x
, point
->X
))
468 if (!BN_copy(y
, point
->Y
))
472 if (!BN_copy(z
, point
->Z
))
480 BN_CTX_free(new_ctx
);
484 int ossl_ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP
*group
,
487 const BIGNUM
*y
, BN_CTX
*ctx
)
489 if (x
== NULL
|| y
== NULL
) {
491 * unlike for projective coordinates, we do not tolerate this
493 ERR_raise(ERR_LIB_EC
, ERR_R_PASSED_NULL_PARAMETER
);
497 return EC_POINT_set_Jprojective_coordinates_GFp(group
, point
, x
, y
,
498 BN_value_one(), ctx
);
501 int ossl_ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP
*group
,
502 const EC_POINT
*point
,
503 BIGNUM
*x
, BIGNUM
*y
,
506 BN_CTX
*new_ctx
= NULL
;
507 BIGNUM
*Z
, *Z_1
, *Z_2
, *Z_3
;
511 if (EC_POINT_is_at_infinity(group
, point
)) {
512 ERR_raise(ERR_LIB_EC
, EC_R_POINT_AT_INFINITY
);
517 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
524 Z_1
= BN_CTX_get(ctx
);
525 Z_2
= BN_CTX_get(ctx
);
526 Z_3
= BN_CTX_get(ctx
);
530 /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */
532 if (group
->meth
->field_decode
) {
533 if (!group
->meth
->field_decode(group
, Z
, point
->Z
, ctx
))
541 if (group
->meth
->field_decode
) {
543 if (!group
->meth
->field_decode(group
, x
, point
->X
, ctx
))
547 if (!group
->meth
->field_decode(group
, y
, point
->Y
, ctx
))
552 if (!BN_copy(x
, point
->X
))
556 if (!BN_copy(y
, point
->Y
))
561 if (!group
->meth
->field_inv(group
, Z_1
, Z_
, ctx
)) {
562 ERR_raise(ERR_LIB_EC
, ERR_R_BN_LIB
);
566 if (group
->meth
->field_encode
== 0) {
567 /* field_sqr works on standard representation */
568 if (!group
->meth
->field_sqr(group
, Z_2
, Z_1
, ctx
))
571 if (!BN_mod_sqr(Z_2
, Z_1
, group
->field
, ctx
))
577 * in the Montgomery case, field_mul will cancel out Montgomery
580 if (!group
->meth
->field_mul(group
, x
, point
->X
, Z_2
, ctx
))
585 if (group
->meth
->field_encode
== 0) {
587 * field_mul works on standard representation
589 if (!group
->meth
->field_mul(group
, Z_3
, Z_2
, Z_1
, ctx
))
592 if (!BN_mod_mul(Z_3
, Z_2
, Z_1
, group
->field
, ctx
))
597 * in the Montgomery case, field_mul will cancel out Montgomery
600 if (!group
->meth
->field_mul(group
, y
, point
->Y
, Z_3
, ctx
))
609 BN_CTX_free(new_ctx
);
613 int ossl_ec_GFp_simple_add(const EC_GROUP
*group
, EC_POINT
*r
, const EC_POINT
*a
,
614 const EC_POINT
*b
, BN_CTX
*ctx
)
616 int (*field_mul
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*,
617 const BIGNUM
*, BN_CTX
*);
618 int (*field_sqr
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*, BN_CTX
*);
620 BN_CTX
*new_ctx
= NULL
;
621 BIGNUM
*n0
, *n1
, *n2
, *n3
, *n4
, *n5
, *n6
;
625 return EC_POINT_dbl(group
, r
, a
, ctx
);
626 if (EC_POINT_is_at_infinity(group
, a
))
627 return EC_POINT_copy(r
, b
);
628 if (EC_POINT_is_at_infinity(group
, b
))
629 return EC_POINT_copy(r
, a
);
631 field_mul
= group
->meth
->field_mul
;
632 field_sqr
= group
->meth
->field_sqr
;
636 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
642 n0
= BN_CTX_get(ctx
);
643 n1
= BN_CTX_get(ctx
);
644 n2
= BN_CTX_get(ctx
);
645 n3
= BN_CTX_get(ctx
);
646 n4
= BN_CTX_get(ctx
);
647 n5
= BN_CTX_get(ctx
);
648 n6
= BN_CTX_get(ctx
);
653 * Note that in this function we must not read components of 'a' or 'b'
654 * once we have written the corresponding components of 'r'. ('r' might
655 * be one of 'a' or 'b'.)
660 if (!BN_copy(n1
, a
->X
))
662 if (!BN_copy(n2
, a
->Y
))
667 if (!field_sqr(group
, n0
, b
->Z
, ctx
))
669 if (!field_mul(group
, n1
, a
->X
, n0
, ctx
))
671 /* n1 = X_a * Z_b^2 */
673 if (!field_mul(group
, n0
, n0
, b
->Z
, ctx
))
675 if (!field_mul(group
, n2
, a
->Y
, n0
, ctx
))
677 /* n2 = Y_a * Z_b^3 */
682 if (!BN_copy(n3
, b
->X
))
684 if (!BN_copy(n4
, b
->Y
))
689 if (!field_sqr(group
, n0
, a
->Z
, ctx
))
691 if (!field_mul(group
, n3
, b
->X
, n0
, ctx
))
693 /* n3 = X_b * Z_a^2 */
695 if (!field_mul(group
, n0
, n0
, a
->Z
, ctx
))
697 if (!field_mul(group
, n4
, b
->Y
, n0
, ctx
))
699 /* n4 = Y_b * Z_a^3 */
703 if (!BN_mod_sub_quick(n5
, n1
, n3
, p
))
705 if (!BN_mod_sub_quick(n6
, n2
, n4
, p
))
710 if (BN_is_zero(n5
)) {
711 if (BN_is_zero(n6
)) {
712 /* a is the same point as b */
714 ret
= EC_POINT_dbl(group
, r
, a
, ctx
);
718 /* a is the inverse of b */
727 if (!BN_mod_add_quick(n1
, n1
, n3
, p
))
729 if (!BN_mod_add_quick(n2
, n2
, n4
, p
))
735 if (a
->Z_is_one
&& b
->Z_is_one
) {
736 if (!BN_copy(r
->Z
, n5
))
740 if (!BN_copy(n0
, b
->Z
))
742 } else if (b
->Z_is_one
) {
743 if (!BN_copy(n0
, a
->Z
))
746 if (!field_mul(group
, n0
, a
->Z
, b
->Z
, ctx
))
749 if (!field_mul(group
, r
->Z
, n0
, n5
, ctx
))
753 /* Z_r = Z_a * Z_b * n5 */
756 if (!field_sqr(group
, n0
, n6
, ctx
))
758 if (!field_sqr(group
, n4
, n5
, ctx
))
760 if (!field_mul(group
, n3
, n1
, n4
, ctx
))
762 if (!BN_mod_sub_quick(r
->X
, n0
, n3
, p
))
764 /* X_r = n6^2 - n5^2 * 'n7' */
767 if (!BN_mod_lshift1_quick(n0
, r
->X
, p
))
769 if (!BN_mod_sub_quick(n0
, n3
, n0
, p
))
771 /* n9 = n5^2 * 'n7' - 2 * X_r */
774 if (!field_mul(group
, n0
, n0
, n6
, ctx
))
776 if (!field_mul(group
, n5
, n4
, n5
, ctx
))
777 goto end
; /* now n5 is n5^3 */
778 if (!field_mul(group
, n1
, n2
, n5
, ctx
))
780 if (!BN_mod_sub_quick(n0
, n0
, n1
, p
))
783 if (!BN_add(n0
, n0
, p
))
785 /* now 0 <= n0 < 2*p, and n0 is even */
786 if (!BN_rshift1(r
->Y
, n0
))
788 /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
794 BN_CTX_free(new_ctx
);
798 int ossl_ec_GFp_simple_dbl(const EC_GROUP
*group
, EC_POINT
*r
, const EC_POINT
*a
,
801 int (*field_mul
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*,
802 const BIGNUM
*, BN_CTX
*);
803 int (*field_sqr
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*, BN_CTX
*);
805 BN_CTX
*new_ctx
= NULL
;
806 BIGNUM
*n0
, *n1
, *n2
, *n3
;
809 if (EC_POINT_is_at_infinity(group
, a
)) {
815 field_mul
= group
->meth
->field_mul
;
816 field_sqr
= group
->meth
->field_sqr
;
820 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
826 n0
= BN_CTX_get(ctx
);
827 n1
= BN_CTX_get(ctx
);
828 n2
= BN_CTX_get(ctx
);
829 n3
= BN_CTX_get(ctx
);
834 * Note that in this function we must not read components of 'a' once we
835 * have written the corresponding components of 'r'. ('r' might the same
841 if (!field_sqr(group
, n0
, a
->X
, ctx
))
843 if (!BN_mod_lshift1_quick(n1
, n0
, p
))
845 if (!BN_mod_add_quick(n0
, n0
, n1
, p
))
847 if (!BN_mod_add_quick(n1
, n0
, group
->a
, p
))
849 /* n1 = 3 * X_a^2 + a_curve */
850 } else if (group
->a_is_minus3
) {
851 if (!field_sqr(group
, n1
, a
->Z
, ctx
))
853 if (!BN_mod_add_quick(n0
, a
->X
, n1
, p
))
855 if (!BN_mod_sub_quick(n2
, a
->X
, n1
, p
))
857 if (!field_mul(group
, n1
, n0
, n2
, ctx
))
859 if (!BN_mod_lshift1_quick(n0
, n1
, p
))
861 if (!BN_mod_add_quick(n1
, n0
, n1
, p
))
864 * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
865 * = 3 * X_a^2 - 3 * Z_a^4
868 if (!field_sqr(group
, n0
, a
->X
, ctx
))
870 if (!BN_mod_lshift1_quick(n1
, n0
, p
))
872 if (!BN_mod_add_quick(n0
, n0
, n1
, p
))
874 if (!field_sqr(group
, n1
, a
->Z
, ctx
))
876 if (!field_sqr(group
, n1
, n1
, ctx
))
878 if (!field_mul(group
, n1
, n1
, group
->a
, ctx
))
880 if (!BN_mod_add_quick(n1
, n1
, n0
, p
))
882 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
887 if (!BN_copy(n0
, a
->Y
))
890 if (!field_mul(group
, n0
, a
->Y
, a
->Z
, ctx
))
893 if (!BN_mod_lshift1_quick(r
->Z
, n0
, p
))
896 /* Z_r = 2 * Y_a * Z_a */
899 if (!field_sqr(group
, n3
, a
->Y
, ctx
))
901 if (!field_mul(group
, n2
, a
->X
, n3
, ctx
))
903 if (!BN_mod_lshift_quick(n2
, n2
, 2, p
))
905 /* n2 = 4 * X_a * Y_a^2 */
908 if (!BN_mod_lshift1_quick(n0
, n2
, p
))
910 if (!field_sqr(group
, r
->X
, n1
, ctx
))
912 if (!BN_mod_sub_quick(r
->X
, r
->X
, n0
, p
))
914 /* X_r = n1^2 - 2 * n2 */
917 if (!field_sqr(group
, n0
, n3
, ctx
))
919 if (!BN_mod_lshift_quick(n3
, n0
, 3, p
))
924 if (!BN_mod_sub_quick(n0
, n2
, r
->X
, p
))
926 if (!field_mul(group
, n0
, n1
, n0
, ctx
))
928 if (!BN_mod_sub_quick(r
->Y
, n0
, n3
, p
))
930 /* Y_r = n1 * (n2 - X_r) - n3 */
936 BN_CTX_free(new_ctx
);
940 int ossl_ec_GFp_simple_invert(const EC_GROUP
*group
, EC_POINT
*point
,
943 if (EC_POINT_is_at_infinity(group
, point
) || BN_is_zero(point
->Y
))
944 /* point is its own inverse */
947 return BN_usub(point
->Y
, group
->field
, point
->Y
);
950 int ossl_ec_GFp_simple_is_at_infinity(const EC_GROUP
*group
,
951 const EC_POINT
*point
)
953 return BN_is_zero(point
->Z
);
956 int ossl_ec_GFp_simple_is_on_curve(const EC_GROUP
*group
, const EC_POINT
*point
,
959 int (*field_mul
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*,
960 const BIGNUM
*, BN_CTX
*);
961 int (*field_sqr
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*, BN_CTX
*);
963 BN_CTX
*new_ctx
= NULL
;
964 BIGNUM
*rh
, *tmp
, *Z4
, *Z6
;
967 if (EC_POINT_is_at_infinity(group
, point
))
970 field_mul
= group
->meth
->field_mul
;
971 field_sqr
= group
->meth
->field_sqr
;
975 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
981 rh
= BN_CTX_get(ctx
);
982 tmp
= BN_CTX_get(ctx
);
983 Z4
= BN_CTX_get(ctx
);
984 Z6
= BN_CTX_get(ctx
);
989 * We have a curve defined by a Weierstrass equation
990 * y^2 = x^3 + a*x + b.
991 * The point to consider is given in Jacobian projective coordinates
992 * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3).
993 * Substituting this and multiplying by Z^6 transforms the above equation into
994 * Y^2 = X^3 + a*X*Z^4 + b*Z^6.
995 * To test this, we add up the right-hand side in 'rh'.
999 if (!field_sqr(group
, rh
, point
->X
, ctx
))
1002 if (!point
->Z_is_one
) {
1003 if (!field_sqr(group
, tmp
, point
->Z
, ctx
))
1005 if (!field_sqr(group
, Z4
, tmp
, ctx
))
1007 if (!field_mul(group
, Z6
, Z4
, tmp
, ctx
))
1010 /* rh := (rh + a*Z^4)*X */
1011 if (group
->a_is_minus3
) {
1012 if (!BN_mod_lshift1_quick(tmp
, Z4
, p
))
1014 if (!BN_mod_add_quick(tmp
, tmp
, Z4
, p
))
1016 if (!BN_mod_sub_quick(rh
, rh
, tmp
, p
))
1018 if (!field_mul(group
, rh
, rh
, point
->X
, ctx
))
1021 if (!field_mul(group
, tmp
, Z4
, group
->a
, ctx
))
1023 if (!BN_mod_add_quick(rh
, rh
, tmp
, p
))
1025 if (!field_mul(group
, rh
, rh
, point
->X
, ctx
))
1029 /* rh := rh + b*Z^6 */
1030 if (!field_mul(group
, tmp
, group
->b
, Z6
, ctx
))
1032 if (!BN_mod_add_quick(rh
, rh
, tmp
, p
))
1035 /* point->Z_is_one */
1037 /* rh := (rh + a)*X */
1038 if (!BN_mod_add_quick(rh
, rh
, group
->a
, p
))
1040 if (!field_mul(group
, rh
, rh
, point
->X
, ctx
))
1043 if (!BN_mod_add_quick(rh
, rh
, group
->b
, p
))
1048 if (!field_sqr(group
, tmp
, point
->Y
, ctx
))
1051 ret
= (0 == BN_ucmp(tmp
, rh
));
1055 BN_CTX_free(new_ctx
);
1059 int ossl_ec_GFp_simple_cmp(const EC_GROUP
*group
, const EC_POINT
*a
,
1060 const EC_POINT
*b
, BN_CTX
*ctx
)
1065 * 0 equal (in affine coordinates)
1069 int (*field_mul
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*,
1070 const BIGNUM
*, BN_CTX
*);
1071 int (*field_sqr
) (const EC_GROUP
*, BIGNUM
*, const BIGNUM
*, BN_CTX
*);
1072 BN_CTX
*new_ctx
= NULL
;
1073 BIGNUM
*tmp1
, *tmp2
, *Za23
, *Zb23
;
1074 const BIGNUM
*tmp1_
, *tmp2_
;
1077 if (EC_POINT_is_at_infinity(group
, a
)) {
1078 return EC_POINT_is_at_infinity(group
, b
) ? 0 : 1;
1081 if (EC_POINT_is_at_infinity(group
, b
))
1084 if (a
->Z_is_one
&& b
->Z_is_one
) {
1085 return ((BN_cmp(a
->X
, b
->X
) == 0) && BN_cmp(a
->Y
, b
->Y
) == 0) ? 0 : 1;
1088 field_mul
= group
->meth
->field_mul
;
1089 field_sqr
= group
->meth
->field_sqr
;
1092 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
1098 tmp1
= BN_CTX_get(ctx
);
1099 tmp2
= BN_CTX_get(ctx
);
1100 Za23
= BN_CTX_get(ctx
);
1101 Zb23
= BN_CTX_get(ctx
);
1106 * We have to decide whether
1107 * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
1108 * or equivalently, whether
1109 * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
1113 if (!field_sqr(group
, Zb23
, b
->Z
, ctx
))
1115 if (!field_mul(group
, tmp1
, a
->X
, Zb23
, ctx
))
1121 if (!field_sqr(group
, Za23
, a
->Z
, ctx
))
1123 if (!field_mul(group
, tmp2
, b
->X
, Za23
, ctx
))
1129 /* compare X_a*Z_b^2 with X_b*Z_a^2 */
1130 if (BN_cmp(tmp1_
, tmp2_
) != 0) {
1131 ret
= 1; /* points differ */
1136 if (!field_mul(group
, Zb23
, Zb23
, b
->Z
, ctx
))
1138 if (!field_mul(group
, tmp1
, a
->Y
, Zb23
, ctx
))
1144 if (!field_mul(group
, Za23
, Za23
, a
->Z
, ctx
))
1146 if (!field_mul(group
, tmp2
, b
->Y
, Za23
, ctx
))
1152 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */
1153 if (BN_cmp(tmp1_
, tmp2_
) != 0) {
1154 ret
= 1; /* points differ */
1158 /* points are equal */
1163 BN_CTX_free(new_ctx
);
1167 int ossl_ec_GFp_simple_make_affine(const EC_GROUP
*group
, EC_POINT
*point
,
1170 BN_CTX
*new_ctx
= NULL
;
1174 if (point
->Z_is_one
|| EC_POINT_is_at_infinity(group
, point
))
1178 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
1184 x
= BN_CTX_get(ctx
);
1185 y
= BN_CTX_get(ctx
);
1189 if (!EC_POINT_get_affine_coordinates(group
, point
, x
, y
, ctx
))
1191 if (!EC_POINT_set_affine_coordinates(group
, point
, x
, y
, ctx
))
1193 if (!point
->Z_is_one
) {
1194 ERR_raise(ERR_LIB_EC
, ERR_R_INTERNAL_ERROR
);
1202 BN_CTX_free(new_ctx
);
1206 int ossl_ec_GFp_simple_points_make_affine(const EC_GROUP
*group
, size_t num
,
1207 EC_POINT
*points
[], BN_CTX
*ctx
)
1209 BN_CTX
*new_ctx
= NULL
;
1210 BIGNUM
*tmp
, *tmp_Z
;
1211 BIGNUM
**prod_Z
= NULL
;
1219 ctx
= new_ctx
= BN_CTX_new_ex(group
->libctx
);
1225 tmp
= BN_CTX_get(ctx
);
1226 tmp_Z
= BN_CTX_get(ctx
);
1230 prod_Z
= OPENSSL_malloc(num
* sizeof(prod_Z
[0]));
1233 for (i
= 0; i
< num
; i
++) {
1234 prod_Z
[i
] = BN_new();
1235 if (prod_Z
[i
] == NULL
)
1240 * Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z,
1241 * skipping any zero-valued inputs (pretend that they're 1).
1244 if (!BN_is_zero(points
[0]->Z
)) {
1245 if (!BN_copy(prod_Z
[0], points
[0]->Z
))
1248 if (group
->meth
->field_set_to_one
!= 0) {
1249 if (!group
->meth
->field_set_to_one(group
, prod_Z
[0], ctx
))
1252 if (!BN_one(prod_Z
[0]))
1257 for (i
= 1; i
< num
; i
++) {
1258 if (!BN_is_zero(points
[i
]->Z
)) {
1260 meth
->field_mul(group
, prod_Z
[i
], prod_Z
[i
- 1], points
[i
]->Z
,
1264 if (!BN_copy(prod_Z
[i
], prod_Z
[i
- 1]))
1270 * Now use a single explicit inversion to replace every non-zero
1271 * points[i]->Z by its inverse.
1274 if (!group
->meth
->field_inv(group
, tmp
, prod_Z
[num
- 1], ctx
)) {
1275 ERR_raise(ERR_LIB_EC
, ERR_R_BN_LIB
);
1278 if (group
->meth
->field_encode
!= 0) {
1280 * In the Montgomery case, we just turned R*H (representing H) into
1281 * 1/(R*H), but we need R*(1/H) (representing 1/H); i.e. we need to
1282 * multiply by the Montgomery factor twice.
1284 if (!group
->meth
->field_encode(group
, tmp
, tmp
, ctx
))
1286 if (!group
->meth
->field_encode(group
, tmp
, tmp
, ctx
))
1290 for (i
= num
- 1; i
> 0; --i
) {
1292 * Loop invariant: tmp is the product of the inverses of points[0]->Z
1293 * .. points[i]->Z (zero-valued inputs skipped).
1295 if (!BN_is_zero(points
[i
]->Z
)) {
1297 * Set tmp_Z to the inverse of points[i]->Z (as product of Z
1298 * inverses 0 .. i, Z values 0 .. i - 1).
1301 meth
->field_mul(group
, tmp_Z
, prod_Z
[i
- 1], tmp
, ctx
))
1304 * Update tmp to satisfy the loop invariant for i - 1.
1306 if (!group
->meth
->field_mul(group
, tmp
, tmp
, points
[i
]->Z
, ctx
))
1308 /* Replace points[i]->Z by its inverse. */
1309 if (!BN_copy(points
[i
]->Z
, tmp_Z
))
1314 if (!BN_is_zero(points
[0]->Z
)) {
1315 /* Replace points[0]->Z by its inverse. */
1316 if (!BN_copy(points
[0]->Z
, tmp
))
1320 /* Finally, fix up the X and Y coordinates for all points. */
1322 for (i
= 0; i
< num
; i
++) {
1323 EC_POINT
*p
= points
[i
];
1325 if (!BN_is_zero(p
->Z
)) {
1326 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */
1328 if (!group
->meth
->field_sqr(group
, tmp
, p
->Z
, ctx
))
1330 if (!group
->meth
->field_mul(group
, p
->X
, p
->X
, tmp
, ctx
))
1333 if (!group
->meth
->field_mul(group
, tmp
, tmp
, p
->Z
, ctx
))
1335 if (!group
->meth
->field_mul(group
, p
->Y
, p
->Y
, tmp
, ctx
))
1338 if (group
->meth
->field_set_to_one
!= 0) {
1339 if (!group
->meth
->field_set_to_one(group
, p
->Z
, ctx
))
1353 BN_CTX_free(new_ctx
);
1354 if (prod_Z
!= NULL
) {
1355 for (i
= 0; i
< num
; i
++) {
1356 if (prod_Z
[i
] == NULL
)
1358 BN_clear_free(prod_Z
[i
]);
1360 OPENSSL_free(prod_Z
);
1365 int ossl_ec_GFp_simple_field_mul(const EC_GROUP
*group
, BIGNUM
*r
, const BIGNUM
*a
,
1366 const BIGNUM
*b
, BN_CTX
*ctx
)
1368 return BN_mod_mul(r
, a
, b
, group
->field
, ctx
);
1371 int ossl_ec_GFp_simple_field_sqr(const EC_GROUP
*group
, BIGNUM
*r
, const BIGNUM
*a
,
1374 return BN_mod_sqr(r
, a
, group
->field
, ctx
);
1378 * Computes the multiplicative inverse of a in GF(p), storing the result in r.
1379 * If a is zero (or equivalent), you'll get an EC_R_CANNOT_INVERT error.
1380 * Since we don't have a Mont structure here, SCA hardening is with blinding.
1381 * NB: "a" must be in _decoded_ form. (i.e. field_decode must precede.)
1383 int ossl_ec_GFp_simple_field_inv(const EC_GROUP
*group
, BIGNUM
*r
,
1384 const BIGNUM
*a
, BN_CTX
*ctx
)
1387 BN_CTX
*new_ctx
= NULL
;
1391 && (ctx
= new_ctx
= BN_CTX_secure_new_ex(group
->libctx
)) == NULL
)
1395 if ((e
= BN_CTX_get(ctx
)) == NULL
)
1399 if (!BN_priv_rand_range_ex(e
, group
->field
, 0, ctx
))
1401 } while (BN_is_zero(e
));
1404 if (!group
->meth
->field_mul(group
, r
, a
, e
, ctx
))
1406 /* r := 1/(a * e) */
1407 if (!BN_mod_inverse(r
, r
, group
->field
, ctx
)) {
1408 ERR_raise(ERR_LIB_EC
, EC_R_CANNOT_INVERT
);
1411 /* r := e/(a * e) = 1/a */
1412 if (!group
->meth
->field_mul(group
, r
, r
, e
, ctx
))
1419 BN_CTX_free(new_ctx
);
1424 * Apply randomization of EC point projective coordinates:
1426 * (X, Y, Z) = (lambda^2*X, lambda^3*Y, lambda*Z)
1427 * lambda = [1, group->field)
1430 int ossl_ec_GFp_simple_blind_coordinates(const EC_GROUP
*group
, EC_POINT
*p
,
1434 BIGNUM
*lambda
= NULL
;
1435 BIGNUM
*temp
= NULL
;
1438 lambda
= BN_CTX_get(ctx
);
1439 temp
= BN_CTX_get(ctx
);
1441 ERR_raise(ERR_LIB_EC
, ERR_R_BN_LIB
);
1446 * Make sure lambda is not zero.
1447 * If the RNG fails, we cannot blind but nevertheless want
1448 * code to continue smoothly and not clobber the error stack.
1452 ret
= BN_priv_rand_range_ex(lambda
, group
->field
, 0, ctx
);
1458 } while (BN_is_zero(lambda
));
1460 /* if field_encode defined convert between representations */
1461 if ((group
->meth
->field_encode
!= NULL
1462 && !group
->meth
->field_encode(group
, lambda
, lambda
, ctx
))
1463 || !group
->meth
->field_mul(group
, p
->Z
, p
->Z
, lambda
, ctx
)
1464 || !group
->meth
->field_sqr(group
, temp
, lambda
, ctx
)
1465 || !group
->meth
->field_mul(group
, p
->X
, p
->X
, temp
, ctx
)
1466 || !group
->meth
->field_mul(group
, temp
, temp
, lambda
, ctx
)
1467 || !group
->meth
->field_mul(group
, p
->Y
, p
->Y
, temp
, ctx
))
1480 * - p: affine coordinates
1483 * - s := p, r := 2p: blinded projective (homogeneous) coordinates
1485 * For doubling we use Formula 3 from Izu-Takagi "A fast parallel elliptic curve
1486 * multiplication resistant against side channel attacks" appendix, described at
1487 * https://hyperelliptic.org/EFD/g1p/auto-shortw-xz.html#doubling-dbl-2002-it-2
1488 * simplified for Z1=1.
1490 * Blinding uses the equivalence relation (\lambda X, \lambda Y, \lambda Z)
1491 * for any non-zero \lambda that holds for projective (homogeneous) coords.
1493 int ossl_ec_GFp_simple_ladder_pre(const EC_GROUP
*group
,
1494 EC_POINT
*r
, EC_POINT
*s
,
1495 EC_POINT
*p
, BN_CTX
*ctx
)
1497 BIGNUM
*t1
, *t2
, *t3
, *t4
, *t5
= NULL
;
1505 if (!p
->Z_is_one
/* r := 2p */
1506 || !group
->meth
->field_sqr(group
, t3
, p
->X
, ctx
)
1507 || !BN_mod_sub_quick(t4
, t3
, group
->a
, group
->field
)
1508 || !group
->meth
->field_sqr(group
, t4
, t4
, ctx
)
1509 || !group
->meth
->field_mul(group
, t5
, p
->X
, group
->b
, ctx
)
1510 || !BN_mod_lshift_quick(t5
, t5
, 3, group
->field
)
1511 /* r->X coord output */
1512 || !BN_mod_sub_quick(r
->X
, t4
, t5
, group
->field
)
1513 || !BN_mod_add_quick(t1
, t3
, group
->a
, group
->field
)
1514 || !group
->meth
->field_mul(group
, t2
, p
->X
, t1
, ctx
)
1515 || !BN_mod_add_quick(t2
, group
->b
, t2
, group
->field
)
1516 /* r->Z coord output */
1517 || !BN_mod_lshift_quick(r
->Z
, t2
, 2, group
->field
))
1520 /* make sure lambda (r->Y here for storage) is not zero */
1522 if (!BN_priv_rand_range_ex(r
->Y
, group
->field
, 0, ctx
))
1524 } while (BN_is_zero(r
->Y
));
1526 /* make sure lambda (s->Z here for storage) is not zero */
1528 if (!BN_priv_rand_range_ex(s
->Z
, group
->field
, 0, ctx
))
1530 } while (BN_is_zero(s
->Z
));
1532 /* if field_encode defined convert between representations */
1533 if (group
->meth
->field_encode
!= NULL
1534 && (!group
->meth
->field_encode(group
, r
->Y
, r
->Y
, ctx
)
1535 || !group
->meth
->field_encode(group
, s
->Z
, s
->Z
, ctx
)))
1538 /* blind r and s independently */
1539 if (!group
->meth
->field_mul(group
, r
->Z
, r
->Z
, r
->Y
, ctx
)
1540 || !group
->meth
->field_mul(group
, r
->X
, r
->X
, r
->Y
, ctx
)
1541 || !group
->meth
->field_mul(group
, s
->X
, p
->X
, s
->Z
, ctx
)) /* s := p */
1552 * - s, r: projective (homogeneous) coordinates
1553 * - p: affine coordinates
1556 * - s := r + s, r := 2r: projective (homogeneous) coordinates
1558 * Differential addition-and-doubling using Eq. (9) and (10) from Izu-Takagi
1559 * "A fast parallel elliptic curve multiplication resistant against side channel
1560 * attacks", as described at
1561 * https://hyperelliptic.org/EFD/g1p/auto-shortw-xz.html#ladder-mladd-2002-it-4
1563 int ossl_ec_GFp_simple_ladder_step(const EC_GROUP
*group
,
1564 EC_POINT
*r
, EC_POINT
*s
,
1565 EC_POINT
*p
, BN_CTX
*ctx
)
1568 BIGNUM
*t0
, *t1
, *t2
, *t3
, *t4
, *t5
, *t6
= NULL
;
1571 t0
= BN_CTX_get(ctx
);
1572 t1
= BN_CTX_get(ctx
);
1573 t2
= BN_CTX_get(ctx
);
1574 t3
= BN_CTX_get(ctx
);
1575 t4
= BN_CTX_get(ctx
);
1576 t5
= BN_CTX_get(ctx
);
1577 t6
= BN_CTX_get(ctx
);
1580 || !group
->meth
->field_mul(group
, t6
, r
->X
, s
->X
, ctx
)
1581 || !group
->meth
->field_mul(group
, t0
, r
->Z
, s
->Z
, ctx
)
1582 || !group
->meth
->field_mul(group
, t4
, r
->X
, s
->Z
, ctx
)
1583 || !group
->meth
->field_mul(group
, t3
, r
->Z
, s
->X
, ctx
)
1584 || !group
->meth
->field_mul(group
, t5
, group
->a
, t0
, ctx
)
1585 || !BN_mod_add_quick(t5
, t6
, t5
, group
->field
)
1586 || !BN_mod_add_quick(t6
, t3
, t4
, group
->field
)
1587 || !group
->meth
->field_mul(group
, t5
, t6
, t5
, ctx
)
1588 || !group
->meth
->field_sqr(group
, t0
, t0
, ctx
)
1589 || !BN_mod_lshift_quick(t2
, group
->b
, 2, group
->field
)
1590 || !group
->meth
->field_mul(group
, t0
, t2
, t0
, ctx
)
1591 || !BN_mod_lshift1_quick(t5
, t5
, group
->field
)
1592 || !BN_mod_sub_quick(t3
, t4
, t3
, group
->field
)
1593 /* s->Z coord output */
1594 || !group
->meth
->field_sqr(group
, s
->Z
, t3
, ctx
)
1595 || !group
->meth
->field_mul(group
, t4
, s
->Z
, p
->X
, ctx
)
1596 || !BN_mod_add_quick(t0
, t0
, t5
, group
->field
)
1597 /* s->X coord output */
1598 || !BN_mod_sub_quick(s
->X
, t0
, t4
, group
->field
)
1599 || !group
->meth
->field_sqr(group
, t4
, r
->X
, ctx
)
1600 || !group
->meth
->field_sqr(group
, t5
, r
->Z
, ctx
)
1601 || !group
->meth
->field_mul(group
, t6
, t5
, group
->a
, ctx
)
1602 || !BN_mod_add_quick(t1
, r
->X
, r
->Z
, group
->field
)
1603 || !group
->meth
->field_sqr(group
, t1
, t1
, ctx
)
1604 || !BN_mod_sub_quick(t1
, t1
, t4
, group
->field
)
1605 || !BN_mod_sub_quick(t1
, t1
, t5
, group
->field
)
1606 || !BN_mod_sub_quick(t3
, t4
, t6
, group
->field
)
1607 || !group
->meth
->field_sqr(group
, t3
, t3
, ctx
)
1608 || !group
->meth
->field_mul(group
, t0
, t5
, t1
, ctx
)
1609 || !group
->meth
->field_mul(group
, t0
, t2
, t0
, ctx
)
1610 /* r->X coord output */
1611 || !BN_mod_sub_quick(r
->X
, t3
, t0
, group
->field
)
1612 || !BN_mod_add_quick(t3
, t4
, t6
, group
->field
)
1613 || !group
->meth
->field_sqr(group
, t4
, t5
, ctx
)
1614 || !group
->meth
->field_mul(group
, t4
, t4
, t2
, ctx
)
1615 || !group
->meth
->field_mul(group
, t1
, t1
, t3
, ctx
)
1616 || !BN_mod_lshift1_quick(t1
, t1
, group
->field
)
1617 /* r->Z coord output */
1618 || !BN_mod_add_quick(r
->Z
, t4
, t1
, group
->field
))
1630 * - s, r: projective (homogeneous) coordinates
1631 * - p: affine coordinates
1634 * - r := (x,y): affine coordinates
1636 * Recovers the y-coordinate of r using Eq. (8) from Brier-Joye, "Weierstrass
1637 * Elliptic Curves and Side-Channel Attacks", modified to work in mixed
1638 * projective coords, i.e. p is affine and (r,s) in projective (homogeneous)
1639 * coords, and return r in affine coordinates.
1641 * X4 = two*Y1*X2*Z3*Z2;
1642 * Y4 = two*b*Z3*SQR(Z2) + Z3*(a*Z2+X1*X2)*(X1*Z2+X2) - X3*SQR(X1*Z2-X2);
1643 * Z4 = two*Y1*Z3*SQR(Z2);
1646 * - Z2==0 implies r is at infinity (handled by the BN_is_zero(r->Z) branch);
1647 * - Z3==0 implies s is at infinity (handled by the BN_is_zero(s->Z) branch);
1648 * - Y1==0 implies p has order 2, so either r or s are infinity and handled by
1649 * one of the BN_is_zero(...) branches.
1651 int ossl_ec_GFp_simple_ladder_post(const EC_GROUP
*group
,
1652 EC_POINT
*r
, EC_POINT
*s
,
1653 EC_POINT
*p
, BN_CTX
*ctx
)
1656 BIGNUM
*t0
, *t1
, *t2
, *t3
, *t4
, *t5
, *t6
= NULL
;
1658 if (BN_is_zero(r
->Z
))
1659 return EC_POINT_set_to_infinity(group
, r
);
1661 if (BN_is_zero(s
->Z
)) {
1662 if (!EC_POINT_copy(r
, p
)
1663 || !EC_POINT_invert(group
, r
, ctx
))
1669 t0
= BN_CTX_get(ctx
);
1670 t1
= BN_CTX_get(ctx
);
1671 t2
= BN_CTX_get(ctx
);
1672 t3
= BN_CTX_get(ctx
);
1673 t4
= BN_CTX_get(ctx
);
1674 t5
= BN_CTX_get(ctx
);
1675 t6
= BN_CTX_get(ctx
);
1678 || !BN_mod_lshift1_quick(t4
, p
->Y
, group
->field
)
1679 || !group
->meth
->field_mul(group
, t6
, r
->X
, t4
, ctx
)
1680 || !group
->meth
->field_mul(group
, t6
, s
->Z
, t6
, ctx
)
1681 || !group
->meth
->field_mul(group
, t5
, r
->Z
, t6
, ctx
)
1682 || !BN_mod_lshift1_quick(t1
, group
->b
, group
->field
)
1683 || !group
->meth
->field_mul(group
, t1
, s
->Z
, t1
, ctx
)
1684 || !group
->meth
->field_sqr(group
, t3
, r
->Z
, ctx
)
1685 || !group
->meth
->field_mul(group
, t2
, t3
, t1
, ctx
)
1686 || !group
->meth
->field_mul(group
, t6
, r
->Z
, group
->a
, ctx
)
1687 || !group
->meth
->field_mul(group
, t1
, p
->X
, r
->X
, ctx
)
1688 || !BN_mod_add_quick(t1
, t1
, t6
, group
->field
)
1689 || !group
->meth
->field_mul(group
, t1
, s
->Z
, t1
, ctx
)
1690 || !group
->meth
->field_mul(group
, t0
, p
->X
, r
->Z
, ctx
)
1691 || !BN_mod_add_quick(t6
, r
->X
, t0
, group
->field
)
1692 || !group
->meth
->field_mul(group
, t6
, t6
, t1
, ctx
)
1693 || !BN_mod_add_quick(t6
, t6
, t2
, group
->field
)
1694 || !BN_mod_sub_quick(t0
, t0
, r
->X
, group
->field
)
1695 || !group
->meth
->field_sqr(group
, t0
, t0
, ctx
)
1696 || !group
->meth
->field_mul(group
, t0
, t0
, s
->X
, ctx
)
1697 || !BN_mod_sub_quick(t0
, t6
, t0
, group
->field
)
1698 || !group
->meth
->field_mul(group
, t1
, s
->Z
, t4
, ctx
)
1699 || !group
->meth
->field_mul(group
, t1
, t3
, t1
, ctx
)
1700 || (group
->meth
->field_decode
!= NULL
1701 && !group
->meth
->field_decode(group
, t1
, t1
, ctx
))
1702 || !group
->meth
->field_inv(group
, t1
, t1
, ctx
)
1703 || (group
->meth
->field_encode
!= NULL
1704 && !group
->meth
->field_encode(group
, t1
, t1
, ctx
))
1705 || !group
->meth
->field_mul(group
, r
->X
, t5
, t1
, ctx
)
1706 || !group
->meth
->field_mul(group
, r
->Y
, t0
, t1
, ctx
))
1709 if (group
->meth
->field_set_to_one
!= NULL
) {
1710 if (!group
->meth
->field_set_to_one(group
, r
->Z
, ctx
))