1/* crypto/ec/ecp_smpl.c */
2/* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
3 * for the OpenSSL project.
4 * Includes code written by Bodo Moeller for the OpenSSL project.
5*/
6/* ====================================================================
7 * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * 1. Redistributions of source code must retain the above copyright
14 *    notice, this list of conditions and the following disclaimer.
15 *
16 * 2. Redistributions in binary form must reproduce the above copyright
17 *    notice, this list of conditions and the following disclaimer in
18 *    the documentation and/or other materials provided with the
19 *    distribution.
20 *
21 * 3. All advertising materials mentioning features or use of this
22 *    software must display the following acknowledgment:
23 *    "This product includes software developed by the OpenSSL Project
24 *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
25 *
26 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
27 *    endorse or promote products derived from this software without
28 *    prior written permission. For written permission, please contact
29 *    openssl-core@openssl.org.
30 *
31 * 5. Products derived from this software may not be called "OpenSSL"
32 *    nor may "OpenSSL" appear in their names without prior written
33 *    permission of the OpenSSL Project.
34 *
35 * 6. Redistributions of any form whatsoever must retain the following
36 *    acknowledgment:
37 *    "This product includes software developed by the OpenSSL Project
38 *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
39 *
40 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
41 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
43 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
44 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
45 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
46 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
47 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
49 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
50 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
51 * OF THE POSSIBILITY OF SUCH DAMAGE.
52 * ====================================================================
53 *
54 * This product includes cryptographic software written by Eric Young
55 * (eay@cryptsoft.com).  This product includes software written by Tim
56 * Hudson (tjh@cryptsoft.com).
57 *
58 */
59/* ====================================================================
60 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
61 * Portions of this software developed by SUN MICROSYSTEMS, INC.,
62 * and contributed to the OpenSSL project.
63 */
64
65#include <openssl/err.h>
66#include <openssl/symhacks.h>
67
68#include "ec_lcl.h"
69
70const EC_METHOD *EC_GFp_simple_method(void)
71	{
72	static const EC_METHOD ret = {
73		NID_X9_62_prime_field,
74		ec_GFp_simple_group_init,
75		ec_GFp_simple_group_finish,
76		ec_GFp_simple_group_clear_finish,
77		ec_GFp_simple_group_copy,
78		ec_GFp_simple_group_set_curve,
79		ec_GFp_simple_group_get_curve,
80		ec_GFp_simple_group_get_degree,
81		ec_GFp_simple_group_check_discriminant,
82		ec_GFp_simple_point_init,
83		ec_GFp_simple_point_finish,
84		ec_GFp_simple_point_clear_finish,
85		ec_GFp_simple_point_copy,
86		ec_GFp_simple_point_set_to_infinity,
87		ec_GFp_simple_set_Jprojective_coordinates_GFp,
88		ec_GFp_simple_get_Jprojective_coordinates_GFp,
89		ec_GFp_simple_point_set_affine_coordinates,
90		ec_GFp_simple_point_get_affine_coordinates,
91		ec_GFp_simple_set_compressed_coordinates,
92		ec_GFp_simple_point2oct,
93		ec_GFp_simple_oct2point,
94		ec_GFp_simple_add,
95		ec_GFp_simple_dbl,
96		ec_GFp_simple_invert,
97		ec_GFp_simple_is_at_infinity,
98		ec_GFp_simple_is_on_curve,
99		ec_GFp_simple_cmp,
100		ec_GFp_simple_make_affine,
101		ec_GFp_simple_points_make_affine,
102		0 /* mul */,
103		0 /* precompute_mult */,
104		0 /* have_precompute_mult */,
105		ec_GFp_simple_field_mul,
106		ec_GFp_simple_field_sqr,
107		0 /* field_div */,
108		0 /* field_encode */,
109		0 /* field_decode */,
110		0 /* field_set_to_one */ };
111
112	return &ret;
113	}
114
115
116/* Most method functions in this file are designed to work with
117 * non-trivial representations of field elements if necessary
118 * (see ecp_mont.c): while standard modular addition and subtraction
119 * are used, the field_mul and field_sqr methods will be used for
120 * multiplication, and field_encode and field_decode (if defined)
121 * will be used for converting between representations.
122
123 * Functions ec_GFp_simple_points_make_affine() and
124 * ec_GFp_simple_point_get_affine_coordinates() specifically assume
125 * that if a non-trivial representation is used, it is a Montgomery
126 * representation (i.e. 'encoding' means multiplying by some factor R).
127 */
128
129
130int ec_GFp_simple_group_init(EC_GROUP *group)
131	{
132	BN_init(&group->field);
133	BN_init(&group->a);
134	BN_init(&group->b);
135	group->a_is_minus3 = 0;
136	return 1;
137	}
138
139
140void ec_GFp_simple_group_finish(EC_GROUP *group)
141	{
142	BN_free(&group->field);
143	BN_free(&group->a);
144	BN_free(&group->b);
145	}
146
147
148void ec_GFp_simple_group_clear_finish(EC_GROUP *group)
149	{
150	BN_clear_free(&group->field);
151	BN_clear_free(&group->a);
152	BN_clear_free(&group->b);
153	}
154
155
156int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
157	{
158	if (!BN_copy(&dest->field, &src->field)) return 0;
159	if (!BN_copy(&dest->a, &src->a)) return 0;
160	if (!BN_copy(&dest->b, &src->b)) return 0;
161
162	dest->a_is_minus3 = src->a_is_minus3;
163
164	return 1;
165	}
166
167
168int ec_GFp_simple_group_set_curve(EC_GROUP *group,
169	const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
170	{
171	int ret = 0;
172	BN_CTX *new_ctx = NULL;
173	BIGNUM *tmp_a;
174
175	/* p must be a prime > 3 */
176	if (BN_num_bits(p) <= 2 || !BN_is_odd(p))
177		{
178		ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD);
179		return 0;
180		}
181
182	if (ctx == NULL)
183		{
184		ctx = new_ctx = BN_CTX_new();
185		if (ctx == NULL)
186			return 0;
187		}
188
189	BN_CTX_start(ctx);
190	tmp_a = BN_CTX_get(ctx);
191	if (tmp_a == NULL) goto err;
192
193	/* group->field */
194	if (!BN_copy(&group->field, p)) goto err;
195	BN_set_negative(&group->field, 0);
196
197	/* group->a */
198	if (!BN_nnmod(tmp_a, a, p, ctx)) goto err;
199	if (group->meth->field_encode)
200		{ if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) goto err; }
201	else
202		if (!BN_copy(&group->a, tmp_a)) goto err;
203
204	/* group->b */
205	if (!BN_nnmod(&group->b, b, p, ctx)) goto err;
206	if (group->meth->field_encode)
207		if (!group->meth->field_encode(group, &group->b, &group->b, ctx)) goto err;
208
209	/* group->a_is_minus3 */
210	if (!BN_add_word(tmp_a, 3)) goto err;
211	group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
212
213	ret = 1;
214
215 err:
216	BN_CTX_end(ctx);
217	if (new_ctx != NULL)
218		BN_CTX_free(new_ctx);
219	return ret;
220	}
221
222
223int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
224	{
225	int ret = 0;
226	BN_CTX *new_ctx = NULL;
227
228	if (p != NULL)
229		{
230		if (!BN_copy(p, &group->field)) return 0;
231		}
232
233	if (a != NULL || b != NULL)
234		{
235		if (group->meth->field_decode)
236			{
237			if (ctx == NULL)
238				{
239				ctx = new_ctx = BN_CTX_new();
240				if (ctx == NULL)
241					return 0;
242				}
243			if (a != NULL)
244				{
245				if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err;
246				}
247			if (b != NULL)
248				{
249				if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err;
250				}
251			}
252		else
253			{
254			if (a != NULL)
255				{
256				if (!BN_copy(a, &group->a)) goto err;
257				}
258			if (b != NULL)
259				{
260				if (!BN_copy(b, &group->b)) goto err;
261				}
262			}
263		}
264
265	ret = 1;
266
267 err:
268	if (new_ctx)
269		BN_CTX_free(new_ctx);
270	return ret;
271	}
272
273
274int ec_GFp_simple_group_get_degree(const EC_GROUP *group)
275	{
276	return BN_num_bits(&group->field);
277	}
278
279
280int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
281	{
282	int ret = 0;
283	BIGNUM *a,*b,*order,*tmp_1,*tmp_2;
284	const BIGNUM *p = &group->field;
285	BN_CTX *new_ctx = NULL;
286
287	if (ctx == NULL)
288		{
289		ctx = new_ctx = BN_CTX_new();
290		if (ctx == NULL)
291			{
292			ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, ERR_R_MALLOC_FAILURE);
293			goto err;
294			}
295		}
296	BN_CTX_start(ctx);
297	a = BN_CTX_get(ctx);
298	b = BN_CTX_get(ctx);
299	tmp_1 = BN_CTX_get(ctx);
300	tmp_2 = BN_CTX_get(ctx);
301	order = BN_CTX_get(ctx);
302	if (order == NULL) goto err;
303
304	if (group->meth->field_decode)
305		{
306		if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err;
307		if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err;
308		}
309	else
310		{
311		if (!BN_copy(a, &group->a)) goto err;
312		if (!BN_copy(b, &group->b)) goto err;
313		}
314
315	/* check the discriminant:
316	 * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p)
317         * 0 =< a, b < p */
318	if (BN_is_zero(a))
319		{
320		if (BN_is_zero(b)) goto err;
321		}
322	else if (!BN_is_zero(b))
323		{
324		if (!BN_mod_sqr(tmp_1, a, p, ctx)) goto err;
325		if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx)) goto err;
326		if (!BN_lshift(tmp_1, tmp_2, 2)) goto err;
327		/* tmp_1 = 4*a^3 */
328
329		if (!BN_mod_sqr(tmp_2, b, p, ctx)) goto err;
330		if (!BN_mul_word(tmp_2, 27)) goto err;
331		/* tmp_2 = 27*b^2 */
332
333		if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx)) goto err;
334		if (BN_is_zero(a)) goto err;
335		}
336	ret = 1;
337
338err:
339	if (ctx != NULL)
340		BN_CTX_end(ctx);
341	if (new_ctx != NULL)
342		BN_CTX_free(new_ctx);
343	return ret;
344	}
345
346
347int ec_GFp_simple_point_init(EC_POINT *point)
348	{
349	BN_init(&point->X);
350	BN_init(&point->Y);
351	BN_init(&point->Z);
352	point->Z_is_one = 0;
353
354	return 1;
355	}
356
357
358void ec_GFp_simple_point_finish(EC_POINT *point)
359	{
360	BN_free(&point->X);
361	BN_free(&point->Y);
362	BN_free(&point->Z);
363	}
364
365
366void ec_GFp_simple_point_clear_finish(EC_POINT *point)
367	{
368	BN_clear_free(&point->X);
369	BN_clear_free(&point->Y);
370	BN_clear_free(&point->Z);
371	point->Z_is_one = 0;
372	}
373
374
375int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
376	{
377	if (!BN_copy(&dest->X, &src->X)) return 0;
378	if (!BN_copy(&dest->Y, &src->Y)) return 0;
379	if (!BN_copy(&dest->Z, &src->Z)) return 0;
380	dest->Z_is_one = src->Z_is_one;
381
382	return 1;
383	}
384
385
386int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
387	{
388	point->Z_is_one = 0;
389	BN_zero(&point->Z);
390	return 1;
391	}
392
393
394int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
395	const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx)
396	{
397	BN_CTX *new_ctx = NULL;
398	int ret = 0;
399
400	if (ctx == NULL)
401		{
402		ctx = new_ctx = BN_CTX_new();
403		if (ctx == NULL)
404			return 0;
405		}
406
407	if (x != NULL)
408		{
409		if (!BN_nnmod(&point->X, x, &group->field, ctx)) goto err;
410		if (group->meth->field_encode)
411			{
412			if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) goto err;
413			}
414		}
415
416	if (y != NULL)
417		{
418		if (!BN_nnmod(&point->Y, y, &group->field, ctx)) goto err;
419		if (group->meth->field_encode)
420			{
421			if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) goto err;
422			}
423		}
424
425	if (z != NULL)
426		{
427		int Z_is_one;
428
429		if (!BN_nnmod(&point->Z, z, &group->field, ctx)) goto err;
430		Z_is_one = BN_is_one(&point->Z);
431		if (group->meth->field_encode)
432			{
433			if (Z_is_one && (group->meth->field_set_to_one != 0))
434				{
435				if (!group->meth->field_set_to_one(group, &point->Z, ctx)) goto err;
436				}
437			else
438				{
439				if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err;
440				}
441			}
442		point->Z_is_one = Z_is_one;
443		}
444
445	ret = 1;
446
447 err:
448	if (new_ctx != NULL)
449		BN_CTX_free(new_ctx);
450	return ret;
451	}
452
453
454int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point,
455	BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx)
456	{
457	BN_CTX *new_ctx = NULL;
458	int ret = 0;
459
460	if (group->meth->field_decode != 0)
461		{
462		if (ctx == NULL)
463			{
464			ctx = new_ctx = BN_CTX_new();
465			if (ctx == NULL)
466				return 0;
467			}
468
469		if (x != NULL)
470			{
471			if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err;
472			}
473		if (y != NULL)
474			{
475			if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err;
476			}
477		if (z != NULL)
478			{
479			if (!group->meth->field_decode(group, z, &point->Z, ctx)) goto err;
480			}
481		}
482	else
483		{
484		if (x != NULL)
485			{
486			if (!BN_copy(x, &point->X)) goto err;
487			}
488		if (y != NULL)
489			{
490			if (!BN_copy(y, &point->Y)) goto err;
491			}
492		if (z != NULL)
493			{
494			if (!BN_copy(z, &point->Z)) goto err;
495			}
496		}
497
498	ret = 1;
499
500 err:
501	if (new_ctx != NULL)
502		BN_CTX_free(new_ctx);
503	return ret;
504	}
505
506
507int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point,
508	const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
509	{
510	if (x == NULL || y == NULL)
511		{
512		/* unlike for projective coordinates, we do not tolerate this */
513		ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PASSED_NULL_PARAMETER);
514		return 0;
515		}
516
517	return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, BN_value_one(), ctx);
518	}
519
520
521int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point,
522	BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
523	{
524	BN_CTX *new_ctx = NULL;
525	BIGNUM *Z, *Z_1, *Z_2, *Z_3;
526	const BIGNUM *Z_;
527	int ret = 0;
528
529	if (EC_POINT_is_at_infinity(group, point))
530		{
531		ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POINT_AT_INFINITY);
532		return 0;
533		}
534
535	if (ctx == NULL)
536		{
537		ctx = new_ctx = BN_CTX_new();
538		if (ctx == NULL)
539			return 0;
540		}
541
542	BN_CTX_start(ctx);
543	Z = BN_CTX_get(ctx);
544	Z_1 = BN_CTX_get(ctx);
545	Z_2 = BN_CTX_get(ctx);
546	Z_3 = BN_CTX_get(ctx);
547	if (Z_3 == NULL) goto err;
548
549	/* transform  (X, Y, Z)  into  (x, y) := (X/Z^2, Y/Z^3) */
550
551	if (group->meth->field_decode)
552		{
553		if (!group->meth->field_decode(group, Z, &point->Z, ctx)) goto err;
554		Z_ = Z;
555		}
556	else
557		{
558		Z_ = &point->Z;
559		}
560
561	if (BN_is_one(Z_))
562		{
563		if (group->meth->field_decode)
564			{
565			if (x != NULL)
566				{
567				if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err;
568				}
569			if (y != NULL)
570				{
571				if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err;
572				}
573			}
574		else
575			{
576			if (x != NULL)
577				{
578				if (!BN_copy(x, &point->X)) goto err;
579				}
580			if (y != NULL)
581				{
582				if (!BN_copy(y, &point->Y)) goto err;
583				}
584			}
585		}
586	else
587		{
588		if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx))
589			{
590			ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_BN_LIB);
591			goto err;
592			}
593
594		if (group->meth->field_encode == 0)
595			{
596			/* field_sqr works on standard representation */
597			if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) goto err;
598			}
599		else
600			{
601			if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err;
602			}
603
604		if (x != NULL)
605			{
606			/* in the Montgomery case, field_mul will cancel out Montgomery factor in X: */
607			if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx)) goto err;
608			}
609
610		if (y != NULL)
611			{
612			if (group->meth->field_encode == 0)
613				{
614				/* field_mul works on standard representation */
615				if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) goto err;
616				}
617			else
618				{
619				if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto err;
620				}
621
622			/* in the Montgomery case, field_mul will cancel out Montgomery factor in Y: */
623			if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) goto err;
624			}
625		}
626
627	ret = 1;
628
629 err:
630	BN_CTX_end(ctx);
631	if (new_ctx != NULL)
632		BN_CTX_free(new_ctx);
633	return ret;
634	}
635
636
637int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, EC_POINT *point,
638	const BIGNUM *x_, int y_bit, BN_CTX *ctx)
639	{
640	BN_CTX *new_ctx = NULL;
641	BIGNUM *tmp1, *tmp2, *x, *y;
642	int ret = 0;
643
644	/* clear error queue*/
645	ERR_clear_error();
646
647	if (ctx == NULL)
648		{
649		ctx = new_ctx = BN_CTX_new();
650		if (ctx == NULL)
651			return 0;
652		}
653
654	y_bit = (y_bit != 0);
655
656	BN_CTX_start(ctx);
657	tmp1 = BN_CTX_get(ctx);
658	tmp2 = BN_CTX_get(ctx);
659	x = BN_CTX_get(ctx);
660	y = BN_CTX_get(ctx);
661	if (y == NULL) goto err;
662
663	/* Recover y.  We have a Weierstrass equation
664	 *     y^2 = x^3 + a*x + b,
665	 * so  y  is one of the square roots of  x^3 + a*x + b.
666	 */
667
668	/* tmp1 := x^3 */
669	if (!BN_nnmod(x, x_, &group->field,ctx)) goto err;
670	if (group->meth->field_decode == 0)
671		{
672		/* field_{sqr,mul} work on standard representation */
673		if (!group->meth->field_sqr(group, tmp2, x_, ctx)) goto err;
674		if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) goto err;
675		}
676	else
677		{
678		if (!BN_mod_sqr(tmp2, x_, &group->field, ctx)) goto err;
679		if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) goto err;
680		}
681
682	/* tmp1 := tmp1 + a*x */
683	if (group->a_is_minus3)
684		{
685		if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) goto err;
686		if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) goto err;
687		if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
688		}
689	else
690		{
691		if (group->meth->field_decode)
692			{
693			if (!group->meth->field_decode(group, tmp2, &group->a, ctx)) goto err;
694			if (!BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) goto err;
695			}
696		else
697			{
698			/* field_mul works on standard representation */
699			if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) goto err;
700			}
701
702		if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
703		}
704
705	/* tmp1 := tmp1 + b */
706	if (group->meth->field_decode)
707		{
708		if (!group->meth->field_decode(group, tmp2, &group->b, ctx)) goto err;
709		if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
710		}
711	else
712		{
713		if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) goto err;
714		}
715
716	if (!BN_mod_sqrt(y, tmp1, &group->field, ctx))
717		{
718		unsigned long err = ERR_peek_last_error();
719
720		if (ERR_GET_LIB(err) == ERR_LIB_BN && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE)
721			{
722			ERR_clear_error();
723			ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
724			}
725		else
726			ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_BN_LIB);
727		goto err;
728		}
729
730	if (y_bit != BN_is_odd(y))
731		{
732		if (BN_is_zero(y))
733			{
734			int kron;
735
736			kron = BN_kronecker(x, &group->field, ctx);
737			if (kron == -2) goto err;
738
739			if (kron == 1)
740				ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSION_BIT);
741			else
742				/* BN_mod_sqrt() should have cought this error (not a square) */
743				ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
744			goto err;
745			}
746		if (!BN_usub(y, &group->field, y)) goto err;
747		}
748	if (y_bit != BN_is_odd(y))
749		{
750		ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_INTERNAL_ERROR);
751		goto err;
752		}
753
754	if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
755
756	ret = 1;
757
758 err:
759	BN_CTX_end(ctx);
760	if (new_ctx != NULL)
761		BN_CTX_free(new_ctx);
762	return ret;
763	}
764
765
766size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, point_conversion_form_t form,
767	unsigned char *buf, size_t len, BN_CTX *ctx)
768	{
769	size_t ret;
770	BN_CTX *new_ctx = NULL;
771	int used_ctx = 0;
772	BIGNUM *x, *y;
773	size_t field_len, i, skip;
774
775	if ((form != POINT_CONVERSION_COMPRESSED)
776		&& (form != POINT_CONVERSION_UNCOMPRESSED)
777		&& (form != POINT_CONVERSION_HYBRID))
778		{
779		ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
780		goto err;
781		}
782
783	if (EC_POINT_is_at_infinity(group, point))
784		{
785		/* encodes to a single 0 octet */
786		if (buf != NULL)
787			{
788			if (len < 1)
789				{
790				ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
791				return 0;
792				}
793			buf[0] = 0;
794			}
795		return 1;
796		}
797
798
799	/* ret := required output buffer length */
800	field_len = BN_num_bytes(&group->field);
801	ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
802
803	/* if 'buf' is NULL, just return required length */
804	if (buf != NULL)
805		{
806		if (len < ret)
807			{
808			ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
809			goto err;
810			}
811
812		if (ctx == NULL)
813			{
814			ctx = new_ctx = BN_CTX_new();
815			if (ctx == NULL)
816				return 0;
817			}
818
819		BN_CTX_start(ctx);
820		used_ctx = 1;
821		x = BN_CTX_get(ctx);
822		y = BN_CTX_get(ctx);
823		if (y == NULL) goto err;
824
825		if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
826
827		if ((form == POINT_CONVERSION_COMPRESSED || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y))
828			buf[0] = form + 1;
829		else
830			buf[0] = form;
831
832		i = 1;
833
834		skip = field_len - BN_num_bytes(x);
835		if (skip > field_len)
836			{
837			ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
838			goto err;
839			}
840		while (skip > 0)
841			{
842			buf[i++] = 0;
843			skip--;
844			}
845		skip = BN_bn2bin(x, buf + i);
846		i += skip;
847		if (i != 1 + field_len)
848			{
849			ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
850			goto err;
851			}
852
853		if (form == POINT_CONVERSION_UNCOMPRESSED || form == POINT_CONVERSION_HYBRID)
854			{
855			skip = field_len - BN_num_bytes(y);
856			if (skip > field_len)
857				{
858				ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
859				goto err;
860				}
861			while (skip > 0)
862				{
863				buf[i++] = 0;
864				skip--;
865				}
866			skip = BN_bn2bin(y, buf + i);
867			i += skip;
868			}
869
870		if (i != ret)
871			{
872			ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
873			goto err;
874			}
875		}
876
877	if (used_ctx)
878		BN_CTX_end(ctx);
879	if (new_ctx != NULL)
880		BN_CTX_free(new_ctx);
881	return ret;
882
883 err:
884	if (used_ctx)
885		BN_CTX_end(ctx);
886	if (new_ctx != NULL)
887		BN_CTX_free(new_ctx);
888	return 0;
889	}
890
891
892int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
893	const unsigned char *buf, size_t len, BN_CTX *ctx)
894	{
895	point_conversion_form_t form;
896	int y_bit;
897	BN_CTX *new_ctx = NULL;
898	BIGNUM *x, *y;
899	size_t field_len, enc_len;
900	int ret = 0;
901
902	if (len == 0)
903		{
904		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
905		return 0;
906		}
907	form = buf[0];
908	y_bit = form & 1;
909	form = form & ~1U;
910	if ((form != 0)	&& (form != POINT_CONVERSION_COMPRESSED)
911		&& (form != POINT_CONVERSION_UNCOMPRESSED)
912		&& (form != POINT_CONVERSION_HYBRID))
913		{
914		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
915		return 0;
916		}
917	if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit)
918		{
919		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
920		return 0;
921		}
922
923	if (form == 0)
924		{
925		if (len != 1)
926			{
927			ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
928			return 0;
929			}
930
931		return EC_POINT_set_to_infinity(group, point);
932		}
933
934	field_len = BN_num_bytes(&group->field);
935	enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
936
937	if (len != enc_len)
938		{
939		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
940		return 0;
941		}
942
943	if (ctx == NULL)
944		{
945		ctx = new_ctx = BN_CTX_new();
946		if (ctx == NULL)
947			return 0;
948		}
949
950	BN_CTX_start(ctx);
951	x = BN_CTX_get(ctx);
952	y = BN_CTX_get(ctx);
953	if (y == NULL) goto err;
954
955	if (!BN_bin2bn(buf + 1, field_len, x)) goto err;
956	if (BN_ucmp(x, &group->field) >= 0)
957		{
958		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
959		goto err;
960		}
961
962	if (form == POINT_CONVERSION_COMPRESSED)
963		{
964		if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) goto err;
965		}
966	else
967		{
968		if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) goto err;
969		if (BN_ucmp(y, &group->field) >= 0)
970			{
971			ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
972			goto err;
973			}
974		if (form == POINT_CONVERSION_HYBRID)
975			{
976			if (y_bit != BN_is_odd(y))
977				{
978				ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
979				goto err;
980				}
981			}
982
983		if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
984		}
985
986	if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */
987		{
988		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
989		goto err;
990		}
991
992	ret = 1;
993
994 err:
995	BN_CTX_end(ctx);
996	if (new_ctx != NULL)
997		BN_CTX_free(new_ctx);
998	return ret;
999	}
1000
1001
1002int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
1003	{
1004	int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1005	int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1006	const BIGNUM *p;
1007	BN_CTX *new_ctx = NULL;
1008	BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
1009	int ret = 0;
1010
1011	if (a == b)
1012		return EC_POINT_dbl(group, r, a, ctx);
1013	if (EC_POINT_is_at_infinity(group, a))
1014		return EC_POINT_copy(r, b);
1015	if (EC_POINT_is_at_infinity(group, b))
1016		return EC_POINT_copy(r, a);
1017
1018	field_mul = group->meth->field_mul;
1019	field_sqr = group->meth->field_sqr;
1020	p = &group->field;
1021
1022	if (ctx == NULL)
1023		{
1024		ctx = new_ctx = BN_CTX_new();
1025		if (ctx == NULL)
1026			return 0;
1027		}
1028
1029	BN_CTX_start(ctx);
1030	n0 = BN_CTX_get(ctx);
1031	n1 = BN_CTX_get(ctx);
1032	n2 = BN_CTX_get(ctx);
1033	n3 = BN_CTX_get(ctx);
1034	n4 = BN_CTX_get(ctx);
1035	n5 = BN_CTX_get(ctx);
1036	n6 = BN_CTX_get(ctx);
1037	if (n6 == NULL) goto end;
1038
1039	/* Note that in this function we must not read components of 'a' or 'b'
1040	 * once we have written the corresponding components of 'r'.
1041	 * ('r' might be one of 'a' or 'b'.)
1042	 */
1043
1044	/* n1, n2 */
1045	if (b->Z_is_one)
1046		{
1047		if (!BN_copy(n1, &a->X)) goto end;
1048		if (!BN_copy(n2, &a->Y)) goto end;
1049		/* n1 = X_a */
1050		/* n2 = Y_a */
1051		}
1052	else
1053		{
1054		if (!field_sqr(group, n0, &b->Z, ctx)) goto end;
1055		if (!field_mul(group, n1, &a->X, n0, ctx)) goto end;
1056		/* n1 = X_a * Z_b^2 */
1057
1058		if (!field_mul(group, n0, n0, &b->Z, ctx)) goto end;
1059		if (!field_mul(group, n2, &a->Y, n0, ctx)) goto end;
1060		/* n2 = Y_a * Z_b^3 */
1061		}
1062
1063	/* n3, n4 */
1064	if (a->Z_is_one)
1065		{
1066		if (!BN_copy(n3, &b->X)) goto end;
1067		if (!BN_copy(n4, &b->Y)) goto end;
1068		/* n3 = X_b */
1069		/* n4 = Y_b */
1070		}
1071	else
1072		{
1073		if (!field_sqr(group, n0, &a->Z, ctx)) goto end;
1074		if (!field_mul(group, n3, &b->X, n0, ctx)) goto end;
1075		/* n3 = X_b * Z_a^2 */
1076
1077		if (!field_mul(group, n0, n0, &a->Z, ctx)) goto end;
1078		if (!field_mul(group, n4, &b->Y, n0, ctx)) goto end;
1079		/* n4 = Y_b * Z_a^3 */
1080		}
1081
1082	/* n5, n6 */
1083	if (!BN_mod_sub_quick(n5, n1, n3, p)) goto end;
1084	if (!BN_mod_sub_quick(n6, n2, n4, p)) goto end;
1085	/* n5 = n1 - n3 */
1086	/* n6 = n2 - n4 */
1087
1088	if (BN_is_zero(n5))
1089		{
1090		if (BN_is_zero(n6))
1091			{
1092			/* a is the same point as b */
1093			BN_CTX_end(ctx);
1094			ret = EC_POINT_dbl(group, r, a, ctx);
1095			ctx = NULL;
1096			goto end;
1097			}
1098		else
1099			{
1100			/* a is the inverse of b */
1101			BN_zero(&r->Z);
1102			r->Z_is_one = 0;
1103			ret = 1;
1104			goto end;
1105			}
1106		}
1107
1108	/* 'n7', 'n8' */
1109	if (!BN_mod_add_quick(n1, n1, n3, p)) goto end;
1110	if (!BN_mod_add_quick(n2, n2, n4, p)) goto end;
1111	/* 'n7' = n1 + n3 */
1112	/* 'n8' = n2 + n4 */
1113
1114	/* Z_r */
1115	if (a->Z_is_one && b->Z_is_one)
1116		{
1117		if (!BN_copy(&r->Z, n5)) goto end;
1118		}
1119	else
1120		{
1121		if (a->Z_is_one)
1122			{ if (!BN_copy(n0, &b->Z)) goto end; }
1123		else if (b->Z_is_one)
1124			{ if (!BN_copy(n0, &a->Z)) goto end; }
1125		else
1126			{ if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) goto end; }
1127		if (!field_mul(group, &r->Z, n0, n5, ctx)) goto end;
1128		}
1129	r->Z_is_one = 0;
1130	/* Z_r = Z_a * Z_b * n5 */
1131
1132	/* X_r */
1133	if (!field_sqr(group, n0, n6, ctx)) goto end;
1134	if (!field_sqr(group, n4, n5, ctx)) goto end;
1135	if (!field_mul(group, n3, n1, n4, ctx)) goto end;
1136	if (!BN_mod_sub_quick(&r->X, n0, n3, p)) goto end;
1137	/* X_r = n6^2 - n5^2 * 'n7' */
1138
1139	/* 'n9' */
1140	if (!BN_mod_lshift1_quick(n0, &r->X, p)) goto end;
1141	if (!BN_mod_sub_quick(n0, n3, n0, p)) goto end;
1142	/* n9 = n5^2 * 'n7' - 2 * X_r */
1143
1144	/* Y_r */
1145	if (!field_mul(group, n0, n0, n6, ctx)) goto end;
1146	if (!field_mul(group, n5, n4, n5, ctx)) goto end; /* now n5 is n5^3 */
1147	if (!field_mul(group, n1, n2, n5, ctx)) goto end;
1148	if (!BN_mod_sub_quick(n0, n0, n1, p)) goto end;
1149	if (BN_is_odd(n0))
1150		if (!BN_add(n0, n0, p)) goto end;
1151	/* now  0 <= n0 < 2*p,  and n0 is even */
1152	if (!BN_rshift1(&r->Y, n0)) goto end;
1153	/* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
1154
1155	ret = 1;
1156
1157 end:
1158	if (ctx) /* otherwise we already called BN_CTX_end */
1159		BN_CTX_end(ctx);
1160	if (new_ctx != NULL)
1161		BN_CTX_free(new_ctx);
1162	return ret;
1163	}
1164
1165
1166int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
1167	{
1168	int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1169	int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1170	const BIGNUM *p;
1171	BN_CTX *new_ctx = NULL;
1172	BIGNUM *n0, *n1, *n2, *n3;
1173	int ret = 0;
1174
1175	if (EC_POINT_is_at_infinity(group, a))
1176		{
1177		BN_zero(&r->Z);
1178		r->Z_is_one = 0;
1179		return 1;
1180		}
1181
1182	field_mul = group->meth->field_mul;
1183	field_sqr = group->meth->field_sqr;
1184	p = &group->field;
1185
1186	if (ctx == NULL)
1187		{
1188		ctx = new_ctx = BN_CTX_new();
1189		if (ctx == NULL)
1190			return 0;
1191		}
1192
1193	BN_CTX_start(ctx);
1194	n0 = BN_CTX_get(ctx);
1195	n1 = BN_CTX_get(ctx);
1196	n2 = BN_CTX_get(ctx);
1197	n3 = BN_CTX_get(ctx);
1198	if (n3 == NULL) goto err;
1199
1200	/* Note that in this function we must not read components of 'a'
1201	 * once we have written the corresponding components of 'r'.
1202	 * ('r' might the same as 'a'.)
1203	 */
1204
1205	/* n1 */
1206	if (a->Z_is_one)
1207		{
1208		if (!field_sqr(group, n0, &a->X, ctx)) goto err;
1209		if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
1210		if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
1211		if (!BN_mod_add_quick(n1, n0, &group->a, p)) goto err;
1212		/* n1 = 3 * X_a^2 + a_curve */
1213		}
1214	else if (group->a_is_minus3)
1215		{
1216		if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
1217		if (!BN_mod_add_quick(n0, &a->X, n1, p)) goto err;
1218		if (!BN_mod_sub_quick(n2, &a->X, n1, p)) goto err;
1219		if (!field_mul(group, n1, n0, n2, ctx)) goto err;
1220		if (!BN_mod_lshift1_quick(n0, n1, p)) goto err;
1221		if (!BN_mod_add_quick(n1, n0, n1, p)) goto err;
1222		/* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
1223		 *    = 3 * X_a^2 - 3 * Z_a^4 */
1224		}
1225	else
1226		{
1227		if (!field_sqr(group, n0, &a->X, ctx)) goto err;
1228		if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
1229		if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
1230		if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
1231		if (!field_sqr(group, n1, n1, ctx)) goto err;
1232		if (!field_mul(group, n1, n1, &group->a, ctx)) goto err;
1233		if (!BN_mod_add_quick(n1, n1, n0, p)) goto err;
1234		/* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
1235		}
1236
1237	/* Z_r */
1238	if (a->Z_is_one)
1239		{
1240		if (!BN_copy(n0, &a->Y)) goto err;
1241		}
1242	else
1243		{
1244		if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) goto err;
1245		}
1246	if (!BN_mod_lshift1_quick(&r->Z, n0, p)) goto err;
1247	r->Z_is_one = 0;
1248	/* Z_r = 2 * Y_a * Z_a */
1249
1250	/* n2 */
1251	if (!field_sqr(group, n3, &a->Y, ctx)) goto err;
1252	if (!field_mul(group, n2, &a->X, n3, ctx)) goto err;
1253	if (!BN_mod_lshift_quick(n2, n2, 2, p)) goto err;
1254	/* n2 = 4 * X_a * Y_a^2 */
1255
1256	/* X_r */
1257	if (!BN_mod_lshift1_quick(n0, n2, p)) goto err;
1258	if (!field_sqr(group, &r->X, n1, ctx)) goto err;
1259	if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) goto err;
1260	/* X_r = n1^2 - 2 * n2 */
1261
1262	/* n3 */
1263	if (!field_sqr(group, n0, n3, ctx)) goto err;
1264	if (!BN_mod_lshift_quick(n3, n0, 3, p)) goto err;
1265	/* n3 = 8 * Y_a^4 */
1266
1267	/* Y_r */
1268	if (!BN_mod_sub_quick(n0, n2, &r->X, p)) goto err;
1269	if (!field_mul(group, n0, n1, n0, ctx)) goto err;
1270	if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) goto err;
1271	/* Y_r = n1 * (n2 - X_r) - n3 */
1272
1273	ret = 1;
1274
1275 err:
1276	BN_CTX_end(ctx);
1277	if (new_ctx != NULL)
1278		BN_CTX_free(new_ctx);
1279	return ret;
1280	}
1281
1282
1283int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1284	{
1285	if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y))
1286		/* point is its own inverse */
1287		return 1;
1288
1289	return BN_usub(&point->Y, &group->field, &point->Y);
1290	}
1291
1292
1293int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
1294	{
1295	return BN_is_zero(&point->Z);
1296	}
1297
1298
1299int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
1300	{
1301	int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1302	int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1303	const BIGNUM *p;
1304	BN_CTX *new_ctx = NULL;
1305	BIGNUM *rh, *tmp, *Z4, *Z6;
1306	int ret = -1;
1307
1308	if (EC_POINT_is_at_infinity(group, point))
1309		return 1;
1310
1311	field_mul = group->meth->field_mul;
1312	field_sqr = group->meth->field_sqr;
1313	p = &group->field;
1314
1315	if (ctx == NULL)
1316		{
1317		ctx = new_ctx = BN_CTX_new();
1318		if (ctx == NULL)
1319			return -1;
1320		}
1321
1322	BN_CTX_start(ctx);
1323	rh = BN_CTX_get(ctx);
1324	tmp = BN_CTX_get(ctx);
1325	Z4 = BN_CTX_get(ctx);
1326	Z6 = BN_CTX_get(ctx);
1327	if (Z6 == NULL) goto err;
1328
1329	/* We have a curve defined by a Weierstrass equation
1330	 *      y^2 = x^3 + a*x + b.
1331	 * The point to consider is given in Jacobian projective coordinates
1332	 * where  (X, Y, Z)  represents  (x, y) = (X/Z^2, Y/Z^3).
1333	 * Substituting this and multiplying by  Z^6  transforms the above equation into
1334	 *      Y^2 = X^3 + a*X*Z^4 + b*Z^6.
1335	 * To test this, we add up the right-hand side in 'rh'.
1336	 */
1337
1338	/* rh := X^2 */
1339	if (!field_sqr(group, rh, &point->X, ctx)) goto err;
1340
1341	if (!point->Z_is_one)
1342		{
1343		if (!field_sqr(group, tmp, &point->Z, ctx)) goto err;
1344		if (!field_sqr(group, Z4, tmp, ctx)) goto err;
1345		if (!field_mul(group, Z6, Z4, tmp, ctx)) goto err;
1346
1347		/* rh := (rh + a*Z^4)*X */
1348		if (group->a_is_minus3)
1349			{
1350			if (!BN_mod_lshift1_quick(tmp, Z4, p)) goto err;
1351			if (!BN_mod_add_quick(tmp, tmp, Z4, p)) goto err;
1352			if (!BN_mod_sub_quick(rh, rh, tmp, p)) goto err;
1353			if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1354			}
1355		else
1356			{
1357			if (!field_mul(group, tmp, Z4, &group->a, ctx)) goto err;
1358			if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err;
1359			if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1360			}
1361
1362		/* rh := rh + b*Z^6 */
1363		if (!field_mul(group, tmp, &group->b, Z6, ctx)) goto err;
1364		if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err;
1365		}
1366	else
1367		{
1368		/* point->Z_is_one */
1369
1370		/* rh := (rh + a)*X */
1371		if (!BN_mod_add_quick(rh, rh, &group->a, p)) goto err;
1372		if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1373		/* rh := rh + b */
1374		if (!BN_mod_add_quick(rh, rh, &group->b, p)) goto err;
1375		}
1376
1377	/* 'lh' := Y^2 */
1378	if (!field_sqr(group, tmp, &point->Y, ctx)) goto err;
1379
1380	ret = (0 == BN_ucmp(tmp, rh));
1381
1382 err:
1383	BN_CTX_end(ctx);
1384	if (new_ctx != NULL)
1385		BN_CTX_free(new_ctx);
1386	return ret;
1387	}
1388
1389
1390int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
1391	{
1392	/* return values:
1393	 *  -1   error
1394	 *   0   equal (in affine coordinates)
1395	 *   1   not equal
1396	 */
1397
1398	int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1399	int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1400	BN_CTX *new_ctx = NULL;
1401	BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
1402	const BIGNUM *tmp1_, *tmp2_;
1403	int ret = -1;
1404
1405	if (EC_POINT_is_at_infinity(group, a))
1406		{
1407		return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
1408		}
1409
1410	if (a->Z_is_one && b->Z_is_one)
1411		{
1412		return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
1413		}
1414
1415	field_mul = group->meth->field_mul;
1416	field_sqr = group->meth->field_sqr;
1417
1418	if (ctx == NULL)
1419		{
1420		ctx = new_ctx = BN_CTX_new();
1421		if (ctx == NULL)
1422			return -1;
1423		}
1424
1425	BN_CTX_start(ctx);
1426	tmp1 = BN_CTX_get(ctx);
1427	tmp2 = BN_CTX_get(ctx);
1428	Za23 = BN_CTX_get(ctx);
1429	Zb23 = BN_CTX_get(ctx);
1430	if (Zb23 == NULL) goto end;
1431
1432	/* We have to decide whether
1433	 *     (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
1434	 * or equivalently, whether
1435	 *     (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
1436	 */
1437
1438	if (!b->Z_is_one)
1439		{
1440		if (!field_sqr(group, Zb23, &b->Z, ctx)) goto end;
1441		if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) goto end;
1442		tmp1_ = tmp1;
1443		}
1444	else
1445		tmp1_ = &a->X;
1446	if (!a->Z_is_one)
1447		{
1448		if (!field_sqr(group, Za23, &a->Z, ctx)) goto end;
1449		if (!field_mul(group, tmp2, &b->X, Za23, ctx)) goto end;
1450		tmp2_ = tmp2;
1451		}
1452	else
1453		tmp2_ = &b->X;
1454
1455	/* compare  X_a*Z_b^2  with  X_b*Z_a^2 */
1456	if (BN_cmp(tmp1_, tmp2_) != 0)
1457		{
1458		ret = 1; /* points differ */
1459		goto end;
1460		}
1461
1462
1463	if (!b->Z_is_one)
1464		{
1465		if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) goto end;
1466		if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) goto end;
1467		/* tmp1_ = tmp1 */
1468		}
1469	else
1470		tmp1_ = &a->Y;
1471	if (!a->Z_is_one)
1472		{
1473		if (!field_mul(group, Za23, Za23, &a->Z, ctx)) goto end;
1474		if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) goto end;
1475		/* tmp2_ = tmp2 */
1476		}
1477	else
1478		tmp2_ = &b->Y;
1479
1480	/* compare  Y_a*Z_b^3  with  Y_b*Z_a^3 */
1481	if (BN_cmp(tmp1_, tmp2_) != 0)
1482		{
1483		ret = 1; /* points differ */
1484		goto end;
1485		}
1486
1487	/* points are equal */
1488	ret = 0;
1489
1490 end:
1491	BN_CTX_end(ctx);
1492	if (new_ctx != NULL)
1493		BN_CTX_free(new_ctx);
1494	return ret;
1495	}
1496
1497
1498int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1499	{
1500	BN_CTX *new_ctx = NULL;
1501	BIGNUM *x, *y;
1502	int ret = 0;
1503
1504	if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
1505		return 1;
1506
1507	if (ctx == NULL)
1508		{
1509		ctx = new_ctx = BN_CTX_new();
1510		if (ctx == NULL)
1511			return 0;
1512		}
1513
1514	BN_CTX_start(ctx);
1515	x = BN_CTX_get(ctx);
1516	y = BN_CTX_get(ctx);
1517	if (y == NULL) goto err;
1518
1519	if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
1520	if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
1521	if (!point->Z_is_one)
1522		{
1523		ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
1524		goto err;
1525		}
1526
1527	ret = 1;
1528
1529 err:
1530	BN_CTX_end(ctx);
1531	if (new_ctx != NULL)
1532		BN_CTX_free(new_ctx);
1533	return ret;
1534	}
1535
1536
1537int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
1538	{
1539	BN_CTX *new_ctx = NULL;
1540	BIGNUM *tmp0, *tmp1;
1541	size_t pow2 = 0;
1542	BIGNUM **heap = NULL;
1543	size_t i;
1544	int ret = 0;
1545
1546	if (num == 0)
1547		return 1;
1548
1549	if (ctx == NULL)
1550		{
1551		ctx = new_ctx = BN_CTX_new();
1552		if (ctx == NULL)
1553			return 0;
1554		}
1555
1556	BN_CTX_start(ctx);
1557	tmp0 = BN_CTX_get(ctx);
1558	tmp1 = BN_CTX_get(ctx);
1559	if (tmp0  == NULL || tmp1 == NULL) goto err;
1560
1561	/* Before converting the individual points, compute inverses of all Z values.
1562	 * Modular inversion is rather slow, but luckily we can do with a single
1563	 * explicit inversion, plus about 3 multiplications per input value.
1564	 */
1565
1566	pow2 = 1;
1567	while (num > pow2)
1568		pow2 <<= 1;
1569	/* Now pow2 is the smallest power of 2 satifsying pow2 >= num.
1570	 * We need twice that. */
1571	pow2 <<= 1;
1572
1573	heap = OPENSSL_malloc(pow2 * sizeof heap[0]);
1574	if (heap == NULL) goto err;
1575
1576	/* The array is used as a binary tree, exactly as in heapsort:
1577	 *
1578	 *                               heap[1]
1579	 *                 heap[2]                     heap[3]
1580	 *          heap[4]       heap[5]       heap[6]       heap[7]
1581	 *   heap[8]heap[9] heap[10]heap[11] heap[12]heap[13] heap[14] heap[15]
1582	 *
1583	 * We put the Z's in the last line;
1584	 * then we set each other node to the product of its two child-nodes (where
1585	 * empty or 0 entries are treated as ones);
1586	 * then we invert heap[1];
1587	 * then we invert each other node by replacing it by the product of its
1588	 * parent (after inversion) and its sibling (before inversion).
1589	 */
1590	heap[0] = NULL;
1591	for (i = pow2/2 - 1; i > 0; i--)
1592		heap[i] = NULL;
1593	for (i = 0; i < num; i++)
1594		heap[pow2/2 + i] = &points[i]->Z;
1595	for (i = pow2/2 + num; i < pow2; i++)
1596		heap[i] = NULL;
1597
1598	/* set each node to the product of its children */
1599	for (i = pow2/2 - 1; i > 0; i--)
1600		{
1601		heap[i] = BN_new();
1602		if (heap[i] == NULL) goto err;
1603
1604		if (heap[2*i] != NULL)
1605			{
1606			if ((heap[2*i + 1] == NULL) || BN_is_zero(heap[2*i + 1]))
1607				{
1608				if (!BN_copy(heap[i], heap[2*i])) goto err;
1609				}
1610			else
1611				{
1612				if (BN_is_zero(heap[2*i]))
1613					{
1614					if (!BN_copy(heap[i], heap[2*i + 1])) goto err;
1615					}
1616				else
1617					{
1618					if (!group->meth->field_mul(group, heap[i],
1619						heap[2*i], heap[2*i + 1], ctx)) goto err;
1620					}
1621				}
1622			}
1623		}
1624
1625	/* invert heap[1] */
1626	if (!BN_is_zero(heap[1]))
1627		{
1628		if (!BN_mod_inverse(heap[1], heap[1], &group->field, ctx))
1629			{
1630			ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
1631			goto err;
1632			}
1633		}
1634	if (group->meth->field_encode != 0)
1635		{
1636		/* in the Montgomery case, we just turned  R*H  (representing H)
1637		 * into  1/(R*H),  but we need  R*(1/H)  (representing 1/H);
1638		 * i.e. we have need to multiply by the Montgomery factor twice */
1639		if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
1640		if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
1641		}
1642
1643	/* set other heap[i]'s to their inverses */
1644	for (i = 2; i < pow2/2 + num; i += 2)
1645		{
1646		/* i is even */
1647		if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1]))
1648			{
1649			if (!group->meth->field_mul(group, tmp0, heap[i/2], heap[i + 1], ctx)) goto err;
1650			if (!group->meth->field_mul(group, tmp1, heap[i/2], heap[i], ctx)) goto err;
1651			if (!BN_copy(heap[i], tmp0)) goto err;
1652			if (!BN_copy(heap[i + 1], tmp1)) goto err;
1653			}
1654		else
1655			{
1656			if (!BN_copy(heap[i], heap[i/2])) goto err;
1657			}
1658		}
1659
1660	/* we have replaced all non-zero Z's by their inverses, now fix up all the points */
1661	for (i = 0; i < num; i++)
1662		{
1663		EC_POINT *p = points[i];
1664
1665		if (!BN_is_zero(&p->Z))
1666			{
1667			/* turn  (X, Y, 1/Z)  into  (X/Z^2, Y/Z^3, 1) */
1668
1669			if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx)) goto err;
1670			if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx)) goto err;
1671
1672			if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx)) goto err;
1673			if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx)) goto err;
1674
1675			if (group->meth->field_set_to_one != 0)
1676				{
1677				if (!group->meth->field_set_to_one(group, &p->Z, ctx)) goto err;
1678				}
1679			else
1680				{
1681				if (!BN_one(&p->Z)) goto err;
1682				}
1683			p->Z_is_one = 1;
1684			}
1685		}
1686
1687	ret = 1;
1688
1689 err:
1690	BN_CTX_end(ctx);
1691	if (new_ctx != NULL)
1692		BN_CTX_free(new_ctx);
1693	if (heap != NULL)
1694		{
1695		/* heap[pow2/2] .. heap[pow2-1] have not been allocated locally! */
1696		for (i = pow2/2 - 1; i > 0; i--)
1697			{
1698			if (heap[i] != NULL)
1699				BN_clear_free(heap[i]);
1700			}
1701		OPENSSL_free(heap);
1702		}
1703	return ret;
1704	}
1705
1706
1707int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
1708	{
1709	return BN_mod_mul(r, a, b, &group->field, ctx);
1710	}
1711
1712
1713int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
1714	{
1715	return BN_mod_sqr(r, a, &group->field, ctx);
1716	}
1717