ec2_smpl.c@ 96662

Last change on this file since 96662 was 94082, checked in by vboxsync, 3 years ago
libs/openssl-3.0.1: started applying and adjusting our OpenSSL changes to 3.0.1. bugref:10128
File size: 27.4 KB

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

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

source: vbox/trunk/src/libs/openssl-3.0.3/crypto/ec/ec2_smpl.c@ 96662

Download in other formats: