xref: /illumos-gate/usr/src/common/crypto/ecc/ecl.c (revision f9fbec18)
1 /*
2  * ***** BEGIN LICENSE BLOCK *****
3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
4  *
5  * The contents of this file are subject to the Mozilla Public License Version
6  * 1.1 (the "License"); you may not use this file except in compliance with
7  * the License. You may obtain a copy of the License at
8  * http://www.mozilla.org/MPL/
9  *
10  * Software distributed under the License is distributed on an "AS IS" basis,
11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
12  * for the specific language governing rights and limitations under the
13  * License.
14  *
15  * The Original Code is the elliptic curve math library.
16  *
17  * The Initial Developer of the Original Code is
18  * Sun Microsystems, Inc.
19  * Portions created by the Initial Developer are Copyright (C) 2003
20  * the Initial Developer. All Rights Reserved.
21  *
22  * Contributor(s):
23  *   Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
24  *
25  * Alternatively, the contents of this file may be used under the terms of
26  * either the GNU General Public License Version 2 or later (the "GPL"), or
27  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
28  * in which case the provisions of the GPL or the LGPL are applicable instead
29  * of those above. If you wish to allow use of your version of this file only
30  * under the terms of either the GPL or the LGPL, and not to allow others to
31  * use your version of this file under the terms of the MPL, indicate your
32  * decision by deleting the provisions above and replace them with the notice
33  * and other provisions required by the GPL or the LGPL. If you do not delete
34  * the provisions above, a recipient may use your version of this file under
35  * the terms of any one of the MPL, the GPL or the LGPL.
36  *
37  * ***** END LICENSE BLOCK ***** */
38 /*
39  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
40  * Use is subject to license terms.
41  *
42  * Sun elects to use this software under the MPL license.
43  */
44 
45 #pragma ident	"%Z%%M%	%I%	%E% SMI"
46 
47 #include "mpi.h"
48 #include "mplogic.h"
49 #include "ecl.h"
50 #include "ecl-priv.h"
51 #include "ec2.h"
52 #include "ecp.h"
53 #ifndef _KERNEL
54 #include <stdlib.h>
55 #include <string.h>
56 #endif
57 
58 /* Allocate memory for a new ECGroup object. */
59 ECGroup *
ECGroup_new(int kmflag)60 ECGroup_new(int kmflag)
61 {
62 	mp_err res = MP_OKAY;
63 	ECGroup *group;
64 #ifdef _KERNEL
65 	group = (ECGroup *) kmem_alloc(sizeof(ECGroup), kmflag);
66 #else
67 	group = (ECGroup *) malloc(sizeof(ECGroup));
68 #endif
69 	if (group == NULL)
70 		return NULL;
71 	group->constructed = MP_YES;
72         group->meth = NULL;
73 	group->text = NULL;
74 	MP_DIGITS(&group->curvea) = 0;
75 	MP_DIGITS(&group->curveb) = 0;
76 	MP_DIGITS(&group->genx) = 0;
77 	MP_DIGITS(&group->geny) = 0;
78 	MP_DIGITS(&group->order) = 0;
79 	group->base_point_mul = NULL;
80 	group->points_mul = NULL;
81 	group->validate_point = NULL;
82 	group->extra1 = NULL;
83 	group->extra2 = NULL;
84 	group->extra_free = NULL;
85 	MP_CHECKOK(mp_init(&group->curvea, kmflag));
86 	MP_CHECKOK(mp_init(&group->curveb, kmflag));
87 	MP_CHECKOK(mp_init(&group->genx, kmflag));
88 	MP_CHECKOK(mp_init(&group->geny, kmflag));
89 	MP_CHECKOK(mp_init(&group->order, kmflag));
90 
91   CLEANUP:
92 	if (res != MP_OKAY) {
93 		ECGroup_free(group);
94 		return NULL;
95 	}
96 	return group;
97 }
98 
99 /* Construct a generic ECGroup for elliptic curves over prime fields. */
100 ECGroup *
ECGroup_consGFp(const mp_int * irr,const mp_int * curvea,const mp_int * curveb,const mp_int * genx,const mp_int * geny,const mp_int * order,int cofactor)101 ECGroup_consGFp(const mp_int *irr, const mp_int *curvea,
102 				const mp_int *curveb, const mp_int *genx,
103 				const mp_int *geny, const mp_int *order, int cofactor)
104 {
105 	mp_err res = MP_OKAY;
106 	ECGroup *group = NULL;
107 
108 	group = ECGroup_new(FLAG(irr));
109 	if (group == NULL)
110 		return NULL;
111 
112 	group->meth = GFMethod_consGFp(irr);
113 	if (group->meth == NULL) {
114 		res = MP_MEM;
115 		goto CLEANUP;
116 	}
117 	MP_CHECKOK(mp_copy(curvea, &group->curvea));
118 	MP_CHECKOK(mp_copy(curveb, &group->curveb));
119 	MP_CHECKOK(mp_copy(genx, &group->genx));
120 	MP_CHECKOK(mp_copy(geny, &group->geny));
121 	MP_CHECKOK(mp_copy(order, &group->order));
122 	group->cofactor = cofactor;
123 	group->point_add = &ec_GFp_pt_add_aff;
124 	group->point_sub = &ec_GFp_pt_sub_aff;
125 	group->point_dbl = &ec_GFp_pt_dbl_aff;
126 	group->point_mul = &ec_GFp_pt_mul_jm_wNAF;
127 	group->base_point_mul = NULL;
128 	group->points_mul = &ec_GFp_pts_mul_jac;
129 	group->validate_point = &ec_GFp_validate_point;
130 
131   CLEANUP:
132 	if (res != MP_OKAY) {
133 		ECGroup_free(group);
134 		return NULL;
135 	}
136 	return group;
137 }
138 
139 /* Construct a generic ECGroup for elliptic curves over prime fields with
140  * field arithmetic implemented in Montgomery coordinates. */
141 ECGroup *
ECGroup_consGFp_mont(const mp_int * irr,const mp_int * curvea,const mp_int * curveb,const mp_int * genx,const mp_int * geny,const mp_int * order,int cofactor)142 ECGroup_consGFp_mont(const mp_int *irr, const mp_int *curvea,
143 					 const mp_int *curveb, const mp_int *genx,
144 					 const mp_int *geny, const mp_int *order, int cofactor)
145 {
146 	mp_err res = MP_OKAY;
147 	ECGroup *group = NULL;
148 
149 	group = ECGroup_new(FLAG(irr));
150 	if (group == NULL)
151 		return NULL;
152 
153 	group->meth = GFMethod_consGFp_mont(irr);
154 	if (group->meth == NULL) {
155 		res = MP_MEM;
156 		goto CLEANUP;
157 	}
158 	MP_CHECKOK(group->meth->
159 			   field_enc(curvea, &group->curvea, group->meth));
160 	MP_CHECKOK(group->meth->
161 			   field_enc(curveb, &group->curveb, group->meth));
162 	MP_CHECKOK(group->meth->field_enc(genx, &group->genx, group->meth));
163 	MP_CHECKOK(group->meth->field_enc(geny, &group->geny, group->meth));
164 	MP_CHECKOK(mp_copy(order, &group->order));
165 	group->cofactor = cofactor;
166 	group->point_add = &ec_GFp_pt_add_aff;
167 	group->point_sub = &ec_GFp_pt_sub_aff;
168 	group->point_dbl = &ec_GFp_pt_dbl_aff;
169 	group->point_mul = &ec_GFp_pt_mul_jm_wNAF;
170 	group->base_point_mul = NULL;
171 	group->points_mul = &ec_GFp_pts_mul_jac;
172 	group->validate_point = &ec_GFp_validate_point;
173 
174   CLEANUP:
175 	if (res != MP_OKAY) {
176 		ECGroup_free(group);
177 		return NULL;
178 	}
179 	return group;
180 }
181 
182 #ifdef NSS_ECC_MORE_THAN_SUITE_B
183 /* Construct a generic ECGroup for elliptic curves over binary polynomial
184  * fields. */
185 ECGroup *
ECGroup_consGF2m(const mp_int * irr,const unsigned int irr_arr[5],const mp_int * curvea,const mp_int * curveb,const mp_int * genx,const mp_int * geny,const mp_int * order,int cofactor)186 ECGroup_consGF2m(const mp_int *irr, const unsigned int irr_arr[5],
187 				 const mp_int *curvea, const mp_int *curveb,
188 				 const mp_int *genx, const mp_int *geny,
189 				 const mp_int *order, int cofactor)
190 {
191 	mp_err res = MP_OKAY;
192 	ECGroup *group = NULL;
193 
194 	group = ECGroup_new(FLAG(irr));
195 	if (group == NULL)
196 		return NULL;
197 
198 	group->meth = GFMethod_consGF2m(irr, irr_arr);
199 	if (group->meth == NULL) {
200 		res = MP_MEM;
201 		goto CLEANUP;
202 	}
203 	MP_CHECKOK(mp_copy(curvea, &group->curvea));
204 	MP_CHECKOK(mp_copy(curveb, &group->curveb));
205 	MP_CHECKOK(mp_copy(genx, &group->genx));
206 	MP_CHECKOK(mp_copy(geny, &group->geny));
207 	MP_CHECKOK(mp_copy(order, &group->order));
208 	group->cofactor = cofactor;
209 	group->point_add = &ec_GF2m_pt_add_aff;
210 	group->point_sub = &ec_GF2m_pt_sub_aff;
211 	group->point_dbl = &ec_GF2m_pt_dbl_aff;
212 	group->point_mul = &ec_GF2m_pt_mul_mont;
213 	group->base_point_mul = NULL;
214 	group->points_mul = &ec_pts_mul_basic;
215 	group->validate_point = &ec_GF2m_validate_point;
216 
217   CLEANUP:
218 	if (res != MP_OKAY) {
219 		ECGroup_free(group);
220 		return NULL;
221 	}
222 	return group;
223 }
224 #endif
225 
226 /* Construct ECGroup from hex parameters and name, if any. Called by
227  * ECGroup_fromHex and ECGroup_fromName. */
228 ECGroup *
ecgroup_fromNameAndHex(const ECCurveName name,const ECCurveParams * params,int kmflag)229 ecgroup_fromNameAndHex(const ECCurveName name,
230 				   const ECCurveParams * params, int kmflag)
231 {
232 	mp_int irr, curvea, curveb, genx, geny, order;
233 	int bits;
234 	ECGroup *group = NULL;
235 	mp_err res = MP_OKAY;
236 
237 	/* initialize values */
238 	MP_DIGITS(&irr) = 0;
239 	MP_DIGITS(&curvea) = 0;
240 	MP_DIGITS(&curveb) = 0;
241 	MP_DIGITS(&genx) = 0;
242 	MP_DIGITS(&geny) = 0;
243 	MP_DIGITS(&order) = 0;
244 	MP_CHECKOK(mp_init(&irr, kmflag));
245 	MP_CHECKOK(mp_init(&curvea, kmflag));
246 	MP_CHECKOK(mp_init(&curveb, kmflag));
247 	MP_CHECKOK(mp_init(&genx, kmflag));
248 	MP_CHECKOK(mp_init(&geny, kmflag));
249 	MP_CHECKOK(mp_init(&order, kmflag));
250 	MP_CHECKOK(mp_read_radix(&irr, params->irr, 16));
251 	MP_CHECKOK(mp_read_radix(&curvea, params->curvea, 16));
252 	MP_CHECKOK(mp_read_radix(&curveb, params->curveb, 16));
253 	MP_CHECKOK(mp_read_radix(&genx, params->genx, 16));
254 	MP_CHECKOK(mp_read_radix(&geny, params->geny, 16));
255 	MP_CHECKOK(mp_read_radix(&order, params->order, 16));
256 
257 	/* determine number of bits */
258 	bits = mpl_significant_bits(&irr) - 1;
259 	if (bits < MP_OKAY) {
260 		res = bits;
261 		goto CLEANUP;
262 	}
263 
264 	/* determine which optimizations (if any) to use */
265 	if (params->field == ECField_GFp) {
266 #ifdef NSS_ECC_MORE_THAN_SUITE_B
267 	    switch (name) {
268 #ifdef ECL_USE_FP
269 		case ECCurve_SECG_PRIME_160R1:
270 			group =
271 				ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
272 								&order, params->cofactor);
273 			if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
274 			MP_CHECKOK(ec_group_set_secp160r1_fp(group));
275 			break;
276 #endif
277 		case ECCurve_SECG_PRIME_192R1:
278 #ifdef ECL_USE_FP
279 			group =
280 				ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
281 								&order, params->cofactor);
282 			if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
283 			MP_CHECKOK(ec_group_set_nistp192_fp(group));
284 #else
285 			group =
286 				ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
287 								&order, params->cofactor);
288 			if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
289 			MP_CHECKOK(ec_group_set_gfp192(group, name));
290 #endif
291 			break;
292 		case ECCurve_SECG_PRIME_224R1:
293 #ifdef ECL_USE_FP
294 			group =
295 				ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
296 								&order, params->cofactor);
297 			if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
298 			MP_CHECKOK(ec_group_set_nistp224_fp(group));
299 #else
300 			group =
301 				ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
302 								&order, params->cofactor);
303 			if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
304 			MP_CHECKOK(ec_group_set_gfp224(group, name));
305 #endif
306 			break;
307 		case ECCurve_SECG_PRIME_256R1:
308 			group =
309 				ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
310 								&order, params->cofactor);
311 			if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
312 			MP_CHECKOK(ec_group_set_gfp256(group, name));
313 			break;
314 		case ECCurve_SECG_PRIME_521R1:
315 			group =
316 				ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
317 								&order, params->cofactor);
318 			if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
319 			MP_CHECKOK(ec_group_set_gfp521(group, name));
320 			break;
321 		default:
322 			/* use generic arithmetic */
323 #endif
324 			group =
325 				ECGroup_consGFp_mont(&irr, &curvea, &curveb, &genx, &geny,
326 									 &order, params->cofactor);
327 			if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
328 #ifdef NSS_ECC_MORE_THAN_SUITE_B
329 		}
330 	} else if (params->field == ECField_GF2m) {
331 		group = ECGroup_consGF2m(&irr, NULL, &curvea, &curveb, &genx, &geny, &order, params->cofactor);
332 		if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
333 		if ((name == ECCurve_NIST_K163) ||
334 		    (name == ECCurve_NIST_B163) ||
335 		    (name == ECCurve_SECG_CHAR2_163R1)) {
336 			MP_CHECKOK(ec_group_set_gf2m163(group, name));
337 		} else if ((name == ECCurve_SECG_CHAR2_193R1) ||
338 		           (name == ECCurve_SECG_CHAR2_193R2)) {
339 			MP_CHECKOK(ec_group_set_gf2m193(group, name));
340 		} else if ((name == ECCurve_NIST_K233) ||
341 		           (name == ECCurve_NIST_B233)) {
342 			MP_CHECKOK(ec_group_set_gf2m233(group, name));
343 		}
344 #endif
345 	} else {
346 		res = MP_UNDEF;
347 		goto CLEANUP;
348 	}
349 
350 	/* set name, if any */
351 	if ((group != NULL) && (params->text != NULL)) {
352 #ifdef _KERNEL
353 		int n = strlen(params->text) + 1;
354 
355 		group->text = kmem_alloc(n, kmflag);
356 		if (group->text == NULL) {
357 			res = MP_MEM;
358 			goto CLEANUP;
359 		}
360 		bcopy(params->text, group->text, n);
361 		group->text_len = n;
362 #else
363 		group->text = strdup(params->text);
364 		if (group->text == NULL) {
365 			res = MP_MEM;
366 		}
367 #endif
368 	}
369 
370   CLEANUP:
371 	mp_clear(&irr);
372 	mp_clear(&curvea);
373 	mp_clear(&curveb);
374 	mp_clear(&genx);
375 	mp_clear(&geny);
376 	mp_clear(&order);
377 	if (res != MP_OKAY) {
378 		ECGroup_free(group);
379 		return NULL;
380 	}
381 	return group;
382 }
383 
384 /* Construct ECGroup from hexadecimal representations of parameters. */
385 ECGroup *
ECGroup_fromHex(const ECCurveParams * params,int kmflag)386 ECGroup_fromHex(const ECCurveParams * params, int kmflag)
387 {
388 	return ecgroup_fromNameAndHex(ECCurve_noName, params, kmflag);
389 }
390 
391 /* Construct ECGroup from named parameters. */
392 ECGroup *
ECGroup_fromName(const ECCurveName name,int kmflag)393 ECGroup_fromName(const ECCurveName name, int kmflag)
394 {
395 	ECGroup *group = NULL;
396 	ECCurveParams *params = NULL;
397 	mp_err res = MP_OKAY;
398 
399 	params = EC_GetNamedCurveParams(name, kmflag);
400 	if (params == NULL) {
401 		res = MP_UNDEF;
402 		goto CLEANUP;
403 	}
404 
405 	/* construct actual group */
406 	group = ecgroup_fromNameAndHex(name, params, kmflag);
407 	if (group == NULL) {
408 		res = MP_UNDEF;
409 		goto CLEANUP;
410 	}
411 
412   CLEANUP:
413 	EC_FreeCurveParams(params);
414 	if (res != MP_OKAY) {
415 		ECGroup_free(group);
416 		return NULL;
417 	}
418 	return group;
419 }
420 
421 /* Validates an EC public key as described in Section 5.2.2 of X9.62. */
ECPoint_validate(const ECGroup * group,const mp_int * px,const mp_int * py)422 mp_err ECPoint_validate(const ECGroup *group, const mp_int *px, const
423 					mp_int *py)
424 {
425     /* 1: Verify that publicValue is not the point at infinity */
426     /* 2: Verify that the coordinates of publicValue are elements
427      *    of the field.
428      */
429     /* 3: Verify that publicValue is on the curve. */
430     /* 4: Verify that the order of the curve times the publicValue
431      *    is the point at infinity.
432      */
433 	return group->validate_point(px, py, group);
434 }
435 
436 /* Free the memory allocated (if any) to an ECGroup object. */
437 void
ECGroup_free(ECGroup * group)438 ECGroup_free(ECGroup *group)
439 {
440 	if (group == NULL)
441 		return;
442 	GFMethod_free(group->meth);
443 	if (group->constructed == MP_NO)
444 		return;
445 	mp_clear(&group->curvea);
446 	mp_clear(&group->curveb);
447 	mp_clear(&group->genx);
448 	mp_clear(&group->geny);
449 	mp_clear(&group->order);
450 	if (group->text != NULL)
451 #ifdef _KERNEL
452 		kmem_free(group->text, group->text_len);
453 #else
454 		free(group->text);
455 #endif
456 	if (group->extra_free != NULL)
457 		group->extra_free(group);
458 #ifdef _KERNEL
459 	kmem_free(group, sizeof (ECGroup));
460 #else
461 	free(group);
462 #endif
463 }
464