1*de0e0e4dSAntonio Huete Jimenez /* $OpenBSD: ecp_smpl.c,v 1.34 2022/01/20 11:02:44 inoguchi Exp $ */
2f5b1c8a1SJohn Marino /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
3f5b1c8a1SJohn Marino * for the OpenSSL project.
4f5b1c8a1SJohn Marino * Includes code written by Bodo Moeller for the OpenSSL project.
5f5b1c8a1SJohn Marino */
6f5b1c8a1SJohn Marino /* ====================================================================
7f5b1c8a1SJohn Marino * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved.
8f5b1c8a1SJohn Marino *
9f5b1c8a1SJohn Marino * Redistribution and use in source and binary forms, with or without
10f5b1c8a1SJohn Marino * modification, are permitted provided that the following conditions
11f5b1c8a1SJohn Marino * are met:
12f5b1c8a1SJohn Marino *
13f5b1c8a1SJohn Marino * 1. Redistributions of source code must retain the above copyright
14f5b1c8a1SJohn Marino * notice, this list of conditions and the following disclaimer.
15f5b1c8a1SJohn Marino *
16f5b1c8a1SJohn Marino * 2. Redistributions in binary form must reproduce the above copyright
17f5b1c8a1SJohn Marino * notice, this list of conditions and the following disclaimer in
18f5b1c8a1SJohn Marino * the documentation and/or other materials provided with the
19f5b1c8a1SJohn Marino * distribution.
20f5b1c8a1SJohn Marino *
21f5b1c8a1SJohn Marino * 3. All advertising materials mentioning features or use of this
22f5b1c8a1SJohn Marino * software must display the following acknowledgment:
23f5b1c8a1SJohn Marino * "This product includes software developed by the OpenSSL Project
24f5b1c8a1SJohn Marino * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
25f5b1c8a1SJohn Marino *
26f5b1c8a1SJohn Marino * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
27f5b1c8a1SJohn Marino * endorse or promote products derived from this software without
28f5b1c8a1SJohn Marino * prior written permission. For written permission, please contact
29f5b1c8a1SJohn Marino * openssl-core@openssl.org.
30f5b1c8a1SJohn Marino *
31f5b1c8a1SJohn Marino * 5. Products derived from this software may not be called "OpenSSL"
32f5b1c8a1SJohn Marino * nor may "OpenSSL" appear in their names without prior written
33f5b1c8a1SJohn Marino * permission of the OpenSSL Project.
34f5b1c8a1SJohn Marino *
35f5b1c8a1SJohn Marino * 6. Redistributions of any form whatsoever must retain the following
36f5b1c8a1SJohn Marino * acknowledgment:
37f5b1c8a1SJohn Marino * "This product includes software developed by the OpenSSL Project
38f5b1c8a1SJohn Marino * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
39f5b1c8a1SJohn Marino *
40f5b1c8a1SJohn Marino * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
41f5b1c8a1SJohn Marino * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42f5b1c8a1SJohn Marino * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
43f5b1c8a1SJohn Marino * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
44f5b1c8a1SJohn Marino * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
45f5b1c8a1SJohn Marino * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
46f5b1c8a1SJohn Marino * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
47f5b1c8a1SJohn Marino * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48f5b1c8a1SJohn Marino * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
49f5b1c8a1SJohn Marino * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
50f5b1c8a1SJohn Marino * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
51f5b1c8a1SJohn Marino * OF THE POSSIBILITY OF SUCH DAMAGE.
52f5b1c8a1SJohn Marino * ====================================================================
53f5b1c8a1SJohn Marino *
54f5b1c8a1SJohn Marino * This product includes cryptographic software written by Eric Young
55f5b1c8a1SJohn Marino * (eay@cryptsoft.com). This product includes software written by Tim
56f5b1c8a1SJohn Marino * Hudson (tjh@cryptsoft.com).
57f5b1c8a1SJohn Marino *
58f5b1c8a1SJohn Marino */
59f5b1c8a1SJohn Marino /* ====================================================================
60f5b1c8a1SJohn Marino * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
61f5b1c8a1SJohn Marino * Portions of this software developed by SUN MICROSYSTEMS, INC.,
62f5b1c8a1SJohn Marino * and contributed to the OpenSSL project.
63f5b1c8a1SJohn Marino */
64f5b1c8a1SJohn Marino
65f5b1c8a1SJohn Marino #include <openssl/err.h>
66f5b1c8a1SJohn Marino
6772c33676SMaxim Ag #include "bn_lcl.h"
68f5b1c8a1SJohn Marino #include "ec_lcl.h"
69f5b1c8a1SJohn Marino
70f5b1c8a1SJohn Marino const EC_METHOD *
EC_GFp_simple_method(void)71f5b1c8a1SJohn Marino EC_GFp_simple_method(void)
72f5b1c8a1SJohn Marino {
73f5b1c8a1SJohn Marino static const EC_METHOD ret = {
74f5b1c8a1SJohn Marino .flags = EC_FLAGS_DEFAULT_OCT,
75f5b1c8a1SJohn Marino .field_type = NID_X9_62_prime_field,
76f5b1c8a1SJohn Marino .group_init = ec_GFp_simple_group_init,
77f5b1c8a1SJohn Marino .group_finish = ec_GFp_simple_group_finish,
78f5b1c8a1SJohn Marino .group_clear_finish = ec_GFp_simple_group_clear_finish,
79f5b1c8a1SJohn Marino .group_copy = ec_GFp_simple_group_copy,
80f5b1c8a1SJohn Marino .group_set_curve = ec_GFp_simple_group_set_curve,
81f5b1c8a1SJohn Marino .group_get_curve = ec_GFp_simple_group_get_curve,
82f5b1c8a1SJohn Marino .group_get_degree = ec_GFp_simple_group_get_degree,
83*de0e0e4dSAntonio Huete Jimenez .group_order_bits = ec_group_simple_order_bits,
84f5b1c8a1SJohn Marino .group_check_discriminant =
85f5b1c8a1SJohn Marino ec_GFp_simple_group_check_discriminant,
86f5b1c8a1SJohn Marino .point_init = ec_GFp_simple_point_init,
87f5b1c8a1SJohn Marino .point_finish = ec_GFp_simple_point_finish,
88f5b1c8a1SJohn Marino .point_clear_finish = ec_GFp_simple_point_clear_finish,
89f5b1c8a1SJohn Marino .point_copy = ec_GFp_simple_point_copy,
90f5b1c8a1SJohn Marino .point_set_to_infinity = ec_GFp_simple_point_set_to_infinity,
91*de0e0e4dSAntonio Huete Jimenez .point_set_Jprojective_coordinates =
92*de0e0e4dSAntonio Huete Jimenez ec_GFp_simple_set_Jprojective_coordinates,
93*de0e0e4dSAntonio Huete Jimenez .point_get_Jprojective_coordinates =
94*de0e0e4dSAntonio Huete Jimenez ec_GFp_simple_get_Jprojective_coordinates,
95f5b1c8a1SJohn Marino .point_set_affine_coordinates =
96f5b1c8a1SJohn Marino ec_GFp_simple_point_set_affine_coordinates,
97f5b1c8a1SJohn Marino .point_get_affine_coordinates =
98f5b1c8a1SJohn Marino ec_GFp_simple_point_get_affine_coordinates,
99f5b1c8a1SJohn Marino .add = ec_GFp_simple_add,
100f5b1c8a1SJohn Marino .dbl = ec_GFp_simple_dbl,
101f5b1c8a1SJohn Marino .invert = ec_GFp_simple_invert,
102f5b1c8a1SJohn Marino .is_at_infinity = ec_GFp_simple_is_at_infinity,
103f5b1c8a1SJohn Marino .is_on_curve = ec_GFp_simple_is_on_curve,
104f5b1c8a1SJohn Marino .point_cmp = ec_GFp_simple_cmp,
105f5b1c8a1SJohn Marino .make_affine = ec_GFp_simple_make_affine,
106f5b1c8a1SJohn Marino .points_make_affine = ec_GFp_simple_points_make_affine,
10772c33676SMaxim Ag .mul_generator_ct = ec_GFp_simple_mul_generator_ct,
10872c33676SMaxim Ag .mul_single_ct = ec_GFp_simple_mul_single_ct,
10972c33676SMaxim Ag .mul_double_nonct = ec_GFp_simple_mul_double_nonct,
110f5b1c8a1SJohn Marino .field_mul = ec_GFp_simple_field_mul,
11172c33676SMaxim Ag .field_sqr = ec_GFp_simple_field_sqr,
11272c33676SMaxim Ag .blind_coordinates = ec_GFp_simple_blind_coordinates,
113f5b1c8a1SJohn Marino };
114f5b1c8a1SJohn Marino
115f5b1c8a1SJohn Marino return &ret;
116f5b1c8a1SJohn Marino }
117f5b1c8a1SJohn Marino
118f5b1c8a1SJohn Marino
119f5b1c8a1SJohn Marino /* Most method functions in this file are designed to work with
120f5b1c8a1SJohn Marino * non-trivial representations of field elements if necessary
121f5b1c8a1SJohn Marino * (see ecp_mont.c): while standard modular addition and subtraction
122f5b1c8a1SJohn Marino * are used, the field_mul and field_sqr methods will be used for
123f5b1c8a1SJohn Marino * multiplication, and field_encode and field_decode (if defined)
124f5b1c8a1SJohn Marino * will be used for converting between representations.
125f5b1c8a1SJohn Marino
126f5b1c8a1SJohn Marino * Functions ec_GFp_simple_points_make_affine() and
127f5b1c8a1SJohn Marino * ec_GFp_simple_point_get_affine_coordinates() specifically assume
128f5b1c8a1SJohn Marino * that if a non-trivial representation is used, it is a Montgomery
129f5b1c8a1SJohn Marino * representation (i.e. 'encoding' means multiplying by some factor R).
130f5b1c8a1SJohn Marino */
131f5b1c8a1SJohn Marino
132f5b1c8a1SJohn Marino
133f5b1c8a1SJohn Marino int
ec_GFp_simple_group_init(EC_GROUP * group)134f5b1c8a1SJohn Marino ec_GFp_simple_group_init(EC_GROUP * group)
135f5b1c8a1SJohn Marino {
136f5b1c8a1SJohn Marino BN_init(&group->field);
137f5b1c8a1SJohn Marino BN_init(&group->a);
138f5b1c8a1SJohn Marino BN_init(&group->b);
139f5b1c8a1SJohn Marino group->a_is_minus3 = 0;
140f5b1c8a1SJohn Marino return 1;
141f5b1c8a1SJohn Marino }
142f5b1c8a1SJohn Marino
143f5b1c8a1SJohn Marino
144f5b1c8a1SJohn Marino void
ec_GFp_simple_group_finish(EC_GROUP * group)145f5b1c8a1SJohn Marino ec_GFp_simple_group_finish(EC_GROUP * group)
146f5b1c8a1SJohn Marino {
147f5b1c8a1SJohn Marino BN_free(&group->field);
148f5b1c8a1SJohn Marino BN_free(&group->a);
149f5b1c8a1SJohn Marino BN_free(&group->b);
150f5b1c8a1SJohn Marino }
151f5b1c8a1SJohn Marino
152f5b1c8a1SJohn Marino
153f5b1c8a1SJohn Marino void
ec_GFp_simple_group_clear_finish(EC_GROUP * group)154f5b1c8a1SJohn Marino ec_GFp_simple_group_clear_finish(EC_GROUP * group)
155f5b1c8a1SJohn Marino {
156f5b1c8a1SJohn Marino BN_clear_free(&group->field);
157f5b1c8a1SJohn Marino BN_clear_free(&group->a);
158f5b1c8a1SJohn Marino BN_clear_free(&group->b);
159f5b1c8a1SJohn Marino }
160f5b1c8a1SJohn Marino
161f5b1c8a1SJohn Marino
162f5b1c8a1SJohn Marino int
ec_GFp_simple_group_copy(EC_GROUP * dest,const EC_GROUP * src)163f5b1c8a1SJohn Marino ec_GFp_simple_group_copy(EC_GROUP * dest, const EC_GROUP * src)
164f5b1c8a1SJohn Marino {
165f5b1c8a1SJohn Marino if (!BN_copy(&dest->field, &src->field))
166f5b1c8a1SJohn Marino return 0;
167f5b1c8a1SJohn Marino if (!BN_copy(&dest->a, &src->a))
168f5b1c8a1SJohn Marino return 0;
169f5b1c8a1SJohn Marino if (!BN_copy(&dest->b, &src->b))
170f5b1c8a1SJohn Marino return 0;
171f5b1c8a1SJohn Marino
172f5b1c8a1SJohn Marino dest->a_is_minus3 = src->a_is_minus3;
173f5b1c8a1SJohn Marino
174f5b1c8a1SJohn Marino return 1;
175f5b1c8a1SJohn Marino }
176f5b1c8a1SJohn Marino
177f5b1c8a1SJohn Marino
178f5b1c8a1SJohn Marino int
ec_GFp_simple_group_set_curve(EC_GROUP * group,const BIGNUM * p,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)179f5b1c8a1SJohn Marino ec_GFp_simple_group_set_curve(EC_GROUP * group,
180f5b1c8a1SJohn Marino const BIGNUM * p, const BIGNUM * a, const BIGNUM * b, BN_CTX * ctx)
181f5b1c8a1SJohn Marino {
182f5b1c8a1SJohn Marino int ret = 0;
183f5b1c8a1SJohn Marino BN_CTX *new_ctx = NULL;
184f5b1c8a1SJohn Marino BIGNUM *tmp_a;
185f5b1c8a1SJohn Marino
186f5b1c8a1SJohn Marino /* p must be a prime > 3 */
187f5b1c8a1SJohn Marino if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) {
18872c33676SMaxim Ag ECerror(EC_R_INVALID_FIELD);
189f5b1c8a1SJohn Marino return 0;
190f5b1c8a1SJohn Marino }
191f5b1c8a1SJohn Marino if (ctx == NULL) {
192f5b1c8a1SJohn Marino ctx = new_ctx = BN_CTX_new();
193f5b1c8a1SJohn Marino if (ctx == NULL)
194f5b1c8a1SJohn Marino return 0;
195f5b1c8a1SJohn Marino }
196f5b1c8a1SJohn Marino BN_CTX_start(ctx);
197f5b1c8a1SJohn Marino if ((tmp_a = BN_CTX_get(ctx)) == NULL)
198f5b1c8a1SJohn Marino goto err;
199f5b1c8a1SJohn Marino
200f5b1c8a1SJohn Marino /* group->field */
201f5b1c8a1SJohn Marino if (!BN_copy(&group->field, p))
202f5b1c8a1SJohn Marino goto err;
203f5b1c8a1SJohn Marino BN_set_negative(&group->field, 0);
204f5b1c8a1SJohn Marino
205f5b1c8a1SJohn Marino /* group->a */
206f5b1c8a1SJohn Marino if (!BN_nnmod(tmp_a, a, p, ctx))
207f5b1c8a1SJohn Marino goto err;
208f5b1c8a1SJohn Marino if (group->meth->field_encode) {
209f5b1c8a1SJohn Marino if (!group->meth->field_encode(group, &group->a, tmp_a, ctx))
210f5b1c8a1SJohn Marino goto err;
211f5b1c8a1SJohn Marino } else if (!BN_copy(&group->a, tmp_a))
212f5b1c8a1SJohn Marino goto err;
213f5b1c8a1SJohn Marino
214f5b1c8a1SJohn Marino /* group->b */
215f5b1c8a1SJohn Marino if (!BN_nnmod(&group->b, b, p, ctx))
216f5b1c8a1SJohn Marino goto err;
217f5b1c8a1SJohn Marino if (group->meth->field_encode)
218f5b1c8a1SJohn Marino if (!group->meth->field_encode(group, &group->b, &group->b, ctx))
219f5b1c8a1SJohn Marino goto err;
220f5b1c8a1SJohn Marino
221f5b1c8a1SJohn Marino /* group->a_is_minus3 */
222f5b1c8a1SJohn Marino if (!BN_add_word(tmp_a, 3))
223f5b1c8a1SJohn Marino goto err;
224f5b1c8a1SJohn Marino group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
225f5b1c8a1SJohn Marino
226f5b1c8a1SJohn Marino ret = 1;
227f5b1c8a1SJohn Marino
228f5b1c8a1SJohn Marino err:
229f5b1c8a1SJohn Marino BN_CTX_end(ctx);
230f5b1c8a1SJohn Marino BN_CTX_free(new_ctx);
231f5b1c8a1SJohn Marino return ret;
232f5b1c8a1SJohn Marino }
233f5b1c8a1SJohn Marino
234f5b1c8a1SJohn Marino
235f5b1c8a1SJohn Marino int
ec_GFp_simple_group_get_curve(const EC_GROUP * group,BIGNUM * p,BIGNUM * a,BIGNUM * b,BN_CTX * ctx)236f5b1c8a1SJohn Marino ec_GFp_simple_group_get_curve(const EC_GROUP * group, BIGNUM * p, BIGNUM * a, BIGNUM * b, BN_CTX * ctx)
237f5b1c8a1SJohn Marino {
238f5b1c8a1SJohn Marino int ret = 0;
239f5b1c8a1SJohn Marino BN_CTX *new_ctx = NULL;
240f5b1c8a1SJohn Marino
241f5b1c8a1SJohn Marino if (p != NULL) {
242f5b1c8a1SJohn Marino if (!BN_copy(p, &group->field))
243f5b1c8a1SJohn Marino return 0;
244f5b1c8a1SJohn Marino }
245f5b1c8a1SJohn Marino if (a != NULL || b != NULL) {
246f5b1c8a1SJohn Marino if (group->meth->field_decode) {
247f5b1c8a1SJohn Marino if (ctx == NULL) {
248f5b1c8a1SJohn Marino ctx = new_ctx = BN_CTX_new();
249f5b1c8a1SJohn Marino if (ctx == NULL)
250f5b1c8a1SJohn Marino return 0;
251f5b1c8a1SJohn Marino }
252f5b1c8a1SJohn Marino if (a != NULL) {
253f5b1c8a1SJohn Marino if (!group->meth->field_decode(group, a, &group->a, ctx))
254f5b1c8a1SJohn Marino goto err;
255f5b1c8a1SJohn Marino }
256f5b1c8a1SJohn Marino if (b != NULL) {
257f5b1c8a1SJohn Marino if (!group->meth->field_decode(group, b, &group->b, ctx))
258f5b1c8a1SJohn Marino goto err;
259f5b1c8a1SJohn Marino }
260f5b1c8a1SJohn Marino } else {
261f5b1c8a1SJohn Marino if (a != NULL) {
262f5b1c8a1SJohn Marino if (!BN_copy(a, &group->a))
263f5b1c8a1SJohn Marino goto err;
264f5b1c8a1SJohn Marino }
265f5b1c8a1SJohn Marino if (b != NULL) {
266f5b1c8a1SJohn Marino if (!BN_copy(b, &group->b))
267f5b1c8a1SJohn Marino goto err;
268f5b1c8a1SJohn Marino }
269f5b1c8a1SJohn Marino }
270f5b1c8a1SJohn Marino }
271f5b1c8a1SJohn Marino ret = 1;
272f5b1c8a1SJohn Marino
273f5b1c8a1SJohn Marino err:
274f5b1c8a1SJohn Marino BN_CTX_free(new_ctx);
275f5b1c8a1SJohn Marino return ret;
276f5b1c8a1SJohn Marino }
277f5b1c8a1SJohn Marino
278f5b1c8a1SJohn Marino
279f5b1c8a1SJohn Marino int
ec_GFp_simple_group_get_degree(const EC_GROUP * group)280f5b1c8a1SJohn Marino ec_GFp_simple_group_get_degree(const EC_GROUP * group)
281f5b1c8a1SJohn Marino {
282f5b1c8a1SJohn Marino return BN_num_bits(&group->field);
283f5b1c8a1SJohn Marino }
284f5b1c8a1SJohn Marino
285f5b1c8a1SJohn Marino
286f5b1c8a1SJohn Marino int
ec_GFp_simple_group_check_discriminant(const EC_GROUP * group,BN_CTX * ctx)287f5b1c8a1SJohn Marino ec_GFp_simple_group_check_discriminant(const EC_GROUP * group, BN_CTX * ctx)
288f5b1c8a1SJohn Marino {
289f5b1c8a1SJohn Marino int ret = 0;
290f5b1c8a1SJohn Marino BIGNUM *a, *b, *order, *tmp_1, *tmp_2;
291f5b1c8a1SJohn Marino const BIGNUM *p = &group->field;
292f5b1c8a1SJohn Marino BN_CTX *new_ctx = NULL;
293f5b1c8a1SJohn Marino
294f5b1c8a1SJohn Marino if (ctx == NULL) {
295f5b1c8a1SJohn Marino ctx = new_ctx = BN_CTX_new();
296f5b1c8a1SJohn Marino if (ctx == NULL) {
29772c33676SMaxim Ag ECerror(ERR_R_MALLOC_FAILURE);
298f5b1c8a1SJohn Marino goto err;
299f5b1c8a1SJohn Marino }
300f5b1c8a1SJohn Marino }
301f5b1c8a1SJohn Marino BN_CTX_start(ctx);
302f5b1c8a1SJohn Marino if ((a = BN_CTX_get(ctx)) == NULL)
303f5b1c8a1SJohn Marino goto err;
304f5b1c8a1SJohn Marino if ((b = BN_CTX_get(ctx)) == NULL)
305f5b1c8a1SJohn Marino goto err;
306f5b1c8a1SJohn Marino if ((tmp_1 = BN_CTX_get(ctx)) == NULL)
307f5b1c8a1SJohn Marino goto err;
308f5b1c8a1SJohn Marino if ((tmp_2 = BN_CTX_get(ctx)) == NULL)
309f5b1c8a1SJohn Marino goto err;
310f5b1c8a1SJohn Marino if ((order = BN_CTX_get(ctx)) == NULL)
311f5b1c8a1SJohn Marino goto err;
312f5b1c8a1SJohn Marino
313f5b1c8a1SJohn Marino if (group->meth->field_decode) {
314f5b1c8a1SJohn Marino if (!group->meth->field_decode(group, a, &group->a, ctx))
315f5b1c8a1SJohn Marino goto err;
316f5b1c8a1SJohn Marino if (!group->meth->field_decode(group, b, &group->b, ctx))
317f5b1c8a1SJohn Marino goto err;
318f5b1c8a1SJohn Marino } else {
319f5b1c8a1SJohn Marino if (!BN_copy(a, &group->a))
320f5b1c8a1SJohn Marino goto err;
321f5b1c8a1SJohn Marino if (!BN_copy(b, &group->b))
322f5b1c8a1SJohn Marino goto err;
323f5b1c8a1SJohn Marino }
324f5b1c8a1SJohn Marino
325f5b1c8a1SJohn Marino /*
326f5b1c8a1SJohn Marino * check the discriminant: y^2 = x^3 + a*x + b is an elliptic curve
327f5b1c8a1SJohn Marino * <=> 4*a^3 + 27*b^2 != 0 (mod p) 0 =< a, b < p
328f5b1c8a1SJohn Marino */
329f5b1c8a1SJohn Marino if (BN_is_zero(a)) {
330f5b1c8a1SJohn Marino if (BN_is_zero(b))
331f5b1c8a1SJohn Marino goto err;
332f5b1c8a1SJohn Marino } else if (!BN_is_zero(b)) {
333f5b1c8a1SJohn Marino if (!BN_mod_sqr(tmp_1, a, p, ctx))
334f5b1c8a1SJohn Marino goto err;
335f5b1c8a1SJohn Marino if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx))
336f5b1c8a1SJohn Marino goto err;
337f5b1c8a1SJohn Marino if (!BN_lshift(tmp_1, tmp_2, 2))
338f5b1c8a1SJohn Marino goto err;
339f5b1c8a1SJohn Marino /* tmp_1 = 4*a^3 */
340f5b1c8a1SJohn Marino
341f5b1c8a1SJohn Marino if (!BN_mod_sqr(tmp_2, b, p, ctx))
342f5b1c8a1SJohn Marino goto err;
343f5b1c8a1SJohn Marino if (!BN_mul_word(tmp_2, 27))
344f5b1c8a1SJohn Marino goto err;
345f5b1c8a1SJohn Marino /* tmp_2 = 27*b^2 */
346f5b1c8a1SJohn Marino
347f5b1c8a1SJohn Marino if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx))
348f5b1c8a1SJohn Marino goto err;
349f5b1c8a1SJohn Marino if (BN_is_zero(a))
350f5b1c8a1SJohn Marino goto err;
351f5b1c8a1SJohn Marino }
352f5b1c8a1SJohn Marino ret = 1;
353f5b1c8a1SJohn Marino
354f5b1c8a1SJohn Marino err:
355f5b1c8a1SJohn Marino if (ctx != NULL)
356f5b1c8a1SJohn Marino BN_CTX_end(ctx);
357f5b1c8a1SJohn Marino BN_CTX_free(new_ctx);
358f5b1c8a1SJohn Marino return ret;
359f5b1c8a1SJohn Marino }
360f5b1c8a1SJohn Marino
361f5b1c8a1SJohn Marino
362f5b1c8a1SJohn Marino int
ec_GFp_simple_point_init(EC_POINT * point)363f5b1c8a1SJohn Marino ec_GFp_simple_point_init(EC_POINT * point)
364f5b1c8a1SJohn Marino {
365f5b1c8a1SJohn Marino BN_init(&point->X);
366f5b1c8a1SJohn Marino BN_init(&point->Y);
367f5b1c8a1SJohn Marino BN_init(&point->Z);
368f5b1c8a1SJohn Marino point->Z_is_one = 0;
369f5b1c8a1SJohn Marino
370f5b1c8a1SJohn Marino return 1;
371f5b1c8a1SJohn Marino }
372f5b1c8a1SJohn Marino
373f5b1c8a1SJohn Marino
374f5b1c8a1SJohn Marino void
ec_GFp_simple_point_finish(EC_POINT * point)375f5b1c8a1SJohn Marino ec_GFp_simple_point_finish(EC_POINT * point)
376f5b1c8a1SJohn Marino {
377f5b1c8a1SJohn Marino BN_free(&point->X);
378f5b1c8a1SJohn Marino BN_free(&point->Y);
379f5b1c8a1SJohn Marino BN_free(&point->Z);
380f5b1c8a1SJohn Marino }
381f5b1c8a1SJohn Marino
382f5b1c8a1SJohn Marino
383f5b1c8a1SJohn Marino void
ec_GFp_simple_point_clear_finish(EC_POINT * point)384f5b1c8a1SJohn Marino ec_GFp_simple_point_clear_finish(EC_POINT * point)
385f5b1c8a1SJohn Marino {
386f5b1c8a1SJohn Marino BN_clear_free(&point->X);
387f5b1c8a1SJohn Marino BN_clear_free(&point->Y);
388f5b1c8a1SJohn Marino BN_clear_free(&point->Z);
389f5b1c8a1SJohn Marino point->Z_is_one = 0;
390f5b1c8a1SJohn Marino }
391f5b1c8a1SJohn Marino
392f5b1c8a1SJohn Marino
393f5b1c8a1SJohn Marino int
ec_GFp_simple_point_copy(EC_POINT * dest,const EC_POINT * src)394f5b1c8a1SJohn Marino ec_GFp_simple_point_copy(EC_POINT * dest, const EC_POINT * src)
395f5b1c8a1SJohn Marino {
396f5b1c8a1SJohn Marino if (!BN_copy(&dest->X, &src->X))
397f5b1c8a1SJohn Marino return 0;
398f5b1c8a1SJohn Marino if (!BN_copy(&dest->Y, &src->Y))
399f5b1c8a1SJohn Marino return 0;
400f5b1c8a1SJohn Marino if (!BN_copy(&dest->Z, &src->Z))
401f5b1c8a1SJohn Marino return 0;
402f5b1c8a1SJohn Marino dest->Z_is_one = src->Z_is_one;
403f5b1c8a1SJohn Marino
404f5b1c8a1SJohn Marino return 1;
405f5b1c8a1SJohn Marino }
406f5b1c8a1SJohn Marino
407f5b1c8a1SJohn Marino
408f5b1c8a1SJohn Marino int
ec_GFp_simple_point_set_to_infinity(const EC_GROUP * group,EC_POINT * point)409f5b1c8a1SJohn Marino ec_GFp_simple_point_set_to_infinity(const EC_GROUP * group, EC_POINT * point)
410f5b1c8a1SJohn Marino {
411f5b1c8a1SJohn Marino point->Z_is_one = 0;
412f5b1c8a1SJohn Marino BN_zero(&point->Z);
413f5b1c8a1SJohn Marino return 1;
414f5b1c8a1SJohn Marino }
415f5b1c8a1SJohn Marino
416f5b1c8a1SJohn Marino
417f5b1c8a1SJohn Marino int
ec_GFp_simple_set_Jprojective_coordinates(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x,const BIGNUM * y,const BIGNUM * z,BN_CTX * ctx)418*de0e0e4dSAntonio Huete Jimenez ec_GFp_simple_set_Jprojective_coordinates(const EC_GROUP *group,
419*de0e0e4dSAntonio Huete Jimenez EC_POINT *point, const BIGNUM *x, const BIGNUM *y, const BIGNUM *z,
420*de0e0e4dSAntonio Huete Jimenez BN_CTX *ctx)
421f5b1c8a1SJohn Marino {
422f5b1c8a1SJohn Marino BN_CTX *new_ctx = NULL;
423f5b1c8a1SJohn Marino int ret = 0;
424f5b1c8a1SJohn Marino
425f5b1c8a1SJohn Marino if (ctx == NULL) {
426f5b1c8a1SJohn Marino ctx = new_ctx = BN_CTX_new();
427f5b1c8a1SJohn Marino if (ctx == NULL)
428f5b1c8a1SJohn Marino return 0;
429f5b1c8a1SJohn Marino }
430f5b1c8a1SJohn Marino if (x != NULL) {
431f5b1c8a1SJohn Marino if (!BN_nnmod(&point->X, x, &group->field, ctx))
432f5b1c8a1SJohn Marino goto err;
433f5b1c8a1SJohn Marino if (group->meth->field_encode) {
434f5b1c8a1SJohn Marino if (!group->meth->field_encode(group, &point->X, &point->X, ctx))
435f5b1c8a1SJohn Marino goto err;
436f5b1c8a1SJohn Marino }
437f5b1c8a1SJohn Marino }
438f5b1c8a1SJohn Marino if (y != NULL) {
439f5b1c8a1SJohn Marino if (!BN_nnmod(&point->Y, y, &group->field, ctx))
440f5b1c8a1SJohn Marino goto err;
441f5b1c8a1SJohn Marino if (group->meth->field_encode) {
442f5b1c8a1SJohn Marino if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx))
443f5b1c8a1SJohn Marino goto err;
444f5b1c8a1SJohn Marino }
445f5b1c8a1SJohn Marino }
446f5b1c8a1SJohn Marino if (z != NULL) {
447f5b1c8a1SJohn Marino int Z_is_one;
448f5b1c8a1SJohn Marino
449f5b1c8a1SJohn Marino if (!BN_nnmod(&point->Z, z, &group->field, ctx))
450f5b1c8a1SJohn Marino goto err;
451f5b1c8a1SJohn Marino Z_is_one = BN_is_one(&point->Z);
452f5b1c8a1SJohn Marino if (group->meth->field_encode) {
453f5b1c8a1SJohn Marino if (Z_is_one && (group->meth->field_set_to_one != 0)) {
454f5b1c8a1SJohn Marino if (!group->meth->field_set_to_one(group, &point->Z, ctx))
455f5b1c8a1SJohn Marino goto err;
456f5b1c8a1SJohn Marino } else {
457f5b1c8a1SJohn Marino if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx))
458f5b1c8a1SJohn Marino goto err;
459f5b1c8a1SJohn Marino }
460f5b1c8a1SJohn Marino }
461f5b1c8a1SJohn Marino point->Z_is_one = Z_is_one;
462f5b1c8a1SJohn Marino }
463f5b1c8a1SJohn Marino ret = 1;
464f5b1c8a1SJohn Marino
465f5b1c8a1SJohn Marino err:
466f5b1c8a1SJohn Marino BN_CTX_free(new_ctx);
467f5b1c8a1SJohn Marino return ret;
468f5b1c8a1SJohn Marino }
469f5b1c8a1SJohn Marino
470f5b1c8a1SJohn Marino int
ec_GFp_simple_get_Jprojective_coordinates(const EC_GROUP * group,const EC_POINT * point,BIGNUM * x,BIGNUM * y,BIGNUM * z,BN_CTX * ctx)471*de0e0e4dSAntonio Huete Jimenez ec_GFp_simple_get_Jprojective_coordinates(const EC_GROUP *group,
472*de0e0e4dSAntonio Huete Jimenez const EC_POINT *point, BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx)
473f5b1c8a1SJohn Marino {
474f5b1c8a1SJohn Marino BN_CTX *new_ctx = NULL;
475f5b1c8a1SJohn Marino int ret = 0;
476f5b1c8a1SJohn Marino
477f5b1c8a1SJohn Marino if (group->meth->field_decode != 0) {
478f5b1c8a1SJohn Marino if (ctx == NULL) {
479f5b1c8a1SJohn Marino ctx = new_ctx = BN_CTX_new();
480f5b1c8a1SJohn Marino if (ctx == NULL)
481f5b1c8a1SJohn Marino return 0;
482f5b1c8a1SJohn Marino }
483f5b1c8a1SJohn Marino if (x != NULL) {
484f5b1c8a1SJohn Marino if (!group->meth->field_decode(group, x, &point->X, ctx))
485f5b1c8a1SJohn Marino goto err;
486f5b1c8a1SJohn Marino }
487f5b1c8a1SJohn Marino if (y != NULL) {
488f5b1c8a1SJohn Marino if (!group->meth->field_decode(group, y, &point->Y, ctx))
489f5b1c8a1SJohn Marino goto err;
490f5b1c8a1SJohn Marino }
491f5b1c8a1SJohn Marino if (z != NULL) {
492f5b1c8a1SJohn Marino if (!group->meth->field_decode(group, z, &point->Z, ctx))
493f5b1c8a1SJohn Marino goto err;
494f5b1c8a1SJohn Marino }
495f5b1c8a1SJohn Marino } else {
496f5b1c8a1SJohn Marino if (x != NULL) {
497f5b1c8a1SJohn Marino if (!BN_copy(x, &point->X))
498f5b1c8a1SJohn Marino goto err;
499f5b1c8a1SJohn Marino }
500f5b1c8a1SJohn Marino if (y != NULL) {
501f5b1c8a1SJohn Marino if (!BN_copy(y, &point->Y))
502f5b1c8a1SJohn Marino goto err;
503f5b1c8a1SJohn Marino }
504f5b1c8a1SJohn Marino if (z != NULL) {
505f5b1c8a1SJohn Marino if (!BN_copy(z, &point->Z))
506f5b1c8a1SJohn Marino goto err;
507f5b1c8a1SJohn Marino }
508f5b1c8a1SJohn Marino }
509f5b1c8a1SJohn Marino
510f5b1c8a1SJohn Marino ret = 1;
511f5b1c8a1SJohn Marino
512f5b1c8a1SJohn Marino err:
513f5b1c8a1SJohn Marino BN_CTX_free(new_ctx);
514f5b1c8a1SJohn Marino return ret;
515f5b1c8a1SJohn Marino }
516f5b1c8a1SJohn Marino
517f5b1c8a1SJohn Marino int
ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x,const BIGNUM * y,BN_CTX * ctx)518f5b1c8a1SJohn Marino ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP * group, EC_POINT * point,
519f5b1c8a1SJohn Marino const BIGNUM * x, const BIGNUM * y, BN_CTX * ctx)
520f5b1c8a1SJohn Marino {
521f5b1c8a1SJohn Marino if (x == NULL || y == NULL) {
522f5b1c8a1SJohn Marino /* unlike for projective coordinates, we do not tolerate this */
52372c33676SMaxim Ag ECerror(ERR_R_PASSED_NULL_PARAMETER);
524f5b1c8a1SJohn Marino return 0;
525f5b1c8a1SJohn Marino }
526*de0e0e4dSAntonio Huete Jimenez return EC_POINT_set_Jprojective_coordinates(group, point, x, y,
527*de0e0e4dSAntonio Huete Jimenez BN_value_one(), ctx);
528f5b1c8a1SJohn Marino }
529f5b1c8a1SJohn Marino
530f5b1c8a1SJohn Marino int
ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP * group,const EC_POINT * point,BIGNUM * x,BIGNUM * y,BN_CTX * ctx)531f5b1c8a1SJohn Marino ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP * group, const EC_POINT * point,
532f5b1c8a1SJohn Marino BIGNUM * x, BIGNUM * y, BN_CTX * ctx)
533f5b1c8a1SJohn Marino {
534f5b1c8a1SJohn Marino BN_CTX *new_ctx = NULL;
535f5b1c8a1SJohn Marino BIGNUM *Z, *Z_1, *Z_2, *Z_3;
536f5b1c8a1SJohn Marino const BIGNUM *Z_;
537f5b1c8a1SJohn Marino int ret = 0;
538f5b1c8a1SJohn Marino
539f5b1c8a1SJohn Marino if (EC_POINT_is_at_infinity(group, point) > 0) {
54072c33676SMaxim Ag ECerror(EC_R_POINT_AT_INFINITY);
541f5b1c8a1SJohn Marino return 0;
542f5b1c8a1SJohn Marino }
543f5b1c8a1SJohn Marino if (ctx == NULL) {
544f5b1c8a1SJohn Marino ctx = new_ctx = BN_CTX_new();
545f5b1c8a1SJohn Marino if (ctx == NULL)
546f5b1c8a1SJohn Marino return 0;
547f5b1c8a1SJohn Marino }
548f5b1c8a1SJohn Marino BN_CTX_start(ctx);
549f5b1c8a1SJohn Marino if ((Z = BN_CTX_get(ctx)) == NULL)
550f5b1c8a1SJohn Marino goto err;
551f5b1c8a1SJohn Marino if ((Z_1 = BN_CTX_get(ctx)) == NULL)
552f5b1c8a1SJohn Marino goto err;
553f5b1c8a1SJohn Marino if ((Z_2 = BN_CTX_get(ctx)) == NULL)
554f5b1c8a1SJohn Marino goto err;
555f5b1c8a1SJohn Marino if ((Z_3 = BN_CTX_get(ctx)) == NULL)
556f5b1c8a1SJohn Marino goto err;
557f5b1c8a1SJohn Marino
558f5b1c8a1SJohn Marino /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */
559f5b1c8a1SJohn Marino
560f5b1c8a1SJohn Marino if (group->meth->field_decode) {
561f5b1c8a1SJohn Marino if (!group->meth->field_decode(group, Z, &point->Z, ctx))
562f5b1c8a1SJohn Marino goto err;
563f5b1c8a1SJohn Marino Z_ = Z;
564f5b1c8a1SJohn Marino } else {
565f5b1c8a1SJohn Marino Z_ = &point->Z;
566f5b1c8a1SJohn Marino }
567f5b1c8a1SJohn Marino
568f5b1c8a1SJohn Marino if (BN_is_one(Z_)) {
569f5b1c8a1SJohn Marino if (group->meth->field_decode) {
570f5b1c8a1SJohn Marino if (x != NULL) {
571f5b1c8a1SJohn Marino if (!group->meth->field_decode(group, x, &point->X, ctx))
572f5b1c8a1SJohn Marino goto err;
573f5b1c8a1SJohn Marino }
574f5b1c8a1SJohn Marino if (y != NULL) {
575f5b1c8a1SJohn Marino if (!group->meth->field_decode(group, y, &point->Y, ctx))
576f5b1c8a1SJohn Marino goto err;
577f5b1c8a1SJohn Marino }
578f5b1c8a1SJohn Marino } else {
579f5b1c8a1SJohn Marino if (x != NULL) {
580f5b1c8a1SJohn Marino if (!BN_copy(x, &point->X))
581f5b1c8a1SJohn Marino goto err;
582f5b1c8a1SJohn Marino }
583f5b1c8a1SJohn Marino if (y != NULL) {
584f5b1c8a1SJohn Marino if (!BN_copy(y, &point->Y))
585f5b1c8a1SJohn Marino goto err;
586f5b1c8a1SJohn Marino }
587f5b1c8a1SJohn Marino }
588f5b1c8a1SJohn Marino } else {
589*de0e0e4dSAntonio Huete Jimenez if (BN_mod_inverse_ct(Z_1, Z_, &group->field, ctx) == NULL) {
59072c33676SMaxim Ag ECerror(ERR_R_BN_LIB);
591f5b1c8a1SJohn Marino goto err;
592f5b1c8a1SJohn Marino }
593f5b1c8a1SJohn Marino if (group->meth->field_encode == 0) {
594f5b1c8a1SJohn Marino /* field_sqr works on standard representation */
595f5b1c8a1SJohn Marino if (!group->meth->field_sqr(group, Z_2, Z_1, ctx))
596f5b1c8a1SJohn Marino goto err;
597f5b1c8a1SJohn Marino } else {
598f5b1c8a1SJohn Marino if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx))
599f5b1c8a1SJohn Marino goto err;
600f5b1c8a1SJohn Marino }
601f5b1c8a1SJohn Marino
602f5b1c8a1SJohn Marino if (x != NULL) {
603f5b1c8a1SJohn Marino /*
604f5b1c8a1SJohn Marino * in the Montgomery case, field_mul will cancel out
605f5b1c8a1SJohn Marino * Montgomery factor in X:
606f5b1c8a1SJohn Marino */
607f5b1c8a1SJohn Marino if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx))
608f5b1c8a1SJohn Marino goto err;
609f5b1c8a1SJohn Marino }
610f5b1c8a1SJohn Marino if (y != NULL) {
611f5b1c8a1SJohn Marino if (group->meth->field_encode == 0) {
612f5b1c8a1SJohn Marino /* field_mul works on standard representation */
613f5b1c8a1SJohn Marino if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx))
614f5b1c8a1SJohn Marino goto err;
615f5b1c8a1SJohn Marino } else {
616f5b1c8a1SJohn Marino if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx))
617f5b1c8a1SJohn Marino goto err;
618f5b1c8a1SJohn Marino }
619f5b1c8a1SJohn Marino
620f5b1c8a1SJohn Marino /*
621f5b1c8a1SJohn Marino * in the Montgomery case, field_mul will cancel out
622f5b1c8a1SJohn Marino * Montgomery factor in Y:
623f5b1c8a1SJohn Marino */
624f5b1c8a1SJohn Marino if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx))
625f5b1c8a1SJohn Marino goto err;
626f5b1c8a1SJohn Marino }
627f5b1c8a1SJohn Marino }
628f5b1c8a1SJohn Marino
629f5b1c8a1SJohn Marino ret = 1;
630f5b1c8a1SJohn Marino
631f5b1c8a1SJohn Marino err:
632f5b1c8a1SJohn Marino BN_CTX_end(ctx);
633f5b1c8a1SJohn Marino BN_CTX_free(new_ctx);
634f5b1c8a1SJohn Marino return ret;
635f5b1c8a1SJohn Marino }
636f5b1c8a1SJohn Marino
637f5b1c8a1SJohn Marino int
ec_GFp_simple_add(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)638f5b1c8a1SJohn Marino ec_GFp_simple_add(const EC_GROUP * group, EC_POINT * r, const EC_POINT * a, const EC_POINT * b, BN_CTX * ctx)
639f5b1c8a1SJohn Marino {
640f5b1c8a1SJohn Marino int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
641f5b1c8a1SJohn Marino int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
642f5b1c8a1SJohn Marino const BIGNUM *p;
643f5b1c8a1SJohn Marino BN_CTX *new_ctx = NULL;
644f5b1c8a1SJohn Marino BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
645f5b1c8a1SJohn Marino int ret = 0;
646f5b1c8a1SJohn Marino
647f5b1c8a1SJohn Marino if (a == b)
648f5b1c8a1SJohn Marino return EC_POINT_dbl(group, r, a, ctx);
649f5b1c8a1SJohn Marino if (EC_POINT_is_at_infinity(group, a) > 0)
650f5b1c8a1SJohn Marino return EC_POINT_copy(r, b);
651f5b1c8a1SJohn Marino if (EC_POINT_is_at_infinity(group, b) > 0)
652f5b1c8a1SJohn Marino return EC_POINT_copy(r, a);
653f5b1c8a1SJohn Marino
654f5b1c8a1SJohn Marino field_mul = group->meth->field_mul;
655f5b1c8a1SJohn Marino field_sqr = group->meth->field_sqr;
656f5b1c8a1SJohn Marino p = &group->field;
657f5b1c8a1SJohn Marino
658f5b1c8a1SJohn Marino if (ctx == NULL) {
659f5b1c8a1SJohn Marino ctx = new_ctx = BN_CTX_new();
660f5b1c8a1SJohn Marino if (ctx == NULL)
661f5b1c8a1SJohn Marino return 0;
662f5b1c8a1SJohn Marino }
663f5b1c8a1SJohn Marino BN_CTX_start(ctx);
664f5b1c8a1SJohn Marino if ((n0 = BN_CTX_get(ctx)) == NULL)
665f5b1c8a1SJohn Marino goto end;
666f5b1c8a1SJohn Marino if ((n1 = BN_CTX_get(ctx)) == NULL)
667f5b1c8a1SJohn Marino goto end;
668f5b1c8a1SJohn Marino if ((n2 = BN_CTX_get(ctx)) == NULL)
669f5b1c8a1SJohn Marino goto end;
670f5b1c8a1SJohn Marino if ((n3 = BN_CTX_get(ctx)) == NULL)
671f5b1c8a1SJohn Marino goto end;
672f5b1c8a1SJohn Marino if ((n4 = BN_CTX_get(ctx)) == NULL)
673f5b1c8a1SJohn Marino goto end;
674f5b1c8a1SJohn Marino if ((n5 = BN_CTX_get(ctx)) == NULL)
675f5b1c8a1SJohn Marino goto end;
676f5b1c8a1SJohn Marino if ((n6 = BN_CTX_get(ctx)) == NULL)
677f5b1c8a1SJohn Marino goto end;
678f5b1c8a1SJohn Marino
679f5b1c8a1SJohn Marino /*
680f5b1c8a1SJohn Marino * Note that in this function we must not read components of 'a' or
681f5b1c8a1SJohn Marino * 'b' once we have written the corresponding components of 'r'. ('r'
682f5b1c8a1SJohn Marino * might be one of 'a' or 'b'.)
683f5b1c8a1SJohn Marino */
684f5b1c8a1SJohn Marino
685f5b1c8a1SJohn Marino /* n1, n2 */
686f5b1c8a1SJohn Marino if (b->Z_is_one) {
687f5b1c8a1SJohn Marino if (!BN_copy(n1, &a->X))
688f5b1c8a1SJohn Marino goto end;
689f5b1c8a1SJohn Marino if (!BN_copy(n2, &a->Y))
690f5b1c8a1SJohn Marino goto end;
691f5b1c8a1SJohn Marino /* n1 = X_a */
692f5b1c8a1SJohn Marino /* n2 = Y_a */
693f5b1c8a1SJohn Marino } else {
694f5b1c8a1SJohn Marino if (!field_sqr(group, n0, &b->Z, ctx))
695f5b1c8a1SJohn Marino goto end;
696f5b1c8a1SJohn Marino if (!field_mul(group, n1, &a->X, n0, ctx))
697f5b1c8a1SJohn Marino goto end;
698f5b1c8a1SJohn Marino /* n1 = X_a * Z_b^2 */
699f5b1c8a1SJohn Marino
700f5b1c8a1SJohn Marino if (!field_mul(group, n0, n0, &b->Z, ctx))
701f5b1c8a1SJohn Marino goto end;
702f5b1c8a1SJohn Marino if (!field_mul(group, n2, &a->Y, n0, ctx))
703f5b1c8a1SJohn Marino goto end;
704f5b1c8a1SJohn Marino /* n2 = Y_a * Z_b^3 */
705f5b1c8a1SJohn Marino }
706f5b1c8a1SJohn Marino
707f5b1c8a1SJohn Marino /* n3, n4 */
708f5b1c8a1SJohn Marino if (a->Z_is_one) {
709f5b1c8a1SJohn Marino if (!BN_copy(n3, &b->X))
710f5b1c8a1SJohn Marino goto end;
711f5b1c8a1SJohn Marino if (!BN_copy(n4, &b->Y))
712f5b1c8a1SJohn Marino goto end;
713f5b1c8a1SJohn Marino /* n3 = X_b */
714f5b1c8a1SJohn Marino /* n4 = Y_b */
715f5b1c8a1SJohn Marino } else {
716f5b1c8a1SJohn Marino if (!field_sqr(group, n0, &a->Z, ctx))
717f5b1c8a1SJohn Marino goto end;
718f5b1c8a1SJohn Marino if (!field_mul(group, n3, &b->X, n0, ctx))
719f5b1c8a1SJohn Marino goto end;
720f5b1c8a1SJohn Marino /* n3 = X_b * Z_a^2 */
721f5b1c8a1SJohn Marino
722f5b1c8a1SJohn Marino if (!field_mul(group, n0, n0, &a->Z, ctx))
723f5b1c8a1SJohn Marino goto end;
724f5b1c8a1SJohn Marino if (!field_mul(group, n4, &b->Y, n0, ctx))
725f5b1c8a1SJohn Marino goto end;
726f5b1c8a1SJohn Marino /* n4 = Y_b * Z_a^3 */
727f5b1c8a1SJohn Marino }
728f5b1c8a1SJohn Marino
729f5b1c8a1SJohn Marino /* n5, n6 */
730f5b1c8a1SJohn Marino if (!BN_mod_sub_quick(n5, n1, n3, p))
731f5b1c8a1SJohn Marino goto end;
732f5b1c8a1SJohn Marino if (!BN_mod_sub_quick(n6, n2, n4, p))
733f5b1c8a1SJohn Marino goto end;
734f5b1c8a1SJohn Marino /* n5 = n1 - n3 */
735f5b1c8a1SJohn Marino /* n6 = n2 - n4 */
736f5b1c8a1SJohn Marino
737f5b1c8a1SJohn Marino if (BN_is_zero(n5)) {
738f5b1c8a1SJohn Marino if (BN_is_zero(n6)) {
739f5b1c8a1SJohn Marino /* a is the same point as b */
740f5b1c8a1SJohn Marino BN_CTX_end(ctx);
741f5b1c8a1SJohn Marino ret = EC_POINT_dbl(group, r, a, ctx);
742f5b1c8a1SJohn Marino ctx = NULL;
743f5b1c8a1SJohn Marino goto end;
744f5b1c8a1SJohn Marino } else {
745f5b1c8a1SJohn Marino /* a is the inverse of b */
746f5b1c8a1SJohn Marino BN_zero(&r->Z);
747f5b1c8a1SJohn Marino r->Z_is_one = 0;
748f5b1c8a1SJohn Marino ret = 1;
749f5b1c8a1SJohn Marino goto end;
750f5b1c8a1SJohn Marino }
751f5b1c8a1SJohn Marino }
752f5b1c8a1SJohn Marino /* 'n7', 'n8' */
753f5b1c8a1SJohn Marino if (!BN_mod_add_quick(n1, n1, n3, p))
754f5b1c8a1SJohn Marino goto end;
755f5b1c8a1SJohn Marino if (!BN_mod_add_quick(n2, n2, n4, p))
756f5b1c8a1SJohn Marino goto end;
757f5b1c8a1SJohn Marino /* 'n7' = n1 + n3 */
758f5b1c8a1SJohn Marino /* 'n8' = n2 + n4 */
759f5b1c8a1SJohn Marino
760f5b1c8a1SJohn Marino /* Z_r */
761f5b1c8a1SJohn Marino if (a->Z_is_one && b->Z_is_one) {
762f5b1c8a1SJohn Marino if (!BN_copy(&r->Z, n5))
763f5b1c8a1SJohn Marino goto end;
764f5b1c8a1SJohn Marino } else {
765f5b1c8a1SJohn Marino if (a->Z_is_one) {
766f5b1c8a1SJohn Marino if (!BN_copy(n0, &b->Z))
767f5b1c8a1SJohn Marino goto end;
768f5b1c8a1SJohn Marino } else if (b->Z_is_one) {
769f5b1c8a1SJohn Marino if (!BN_copy(n0, &a->Z))
770f5b1c8a1SJohn Marino goto end;
771f5b1c8a1SJohn Marino } else {
772f5b1c8a1SJohn Marino if (!field_mul(group, n0, &a->Z, &b->Z, ctx))
773f5b1c8a1SJohn Marino goto end;
774f5b1c8a1SJohn Marino }
775f5b1c8a1SJohn Marino if (!field_mul(group, &r->Z, n0, n5, ctx))
776f5b1c8a1SJohn Marino goto end;
777f5b1c8a1SJohn Marino }
778f5b1c8a1SJohn Marino r->Z_is_one = 0;
779f5b1c8a1SJohn Marino /* Z_r = Z_a * Z_b * n5 */
780f5b1c8a1SJohn Marino
781f5b1c8a1SJohn Marino /* X_r */
782f5b1c8a1SJohn Marino if (!field_sqr(group, n0, n6, ctx))
783f5b1c8a1SJohn Marino goto end;
784f5b1c8a1SJohn Marino if (!field_sqr(group, n4, n5, ctx))
785f5b1c8a1SJohn Marino goto end;
786f5b1c8a1SJohn Marino if (!field_mul(group, n3, n1, n4, ctx))
787f5b1c8a1SJohn Marino goto end;
788f5b1c8a1SJohn Marino if (!BN_mod_sub_quick(&r->X, n0, n3, p))
789f5b1c8a1SJohn Marino goto end;
790f5b1c8a1SJohn Marino /* X_r = n6^2 - n5^2 * 'n7' */
791f5b1c8a1SJohn Marino
792f5b1c8a1SJohn Marino /* 'n9' */
793f5b1c8a1SJohn Marino if (!BN_mod_lshift1_quick(n0, &r->X, p))
794f5b1c8a1SJohn Marino goto end;
795f5b1c8a1SJohn Marino if (!BN_mod_sub_quick(n0, n3, n0, p))
796f5b1c8a1SJohn Marino goto end;
797f5b1c8a1SJohn Marino /* n9 = n5^2 * 'n7' - 2 * X_r */
798f5b1c8a1SJohn Marino
799f5b1c8a1SJohn Marino /* Y_r */
800f5b1c8a1SJohn Marino if (!field_mul(group, n0, n0, n6, ctx))
801f5b1c8a1SJohn Marino goto end;
802f5b1c8a1SJohn Marino if (!field_mul(group, n5, n4, n5, ctx))
803f5b1c8a1SJohn Marino goto end; /* now n5 is n5^3 */
804f5b1c8a1SJohn Marino if (!field_mul(group, n1, n2, n5, ctx))
805f5b1c8a1SJohn Marino goto end;
806f5b1c8a1SJohn Marino if (!BN_mod_sub_quick(n0, n0, n1, p))
807f5b1c8a1SJohn Marino goto end;
808f5b1c8a1SJohn Marino if (BN_is_odd(n0))
809f5b1c8a1SJohn Marino if (!BN_add(n0, n0, p))
810f5b1c8a1SJohn Marino goto end;
811f5b1c8a1SJohn Marino /* now 0 <= n0 < 2*p, and n0 is even */
812f5b1c8a1SJohn Marino if (!BN_rshift1(&r->Y, n0))
813f5b1c8a1SJohn Marino goto end;
814f5b1c8a1SJohn Marino /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
815f5b1c8a1SJohn Marino
816f5b1c8a1SJohn Marino ret = 1;
817f5b1c8a1SJohn Marino
818f5b1c8a1SJohn Marino end:
819f5b1c8a1SJohn Marino if (ctx) /* otherwise we already called BN_CTX_end */
820f5b1c8a1SJohn Marino BN_CTX_end(ctx);
821f5b1c8a1SJohn Marino BN_CTX_free(new_ctx);
822f5b1c8a1SJohn Marino return ret;
823f5b1c8a1SJohn Marino }
824f5b1c8a1SJohn Marino
825f5b1c8a1SJohn Marino
826f5b1c8a1SJohn Marino int
ec_GFp_simple_dbl(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,BN_CTX * ctx)827f5b1c8a1SJohn Marino ec_GFp_simple_dbl(const EC_GROUP * group, EC_POINT * r, const EC_POINT * a, BN_CTX * ctx)
828f5b1c8a1SJohn Marino {
829f5b1c8a1SJohn Marino int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
830f5b1c8a1SJohn Marino int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
831f5b1c8a1SJohn Marino const BIGNUM *p;
832f5b1c8a1SJohn Marino BN_CTX *new_ctx = NULL;
833f5b1c8a1SJohn Marino BIGNUM *n0, *n1, *n2, *n3;
834f5b1c8a1SJohn Marino int ret = 0;
835f5b1c8a1SJohn Marino
836f5b1c8a1SJohn Marino if (EC_POINT_is_at_infinity(group, a) > 0) {
837f5b1c8a1SJohn Marino BN_zero(&r->Z);
838f5b1c8a1SJohn Marino r->Z_is_one = 0;
839f5b1c8a1SJohn Marino return 1;
840f5b1c8a1SJohn Marino }
841f5b1c8a1SJohn Marino field_mul = group->meth->field_mul;
842f5b1c8a1SJohn Marino field_sqr = group->meth->field_sqr;
843f5b1c8a1SJohn Marino p = &group->field;
844f5b1c8a1SJohn Marino
845f5b1c8a1SJohn Marino if (ctx == NULL) {
846f5b1c8a1SJohn Marino ctx = new_ctx = BN_CTX_new();
847f5b1c8a1SJohn Marino if (ctx == NULL)
848f5b1c8a1SJohn Marino return 0;
849f5b1c8a1SJohn Marino }
850f5b1c8a1SJohn Marino BN_CTX_start(ctx);
851f5b1c8a1SJohn Marino if ((n0 = BN_CTX_get(ctx)) == NULL)
852f5b1c8a1SJohn Marino goto err;
853f5b1c8a1SJohn Marino if ((n1 = BN_CTX_get(ctx)) == NULL)
854f5b1c8a1SJohn Marino goto err;
855f5b1c8a1SJohn Marino if ((n2 = BN_CTX_get(ctx)) == NULL)
856f5b1c8a1SJohn Marino goto err;
857f5b1c8a1SJohn Marino if ((n3 = BN_CTX_get(ctx)) == NULL)
858f5b1c8a1SJohn Marino goto err;
859f5b1c8a1SJohn Marino
860f5b1c8a1SJohn Marino /*
861f5b1c8a1SJohn Marino * Note that in this function we must not read components of 'a' once
862f5b1c8a1SJohn Marino * we have written the corresponding components of 'r'. ('r' might
863f5b1c8a1SJohn Marino * the same as 'a'.)
864f5b1c8a1SJohn Marino */
865f5b1c8a1SJohn Marino
866f5b1c8a1SJohn Marino /* n1 */
867f5b1c8a1SJohn Marino if (a->Z_is_one) {
868f5b1c8a1SJohn Marino if (!field_sqr(group, n0, &a->X, ctx))
869f5b1c8a1SJohn Marino goto err;
870f5b1c8a1SJohn Marino if (!BN_mod_lshift1_quick(n1, n0, p))
871f5b1c8a1SJohn Marino goto err;
872f5b1c8a1SJohn Marino if (!BN_mod_add_quick(n0, n0, n1, p))
873f5b1c8a1SJohn Marino goto err;
874f5b1c8a1SJohn Marino if (!BN_mod_add_quick(n1, n0, &group->a, p))
875f5b1c8a1SJohn Marino goto err;
876f5b1c8a1SJohn Marino /* n1 = 3 * X_a^2 + a_curve */
877f5b1c8a1SJohn Marino } else if (group->a_is_minus3) {
878f5b1c8a1SJohn Marino if (!field_sqr(group, n1, &a->Z, ctx))
879f5b1c8a1SJohn Marino goto err;
880f5b1c8a1SJohn Marino if (!BN_mod_add_quick(n0, &a->X, n1, p))
881f5b1c8a1SJohn Marino goto err;
882f5b1c8a1SJohn Marino if (!BN_mod_sub_quick(n2, &a->X, n1, p))
883f5b1c8a1SJohn Marino goto err;
884f5b1c8a1SJohn Marino if (!field_mul(group, n1, n0, n2, ctx))
885f5b1c8a1SJohn Marino goto err;
886f5b1c8a1SJohn Marino if (!BN_mod_lshift1_quick(n0, n1, p))
887f5b1c8a1SJohn Marino goto err;
888f5b1c8a1SJohn Marino if (!BN_mod_add_quick(n1, n0, n1, p))
889f5b1c8a1SJohn Marino goto err;
890f5b1c8a1SJohn Marino /*
891f5b1c8a1SJohn Marino * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) = 3 * X_a^2 - 3 *
892f5b1c8a1SJohn Marino * Z_a^4
893f5b1c8a1SJohn Marino */
894f5b1c8a1SJohn Marino } else {
895f5b1c8a1SJohn Marino if (!field_sqr(group, n0, &a->X, ctx))
896f5b1c8a1SJohn Marino goto err;
897f5b1c8a1SJohn Marino if (!BN_mod_lshift1_quick(n1, n0, p))
898f5b1c8a1SJohn Marino goto err;
899f5b1c8a1SJohn Marino if (!BN_mod_add_quick(n0, n0, n1, p))
900f5b1c8a1SJohn Marino goto err;
901f5b1c8a1SJohn Marino if (!field_sqr(group, n1, &a->Z, ctx))
902f5b1c8a1SJohn Marino goto err;
903f5b1c8a1SJohn Marino if (!field_sqr(group, n1, n1, ctx))
904f5b1c8a1SJohn Marino goto err;
905f5b1c8a1SJohn Marino if (!field_mul(group, n1, n1, &group->a, ctx))
906f5b1c8a1SJohn Marino goto err;
907f5b1c8a1SJohn Marino if (!BN_mod_add_quick(n1, n1, n0, p))
908f5b1c8a1SJohn Marino goto err;
909f5b1c8a1SJohn Marino /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
910f5b1c8a1SJohn Marino }
911f5b1c8a1SJohn Marino
912f5b1c8a1SJohn Marino /* Z_r */
913f5b1c8a1SJohn Marino if (a->Z_is_one) {
914f5b1c8a1SJohn Marino if (!BN_copy(n0, &a->Y))
915f5b1c8a1SJohn Marino goto err;
916f5b1c8a1SJohn Marino } else {
917f5b1c8a1SJohn Marino if (!field_mul(group, n0, &a->Y, &a->Z, ctx))
918f5b1c8a1SJohn Marino goto err;
919f5b1c8a1SJohn Marino }
920f5b1c8a1SJohn Marino if (!BN_mod_lshift1_quick(&r->Z, n0, p))
921f5b1c8a1SJohn Marino goto err;
922f5b1c8a1SJohn Marino r->Z_is_one = 0;
923f5b1c8a1SJohn Marino /* Z_r = 2 * Y_a * Z_a */
924f5b1c8a1SJohn Marino
925f5b1c8a1SJohn Marino /* n2 */
926f5b1c8a1SJohn Marino if (!field_sqr(group, n3, &a->Y, ctx))
927f5b1c8a1SJohn Marino goto err;
928f5b1c8a1SJohn Marino if (!field_mul(group, n2, &a->X, n3, ctx))
929f5b1c8a1SJohn Marino goto err;
930f5b1c8a1SJohn Marino if (!BN_mod_lshift_quick(n2, n2, 2, p))
931f5b1c8a1SJohn Marino goto err;
932f5b1c8a1SJohn Marino /* n2 = 4 * X_a * Y_a^2 */
933f5b1c8a1SJohn Marino
934f5b1c8a1SJohn Marino /* X_r */
935f5b1c8a1SJohn Marino if (!BN_mod_lshift1_quick(n0, n2, p))
936f5b1c8a1SJohn Marino goto err;
937f5b1c8a1SJohn Marino if (!field_sqr(group, &r->X, n1, ctx))
938f5b1c8a1SJohn Marino goto err;
939f5b1c8a1SJohn Marino if (!BN_mod_sub_quick(&r->X, &r->X, n0, p))
940f5b1c8a1SJohn Marino goto err;
941f5b1c8a1SJohn Marino /* X_r = n1^2 - 2 * n2 */
942f5b1c8a1SJohn Marino
943f5b1c8a1SJohn Marino /* n3 */
944f5b1c8a1SJohn Marino if (!field_sqr(group, n0, n3, ctx))
945f5b1c8a1SJohn Marino goto err;
946f5b1c8a1SJohn Marino if (!BN_mod_lshift_quick(n3, n0, 3, p))
947f5b1c8a1SJohn Marino goto err;
948f5b1c8a1SJohn Marino /* n3 = 8 * Y_a^4 */
949f5b1c8a1SJohn Marino
950f5b1c8a1SJohn Marino /* Y_r */
951f5b1c8a1SJohn Marino if (!BN_mod_sub_quick(n0, n2, &r->X, p))
952f5b1c8a1SJohn Marino goto err;
953f5b1c8a1SJohn Marino if (!field_mul(group, n0, n1, n0, ctx))
954f5b1c8a1SJohn Marino goto err;
955f5b1c8a1SJohn Marino if (!BN_mod_sub_quick(&r->Y, n0, n3, p))
956f5b1c8a1SJohn Marino goto err;
957f5b1c8a1SJohn Marino /* Y_r = n1 * (n2 - X_r) - n3 */
958f5b1c8a1SJohn Marino
959f5b1c8a1SJohn Marino ret = 1;
960f5b1c8a1SJohn Marino
961f5b1c8a1SJohn Marino err:
962f5b1c8a1SJohn Marino BN_CTX_end(ctx);
963f5b1c8a1SJohn Marino BN_CTX_free(new_ctx);
964f5b1c8a1SJohn Marino return ret;
965f5b1c8a1SJohn Marino }
966f5b1c8a1SJohn Marino
967f5b1c8a1SJohn Marino
968f5b1c8a1SJohn Marino int
ec_GFp_simple_invert(const EC_GROUP * group,EC_POINT * point,BN_CTX * ctx)969f5b1c8a1SJohn Marino ec_GFp_simple_invert(const EC_GROUP * group, EC_POINT * point, BN_CTX * ctx)
970f5b1c8a1SJohn Marino {
971f5b1c8a1SJohn Marino if (EC_POINT_is_at_infinity(group, point) > 0 || BN_is_zero(&point->Y))
972f5b1c8a1SJohn Marino /* point is its own inverse */
973f5b1c8a1SJohn Marino return 1;
974f5b1c8a1SJohn Marino
975f5b1c8a1SJohn Marino return BN_usub(&point->Y, &group->field, &point->Y);
976f5b1c8a1SJohn Marino }
977f5b1c8a1SJohn Marino
978f5b1c8a1SJohn Marino
979f5b1c8a1SJohn Marino int
ec_GFp_simple_is_at_infinity(const EC_GROUP * group,const EC_POINT * point)980f5b1c8a1SJohn Marino ec_GFp_simple_is_at_infinity(const EC_GROUP * group, const EC_POINT * point)
981f5b1c8a1SJohn Marino {
982f5b1c8a1SJohn Marino return BN_is_zero(&point->Z);
983f5b1c8a1SJohn Marino }
984f5b1c8a1SJohn Marino
985f5b1c8a1SJohn Marino
986f5b1c8a1SJohn Marino int
ec_GFp_simple_is_on_curve(const EC_GROUP * group,const EC_POINT * point,BN_CTX * ctx)987f5b1c8a1SJohn Marino ec_GFp_simple_is_on_curve(const EC_GROUP * group, const EC_POINT * point, BN_CTX * ctx)
988f5b1c8a1SJohn Marino {
989f5b1c8a1SJohn Marino int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
990f5b1c8a1SJohn Marino int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
991f5b1c8a1SJohn Marino const BIGNUM *p;
992f5b1c8a1SJohn Marino BN_CTX *new_ctx = NULL;
993f5b1c8a1SJohn Marino BIGNUM *rh, *tmp, *Z4, *Z6;
994f5b1c8a1SJohn Marino int ret = -1;
995f5b1c8a1SJohn Marino
996f5b1c8a1SJohn Marino if (EC_POINT_is_at_infinity(group, point) > 0)
997f5b1c8a1SJohn Marino return 1;
998f5b1c8a1SJohn Marino
999f5b1c8a1SJohn Marino field_mul = group->meth->field_mul;
1000f5b1c8a1SJohn Marino field_sqr = group->meth->field_sqr;
1001f5b1c8a1SJohn Marino p = &group->field;
1002f5b1c8a1SJohn Marino
1003f5b1c8a1SJohn Marino if (ctx == NULL) {
1004f5b1c8a1SJohn Marino ctx = new_ctx = BN_CTX_new();
1005f5b1c8a1SJohn Marino if (ctx == NULL)
1006f5b1c8a1SJohn Marino return -1;
1007f5b1c8a1SJohn Marino }
1008f5b1c8a1SJohn Marino BN_CTX_start(ctx);
1009f5b1c8a1SJohn Marino if ((rh = BN_CTX_get(ctx)) == NULL)
1010f5b1c8a1SJohn Marino goto err;
1011f5b1c8a1SJohn Marino if ((tmp = BN_CTX_get(ctx)) == NULL)
1012f5b1c8a1SJohn Marino goto err;
1013f5b1c8a1SJohn Marino if ((Z4 = BN_CTX_get(ctx)) == NULL)
1014f5b1c8a1SJohn Marino goto err;
1015f5b1c8a1SJohn Marino if ((Z6 = BN_CTX_get(ctx)) == NULL)
1016f5b1c8a1SJohn Marino goto err;
1017f5b1c8a1SJohn Marino
1018f5b1c8a1SJohn Marino /*
1019f5b1c8a1SJohn Marino * We have a curve defined by a Weierstrass equation y^2 = x^3 + a*x
1020f5b1c8a1SJohn Marino * + b. The point to consider is given in Jacobian projective
1021f5b1c8a1SJohn Marino * coordinates where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3).
1022f5b1c8a1SJohn Marino * Substituting this and multiplying by Z^6 transforms the above
1023f5b1c8a1SJohn Marino * equation into Y^2 = X^3 + a*X*Z^4 + b*Z^6. To test this, we add up
1024f5b1c8a1SJohn Marino * the right-hand side in 'rh'.
1025f5b1c8a1SJohn Marino */
1026f5b1c8a1SJohn Marino
1027f5b1c8a1SJohn Marino /* rh := X^2 */
1028f5b1c8a1SJohn Marino if (!field_sqr(group, rh, &point->X, ctx))
1029f5b1c8a1SJohn Marino goto err;
1030f5b1c8a1SJohn Marino
1031f5b1c8a1SJohn Marino if (!point->Z_is_one) {
1032f5b1c8a1SJohn Marino if (!field_sqr(group, tmp, &point->Z, ctx))
1033f5b1c8a1SJohn Marino goto err;
1034f5b1c8a1SJohn Marino if (!field_sqr(group, Z4, tmp, ctx))
1035f5b1c8a1SJohn Marino goto err;
1036f5b1c8a1SJohn Marino if (!field_mul(group, Z6, Z4, tmp, ctx))
1037f5b1c8a1SJohn Marino goto err;
1038f5b1c8a1SJohn Marino
1039f5b1c8a1SJohn Marino /* rh := (rh + a*Z^4)*X */
1040f5b1c8a1SJohn Marino if (group->a_is_minus3) {
1041f5b1c8a1SJohn Marino if (!BN_mod_lshift1_quick(tmp, Z4, p))
1042f5b1c8a1SJohn Marino goto err;
1043f5b1c8a1SJohn Marino if (!BN_mod_add_quick(tmp, tmp, Z4, p))
1044f5b1c8a1SJohn Marino goto err;
1045f5b1c8a1SJohn Marino if (!BN_mod_sub_quick(rh, rh, tmp, p))
1046f5b1c8a1SJohn Marino goto err;
1047f5b1c8a1SJohn Marino if (!field_mul(group, rh, rh, &point->X, ctx))
1048f5b1c8a1SJohn Marino goto err;
1049f5b1c8a1SJohn Marino } else {
1050f5b1c8a1SJohn Marino if (!field_mul(group, tmp, Z4, &group->a, ctx))
1051f5b1c8a1SJohn Marino goto err;
1052f5b1c8a1SJohn Marino if (!BN_mod_add_quick(rh, rh, tmp, p))
1053f5b1c8a1SJohn Marino goto err;
1054f5b1c8a1SJohn Marino if (!field_mul(group, rh, rh, &point->X, ctx))
1055f5b1c8a1SJohn Marino goto err;
1056f5b1c8a1SJohn Marino }
1057f5b1c8a1SJohn Marino
1058f5b1c8a1SJohn Marino /* rh := rh + b*Z^6 */
1059f5b1c8a1SJohn Marino if (!field_mul(group, tmp, &group->b, Z6, ctx))
1060f5b1c8a1SJohn Marino goto err;
1061f5b1c8a1SJohn Marino if (!BN_mod_add_quick(rh, rh, tmp, p))
1062f5b1c8a1SJohn Marino goto err;
1063f5b1c8a1SJohn Marino } else {
1064f5b1c8a1SJohn Marino /* point->Z_is_one */
1065f5b1c8a1SJohn Marino
1066f5b1c8a1SJohn Marino /* rh := (rh + a)*X */
1067f5b1c8a1SJohn Marino if (!BN_mod_add_quick(rh, rh, &group->a, p))
1068f5b1c8a1SJohn Marino goto err;
1069f5b1c8a1SJohn Marino if (!field_mul(group, rh, rh, &point->X, ctx))
1070f5b1c8a1SJohn Marino goto err;
1071f5b1c8a1SJohn Marino /* rh := rh + b */
1072f5b1c8a1SJohn Marino if (!BN_mod_add_quick(rh, rh, &group->b, p))
1073f5b1c8a1SJohn Marino goto err;
1074f5b1c8a1SJohn Marino }
1075f5b1c8a1SJohn Marino
1076f5b1c8a1SJohn Marino /* 'lh' := Y^2 */
1077f5b1c8a1SJohn Marino if (!field_sqr(group, tmp, &point->Y, ctx))
1078f5b1c8a1SJohn Marino goto err;
1079f5b1c8a1SJohn Marino
1080f5b1c8a1SJohn Marino ret = (0 == BN_ucmp(tmp, rh));
1081f5b1c8a1SJohn Marino
1082f5b1c8a1SJohn Marino err:
1083f5b1c8a1SJohn Marino BN_CTX_end(ctx);
1084f5b1c8a1SJohn Marino BN_CTX_free(new_ctx);
1085f5b1c8a1SJohn Marino return ret;
1086f5b1c8a1SJohn Marino }
1087f5b1c8a1SJohn Marino
1088f5b1c8a1SJohn Marino
1089f5b1c8a1SJohn Marino int
ec_GFp_simple_cmp(const EC_GROUP * group,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)1090f5b1c8a1SJohn Marino ec_GFp_simple_cmp(const EC_GROUP * group, const EC_POINT * a, const EC_POINT * b, BN_CTX * ctx)
1091f5b1c8a1SJohn Marino {
1092f5b1c8a1SJohn Marino /*
1093f5b1c8a1SJohn Marino * return values: -1 error 0 equal (in affine coordinates) 1
1094f5b1c8a1SJohn Marino * not equal
1095f5b1c8a1SJohn Marino */
1096f5b1c8a1SJohn Marino
1097f5b1c8a1SJohn Marino int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1098f5b1c8a1SJohn Marino int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1099f5b1c8a1SJohn Marino BN_CTX *new_ctx = NULL;
1100f5b1c8a1SJohn Marino BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
1101f5b1c8a1SJohn Marino const BIGNUM *tmp1_, *tmp2_;
1102f5b1c8a1SJohn Marino int ret = -1;
1103f5b1c8a1SJohn Marino
1104f5b1c8a1SJohn Marino if (EC_POINT_is_at_infinity(group, a) > 0) {
1105f5b1c8a1SJohn Marino return EC_POINT_is_at_infinity(group, b) > 0 ? 0 : 1;
1106f5b1c8a1SJohn Marino }
1107f5b1c8a1SJohn Marino if (EC_POINT_is_at_infinity(group, b) > 0)
1108f5b1c8a1SJohn Marino return 1;
1109f5b1c8a1SJohn Marino
1110f5b1c8a1SJohn Marino if (a->Z_is_one && b->Z_is_one) {
1111f5b1c8a1SJohn Marino return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
1112f5b1c8a1SJohn Marino }
1113f5b1c8a1SJohn Marino field_mul = group->meth->field_mul;
1114f5b1c8a1SJohn Marino field_sqr = group->meth->field_sqr;
1115f5b1c8a1SJohn Marino
1116f5b1c8a1SJohn Marino if (ctx == NULL) {
1117f5b1c8a1SJohn Marino ctx = new_ctx = BN_CTX_new();
1118f5b1c8a1SJohn Marino if (ctx == NULL)
1119f5b1c8a1SJohn Marino return -1;
1120f5b1c8a1SJohn Marino }
1121f5b1c8a1SJohn Marino BN_CTX_start(ctx);
1122f5b1c8a1SJohn Marino if ((tmp1 = BN_CTX_get(ctx)) == NULL)
1123f5b1c8a1SJohn Marino goto end;
1124f5b1c8a1SJohn Marino if ((tmp2 = BN_CTX_get(ctx)) == NULL)
1125f5b1c8a1SJohn Marino goto end;
1126f5b1c8a1SJohn Marino if ((Za23 = BN_CTX_get(ctx)) == NULL)
1127f5b1c8a1SJohn Marino goto end;
1128f5b1c8a1SJohn Marino if ((Zb23 = BN_CTX_get(ctx)) == NULL)
1129f5b1c8a1SJohn Marino goto end;
1130f5b1c8a1SJohn Marino
1131f5b1c8a1SJohn Marino /*
1132f5b1c8a1SJohn Marino * We have to decide whether (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2,
1133f5b1c8a1SJohn Marino * Y_b/Z_b^3), or equivalently, whether (X_a*Z_b^2, Y_a*Z_b^3) =
1134f5b1c8a1SJohn Marino * (X_b*Z_a^2, Y_b*Z_a^3).
1135f5b1c8a1SJohn Marino */
1136f5b1c8a1SJohn Marino
1137f5b1c8a1SJohn Marino if (!b->Z_is_one) {
1138f5b1c8a1SJohn Marino if (!field_sqr(group, Zb23, &b->Z, ctx))
1139f5b1c8a1SJohn Marino goto end;
1140f5b1c8a1SJohn Marino if (!field_mul(group, tmp1, &a->X, Zb23, ctx))
1141f5b1c8a1SJohn Marino goto end;
1142f5b1c8a1SJohn Marino tmp1_ = tmp1;
1143f5b1c8a1SJohn Marino } else
1144f5b1c8a1SJohn Marino tmp1_ = &a->X;
1145f5b1c8a1SJohn Marino if (!a->Z_is_one) {
1146f5b1c8a1SJohn Marino if (!field_sqr(group, Za23, &a->Z, ctx))
1147f5b1c8a1SJohn Marino goto end;
1148f5b1c8a1SJohn Marino if (!field_mul(group, tmp2, &b->X, Za23, ctx))
1149f5b1c8a1SJohn Marino goto end;
1150f5b1c8a1SJohn Marino tmp2_ = tmp2;
1151f5b1c8a1SJohn Marino } else
1152f5b1c8a1SJohn Marino tmp2_ = &b->X;
1153f5b1c8a1SJohn Marino
1154f5b1c8a1SJohn Marino /* compare X_a*Z_b^2 with X_b*Z_a^2 */
1155f5b1c8a1SJohn Marino if (BN_cmp(tmp1_, tmp2_) != 0) {
1156f5b1c8a1SJohn Marino ret = 1; /* points differ */
1157f5b1c8a1SJohn Marino goto end;
1158f5b1c8a1SJohn Marino }
1159f5b1c8a1SJohn Marino if (!b->Z_is_one) {
1160f5b1c8a1SJohn Marino if (!field_mul(group, Zb23, Zb23, &b->Z, ctx))
1161f5b1c8a1SJohn Marino goto end;
1162f5b1c8a1SJohn Marino if (!field_mul(group, tmp1, &a->Y, Zb23, ctx))
1163f5b1c8a1SJohn Marino goto end;
1164f5b1c8a1SJohn Marino /* tmp1_ = tmp1 */
1165f5b1c8a1SJohn Marino } else
1166f5b1c8a1SJohn Marino tmp1_ = &a->Y;
1167f5b1c8a1SJohn Marino if (!a->Z_is_one) {
1168f5b1c8a1SJohn Marino if (!field_mul(group, Za23, Za23, &a->Z, ctx))
1169f5b1c8a1SJohn Marino goto end;
1170f5b1c8a1SJohn Marino if (!field_mul(group, tmp2, &b->Y, Za23, ctx))
1171f5b1c8a1SJohn Marino goto end;
1172f5b1c8a1SJohn Marino /* tmp2_ = tmp2 */
1173f5b1c8a1SJohn Marino } else
1174f5b1c8a1SJohn Marino tmp2_ = &b->Y;
1175f5b1c8a1SJohn Marino
1176f5b1c8a1SJohn Marino /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */
1177f5b1c8a1SJohn Marino if (BN_cmp(tmp1_, tmp2_) != 0) {
1178f5b1c8a1SJohn Marino ret = 1; /* points differ */
1179f5b1c8a1SJohn Marino goto end;
1180f5b1c8a1SJohn Marino }
1181f5b1c8a1SJohn Marino /* points are equal */
1182f5b1c8a1SJohn Marino ret = 0;
1183f5b1c8a1SJohn Marino
1184f5b1c8a1SJohn Marino end:
1185f5b1c8a1SJohn Marino BN_CTX_end(ctx);
1186f5b1c8a1SJohn Marino BN_CTX_free(new_ctx);
1187f5b1c8a1SJohn Marino return ret;
1188f5b1c8a1SJohn Marino }
1189f5b1c8a1SJohn Marino
1190f5b1c8a1SJohn Marino
1191f5b1c8a1SJohn Marino int
ec_GFp_simple_make_affine(const EC_GROUP * group,EC_POINT * point,BN_CTX * ctx)1192f5b1c8a1SJohn Marino ec_GFp_simple_make_affine(const EC_GROUP * group, EC_POINT * point, BN_CTX * ctx)
1193f5b1c8a1SJohn Marino {
1194f5b1c8a1SJohn Marino BN_CTX *new_ctx = NULL;
1195f5b1c8a1SJohn Marino BIGNUM *x, *y;
1196f5b1c8a1SJohn Marino int ret = 0;
1197f5b1c8a1SJohn Marino
1198f5b1c8a1SJohn Marino if (point->Z_is_one || EC_POINT_is_at_infinity(group, point) > 0)
1199f5b1c8a1SJohn Marino return 1;
1200f5b1c8a1SJohn Marino
1201f5b1c8a1SJohn Marino if (ctx == NULL) {
1202f5b1c8a1SJohn Marino ctx = new_ctx = BN_CTX_new();
1203f5b1c8a1SJohn Marino if (ctx == NULL)
1204f5b1c8a1SJohn Marino return 0;
1205f5b1c8a1SJohn Marino }
1206f5b1c8a1SJohn Marino BN_CTX_start(ctx);
1207f5b1c8a1SJohn Marino if ((x = BN_CTX_get(ctx)) == NULL)
1208f5b1c8a1SJohn Marino goto err;
1209f5b1c8a1SJohn Marino if ((y = BN_CTX_get(ctx)) == NULL)
1210f5b1c8a1SJohn Marino goto err;
1211f5b1c8a1SJohn Marino
1212*de0e0e4dSAntonio Huete Jimenez if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
1213f5b1c8a1SJohn Marino goto err;
1214*de0e0e4dSAntonio Huete Jimenez if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx))
1215f5b1c8a1SJohn Marino goto err;
1216f5b1c8a1SJohn Marino if (!point->Z_is_one) {
121772c33676SMaxim Ag ECerror(ERR_R_INTERNAL_ERROR);
1218f5b1c8a1SJohn Marino goto err;
1219f5b1c8a1SJohn Marino }
1220f5b1c8a1SJohn Marino ret = 1;
1221f5b1c8a1SJohn Marino
1222f5b1c8a1SJohn Marino err:
1223f5b1c8a1SJohn Marino BN_CTX_end(ctx);
1224f5b1c8a1SJohn Marino BN_CTX_free(new_ctx);
1225f5b1c8a1SJohn Marino return ret;
1226f5b1c8a1SJohn Marino }
1227f5b1c8a1SJohn Marino
1228f5b1c8a1SJohn Marino
1229f5b1c8a1SJohn Marino int
ec_GFp_simple_points_make_affine(const EC_GROUP * group,size_t num,EC_POINT * points[],BN_CTX * ctx)1230f5b1c8a1SJohn Marino ec_GFp_simple_points_make_affine(const EC_GROUP * group, size_t num, EC_POINT * points[], BN_CTX * ctx)
1231f5b1c8a1SJohn Marino {
1232f5b1c8a1SJohn Marino BN_CTX *new_ctx = NULL;
1233f5b1c8a1SJohn Marino BIGNUM *tmp0, *tmp1;
1234f5b1c8a1SJohn Marino size_t pow2 = 0;
1235f5b1c8a1SJohn Marino BIGNUM **heap = NULL;
1236f5b1c8a1SJohn Marino size_t i;
1237f5b1c8a1SJohn Marino int ret = 0;
1238f5b1c8a1SJohn Marino
1239f5b1c8a1SJohn Marino if (num == 0)
1240f5b1c8a1SJohn Marino return 1;
1241f5b1c8a1SJohn Marino
1242f5b1c8a1SJohn Marino if (ctx == NULL) {
1243f5b1c8a1SJohn Marino ctx = new_ctx = BN_CTX_new();
1244f5b1c8a1SJohn Marino if (ctx == NULL)
1245f5b1c8a1SJohn Marino return 0;
1246f5b1c8a1SJohn Marino }
1247f5b1c8a1SJohn Marino BN_CTX_start(ctx);
1248f5b1c8a1SJohn Marino if ((tmp0 = BN_CTX_get(ctx)) == NULL)
1249f5b1c8a1SJohn Marino goto err;
1250f5b1c8a1SJohn Marino if ((tmp1 = BN_CTX_get(ctx)) == NULL)
1251f5b1c8a1SJohn Marino goto err;
1252f5b1c8a1SJohn Marino
1253f5b1c8a1SJohn Marino /*
1254f5b1c8a1SJohn Marino * Before converting the individual points, compute inverses of all Z
1255f5b1c8a1SJohn Marino * values. Modular inversion is rather slow, but luckily we can do
1256f5b1c8a1SJohn Marino * with a single explicit inversion, plus about 3 multiplications per
1257f5b1c8a1SJohn Marino * input value.
1258f5b1c8a1SJohn Marino */
1259f5b1c8a1SJohn Marino
1260f5b1c8a1SJohn Marino pow2 = 1;
1261f5b1c8a1SJohn Marino while (num > pow2)
1262f5b1c8a1SJohn Marino pow2 <<= 1;
1263f5b1c8a1SJohn Marino /*
1264f5b1c8a1SJohn Marino * Now pow2 is the smallest power of 2 satifsying pow2 >= num. We
1265f5b1c8a1SJohn Marino * need twice that.
1266f5b1c8a1SJohn Marino */
1267f5b1c8a1SJohn Marino pow2 <<= 1;
1268f5b1c8a1SJohn Marino
1269f5b1c8a1SJohn Marino heap = reallocarray(NULL, pow2, sizeof heap[0]);
1270f5b1c8a1SJohn Marino if (heap == NULL)
1271f5b1c8a1SJohn Marino goto err;
1272f5b1c8a1SJohn Marino
1273f5b1c8a1SJohn Marino /*
1274f5b1c8a1SJohn Marino * The array is used as a binary tree, exactly as in heapsort:
1275f5b1c8a1SJohn Marino *
1276f5b1c8a1SJohn Marino * heap[1] heap[2] heap[3] heap[4] heap[5]
1277f5b1c8a1SJohn Marino * heap[6] heap[7] heap[8]heap[9] heap[10]heap[11]
1278f5b1c8a1SJohn Marino * heap[12]heap[13] heap[14] heap[15]
1279f5b1c8a1SJohn Marino *
1280f5b1c8a1SJohn Marino * We put the Z's in the last line; then we set each other node to the
1281f5b1c8a1SJohn Marino * product of its two child-nodes (where empty or 0 entries are
1282f5b1c8a1SJohn Marino * treated as ones); then we invert heap[1]; then we invert each
1283f5b1c8a1SJohn Marino * other node by replacing it by the product of its parent (after
1284f5b1c8a1SJohn Marino * inversion) and its sibling (before inversion).
1285f5b1c8a1SJohn Marino */
1286f5b1c8a1SJohn Marino heap[0] = NULL;
1287f5b1c8a1SJohn Marino for (i = pow2 / 2 - 1; i > 0; i--)
1288f5b1c8a1SJohn Marino heap[i] = NULL;
1289f5b1c8a1SJohn Marino for (i = 0; i < num; i++)
1290f5b1c8a1SJohn Marino heap[pow2 / 2 + i] = &points[i]->Z;
1291f5b1c8a1SJohn Marino for (i = pow2 / 2 + num; i < pow2; i++)
1292f5b1c8a1SJohn Marino heap[i] = NULL;
1293f5b1c8a1SJohn Marino
1294f5b1c8a1SJohn Marino /* set each node to the product of its children */
1295f5b1c8a1SJohn Marino for (i = pow2 / 2 - 1; i > 0; i--) {
1296f5b1c8a1SJohn Marino heap[i] = BN_new();
1297f5b1c8a1SJohn Marino if (heap[i] == NULL)
1298f5b1c8a1SJohn Marino goto err;
1299f5b1c8a1SJohn Marino
1300f5b1c8a1SJohn Marino if (heap[2 * i] != NULL) {
1301f5b1c8a1SJohn Marino if ((heap[2 * i + 1] == NULL) || BN_is_zero(heap[2 * i + 1])) {
1302f5b1c8a1SJohn Marino if (!BN_copy(heap[i], heap[2 * i]))
1303f5b1c8a1SJohn Marino goto err;
1304f5b1c8a1SJohn Marino } else {
1305f5b1c8a1SJohn Marino if (BN_is_zero(heap[2 * i])) {
1306f5b1c8a1SJohn Marino if (!BN_copy(heap[i], heap[2 * i + 1]))
1307f5b1c8a1SJohn Marino goto err;
1308f5b1c8a1SJohn Marino } else {
1309f5b1c8a1SJohn Marino if (!group->meth->field_mul(group, heap[i],
1310f5b1c8a1SJohn Marino heap[2 * i], heap[2 * i + 1], ctx))
1311f5b1c8a1SJohn Marino goto err;
1312f5b1c8a1SJohn Marino }
1313f5b1c8a1SJohn Marino }
1314f5b1c8a1SJohn Marino }
1315f5b1c8a1SJohn Marino }
1316f5b1c8a1SJohn Marino
1317f5b1c8a1SJohn Marino /* invert heap[1] */
1318f5b1c8a1SJohn Marino if (!BN_is_zero(heap[1])) {
1319*de0e0e4dSAntonio Huete Jimenez if (BN_mod_inverse_ct(heap[1], heap[1], &group->field, ctx) == NULL) {
132072c33676SMaxim Ag ECerror(ERR_R_BN_LIB);
1321f5b1c8a1SJohn Marino goto err;
1322f5b1c8a1SJohn Marino }
1323f5b1c8a1SJohn Marino }
1324f5b1c8a1SJohn Marino if (group->meth->field_encode != 0) {
1325f5b1c8a1SJohn Marino /*
1326f5b1c8a1SJohn Marino * in the Montgomery case, we just turned R*H (representing
1327f5b1c8a1SJohn Marino * H) into 1/(R*H), but we need R*(1/H) (representing
1328f5b1c8a1SJohn Marino * 1/H); i.e. we have need to multiply by the Montgomery
1329f5b1c8a1SJohn Marino * factor twice
1330f5b1c8a1SJohn Marino */
1331f5b1c8a1SJohn Marino if (!group->meth->field_encode(group, heap[1], heap[1], ctx))
1332f5b1c8a1SJohn Marino goto err;
1333f5b1c8a1SJohn Marino if (!group->meth->field_encode(group, heap[1], heap[1], ctx))
1334f5b1c8a1SJohn Marino goto err;
1335f5b1c8a1SJohn Marino }
1336f5b1c8a1SJohn Marino /* set other heap[i]'s to their inverses */
1337f5b1c8a1SJohn Marino for (i = 2; i < pow2 / 2 + num; i += 2) {
1338f5b1c8a1SJohn Marino /* i is even */
1339f5b1c8a1SJohn Marino if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1])) {
1340f5b1c8a1SJohn Marino if (!group->meth->field_mul(group, tmp0, heap[i / 2], heap[i + 1], ctx))
1341f5b1c8a1SJohn Marino goto err;
1342f5b1c8a1SJohn Marino if (!group->meth->field_mul(group, tmp1, heap[i / 2], heap[i], ctx))
1343f5b1c8a1SJohn Marino goto err;
1344f5b1c8a1SJohn Marino if (!BN_copy(heap[i], tmp0))
1345f5b1c8a1SJohn Marino goto err;
1346f5b1c8a1SJohn Marino if (!BN_copy(heap[i + 1], tmp1))
1347f5b1c8a1SJohn Marino goto err;
1348f5b1c8a1SJohn Marino } else {
1349f5b1c8a1SJohn Marino if (!BN_copy(heap[i], heap[i / 2]))
1350f5b1c8a1SJohn Marino goto err;
1351f5b1c8a1SJohn Marino }
1352f5b1c8a1SJohn Marino }
1353f5b1c8a1SJohn Marino
1354f5b1c8a1SJohn Marino /*
1355f5b1c8a1SJohn Marino * we have replaced all non-zero Z's by their inverses, now fix up
1356f5b1c8a1SJohn Marino * all the points
1357f5b1c8a1SJohn Marino */
1358f5b1c8a1SJohn Marino for (i = 0; i < num; i++) {
1359f5b1c8a1SJohn Marino EC_POINT *p = points[i];
1360f5b1c8a1SJohn Marino
1361f5b1c8a1SJohn Marino if (!BN_is_zero(&p->Z)) {
1362f5b1c8a1SJohn Marino /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */
1363f5b1c8a1SJohn Marino
1364f5b1c8a1SJohn Marino if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx))
1365f5b1c8a1SJohn Marino goto err;
1366f5b1c8a1SJohn Marino if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx))
1367f5b1c8a1SJohn Marino goto err;
1368f5b1c8a1SJohn Marino
1369f5b1c8a1SJohn Marino if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx))
1370f5b1c8a1SJohn Marino goto err;
1371f5b1c8a1SJohn Marino if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx))
1372f5b1c8a1SJohn Marino goto err;
1373f5b1c8a1SJohn Marino
1374f5b1c8a1SJohn Marino if (group->meth->field_set_to_one != 0) {
1375f5b1c8a1SJohn Marino if (!group->meth->field_set_to_one(group, &p->Z, ctx))
1376f5b1c8a1SJohn Marino goto err;
1377f5b1c8a1SJohn Marino } else {
1378f5b1c8a1SJohn Marino if (!BN_one(&p->Z))
1379f5b1c8a1SJohn Marino goto err;
1380f5b1c8a1SJohn Marino }
1381f5b1c8a1SJohn Marino p->Z_is_one = 1;
1382f5b1c8a1SJohn Marino }
1383f5b1c8a1SJohn Marino }
1384f5b1c8a1SJohn Marino
1385f5b1c8a1SJohn Marino ret = 1;
1386f5b1c8a1SJohn Marino
1387f5b1c8a1SJohn Marino err:
1388f5b1c8a1SJohn Marino BN_CTX_end(ctx);
1389f5b1c8a1SJohn Marino BN_CTX_free(new_ctx);
1390f5b1c8a1SJohn Marino if (heap != NULL) {
1391f5b1c8a1SJohn Marino /*
1392f5b1c8a1SJohn Marino * heap[pow2/2] .. heap[pow2-1] have not been allocated
1393f5b1c8a1SJohn Marino * locally!
1394f5b1c8a1SJohn Marino */
1395f5b1c8a1SJohn Marino for (i = pow2 / 2 - 1; i > 0; i--) {
1396f5b1c8a1SJohn Marino BN_clear_free(heap[i]);
1397f5b1c8a1SJohn Marino }
1398f5b1c8a1SJohn Marino free(heap);
1399f5b1c8a1SJohn Marino }
1400f5b1c8a1SJohn Marino return ret;
1401f5b1c8a1SJohn Marino }
1402f5b1c8a1SJohn Marino
1403f5b1c8a1SJohn Marino
1404f5b1c8a1SJohn Marino int
ec_GFp_simple_field_mul(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)1405f5b1c8a1SJohn Marino ec_GFp_simple_field_mul(const EC_GROUP * group, BIGNUM * r, const BIGNUM * a, const BIGNUM * b, BN_CTX * ctx)
1406f5b1c8a1SJohn Marino {
1407f5b1c8a1SJohn Marino return BN_mod_mul(r, a, b, &group->field, ctx);
1408f5b1c8a1SJohn Marino }
1409f5b1c8a1SJohn Marino
1410f5b1c8a1SJohn Marino int
ec_GFp_simple_field_sqr(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,BN_CTX * ctx)1411f5b1c8a1SJohn Marino ec_GFp_simple_field_sqr(const EC_GROUP * group, BIGNUM * r, const BIGNUM * a, BN_CTX * ctx)
1412f5b1c8a1SJohn Marino {
1413f5b1c8a1SJohn Marino return BN_mod_sqr(r, a, &group->field, ctx);
1414f5b1c8a1SJohn Marino }
141572c33676SMaxim Ag
141672c33676SMaxim Ag /*
141772c33676SMaxim Ag * Apply randomization of EC point projective coordinates:
141872c33676SMaxim Ag *
141972c33676SMaxim Ag * (X, Y, Z) = (lambda^2 * X, lambda^3 * Y, lambda * Z)
142072c33676SMaxim Ag *
142172c33676SMaxim Ag * where lambda is in the interval [1, group->field).
142272c33676SMaxim Ag */
142372c33676SMaxim Ag int
ec_GFp_simple_blind_coordinates(const EC_GROUP * group,EC_POINT * p,BN_CTX * ctx)142472c33676SMaxim Ag ec_GFp_simple_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx)
142572c33676SMaxim Ag {
142672c33676SMaxim Ag BIGNUM *lambda = NULL;
142772c33676SMaxim Ag BIGNUM *tmp = NULL;
142872c33676SMaxim Ag int ret = 0;
142972c33676SMaxim Ag
143072c33676SMaxim Ag BN_CTX_start(ctx);
143172c33676SMaxim Ag if ((lambda = BN_CTX_get(ctx)) == NULL)
143272c33676SMaxim Ag goto err;
143372c33676SMaxim Ag if ((tmp = BN_CTX_get(ctx)) == NULL)
143472c33676SMaxim Ag goto err;
143572c33676SMaxim Ag
143672c33676SMaxim Ag /* Generate lambda in [1, group->field - 1] */
143772c33676SMaxim Ag if (!bn_rand_interval(lambda, BN_value_one(), &group->field))
143872c33676SMaxim Ag goto err;
143972c33676SMaxim Ag
144072c33676SMaxim Ag if (group->meth->field_encode != NULL &&
144172c33676SMaxim Ag !group->meth->field_encode(group, lambda, lambda, ctx))
144272c33676SMaxim Ag goto err;
144372c33676SMaxim Ag
144472c33676SMaxim Ag /* Z = lambda * Z */
144572c33676SMaxim Ag if (!group->meth->field_mul(group, &p->Z, lambda, &p->Z, ctx))
144672c33676SMaxim Ag goto err;
144772c33676SMaxim Ag
144872c33676SMaxim Ag /* tmp = lambda^2 */
144972c33676SMaxim Ag if (!group->meth->field_sqr(group, tmp, lambda, ctx))
145072c33676SMaxim Ag goto err;
145172c33676SMaxim Ag
145272c33676SMaxim Ag /* X = lambda^2 * X */
145372c33676SMaxim Ag if (!group->meth->field_mul(group, &p->X, tmp, &p->X, ctx))
145472c33676SMaxim Ag goto err;
145572c33676SMaxim Ag
145672c33676SMaxim Ag /* tmp = lambda^3 */
145772c33676SMaxim Ag if (!group->meth->field_mul(group, tmp, tmp, lambda, ctx))
145872c33676SMaxim Ag goto err;
145972c33676SMaxim Ag
146072c33676SMaxim Ag /* Y = lambda^3 * Y */
146172c33676SMaxim Ag if (!group->meth->field_mul(group, &p->Y, tmp, &p->Y, ctx))
146272c33676SMaxim Ag goto err;
146372c33676SMaxim Ag
146472c33676SMaxim Ag /* Disable optimized arithmetics after replacing Z by lambda * Z. */
146572c33676SMaxim Ag p->Z_is_one = 0;
146672c33676SMaxim Ag
146772c33676SMaxim Ag ret = 1;
146872c33676SMaxim Ag
146972c33676SMaxim Ag err:
147072c33676SMaxim Ag BN_CTX_end(ctx);
147172c33676SMaxim Ag return ret;
147272c33676SMaxim Ag }
147372c33676SMaxim Ag
147472c33676SMaxim Ag
147572c33676SMaxim Ag #define EC_POINT_BN_set_flags(P, flags) do { \
147672c33676SMaxim Ag BN_set_flags(&(P)->X, (flags)); \
147772c33676SMaxim Ag BN_set_flags(&(P)->Y, (flags)); \
147872c33676SMaxim Ag BN_set_flags(&(P)->Z, (flags)); \
147972c33676SMaxim Ag } while(0)
148072c33676SMaxim Ag
148172c33676SMaxim Ag #define EC_POINT_CSWAP(c, a, b, w, t) do { \
148272c33676SMaxim Ag if (!BN_swap_ct(c, &(a)->X, &(b)->X, w) || \
148372c33676SMaxim Ag !BN_swap_ct(c, &(a)->Y, &(b)->Y, w) || \
148472c33676SMaxim Ag !BN_swap_ct(c, &(a)->Z, &(b)->Z, w)) \
148572c33676SMaxim Ag goto err; \
148672c33676SMaxim Ag t = ((a)->Z_is_one ^ (b)->Z_is_one) & (c); \
148772c33676SMaxim Ag (a)->Z_is_one ^= (t); \
148872c33676SMaxim Ag (b)->Z_is_one ^= (t); \
148972c33676SMaxim Ag } while(0)
149072c33676SMaxim Ag
149172c33676SMaxim Ag /*
149272c33676SMaxim Ag * This function computes (in constant time) a point multiplication over the
149372c33676SMaxim Ag * EC group.
149472c33676SMaxim Ag *
149572c33676SMaxim Ag * At a high level, it is Montgomery ladder with conditional swaps.
149672c33676SMaxim Ag *
149772c33676SMaxim Ag * It performs either a fixed point multiplication
149872c33676SMaxim Ag * (scalar * generator)
149972c33676SMaxim Ag * when point is NULL, or a variable point multiplication
150072c33676SMaxim Ag * (scalar * point)
150172c33676SMaxim Ag * when point is not NULL.
150272c33676SMaxim Ag *
150372c33676SMaxim Ag * scalar should be in the range [0,n) otherwise all constant time bets are off.
150472c33676SMaxim Ag *
150572c33676SMaxim Ag * NB: This says nothing about EC_POINT_add and EC_POINT_dbl,
150672c33676SMaxim Ag * which of course are not constant time themselves.
150772c33676SMaxim Ag *
150872c33676SMaxim Ag * The product is stored in r.
150972c33676SMaxim Ag *
151072c33676SMaxim Ag * Returns 1 on success, 0 otherwise.
151172c33676SMaxim Ag */
151272c33676SMaxim Ag static int
ec_GFp_simple_mul_ct(const EC_GROUP * group,EC_POINT * r,const BIGNUM * scalar,const EC_POINT * point,BN_CTX * ctx)151372c33676SMaxim Ag ec_GFp_simple_mul_ct(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
151472c33676SMaxim Ag const EC_POINT *point, BN_CTX *ctx)
151572c33676SMaxim Ag {
151672c33676SMaxim Ag int i, cardinality_bits, group_top, kbit, pbit, Z_is_one;
151772c33676SMaxim Ag EC_POINT *s = NULL;
151872c33676SMaxim Ag BIGNUM *k = NULL;
151972c33676SMaxim Ag BIGNUM *lambda = NULL;
152072c33676SMaxim Ag BIGNUM *cardinality = NULL;
152172c33676SMaxim Ag BN_CTX *new_ctx = NULL;
152272c33676SMaxim Ag int ret = 0;
152372c33676SMaxim Ag
152472c33676SMaxim Ag if (ctx == NULL && (ctx = new_ctx = BN_CTX_new()) == NULL)
152572c33676SMaxim Ag return 0;
152672c33676SMaxim Ag
152772c33676SMaxim Ag BN_CTX_start(ctx);
152872c33676SMaxim Ag
152972c33676SMaxim Ag if ((s = EC_POINT_new(group)) == NULL)
153072c33676SMaxim Ag goto err;
153172c33676SMaxim Ag
153272c33676SMaxim Ag if (point == NULL) {
153372c33676SMaxim Ag if (!EC_POINT_copy(s, group->generator))
153472c33676SMaxim Ag goto err;
153572c33676SMaxim Ag } else {
153672c33676SMaxim Ag if (!EC_POINT_copy(s, point))
153772c33676SMaxim Ag goto err;
153872c33676SMaxim Ag }
153972c33676SMaxim Ag
154072c33676SMaxim Ag EC_POINT_BN_set_flags(s, BN_FLG_CONSTTIME);
154172c33676SMaxim Ag
154272c33676SMaxim Ag if ((cardinality = BN_CTX_get(ctx)) == NULL)
154372c33676SMaxim Ag goto err;
154472c33676SMaxim Ag if ((lambda = BN_CTX_get(ctx)) == NULL)
154572c33676SMaxim Ag goto err;
154672c33676SMaxim Ag if ((k = BN_CTX_get(ctx)) == NULL)
154772c33676SMaxim Ag goto err;
154872c33676SMaxim Ag if (!BN_mul(cardinality, &group->order, &group->cofactor, ctx))
154972c33676SMaxim Ag goto err;
155072c33676SMaxim Ag
155172c33676SMaxim Ag /*
155272c33676SMaxim Ag * Group cardinalities are often on a word boundary.
155372c33676SMaxim Ag * So when we pad the scalar, some timing diff might
155472c33676SMaxim Ag * pop if it needs to be expanded due to carries.
155572c33676SMaxim Ag * So expand ahead of time.
155672c33676SMaxim Ag */
155772c33676SMaxim Ag cardinality_bits = BN_num_bits(cardinality);
155872c33676SMaxim Ag group_top = cardinality->top;
155972c33676SMaxim Ag if ((bn_wexpand(k, group_top + 2) == NULL) ||
156072c33676SMaxim Ag (bn_wexpand(lambda, group_top + 2) == NULL))
156172c33676SMaxim Ag goto err;
156272c33676SMaxim Ag
156372c33676SMaxim Ag if (!BN_copy(k, scalar))
156472c33676SMaxim Ag goto err;
156572c33676SMaxim Ag
156672c33676SMaxim Ag BN_set_flags(k, BN_FLG_CONSTTIME);
156772c33676SMaxim Ag
156872c33676SMaxim Ag if (BN_num_bits(k) > cardinality_bits || BN_is_negative(k)) {
156972c33676SMaxim Ag /*
157072c33676SMaxim Ag * This is an unusual input, and we don't guarantee
157172c33676SMaxim Ag * constant-timeness
157272c33676SMaxim Ag */
157372c33676SMaxim Ag if (!BN_nnmod(k, k, cardinality, ctx))
157472c33676SMaxim Ag goto err;
157572c33676SMaxim Ag }
157672c33676SMaxim Ag
157772c33676SMaxim Ag if (!BN_add(lambda, k, cardinality))
157872c33676SMaxim Ag goto err;
157972c33676SMaxim Ag BN_set_flags(lambda, BN_FLG_CONSTTIME);
158072c33676SMaxim Ag if (!BN_add(k, lambda, cardinality))
158172c33676SMaxim Ag goto err;
158272c33676SMaxim Ag /*
158372c33676SMaxim Ag * lambda := scalar + cardinality
158472c33676SMaxim Ag * k := scalar + 2*cardinality
158572c33676SMaxim Ag */
158672c33676SMaxim Ag kbit = BN_is_bit_set(lambda, cardinality_bits);
158772c33676SMaxim Ag if (!BN_swap_ct(kbit, k, lambda, group_top + 2))
158872c33676SMaxim Ag goto err;
158972c33676SMaxim Ag
159072c33676SMaxim Ag group_top = group->field.top;
159172c33676SMaxim Ag if ((bn_wexpand(&s->X, group_top) == NULL) ||
159272c33676SMaxim Ag (bn_wexpand(&s->Y, group_top) == NULL) ||
159372c33676SMaxim Ag (bn_wexpand(&s->Z, group_top) == NULL) ||
159472c33676SMaxim Ag (bn_wexpand(&r->X, group_top) == NULL) ||
159572c33676SMaxim Ag (bn_wexpand(&r->Y, group_top) == NULL) ||
159672c33676SMaxim Ag (bn_wexpand(&r->Z, group_top) == NULL))
159772c33676SMaxim Ag goto err;
159872c33676SMaxim Ag
159972c33676SMaxim Ag /*
160072c33676SMaxim Ag * Apply coordinate blinding for EC_POINT if the underlying EC_METHOD
160172c33676SMaxim Ag * implements it.
160272c33676SMaxim Ag */
160372c33676SMaxim Ag if (!ec_point_blind_coordinates(group, s, ctx))
160472c33676SMaxim Ag goto err;
160572c33676SMaxim Ag
160672c33676SMaxim Ag /* top bit is a 1, in a fixed pos */
160772c33676SMaxim Ag if (!EC_POINT_copy(r, s))
160872c33676SMaxim Ag goto err;
160972c33676SMaxim Ag
161072c33676SMaxim Ag EC_POINT_BN_set_flags(r, BN_FLG_CONSTTIME);
161172c33676SMaxim Ag
161272c33676SMaxim Ag if (!EC_POINT_dbl(group, s, s, ctx))
161372c33676SMaxim Ag goto err;
161472c33676SMaxim Ag
161572c33676SMaxim Ag pbit = 0;
161672c33676SMaxim Ag
161772c33676SMaxim Ag /*
161872c33676SMaxim Ag * The ladder step, with branches, is
161972c33676SMaxim Ag *
162072c33676SMaxim Ag * k[i] == 0: S = add(R, S), R = dbl(R)
162172c33676SMaxim Ag * k[i] == 1: R = add(S, R), S = dbl(S)
162272c33676SMaxim Ag *
162372c33676SMaxim Ag * Swapping R, S conditionally on k[i] leaves you with state
162472c33676SMaxim Ag *
162572c33676SMaxim Ag * k[i] == 0: T, U = R, S
162672c33676SMaxim Ag * k[i] == 1: T, U = S, R
162772c33676SMaxim Ag *
162872c33676SMaxim Ag * Then perform the ECC ops.
162972c33676SMaxim Ag *
163072c33676SMaxim Ag * U = add(T, U)
163172c33676SMaxim Ag * T = dbl(T)
163272c33676SMaxim Ag *
163372c33676SMaxim Ag * Which leaves you with state
163472c33676SMaxim Ag *
163572c33676SMaxim Ag * k[i] == 0: U = add(R, S), T = dbl(R)
163672c33676SMaxim Ag * k[i] == 1: U = add(S, R), T = dbl(S)
163772c33676SMaxim Ag *
163872c33676SMaxim Ag * Swapping T, U conditionally on k[i] leaves you with state
163972c33676SMaxim Ag *
164072c33676SMaxim Ag * k[i] == 0: R, S = T, U
164172c33676SMaxim Ag * k[i] == 1: R, S = U, T
164272c33676SMaxim Ag *
164372c33676SMaxim Ag * Which leaves you with state
164472c33676SMaxim Ag *
164572c33676SMaxim Ag * k[i] == 0: S = add(R, S), R = dbl(R)
164672c33676SMaxim Ag * k[i] == 1: R = add(S, R), S = dbl(S)
164772c33676SMaxim Ag *
164872c33676SMaxim Ag * So we get the same logic, but instead of a branch it's a
164972c33676SMaxim Ag * conditional swap, followed by ECC ops, then another conditional swap.
165072c33676SMaxim Ag *
165172c33676SMaxim Ag * Optimization: The end of iteration i and start of i-1 looks like
165272c33676SMaxim Ag *
165372c33676SMaxim Ag * ...
165472c33676SMaxim Ag * CSWAP(k[i], R, S)
165572c33676SMaxim Ag * ECC
165672c33676SMaxim Ag * CSWAP(k[i], R, S)
165772c33676SMaxim Ag * (next iteration)
165872c33676SMaxim Ag * CSWAP(k[i-1], R, S)
165972c33676SMaxim Ag * ECC
166072c33676SMaxim Ag * CSWAP(k[i-1], R, S)
166172c33676SMaxim Ag * ...
166272c33676SMaxim Ag *
166372c33676SMaxim Ag * So instead of two contiguous swaps, you can merge the condition
166472c33676SMaxim Ag * bits and do a single swap.
166572c33676SMaxim Ag *
166672c33676SMaxim Ag * k[i] k[i-1] Outcome
166772c33676SMaxim Ag * 0 0 No Swap
166872c33676SMaxim Ag * 0 1 Swap
166972c33676SMaxim Ag * 1 0 Swap
167072c33676SMaxim Ag * 1 1 No Swap
167172c33676SMaxim Ag *
167272c33676SMaxim Ag * This is XOR. pbit tracks the previous bit of k.
167372c33676SMaxim Ag */
167472c33676SMaxim Ag
167572c33676SMaxim Ag for (i = cardinality_bits - 1; i >= 0; i--) {
167672c33676SMaxim Ag kbit = BN_is_bit_set(k, i) ^ pbit;
167772c33676SMaxim Ag EC_POINT_CSWAP(kbit, r, s, group_top, Z_is_one);
167872c33676SMaxim Ag if (!EC_POINT_add(group, s, r, s, ctx))
167972c33676SMaxim Ag goto err;
168072c33676SMaxim Ag if (!EC_POINT_dbl(group, r, r, ctx))
168172c33676SMaxim Ag goto err;
168272c33676SMaxim Ag /*
168372c33676SMaxim Ag * pbit logic merges this cswap with that of the
168472c33676SMaxim Ag * next iteration
168572c33676SMaxim Ag */
168672c33676SMaxim Ag pbit ^= kbit;
168772c33676SMaxim Ag }
168872c33676SMaxim Ag /* one final cswap to move the right value into r */
168972c33676SMaxim Ag EC_POINT_CSWAP(pbit, r, s, group_top, Z_is_one);
169072c33676SMaxim Ag
169172c33676SMaxim Ag ret = 1;
169272c33676SMaxim Ag
169372c33676SMaxim Ag err:
169472c33676SMaxim Ag EC_POINT_free(s);
169572c33676SMaxim Ag if (ctx != NULL)
169672c33676SMaxim Ag BN_CTX_end(ctx);
169772c33676SMaxim Ag BN_CTX_free(new_ctx);
169872c33676SMaxim Ag
169972c33676SMaxim Ag return ret;
170072c33676SMaxim Ag }
170172c33676SMaxim Ag
170272c33676SMaxim Ag #undef EC_POINT_BN_set_flags
170372c33676SMaxim Ag #undef EC_POINT_CSWAP
170472c33676SMaxim Ag
170572c33676SMaxim Ag int
ec_GFp_simple_mul_generator_ct(const EC_GROUP * group,EC_POINT * r,const BIGNUM * scalar,BN_CTX * ctx)170672c33676SMaxim Ag ec_GFp_simple_mul_generator_ct(const EC_GROUP *group, EC_POINT *r,
170772c33676SMaxim Ag const BIGNUM *scalar, BN_CTX *ctx)
170872c33676SMaxim Ag {
170972c33676SMaxim Ag return ec_GFp_simple_mul_ct(group, r, scalar, NULL, ctx);
171072c33676SMaxim Ag }
171172c33676SMaxim Ag
171272c33676SMaxim Ag int
ec_GFp_simple_mul_single_ct(const EC_GROUP * group,EC_POINT * r,const BIGNUM * scalar,const EC_POINT * point,BN_CTX * ctx)171372c33676SMaxim Ag ec_GFp_simple_mul_single_ct(const EC_GROUP *group, EC_POINT *r,
171472c33676SMaxim Ag const BIGNUM *scalar, const EC_POINT *point, BN_CTX *ctx)
171572c33676SMaxim Ag {
171672c33676SMaxim Ag return ec_GFp_simple_mul_ct(group, r, scalar, point, ctx);
171772c33676SMaxim Ag }
171872c33676SMaxim Ag
171972c33676SMaxim Ag int
ec_GFp_simple_mul_double_nonct(const EC_GROUP * group,EC_POINT * r,const BIGNUM * g_scalar,const BIGNUM * p_scalar,const EC_POINT * point,BN_CTX * ctx)172072c33676SMaxim Ag ec_GFp_simple_mul_double_nonct(const EC_GROUP *group, EC_POINT *r,
172172c33676SMaxim Ag const BIGNUM *g_scalar, const BIGNUM *p_scalar, const EC_POINT *point,
172272c33676SMaxim Ag BN_CTX *ctx)
172372c33676SMaxim Ag {
172472c33676SMaxim Ag return ec_wNAF_mul(group, r, g_scalar, 1, &point, &p_scalar, ctx);
172572c33676SMaxim Ag }
1726