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