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