xref: /illumos-gate/usr/src/common/crypto/ecc/ecl.c (revision c40a6cd7)
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 #include "mpi.h"
46 #include "mplogic.h"
47 #include "ecl.h"
48 #include "ecl-priv.h"
49 #include "ec2.h"
50 #include "ecp.h"
51 #ifndef _KERNEL
52 #include <stdlib.h>
53 #include <string.h>
54 #endif
55 
56 /* Allocate memory for a new ECGroup object. */
57 ECGroup *
ECGroup_new(int kmflag)58 ECGroup_new(int kmflag)
59 {
60 	mp_err res = MP_OKAY;
61 	ECGroup *group;
62 #ifdef _KERNEL
63 	group = (ECGroup *) kmem_alloc(sizeof(ECGroup), kmflag);
64 #else
65 	group = (ECGroup *) malloc(sizeof(ECGroup));
66 #endif
67 	if (group == NULL)
68 		return NULL;
69 	group->constructed = MP_YES;
70         group->meth = NULL;
71 	group->text = NULL;
72 	MP_DIGITS(&group->curvea) = 0;
73 	MP_DIGITS(&group->curveb) = 0;
74 	MP_DIGITS(&group->genx) = 0;
75 	MP_DIGITS(&group->geny) = 0;
76 	MP_DIGITS(&group->order) = 0;
77 	group->base_point_mul = NULL;
78 	group->points_mul = NULL;
79 	group->validate_point = NULL;
80 	group->extra1 = NULL;
81 	group->extra2 = NULL;
82 	group->extra_free = NULL;
83 	MP_CHECKOK(mp_init(&group->curvea, kmflag));
84 	MP_CHECKOK(mp_init(&group->curveb, kmflag));
85 	MP_CHECKOK(mp_init(&group->genx, kmflag));
86 	MP_CHECKOK(mp_init(&group->geny, kmflag));
87 	MP_CHECKOK(mp_init(&group->order, kmflag));
88 
89   CLEANUP:
90 	if (res != MP_OKAY) {
91 		ECGroup_free(group);
92 		return NULL;
93 	}
94 	return group;
95 }
96 
97 /* Construct a generic ECGroup for elliptic curves over prime fields. */
98 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)99 ECGroup_consGFp(const mp_int *irr, const mp_int *curvea,
100 				const mp_int *curveb, const mp_int *genx,
101 				const mp_int *geny, const mp_int *order, int cofactor)
102 {
103 	mp_err res = MP_OKAY;
104 	ECGroup *group = NULL;
105 
106 	group = ECGroup_new(FLAG(irr));
107 	if (group == NULL)
108 		return NULL;
109 
110 	group->meth = GFMethod_consGFp(irr);
111 	if (group->meth == NULL) {
112 		res = MP_MEM;
113 		goto CLEANUP;
114 	}
115 	MP_CHECKOK(mp_copy(curvea, &group->curvea));
116 	MP_CHECKOK(mp_copy(curveb, &group->curveb));
117 	MP_CHECKOK(mp_copy(genx, &group->genx));
118 	MP_CHECKOK(mp_copy(geny, &group->geny));
119 	MP_CHECKOK(mp_copy(order, &group->order));
120 	group->cofactor = cofactor;
121 	group->point_add = &ec_GFp_pt_add_aff;
122 	group->point_sub = &ec_GFp_pt_sub_aff;
123 	group->point_dbl = &ec_GFp_pt_dbl_aff;
124 	group->point_mul = &ec_GFp_pt_mul_jm_wNAF;
125 	group->base_point_mul = NULL;
126 	group->points_mul = &ec_GFp_pts_mul_jac;
127 	group->validate_point = &ec_GFp_validate_point;
128 
129   CLEANUP:
130 	if (res != MP_OKAY) {
131 		ECGroup_free(group);
132 		return NULL;
133 	}
134 	return group;
135 }
136 
137 /* Construct a generic ECGroup for elliptic curves over prime fields with
138  * field arithmetic implemented in Montgomery coordinates. */
139 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)140 ECGroup_consGFp_mont(const mp_int *irr, const mp_int *curvea,
141 					 const mp_int *curveb, const mp_int *genx,
142 					 const mp_int *geny, const mp_int *order, int cofactor)
143 {
144 	mp_err res = MP_OKAY;
145 	ECGroup *group = NULL;
146 
147 	group = ECGroup_new(FLAG(irr));
148 	if (group == NULL)
149 		return NULL;
150 
151 	group->meth = GFMethod_consGFp_mont(irr);
152 	if (group->meth == NULL) {
153 		res = MP_MEM;
154 		goto CLEANUP;
155 	}
156 	MP_CHECKOK(group->meth->
157 			   field_enc(curvea, &group->curvea, group->meth));
158 	MP_CHECKOK(group->meth->
159 			   field_enc(curveb, &group->curveb, group->meth));
160 	MP_CHECKOK(group->meth->field_enc(genx, &group->genx, group->meth));
161 	MP_CHECKOK(group->meth->field_enc(geny, &group->geny, group->meth));
162 	MP_CHECKOK(mp_copy(order, &group->order));
163 	group->cofactor = cofactor;
164 	group->point_add = &ec_GFp_pt_add_aff;
165 	group->point_sub = &ec_GFp_pt_sub_aff;
166 	group->point_dbl = &ec_GFp_pt_dbl_aff;
167 	group->point_mul = &ec_GFp_pt_mul_jm_wNAF;
168 	group->base_point_mul = NULL;
169 	group->points_mul = &ec_GFp_pts_mul_jac;
170 	group->validate_point = &ec_GFp_validate_point;
171 
172   CLEANUP:
173 	if (res != MP_OKAY) {
174 		ECGroup_free(group);
175 		return NULL;
176 	}
177 	return group;
178 }
179 
180 #ifdef NSS_ECC_MORE_THAN_SUITE_B
181 /* Construct a generic ECGroup for elliptic curves over binary polynomial
182  * fields. */
183 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)184 ECGroup_consGF2m(const mp_int *irr, const unsigned int irr_arr[5],
185 				 const mp_int *curvea, const mp_int *curveb,
186 				 const mp_int *genx, const mp_int *geny,
187 				 const mp_int *order, int cofactor)
188 {
189 	mp_err res = MP_OKAY;
190 	ECGroup *group = NULL;
191 
192 	group = ECGroup_new(FLAG(irr));
193 	if (group == NULL)
194 		return NULL;
195 
196 	group->meth = GFMethod_consGF2m(irr, irr_arr);
197 	if (group->meth == NULL) {
198 		res = MP_MEM;
199 		goto CLEANUP;
200 	}
201 	MP_CHECKOK(mp_copy(curvea, &group->curvea));
202 	MP_CHECKOK(mp_copy(curveb, &group->curveb));
203 	MP_CHECKOK(mp_copy(genx, &group->genx));
204 	MP_CHECKOK(mp_copy(geny, &group->geny));
205 	MP_CHECKOK(mp_copy(order, &group->order));
206 	group->cofactor = cofactor;
207 	group->point_add = &ec_GF2m_pt_add_aff;
208 	group->point_sub = &ec_GF2m_pt_sub_aff;
209 	group->point_dbl = &ec_GF2m_pt_dbl_aff;
210 	group->point_mul = &ec_GF2m_pt_mul_mont;
211 	group->base_point_mul = NULL;
212 	group->points_mul = &ec_pts_mul_basic;
213 	group->validate_point = &ec_GF2m_validate_point;
214 
215   CLEANUP:
216 	if (res != MP_OKAY) {
217 		ECGroup_free(group);
218 		return NULL;
219 	}
220 	return group;
221 }
222 #endif
223 
224 /* Construct ECGroup from hex parameters and name, if any. Called by
225  * ECGroup_fromHex and ECGroup_fromName. */
226 ECGroup *
ecgroup_fromNameAndHex(const ECCurveName name,const ECCurveParams * params,int kmflag)227 ecgroup_fromNameAndHex(const ECCurveName name,
228 				   const ECCurveParams * params, int kmflag)
229 {
230 	mp_int irr, curvea, curveb, genx, geny, order;
231 	int bits;
232 	ECGroup *group = NULL;
233 	mp_err res = MP_OKAY;
234 
235 	/* initialize values */
236 	MP_DIGITS(&irr) = 0;
237 	MP_DIGITS(&curvea) = 0;
238 	MP_DIGITS(&curveb) = 0;
239 	MP_DIGITS(&genx) = 0;
240 	MP_DIGITS(&geny) = 0;
241 	MP_DIGITS(&order) = 0;
242 	MP_CHECKOK(mp_init(&irr, kmflag));
243 	MP_CHECKOK(mp_init(&curvea, kmflag));
244 	MP_CHECKOK(mp_init(&curveb, kmflag));
245 	MP_CHECKOK(mp_init(&genx, kmflag));
246 	MP_CHECKOK(mp_init(&geny, kmflag));
247 	MP_CHECKOK(mp_init(&order, kmflag));
248 	MP_CHECKOK(mp_read_radix(&irr, params->irr, 16));
249 	MP_CHECKOK(mp_read_radix(&curvea, params->curvea, 16));
250 	MP_CHECKOK(mp_read_radix(&curveb, params->curveb, 16));
251 	MP_CHECKOK(mp_read_radix(&genx, params->genx, 16));
252 	MP_CHECKOK(mp_read_radix(&geny, params->geny, 16));
253 	MP_CHECKOK(mp_read_radix(&order, params->order, 16));
254 
255 	/* determine number of bits */
256 	bits = mpl_significant_bits(&irr) - 1;
257 	if (bits < MP_OKAY) {
258 		res = bits;
259 		goto CLEANUP;
260 	}
261 
262 	/* determine which optimizations (if any) to use */
263 	if (params->field == ECField_GFp) {
264 #ifdef NSS_ECC_MORE_THAN_SUITE_B
265 	    switch (name) {
266 #ifdef ECL_USE_FP
267 		case ECCurve_SECG_PRIME_160R1:
268 			group =
269 				ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
270 								&order, params->cofactor);
271 			if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
272 			MP_CHECKOK(ec_group_set_secp160r1_fp(group));
273 			break;
274 #endif
275 		case ECCurve_SECG_PRIME_192R1:
276 #ifdef ECL_USE_FP
277 			group =
278 				ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
279 								&order, params->cofactor);
280 			if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
281 			MP_CHECKOK(ec_group_set_nistp192_fp(group));
282 #else
283 			group =
284 				ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
285 								&order, params->cofactor);
286 			if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
287 			MP_CHECKOK(ec_group_set_gfp192(group, name));
288 #endif
289 			break;
290 		case ECCurve_SECG_PRIME_224R1:
291 #ifdef ECL_USE_FP
292 			group =
293 				ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
294 								&order, params->cofactor);
295 			if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
296 			MP_CHECKOK(ec_group_set_nistp224_fp(group));
297 #else
298 			group =
299 				ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
300 								&order, params->cofactor);
301 			if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
302 			MP_CHECKOK(ec_group_set_gfp224(group, name));
303 #endif
304 			break;
305 		case ECCurve_SECG_PRIME_256R1:
306 			group =
307 				ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
308 								&order, params->cofactor);
309 			if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
310 			MP_CHECKOK(ec_group_set_gfp256(group, name));
311 			break;
312 		case ECCurve_SECG_PRIME_521R1:
313 			group =
314 				ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
315 								&order, params->cofactor);
316 			if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
317 			MP_CHECKOK(ec_group_set_gfp521(group, name));
318 			break;
319 		default:
320 			/* use generic arithmetic */
321 #endif
322 			group =
323 				ECGroup_consGFp_mont(&irr, &curvea, &curveb, &genx, &geny,
324 									 &order, params->cofactor);
325 			if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
326 #ifdef NSS_ECC_MORE_THAN_SUITE_B
327 		}
328 	} else if (params->field == ECField_GF2m) {
329 		group = ECGroup_consGF2m(&irr, NULL, &curvea, &curveb, &genx, &geny, &order, params->cofactor);
330 		if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
331 		if ((name == ECCurve_NIST_K163) ||
332 		    (name == ECCurve_NIST_B163) ||
333 		    (name == ECCurve_SECG_CHAR2_163R1)) {
334 			MP_CHECKOK(ec_group_set_gf2m163(group, name));
335 		} else if ((name == ECCurve_SECG_CHAR2_193R1) ||
336 		           (name == ECCurve_SECG_CHAR2_193R2)) {
337 			MP_CHECKOK(ec_group_set_gf2m193(group, name));
338 		} else if ((name == ECCurve_NIST_K233) ||
339 		           (name == ECCurve_NIST_B233)) {
340 			MP_CHECKOK(ec_group_set_gf2m233(group, name));
341 		}
342 #endif
343 	} else {
344 		res = MP_UNDEF;
345 		goto CLEANUP;
346 	}
347 
348 	/* set name, if any */
349 	if ((group != NULL) && (params->text != NULL)) {
350 #ifdef _KERNEL
351 		int n = strlen(params->text) + 1;
352 
353 		group->text = kmem_alloc(n, kmflag);
354 		if (group->text == NULL) {
355 			res = MP_MEM;
356 			goto CLEANUP;
357 		}
358 		bcopy(params->text, group->text, n);
359 		group->text_len = n;
360 #else
361 		group->text = strdup(params->text);
362 		if (group->text == NULL) {
363 			res = MP_MEM;
364 		}
365 #endif
366 	}
367 
368   CLEANUP:
369 	mp_clear(&irr);
370 	mp_clear(&curvea);
371 	mp_clear(&curveb);
372 	mp_clear(&genx);
373 	mp_clear(&geny);
374 	mp_clear(&order);
375 	if (res != MP_OKAY) {
376 		ECGroup_free(group);
377 		return NULL;
378 	}
379 	return group;
380 }
381 
382 /* Construct ECGroup from hexadecimal representations of parameters. */
383 ECGroup *
ECGroup_fromHex(const ECCurveParams * params,int kmflag)384 ECGroup_fromHex(const ECCurveParams * params, int kmflag)
385 {
386 	return ecgroup_fromNameAndHex(ECCurve_noName, params, kmflag);
387 }
388 
389 /* Construct ECGroup from named parameters. */
390 ECGroup *
ECGroup_fromName(const ECCurveName name,int kmflag)391 ECGroup_fromName(const ECCurveName name, int kmflag)
392 {
393 	ECGroup *group = NULL;
394 	ECCurveParams *params = NULL;
395 	mp_err res = MP_OKAY;
396 
397 	params = EC_GetNamedCurveParams(name, kmflag);
398 	if (params == NULL) {
399 		res = MP_UNDEF;
400 		goto CLEANUP;
401 	}
402 
403 	/* construct actual group */
404 	group = ecgroup_fromNameAndHex(name, params, kmflag);
405 	if (group == NULL) {
406 		res = MP_UNDEF;
407 		goto CLEANUP;
408 	}
409 
410   CLEANUP:
411 	EC_FreeCurveParams(params);
412 	if (res != MP_OKAY) {
413 		ECGroup_free(group);
414 		return NULL;
415 	}
416 	return group;
417 }
418 
419 /* 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)420 mp_err ECPoint_validate(const ECGroup *group, const mp_int *px, const
421 					mp_int *py)
422 {
423     /* 1: Verify that publicValue is not the point at infinity */
424     /* 2: Verify that the coordinates of publicValue are elements
425      *    of the field.
426      */
427     /* 3: Verify that publicValue is on the curve. */
428     /* 4: Verify that the order of the curve times the publicValue
429      *    is the point at infinity.
430      */
431 	return group->validate_point(px, py, group);
432 }
433 
434 /* Free the memory allocated (if any) to an ECGroup object. */
435 void
ECGroup_free(ECGroup * group)436 ECGroup_free(ECGroup *group)
437 {
438 	if (group == NULL)
439 		return;
440 	GFMethod_free(group->meth);
441 	if (group->constructed == MP_NO)
442 		return;
443 	mp_clear(&group->curvea);
444 	mp_clear(&group->curveb);
445 	mp_clear(&group->genx);
446 	mp_clear(&group->geny);
447 	mp_clear(&group->order);
448 	if (group->text != NULL)
449 #ifdef _KERNEL
450 		kmem_free(group->text, group->text_len);
451 #else
452 		free(group->text);
453 #endif
454 	if (group->extra_free != NULL)
455 		group->extra_free(group);
456 #ifdef _KERNEL
457 	kmem_free(group, sizeof (ECGroup));
458 #else
459 	free(group);
460 #endif
461 }
462