ec2_smpl.c@ 83531

Last change on this file since 83531 was 83531, checked in by vboxsync, 5 years ago
setting svn:sync-process=export for openssl-1.1.1f, all files except tests
File size: 26.6 KB

Line
1	/*
2	* Copyright 2002-2019 The OpenSSL Project Authors. All Rights Reserved.
3	* Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
4	*
5	* Licensed under the OpenSSL license (the "License"). You may not use
6	* this file except in compliance with the License. You can obtain a copy
7	* in the file LICENSE in the source distribution or at
8	* https://www.openssl.org/source/license.html
9	*/
10
11	#include <openssl/err.h>
12
13	#include "crypto/bn.h"
14	#include "ec_local.h"
15
16	#ifndef OPENSSL_NO_EC2M
17
18	/*
19	* Initialize a GF(2^m)-based EC_GROUP structure. Note that all other members
20	* are handled by EC_GROUP_new.
21	*/
22	int ec_GF2m_simple_group_init(EC_GROUP *group)
23	{
24	group->field = BN_new();
25	group->a = BN_new();
26	group->b = BN_new();
27
28	if (group->field == NULL \|\| group->a == NULL \|\| group->b == NULL) {
29	BN_free(group->field);
30	BN_free(group->a);
31	BN_free(group->b);
32	return 0;
33	}
34	return 1;
35	}
36
37	/*
38	* Free a GF(2^m)-based EC_GROUP structure. Note that all other members are
39	* handled by EC_GROUP_free.
40	*/
41	void ec_GF2m_simple_group_finish(EC_GROUP *group)
42	{
43	BN_free(group->field);
44	BN_free(group->a);
45	BN_free(group->b);
46	}
47
48	/*
49	* Clear and free a GF(2^m)-based EC_GROUP structure. Note that all other
50	* members are handled by EC_GROUP_clear_free.
51	*/
52	void ec_GF2m_simple_group_clear_finish(EC_GROUP *group)
53	{
54	BN_clear_free(group->field);
55	BN_clear_free(group->a);
56	BN_clear_free(group->b);
57	group->poly[0] = 0;
58	group->poly[1] = 0;
59	group->poly[2] = 0;
60	group->poly[3] = 0;
61	group->poly[4] = 0;
62	group->poly[5] = -1;
63	}
64
65	/*
66	* Copy a GF(2^m)-based EC_GROUP structure. Note that all other members are
67	* handled by EC_GROUP_copy.
68	*/
69	int ec_GF2m_simple_group_copy(EC_GROUP dest, const EC_GROUP src)
70	{
71	if (!BN_copy(dest->field, src->field))
72	return 0;
73	if (!BN_copy(dest->a, src->a))
74	return 0;
75	if (!BN_copy(dest->b, src->b))
76	return 0;
77	dest->poly[0] = src->poly[0];
78	dest->poly[1] = src->poly[1];
79	dest->poly[2] = src->poly[2];
80	dest->poly[3] = src->poly[3];
81	dest->poly[4] = src->poly[4];
82	dest->poly[5] = src->poly[5];
83	if (bn_wexpand(dest->a, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) ==
84	NULL)
85	return 0;
86	if (bn_wexpand(dest->b, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) ==
87	NULL)
88	return 0;
89	bn_set_all_zero(dest->a);
90	bn_set_all_zero(dest->b);
91	return 1;
92	}
93
94	/* Set the curve parameters of an EC_GROUP structure. */
95	int ec_GF2m_simple_group_set_curve(EC_GROUP *group,
96	const BIGNUM p, const BIGNUM a,
97	const BIGNUM b, BN_CTX ctx)
98	{
99	int ret = 0, i;
100
101	/* group->field */
102	if (!BN_copy(group->field, p))
103	goto err;
104	i = BN_GF2m_poly2arr(group->field, group->poly, 6) - 1;
105	if ((i != 5) && (i != 3)) {
106	ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE, EC_R_UNSUPPORTED_FIELD);
107	goto err;
108	}
109
110	/* group->a */
111	if (!BN_GF2m_mod_arr(group->a, a, group->poly))
112	goto err;
113	if (bn_wexpand(group->a, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2)
114	== NULL)
115	goto err;
116	bn_set_all_zero(group->a);
117
118	/* group->b */
119	if (!BN_GF2m_mod_arr(group->b, b, group->poly))
120	goto err;
121	if (bn_wexpand(group->b, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2)
122	== NULL)
123	goto err;
124	bn_set_all_zero(group->b);
125
126	ret = 1;
127	err:
128	return ret;
129	}
130
131	/*
132	* Get the curve parameters of an EC_GROUP structure. If p, a, or b are NULL
133	* then there values will not be set but the method will return with success.
134	*/
135	int ec_GF2m_simple_group_get_curve(const EC_GROUP group, BIGNUM p,
136	BIGNUM a, BIGNUM b, BN_CTX *ctx)
137	{
138	int ret = 0;
139
140	if (p != NULL) {
141	if (!BN_copy(p, group->field))
142	return 0;
143	}
144
145	if (a != NULL) {
146	if (!BN_copy(a, group->a))
147	goto err;
148	}
149
150	if (b != NULL) {
151	if (!BN_copy(b, group->b))
152	goto err;
153	}
154
155	ret = 1;
156
157	err:
158	return ret;
159	}
160
161	/*
162	* Gets the degree of the field. For a curve over GF(2^m) this is the value
163	* m.
164	*/
165	int ec_GF2m_simple_group_get_degree(const EC_GROUP *group)
166	{
167	return BN_num_bits(group->field) - 1;
168	}
169
170	/*
171	* Checks the discriminant of the curve. y^2 + xy = x^3 + ax^2 + b is an
172	* elliptic curve <=> b != 0 (mod p)
173	*/
174	int ec_GF2m_simple_group_check_discriminant(const EC_GROUP *group,
175	BN_CTX *ctx)
176	{
177	int ret = 0;
178	BIGNUM *b;
179	BN_CTX *new_ctx = NULL;
180
181	if (ctx == NULL) {
182	ctx = new_ctx = BN_CTX_new();
183	if (ctx == NULL) {
184	ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT,
185	ERR_R_MALLOC_FAILURE);
186	goto err;
187	}
188	}
189	BN_CTX_start(ctx);
190	b = BN_CTX_get(ctx);
191	if (b == NULL)
192	goto err;
193
194	if (!BN_GF2m_mod_arr(b, group->b, group->poly))
195	goto err;
196
197	/*
198	* check the discriminant: y^2 + xy = x^3 + ax^2 + b is an elliptic
199	* curve <=> b != 0 (mod p)
200	*/
201	if (BN_is_zero(b))
202	goto err;
203
204	ret = 1;
205
206	err:
207	BN_CTX_end(ctx);
208	BN_CTX_free(new_ctx);
209	return ret;
210	}
211
212	/* Initializes an EC_POINT. */
213	int ec_GF2m_simple_point_init(EC_POINT *point)
214	{
215	point->X = BN_new();
216	point->Y = BN_new();
217	point->Z = BN_new();
218
219	if (point->X == NULL \|\| point->Y == NULL \|\| point->Z == NULL) {
220	BN_free(point->X);
221	BN_free(point->Y);
222	BN_free(point->Z);
223	return 0;
224	}
225	return 1;
226	}
227
228	/* Frees an EC_POINT. */
229	void ec_GF2m_simple_point_finish(EC_POINT *point)
230	{
231	BN_free(point->X);
232	BN_free(point->Y);
233	BN_free(point->Z);
234	}
235
236	/* Clears and frees an EC_POINT. */
237	void ec_GF2m_simple_point_clear_finish(EC_POINT *point)
238	{
239	BN_clear_free(point->X);
240	BN_clear_free(point->Y);
241	BN_clear_free(point->Z);
242	point->Z_is_one = 0;
243	}
244
245	/*
246	* Copy the contents of one EC_POINT into another. Assumes dest is
247	* initialized.
248	*/
249	int ec_GF2m_simple_point_copy(EC_POINT dest, const EC_POINT src)
250	{
251	if (!BN_copy(dest->X, src->X))
252	return 0;
253	if (!BN_copy(dest->Y, src->Y))
254	return 0;
255	if (!BN_copy(dest->Z, src->Z))
256	return 0;
257	dest->Z_is_one = src->Z_is_one;
258	dest->curve_name = src->curve_name;
259
260	return 1;
261	}
262
263	/*
264	* Set an EC_POINT to the point at infinity. A point at infinity is
265	* represented by having Z=0.
266	*/
267	int ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group,
268	EC_POINT *point)
269	{
270	point->Z_is_one = 0;
271	BN_zero(point->Z);
272	return 1;
273	}
274
275	/*
276	* Set the coordinates of an EC_POINT using affine coordinates. Note that
277	* the simple implementation only uses affine coordinates.
278	*/
279	int ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP *group,
280	EC_POINT *point,
281	const BIGNUM *x,
282	const BIGNUM y, BN_CTX ctx)
283	{
284	int ret = 0;
285	if (x == NULL \|\| y == NULL) {
286	ECerr(EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES,
287	ERR_R_PASSED_NULL_PARAMETER);
288	return 0;
289	}
290
291	if (!BN_copy(point->X, x))
292	goto err;
293	BN_set_negative(point->X, 0);
294	if (!BN_copy(point->Y, y))
295	goto err;
296	BN_set_negative(point->Y, 0);
297	if (!BN_copy(point->Z, BN_value_one()))
298	goto err;
299	BN_set_negative(point->Z, 0);
300	point->Z_is_one = 1;
301	ret = 1;
302
303	err:
304	return ret;
305	}
306
307	/*
308	* Gets the affine coordinates of an EC_POINT. Note that the simple
309	* implementation only uses affine coordinates.
310	*/
311	int ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group,
312	const EC_POINT *point,
313	BIGNUM x, BIGNUM y,
314	BN_CTX *ctx)
315	{
316	int ret = 0;
317
318	if (EC_POINT_is_at_infinity(group, point)) {
319	ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES,
320	EC_R_POINT_AT_INFINITY);
321	return 0;
322	}
323
324	if (BN_cmp(point->Z, BN_value_one())) {
325	ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES,
326	ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
327	return 0;
328	}
329	if (x != NULL) {
330	if (!BN_copy(x, point->X))
331	goto err;
332	BN_set_negative(x, 0);
333	}
334	if (y != NULL) {
335	if (!BN_copy(y, point->Y))
336	goto err;
337	BN_set_negative(y, 0);
338	}
339	ret = 1;
340
341	err:
342	return ret;
343	}
344
345	/*
346	* Computes a + b and stores the result in r. r could be a or b, a could be
347	* b. Uses algorithm A.10.2 of IEEE P1363.
348	*/
349	int ec_GF2m_simple_add(const EC_GROUP group, EC_POINT r, const EC_POINT *a,
350	const EC_POINT b, BN_CTX ctx)
351	{
352	BN_CTX *new_ctx = NULL;
353	BIGNUM x0, y0, x1, y1, x2, y2, s, t;
354	int ret = 0;
355
356	if (EC_POINT_is_at_infinity(group, a)) {
357	if (!EC_POINT_copy(r, b))
358	return 0;
359	return 1;
360	}
361
362	if (EC_POINT_is_at_infinity(group, b)) {
363	if (!EC_POINT_copy(r, a))
364	return 0;
365	return 1;
366	}
367
368	if (ctx == NULL) {
369	ctx = new_ctx = BN_CTX_new();
370	if (ctx == NULL)
371	return 0;
372	}
373
374	BN_CTX_start(ctx);
375	x0 = BN_CTX_get(ctx);
376	y0 = BN_CTX_get(ctx);
377	x1 = BN_CTX_get(ctx);
378	y1 = BN_CTX_get(ctx);
379	x2 = BN_CTX_get(ctx);
380	y2 = BN_CTX_get(ctx);
381	s = BN_CTX_get(ctx);
382	t = BN_CTX_get(ctx);
383	if (t == NULL)
384	goto err;
385
386	if (a->Z_is_one) {
387	if (!BN_copy(x0, a->X))
388	goto err;
389	if (!BN_copy(y0, a->Y))
390	goto err;
391	} else {
392	if (!EC_POINT_get_affine_coordinates(group, a, x0, y0, ctx))
393	goto err;
394	}
395	if (b->Z_is_one) {
396	if (!BN_copy(x1, b->X))
397	goto err;
398	if (!BN_copy(y1, b->Y))
399	goto err;
400	} else {
401	if (!EC_POINT_get_affine_coordinates(group, b, x1, y1, ctx))
402	goto err;
403	}
404
405	if (BN_GF2m_cmp(x0, x1)) {
406	if (!BN_GF2m_add(t, x0, x1))
407	goto err;
408	if (!BN_GF2m_add(s, y0, y1))
409	goto err;
410	if (!group->meth->field_div(group, s, s, t, ctx))
411	goto err;
412	if (!group->meth->field_sqr(group, x2, s, ctx))
413	goto err;
414	if (!BN_GF2m_add(x2, x2, group->a))
415	goto err;
416	if (!BN_GF2m_add(x2, x2, s))
417	goto err;
418	if (!BN_GF2m_add(x2, x2, t))
419	goto err;
420	} else {
421	if (BN_GF2m_cmp(y0, y1) \|\| BN_is_zero(x1)) {
422	if (!EC_POINT_set_to_infinity(group, r))
423	goto err;
424	ret = 1;
425	goto err;
426	}
427	if (!group->meth->field_div(group, s, y1, x1, ctx))
428	goto err;
429	if (!BN_GF2m_add(s, s, x1))
430	goto err;
431
432	if (!group->meth->field_sqr(group, x2, s, ctx))
433	goto err;
434	if (!BN_GF2m_add(x2, x2, s))
435	goto err;
436	if (!BN_GF2m_add(x2, x2, group->a))
437	goto err;
438	}
439
440	if (!BN_GF2m_add(y2, x1, x2))
441	goto err;
442	if (!group->meth->field_mul(group, y2, y2, s, ctx))
443	goto err;
444	if (!BN_GF2m_add(y2, y2, x2))
445	goto err;
446	if (!BN_GF2m_add(y2, y2, y1))
447	goto err;
448
449	if (!EC_POINT_set_affine_coordinates(group, r, x2, y2, ctx))
450	goto err;
451
452	ret = 1;
453
454	err:
455	BN_CTX_end(ctx);
456	BN_CTX_free(new_ctx);
457	return ret;
458	}
459
460	/*
461	* Computes 2 * a and stores the result in r. r could be a. Uses algorithm
462	* A.10.2 of IEEE P1363.
463	*/
464	int ec_GF2m_simple_dbl(const EC_GROUP group, EC_POINT r, const EC_POINT *a,
465	BN_CTX *ctx)
466	{
467	return ec_GF2m_simple_add(group, r, a, a, ctx);
468	}
469
470	int ec_GF2m_simple_invert(const EC_GROUP group, EC_POINT point, BN_CTX *ctx)
471	{
472	if (EC_POINT_is_at_infinity(group, point) \|\| BN_is_zero(point->Y))
473	/* point is its own inverse */
474	return 1;
475
476	if (!EC_POINT_make_affine(group, point, ctx))
477	return 0;
478	return BN_GF2m_add(point->Y, point->X, point->Y);
479	}
480
481	/* Indicates whether the given point is the point at infinity. */
482	int ec_GF2m_simple_is_at_infinity(const EC_GROUP *group,
483	const EC_POINT *point)
484	{
485	return BN_is_zero(point->Z);
486	}
487
488	/*-
489	* Determines whether the given EC_POINT is an actual point on the curve defined
490	* in the EC_GROUP. A point is valid if it satisfies the Weierstrass equation:
491	* y^2 + xy = x^3 + ax^2 + b.
492	*/
493	int ec_GF2m_simple_is_on_curve(const EC_GROUP group, const EC_POINT point,
494	BN_CTX *ctx)
495	{
496	int ret = -1;
497	BN_CTX *new_ctx = NULL;
498	BIGNUM lh, y2;
499	int (field_mul) (const EC_GROUP , BIGNUM , const BIGNUM ,
500	const BIGNUM , BN_CTX );
501	int (field_sqr) (const EC_GROUP , BIGNUM , const BIGNUM , BN_CTX *);
502
503	if (EC_POINT_is_at_infinity(group, point))
504	return 1;
505
506	field_mul = group->meth->field_mul;
507	field_sqr = group->meth->field_sqr;
508
509	/* only support affine coordinates */
510	if (!point->Z_is_one)
511	return -1;
512
513	if (ctx == NULL) {
514	ctx = new_ctx = BN_CTX_new();
515	if (ctx == NULL)
516	return -1;
517	}
518
519	BN_CTX_start(ctx);
520	y2 = BN_CTX_get(ctx);
521	lh = BN_CTX_get(ctx);
522	if (lh == NULL)
523	goto err;
524
525	/*-
526	* We have a curve defined by a Weierstrass equation
527	* y^2 + xy = x^3 + ax^2 + b.
528	* <=> x^3 + ax^2 + xy + b + y^2 = 0
529	* <=> ((x + a) * x + y ) * x + b + y^2 = 0
530	*/
531	if (!BN_GF2m_add(lh, point->X, group->a))
532	goto err;
533	if (!field_mul(group, lh, lh, point->X, ctx))
534	goto err;
535	if (!BN_GF2m_add(lh, lh, point->Y))
536	goto err;
537	if (!field_mul(group, lh, lh, point->X, ctx))
538	goto err;
539	if (!BN_GF2m_add(lh, lh, group->b))
540	goto err;
541	if (!field_sqr(group, y2, point->Y, ctx))
542	goto err;
543	if (!BN_GF2m_add(lh, lh, y2))
544	goto err;
545	ret = BN_is_zero(lh);
546
547	err:
548	BN_CTX_end(ctx);
549	BN_CTX_free(new_ctx);
550	return ret;
551	}
552
553	/*-
554	* Indicates whether two points are equal.
555	* Return values:
556	* -1 error
557	* 0 equal (in affine coordinates)
558	* 1 not equal
559	*/
560	int ec_GF2m_simple_cmp(const EC_GROUP group, const EC_POINT a,
561	const EC_POINT b, BN_CTX ctx)
562	{
563	BIGNUM aX, aY, bX, bY;
564	BN_CTX *new_ctx = NULL;
565	int ret = -1;
566
567	if (EC_POINT_is_at_infinity(group, a)) {
568	return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
569	}
570
571	if (EC_POINT_is_at_infinity(group, b))
572	return 1;
573
574	if (a->Z_is_one && b->Z_is_one) {
575	return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1;
576	}
577
578	if (ctx == NULL) {
579	ctx = new_ctx = BN_CTX_new();
580	if (ctx == NULL)
581	return -1;
582	}
583
584	BN_CTX_start(ctx);
585	aX = BN_CTX_get(ctx);
586	aY = BN_CTX_get(ctx);
587	bX = BN_CTX_get(ctx);
588	bY = BN_CTX_get(ctx);
589	if (bY == NULL)
590	goto err;
591
592	if (!EC_POINT_get_affine_coordinates(group, a, aX, aY, ctx))
593	goto err;
594	if (!EC_POINT_get_affine_coordinates(group, b, bX, bY, ctx))
595	goto err;
596	ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1;
597
598	err:
599	BN_CTX_end(ctx);
600	BN_CTX_free(new_ctx);
601	return ret;
602	}
603
604	/* Forces the given EC_POINT to internally use affine coordinates. */
605	int ec_GF2m_simple_make_affine(const EC_GROUP group, EC_POINT point,
606	BN_CTX *ctx)
607	{
608	BN_CTX *new_ctx = NULL;
609	BIGNUM x, y;
610	int ret = 0;
611
612	if (point->Z_is_one \|\| EC_POINT_is_at_infinity(group, point))
613	return 1;
614
615	if (ctx == NULL) {
616	ctx = new_ctx = BN_CTX_new();
617	if (ctx == NULL)
618	return 0;
619	}
620
621	BN_CTX_start(ctx);
622	x = BN_CTX_get(ctx);
623	y = BN_CTX_get(ctx);
624	if (y == NULL)
625	goto err;
626
627	if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
628	goto err;
629	if (!BN_copy(point->X, x))
630	goto err;
631	if (!BN_copy(point->Y, y))
632	goto err;
633	if (!BN_one(point->Z))
634	goto err;
635	point->Z_is_one = 1;
636
637	ret = 1;
638
639	err:
640	BN_CTX_end(ctx);
641	BN_CTX_free(new_ctx);
642	return ret;
643	}
644
645	/*
646	* Forces each of the EC_POINTs in the given array to use affine coordinates.
647	*/
648	int ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num,
649	EC_POINT points[], BN_CTX ctx)
650	{
651	size_t i;
652
653	for (i = 0; i < num; i++) {
654	if (!group->meth->make_affine(group, points[i], ctx))
655	return 0;
656	}
657
658	return 1;
659	}
660
661	/* Wrapper to simple binary polynomial field multiplication implementation. */
662	int ec_GF2m_simple_field_mul(const EC_GROUP group, BIGNUM r,
663	const BIGNUM a, const BIGNUM b, BN_CTX *ctx)
664	{
665	return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx);
666	}
667
668	/* Wrapper to simple binary polynomial field squaring implementation. */
669	int ec_GF2m_simple_field_sqr(const EC_GROUP group, BIGNUM r,
670	const BIGNUM a, BN_CTX ctx)
671	{
672	return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx);
673	}
674
675	/* Wrapper to simple binary polynomial field division implementation. */
676	int ec_GF2m_simple_field_div(const EC_GROUP group, BIGNUM r,
677	const BIGNUM a, const BIGNUM b, BN_CTX *ctx)
678	{
679	return BN_GF2m_mod_div(r, a, b, group->field, ctx);
680	}
681
682	/*-
683	* Lopez-Dahab ladder, pre step.
684	* See e.g. "Guide to ECC" Alg 3.40.
685	* Modified to blind s and r independently.
686	* s:= p, r := 2p
687	*/
688	static
689	int ec_GF2m_simple_ladder_pre(const EC_GROUP *group,
690	EC_POINT r, EC_POINT s,
691	EC_POINT p, BN_CTX ctx)
692	{
693	/* if p is not affine, something is wrong */
694	if (p->Z_is_one == 0)
695	return 0;
696
697	/* s blinding: make sure lambda (s->Z here) is not zero */
698	do {
699	if (!BN_priv_rand(s->Z, BN_num_bits(group->field) - 1,
700	BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) {
701	ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_PRE, ERR_R_BN_LIB);
702	return 0;
703	}
704	} while (BN_is_zero(s->Z));
705
706	/* if field_encode defined convert between representations */
707	if ((group->meth->field_encode != NULL
708	&& !group->meth->field_encode(group, s->Z, s->Z, ctx))
709	\|\| !group->meth->field_mul(group, s->X, p->X, s->Z, ctx))
710	return 0;
711
712	/* r blinding: make sure lambda (r->Y here for storage) is not zero */
713	do {
714	if (!BN_priv_rand(r->Y, BN_num_bits(group->field) - 1,
715	BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) {
716	ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_PRE, ERR_R_BN_LIB);
717	return 0;
718	}
719	} while (BN_is_zero(r->Y));
720
721	if ((group->meth->field_encode != NULL
722	&& !group->meth->field_encode(group, r->Y, r->Y, ctx))
723	\|\| !group->meth->field_sqr(group, r->Z, p->X, ctx)
724	\|\| !group->meth->field_sqr(group, r->X, r->Z, ctx)
725	\|\| !BN_GF2m_add(r->X, r->X, group->b)
726	\|\| !group->meth->field_mul(group, r->Z, r->Z, r->Y, ctx)
727	\|\| !group->meth->field_mul(group, r->X, r->X, r->Y, ctx))
728	return 0;
729
730	s->Z_is_one = 0;
731	r->Z_is_one = 0;
732
733	return 1;
734	}
735
736	/*-
737	* Ladder step: differential addition-and-doubling, mixed Lopez-Dahab coords.
738	* http://www.hyperelliptic.org/EFD/g12o/auto-code/shortw/xz/ladder/mladd-2003-s.op3
739	* s := r + s, r := 2r
740	*/
741	static
742	int ec_GF2m_simple_ladder_step(const EC_GROUP *group,
743	EC_POINT r, EC_POINT s,
744	EC_POINT p, BN_CTX ctx)
745	{
746	if (!group->meth->field_mul(group, r->Y, r->Z, s->X, ctx)
747	\|\| !group->meth->field_mul(group, s->X, r->X, s->Z, ctx)
748	\|\| !group->meth->field_sqr(group, s->Y, r->Z, ctx)
749	\|\| !group->meth->field_sqr(group, r->Z, r->X, ctx)
750	\|\| !BN_GF2m_add(s->Z, r->Y, s->X)
751	\|\| !group->meth->field_sqr(group, s->Z, s->Z, ctx)
752	\|\| !group->meth->field_mul(group, s->X, r->Y, s->X, ctx)
753	\|\| !group->meth->field_mul(group, r->Y, s->Z, p->X, ctx)
754	\|\| !BN_GF2m_add(s->X, s->X, r->Y)
755	\|\| !group->meth->field_sqr(group, r->Y, r->Z, ctx)
756	\|\| !group->meth->field_mul(group, r->Z, r->Z, s->Y, ctx)
757	\|\| !group->meth->field_sqr(group, s->Y, s->Y, ctx)
758	\|\| !group->meth->field_mul(group, s->Y, s->Y, group->b, ctx)
759	\|\| !BN_GF2m_add(r->X, r->Y, s->Y))
760	return 0;
761
762	return 1;
763	}
764
765	/*-
766	* Recover affine (x,y) result from Lopez-Dahab r and s, affine p.
767	* See e.g. "Fast Multiplication on Elliptic Curves over GF(2**m)
768	* without Precomputation" (Lopez and Dahab, CHES 1999),
769	* Appendix Alg Mxy.
770	*/
771	static
772	int ec_GF2m_simple_ladder_post(const EC_GROUP *group,
773	EC_POINT r, EC_POINT s,
774	EC_POINT p, BN_CTX ctx)
775	{
776	int ret = 0;
777	BIGNUM t0, t1, *t2 = NULL;
778
779	if (BN_is_zero(r->Z))
780	return EC_POINT_set_to_infinity(group, r);
781
782	if (BN_is_zero(s->Z)) {
783	if (!EC_POINT_copy(r, p)
784	\|\| !EC_POINT_invert(group, r, ctx)) {
785	ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_POST, ERR_R_EC_LIB);
786	return 0;
787	}
788	return 1;
789	}
790
791	BN_CTX_start(ctx);
792	t0 = BN_CTX_get(ctx);
793	t1 = BN_CTX_get(ctx);
794	t2 = BN_CTX_get(ctx);
795	if (t2 == NULL) {
796	ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_POST, ERR_R_MALLOC_FAILURE);
797	goto err;
798	}
799
800	if (!group->meth->field_mul(group, t0, r->Z, s->Z, ctx)
801	\|\| !group->meth->field_mul(group, t1, p->X, r->Z, ctx)
802	\|\| !BN_GF2m_add(t1, r->X, t1)
803	\|\| !group->meth->field_mul(group, t2, p->X, s->Z, ctx)
804	\|\| !group->meth->field_mul(group, r->Z, r->X, t2, ctx)
805	\|\| !BN_GF2m_add(t2, t2, s->X)
806	\|\| !group->meth->field_mul(group, t1, t1, t2, ctx)
807	\|\| !group->meth->field_sqr(group, t2, p->X, ctx)
808	\|\| !BN_GF2m_add(t2, p->Y, t2)
809	\|\| !group->meth->field_mul(group, t2, t2, t0, ctx)
810	\|\| !BN_GF2m_add(t1, t2, t1)
811	\|\| !group->meth->field_mul(group, t2, p->X, t0, ctx)
812	\|\| !group->meth->field_inv(group, t2, t2, ctx)
813	\|\| !group->meth->field_mul(group, t1, t1, t2, ctx)
814	\|\| !group->meth->field_mul(group, r->X, r->Z, t2, ctx)
815	\|\| !BN_GF2m_add(t2, p->X, r->X)
816	\|\| !group->meth->field_mul(group, t2, t2, t1, ctx)
817	\|\| !BN_GF2m_add(r->Y, p->Y, t2)
818	\|\| !BN_one(r->Z))
819	goto err;
820
821	r->Z_is_one = 1;
822
823	/* GF(2^m) field elements should always have BIGNUM::neg = 0 */
824	BN_set_negative(r->X, 0);
825	BN_set_negative(r->Y, 0);
826
827	ret = 1;
828
829	err:
830	BN_CTX_end(ctx);
831	return ret;
832	}
833
834	static
835	int ec_GF2m_simple_points_mul(const EC_GROUP group, EC_POINT r,
836	const BIGNUM *scalar, size_t num,
837	const EC_POINT *points[],
838	const BIGNUM *scalars[],
839	BN_CTX *ctx)
840	{
841	int ret = 0;
842	EC_POINT *t = NULL;
843
844	/*-
845	* We limit use of the ladder only to the following cases:
846	* - r := scalar * G
847	* Fixed point mul: scalar != NULL && num == 0;
848	* - r := scalars[0] * points[0]
849	* Variable point mul: scalar == NULL && num == 1;
850	* - r := scalar * G + scalars[0] * points[0]
851	* used, e.g., in ECDSA verification: scalar != NULL && num == 1
852	*
853	* In any other case (num > 1) we use the default wNAF implementation.
854	*
855	* We also let the default implementation handle degenerate cases like group
856	* order or cofactor set to 0.
857	*/
858	if (num > 1 \|\| BN_is_zero(group->order) \|\| BN_is_zero(group->cofactor))
859	return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
860
861	if (scalar != NULL && num == 0)
862	/* Fixed point multiplication */
863	return ec_scalar_mul_ladder(group, r, scalar, NULL, ctx);
864
865	if (scalar == NULL && num == 1)
866	/* Variable point multiplication */
867	return ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx);
868
869	/*-
870	* Double point multiplication:
871	* r := scalar * G + scalars[0] * points[0]
872	*/
873
874	if ((t = EC_POINT_new(group)) == NULL) {
875	ECerr(EC_F_EC_GF2M_SIMPLE_POINTS_MUL, ERR_R_MALLOC_FAILURE);
876	return 0;
877	}
878
879	if (!ec_scalar_mul_ladder(group, t, scalar, NULL, ctx)
880	\|\| !ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx)
881	\|\| !EC_POINT_add(group, r, t, r, ctx))
882	goto err;
883
884	ret = 1;
885
886	err:
887	EC_POINT_free(t);
888	return ret;
889	}
890
891	/*-
892	* Computes the multiplicative inverse of a in GF(2^m), storing the result in r.
893	* If a is zero (or equivalent), you'll get a EC_R_CANNOT_INVERT error.
894	* SCA hardening is with blinding: BN_GF2m_mod_inv does that.
895	*/
896	static int ec_GF2m_simple_field_inv(const EC_GROUP group, BIGNUM r,
897	const BIGNUM a, BN_CTX ctx)
898	{
899	int ret;
900
901	if (!(ret = BN_GF2m_mod_inv(r, a, group->field, ctx)))
902	ECerr(EC_F_EC_GF2M_SIMPLE_FIELD_INV, EC_R_CANNOT_INVERT);
903	return ret;
904	}
905
906	const EC_METHOD *EC_GF2m_simple_method(void)
907	{
908	static const EC_METHOD ret = {
909	EC_FLAGS_DEFAULT_OCT,
910	NID_X9_62_characteristic_two_field,
911	ec_GF2m_simple_group_init,
912	ec_GF2m_simple_group_finish,
913	ec_GF2m_simple_group_clear_finish,
914	ec_GF2m_simple_group_copy,
915	ec_GF2m_simple_group_set_curve,
916	ec_GF2m_simple_group_get_curve,
917	ec_GF2m_simple_group_get_degree,
918	ec_group_simple_order_bits,
919	ec_GF2m_simple_group_check_discriminant,
920	ec_GF2m_simple_point_init,
921	ec_GF2m_simple_point_finish,
922	ec_GF2m_simple_point_clear_finish,
923	ec_GF2m_simple_point_copy,
924	ec_GF2m_simple_point_set_to_infinity,
925	0, /* set_Jprojective_coordinates_GFp */
926	0, /* get_Jprojective_coordinates_GFp */
927	ec_GF2m_simple_point_set_affine_coordinates,
928	ec_GF2m_simple_point_get_affine_coordinates,
929	0, /* point_set_compressed_coordinates */
930	0, /* point2oct */
931	0, /* oct2point */
932	ec_GF2m_simple_add,
933	ec_GF2m_simple_dbl,
934	ec_GF2m_simple_invert,
935	ec_GF2m_simple_is_at_infinity,
936	ec_GF2m_simple_is_on_curve,
937	ec_GF2m_simple_cmp,
938	ec_GF2m_simple_make_affine,
939	ec_GF2m_simple_points_make_affine,
940	ec_GF2m_simple_points_mul,
941	0, /* precompute_mult */
942	0, /* have_precompute_mult */
943	ec_GF2m_simple_field_mul,
944	ec_GF2m_simple_field_sqr,
945	ec_GF2m_simple_field_div,
946	ec_GF2m_simple_field_inv,
947	0, /* field_encode */
948	0, /* field_decode */
949	0, /* field_set_to_one */
950	ec_key_simple_priv2oct,
951	ec_key_simple_oct2priv,
952	0, /* set private */
953	ec_key_simple_generate_key,
954	ec_key_simple_check_key,
955	ec_key_simple_generate_public_key,
956	0, /* keycopy */
957	0, /* keyfinish */
958	ecdh_simple_compute_key,
959	0, /* field_inverse_mod_ord */
960	0, /* blind_coordinates */
961	ec_GF2m_simple_ladder_pre,
962	ec_GF2m_simple_ladder_step,
963	ec_GF2m_simple_ladder_post
964	};
965
966	return &ret;
967	}
968
969	#endif

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/libs/openssl-1.1.1f/crypto/ec/ec2_smpl.c@ 83531

Download in other formats: