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. */
59ECGroup *
60ECGroup_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. */
100ECGroup *
101ECGroup_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. */
141ECGroup *
142ECGroup_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. */
185ECGroup *
186ECGroup_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. */
228ECGroup *
229ecgroup_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. */
385ECGroup *
386ECGroup_fromHex(const ECCurveParams * params, int kmflag)
387{
388	return ecgroup_fromNameAndHex(ECCurve_noName, params, kmflag);
389}
390
391/* Construct ECGroup from named parameters. */
392ECGroup *
393ECGroup_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. */
422mp_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. */
437void
438ECGroup_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