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 2007 Sun Microsystems, Inc.  All rights reserved.

    54  * Use is subject to license terms.

    55  */

    56 

    57 #pragma ident   "%Z%%M% %I%     %E% SMI"

    58 

    59 #include "mpi.h"

    60 #include "mplogic.h"

    61 #include "ecl.h"

    62 #include "ecl-priv.h"

    63 #include "ec2.h"

    64 #include "ecp.h"

    65 #ifndef _KERNEL

    66 #include <stdlib.h>

    67 #include <string.h>

    68 #endif

    69 

    70 /* Allocate memory for a new ECGroup object. */

    71 ECGroup *

    72 ECGroup_new(int kmflag)

    73 {

    74         mp_err res = MP_OKAY;

    75         ECGroup *group;

    76 #ifdef _KERNEL

    77         group = (ECGroup *) kmem_alloc(sizeof(ECGroup), kmflag);

    78 #else

    79         group = (ECGroup *) malloc(sizeof(ECGroup));

    80 #endif

    81         if (group == NULL)

    82                 return NULL;

    83         group->constructed = MP_YES;

    84         group->meth = NULL;

    85         group->text = NULL;

    86         MP_DIGITS(&group->curvea) = 0;

    87         MP_DIGITS(&group->curveb) = 0;

    88         MP_DIGITS(&group->genx) = 0;

    89         MP_DIGITS(&group->geny) = 0;

    90         MP_DIGITS(&group->order) = 0;

    91         group->base_point_mul = NULL;

    92         group->points_mul = NULL;

    93         group->validate_point = NULL;

    94         group->extra1 = NULL;

    95         group->extra2 = NULL;

    96         group->extra_free = NULL;

    97         MP_CHECKOK(mp_init(&group->curvea, kmflag));

    98         MP_CHECKOK(mp_init(&group->curveb, kmflag));

    99         MP_CHECKOK(mp_init(&group->genx, kmflag));

   100         MP_CHECKOK(mp_init(&group->geny, kmflag));

   101         MP_CHECKOK(mp_init(&group->order, kmflag));

   102 

   103   CLEANUP:

   104         if (res != MP_OKAY) {

   105                 ECGroup_free(group);

   106                 return NULL;

   107         }

   108         return group;

   109 }

   110 

   111 /* Construct a generic ECGroup for elliptic curves over prime fields. */

   112 ECGroup *

   113 ECGroup_consGFp(const mp_int *irr, const mp_int *curvea,

   114                                 const mp_int *curveb, const mp_int *genx,

   115                                 const mp_int *geny, const mp_int *order, int cofactor)

   116 {

   117         mp_err res = MP_OKAY;

   118         ECGroup *group = NULL;

   119 

   120         group = ECGroup_new(FLAG(irr));

   121         if (group == NULL)

   122                 return NULL;

   123 

   124         group->meth = GFMethod_consGFp(irr);

   125         if (group->meth == NULL) {

   126                 res = MP_MEM;

   127                 goto CLEANUP;

   128         }

   129         MP_CHECKOK(mp_copy(curvea, &group->curvea));

   130         MP_CHECKOK(mp_copy(curveb, &group->curveb));

   131         MP_CHECKOK(mp_copy(genx, &group->genx));

   132         MP_CHECKOK(mp_copy(geny, &group->geny));

   133         MP_CHECKOK(mp_copy(order, &group->order));

   134         group->cofactor = cofactor;

   135         group->point_add = &ec_GFp_pt_add_aff;

   136         group->point_sub = &ec_GFp_pt_sub_aff;

   137         group->point_dbl = &ec_GFp_pt_dbl_aff;

   138         group->point_mul = &ec_GFp_pt_mul_jm_wNAF;

   139         group->base_point_mul = NULL;

   140         group->points_mul = &ec_GFp_pts_mul_jac;

   141         group->validate_point = &ec_GFp_validate_point;

   142 

   143   CLEANUP:

   144         if (res != MP_OKAY) {

   145                 ECGroup_free(group);

   146                 return NULL;

   147         }

   148         return group;

   149 }

   150 

   151 /* Construct a generic ECGroup for elliptic curves over prime fields with

   152  * field arithmetic implemented in Montgomery coordinates. */

   153 ECGroup *

   154 ECGroup_consGFp_mont(const mp_int *irr, const mp_int *curvea,

   155                                          const mp_int *curveb, const mp_int *genx,

   156                                          const mp_int *geny, const mp_int *order, int cofactor)

   157 {

   158         mp_err res = MP_OKAY;

   159         ECGroup *group = NULL;

   160 

   161         group = ECGroup_new(FLAG(irr));

   162         if (group == NULL)

   163                 return NULL;

   164 

   165         group->meth = GFMethod_consGFp_mont(irr);

   166         if (group->meth == NULL) {

   167                 res = MP_MEM;

   168                 goto CLEANUP;

   169         }

   170         MP_CHECKOK(group->meth->

   171                            field_enc(curvea, &group->curvea, group->meth));

   172         MP_CHECKOK(group->meth->

   173                            field_enc(curveb, &group->curveb, group->meth));

   174         MP_CHECKOK(group->meth->field_enc(genx, &group->genx, group->meth));

   175         MP_CHECKOK(group->meth->field_enc(geny, &group->geny, group->meth));

   176         MP_CHECKOK(mp_copy(order, &group->order));

   177         group->cofactor = cofactor;

   178         group->point_add = &ec_GFp_pt_add_aff;

   179         group->point_sub = &ec_GFp_pt_sub_aff;

   180         group->point_dbl = &ec_GFp_pt_dbl_aff;

   181         group->point_mul = &ec_GFp_pt_mul_jm_wNAF;

   182         group->base_point_mul = NULL;

   183         group->points_mul = &ec_GFp_pts_mul_jac;

   184         group->validate_point = &ec_GFp_validate_point;

   185 

   186   CLEANUP:

   187         if (res != MP_OKAY) {

   188                 ECGroup_free(group);

   189                 return NULL;

   190         }

   191         return group;

   192 }

   193 

   194 #ifdef NSS_ECC_MORE_THAN_SUITE_B

   195 /* Construct a generic ECGroup for elliptic curves over binary polynomial

   196  * fields. */

   197 ECGroup *

   198 ECGroup_consGF2m(const mp_int *irr, const unsigned int irr_arr[5],

   199                                  const mp_int *curvea, const mp_int *curveb,

   200                                  const mp_int *genx, const mp_int *geny,

   201                                  const mp_int *order, int cofactor)

   202 {

   203         mp_err res = MP_OKAY;

   204         ECGroup *group = NULL;

   205 

   206         group = ECGroup_new(FLAG(irr));

   207         if (group == NULL)

   208                 return NULL;

   209 

   210         group->meth = GFMethod_consGF2m(irr, irr_arr);

   211         if (group->meth == NULL) {

   212                 res = MP_MEM;

   213                 goto CLEANUP;

   214         }

   215         MP_CHECKOK(mp_copy(curvea, &group->curvea));

   216         MP_CHECKOK(mp_copy(curveb, &group->curveb));

   217         MP_CHECKOK(mp_copy(genx, &group->genx));

   218         MP_CHECKOK(mp_copy(geny, &group->geny));

   219         MP_CHECKOK(mp_copy(order, &group->order));

   220         group->cofactor = cofactor;

   221         group->point_add = &ec_GF2m_pt_add_aff;

   222         group->point_sub = &ec_GF2m_pt_sub_aff;

   223         group->point_dbl = &ec_GF2m_pt_dbl_aff;

   224         group->point_mul = &ec_GF2m_pt_mul_mont;

   225         group->base_point_mul = NULL;

   226         group->points_mul = &ec_pts_mul_basic;

   227         group->validate_point = &ec_GF2m_validate_point;

   228 

   229   CLEANUP:

   230         if (res != MP_OKAY) {

   231                 ECGroup_free(group);

   232                 return NULL;

   233         }

   234         return group;

   235 }

   236 #endif

   237 

   238 /* Construct ECGroup from hex parameters and name, if any. Called by

   239  * ECGroup_fromHex and ECGroup_fromName. */

   240 ECGroup *

   241 ecgroup_fromNameAndHex(const ECCurveName name,

   242                                    const ECCurveParams * params, int kmflag)

   243 {

   244         mp_int irr, curvea, curveb, genx, geny, order;

   245         int bits;

   246         ECGroup *group = NULL;

   247         mp_err res = MP_OKAY;

   248 

   249         /* initialize values */

   250         MP_DIGITS(&irr) = 0;

   251         MP_DIGITS(&curvea) = 0;

   252         MP_DIGITS(&curveb) = 0;

   253         MP_DIGITS(&genx) = 0;

   254         MP_DIGITS(&geny) = 0;

   255         MP_DIGITS(&order) = 0;

   256         MP_CHECKOK(mp_init(&irr, kmflag));

   257         MP_CHECKOK(mp_init(&curvea, kmflag));

   258         MP_CHECKOK(mp_init(&curveb, kmflag));

   259         MP_CHECKOK(mp_init(&genx, kmflag));

   260         MP_CHECKOK(mp_init(&geny, kmflag));

   261         MP_CHECKOK(mp_init(&order, kmflag));

   262         MP_CHECKOK(mp_read_radix(&irr, params->irr, 16));

   263         MP_CHECKOK(mp_read_radix(&curvea, params->curvea, 16));

   264         MP_CHECKOK(mp_read_radix(&curveb, params->curveb, 16));

   265         MP_CHECKOK(mp_read_radix(&genx, params->genx, 16));

   266         MP_CHECKOK(mp_read_radix(&geny, params->geny, 16));

   267         MP_CHECKOK(mp_read_radix(&order, params->order, 16));

   268 

   269         /* determine number of bits */

   270         bits = mpl_significant_bits(&irr) - 1;

   271         if (bits < MP_OKAY) {

   272                 res = bits;

   273                 goto CLEANUP;

   274         }

   275 

   276         /* determine which optimizations (if any) to use */

   277         if (params->field == ECField_GFp) {

   278 #ifdef NSS_ECC_MORE_THAN_SUITE_B

   279             switch (name) {

   280 #ifdef ECL_USE_FP

   281                 case ECCurve_SECG_PRIME_160R1:

   282                         group =

   283                                 ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,

   284                                                                 &order, params->cofactor);

   285                         if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }

   286                         MP_CHECKOK(ec_group_set_secp160r1_fp(group));

   287                         break;

   288 #endif

   289                 case ECCurve_SECG_PRIME_192R1:

   290 #ifdef ECL_USE_FP

   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_nistp192_fp(group));

   296 #else

   297                         group =

   298                                 ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,

   299                                                                 &order, params->cofactor);

   300                         if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }

   301                         MP_CHECKOK(ec_group_set_gfp192(group, name));

   302 #endif

   303                         break;

   304                 case ECCurve_SECG_PRIME_224R1:

   305 #ifdef ECL_USE_FP

   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_nistp224_fp(group));

   311 #else

   312                         group =

   313                                 ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,

   314                                                                 &order, params->cofactor);

   315                         if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }

   316                         MP_CHECKOK(ec_group_set_gfp224(group, name));

   317 #endif

   318                         break;

   319                 case ECCurve_SECG_PRIME_256R1:

   320                         group =

   321                                 ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,

   322                                                                 &order, params->cofactor);

   323                         if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }

   324                         MP_CHECKOK(ec_group_set_gfp256(group, name));

   325                         break;

   326                 case ECCurve_SECG_PRIME_521R1:

   327                         group =

   328                                 ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,

   329                                                                 &order, params->cofactor);

   330                         if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }

   331                         MP_CHECKOK(ec_group_set_gfp521(group, name));

   332                         break;

   333                 default:

   334                         /* use generic arithmetic */

   335 #endif

   336                         group =

   337                                 ECGroup_consGFp_mont(&irr, &curvea, &curveb, &genx, &geny,

   338                                                                          &order, params->cofactor);

   339                         if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }

   340 #ifdef NSS_ECC_MORE_THAN_SUITE_B

   341                 }

   342         } else if (params->field == ECField_GF2m) {

   343                 group = ECGroup_consGF2m(&irr, NULL, &curvea, &curveb, &genx, &geny, &order, params->cofactor);

   344                 if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }

   345                 if ((name == ECCurve_NIST_K163) ||

   346                     (name == ECCurve_NIST_B163) ||

   347                     (name == ECCurve_SECG_CHAR2_163R1)) {

   348                         MP_CHECKOK(ec_group_set_gf2m163(group, name));

   349                 } else if ((name == ECCurve_SECG_CHAR2_193R1) ||

   350                            (name == ECCurve_SECG_CHAR2_193R2)) {

   351                         MP_CHECKOK(ec_group_set_gf2m193(group, name));

   352                 } else if ((name == ECCurve_NIST_K233) ||

   353                            (name == ECCurve_NIST_B233)) {

   354                         MP_CHECKOK(ec_group_set_gf2m233(group, name));

   355                 }

   356 #endif

   357         } else {

   358                 res = MP_UNDEF;

   359                 goto CLEANUP;

   360         }

   361 

   362         /* set name, if any */

   363         if ((group != NULL) && (params->text != NULL)) {

   364 #ifdef _KERNEL

   365                 int n = strlen(params->text) + 1;

   366 

   367                 group->text = kmem_alloc(n, kmflag);

   368                 if (group->text == NULL) {

   369                         res = MP_MEM;

   370                         goto CLEANUP;

   371                 }

   372                 bcopy(params->text, group->text, n);

   373                 group->text_len = n;

   374 #else

   375                 group->text = strdup(params->text);

   376                 if (group->text == NULL) {

   377                         res = MP_MEM;

   378                 }

   379 #endif

   380         }

   381 

   382   CLEANUP:

   383         mp_clear(&irr);

   384         mp_clear(&curvea);

   385         mp_clear(&curveb);

   386         mp_clear(&genx);

   387         mp_clear(&geny);

   388         mp_clear(&order);

   389         if (res != MP_OKAY) {

   390                 ECGroup_free(group);

   391                 return NULL;

   392         }

   393         return group;

   394 }

   395 

   396 /* Construct ECGroup from hexadecimal representations of parameters. */

   397 ECGroup *

   398 ECGroup_fromHex(const ECCurveParams * params, int kmflag)

   399 {

   400         return ecgroup_fromNameAndHex(ECCurve_noName, params, kmflag);

   401 }

   402 

   403 /* Construct ECGroup from named parameters. */

   404 ECGroup *

   405 ECGroup_fromName(const ECCurveName name, int kmflag)

   406 {

   407         ECGroup *group = NULL;

   408         ECCurveParams *params = NULL;

   409         mp_err res = MP_OKAY;

   410 

   411         params = EC_GetNamedCurveParams(name, kmflag);

   412         if (params == NULL) {

   413                 res = MP_UNDEF;

   414                 goto CLEANUP;

   415         }

   416 

   417         /* construct actual group */

   418         group = ecgroup_fromNameAndHex(name, params, kmflag);

   419         if (group == NULL) {

   420                 res = MP_UNDEF;

   421                 goto CLEANUP;

   422         }

   423 

   424   CLEANUP:

   425         EC_FreeCurveParams(params);

   426         if (res != MP_OKAY) {

   427                 ECGroup_free(group);

   428                 return NULL;

   429         }

   430         return group;

   431 }

   432 

   433 /* Validates an EC public key as described in Section 5.2.2 of X9.62. */

   434 mp_err ECPoint_validate(const ECGroup *group, const mp_int *px, const

   435                                         mp_int *py)

   436 {

   437     /* 1: Verify that publicValue is not the point at infinity */

   438     /* 2: Verify that the coordinates of publicValue are elements

   439      *    of the field.

   440      */

   441     /* 3: Verify that publicValue is on the curve. */

   442     /* 4: Verify that the order of the curve times the publicValue

   443      *    is the point at infinity.

   444      */

   445         return group->validate_point(px, py, group);

   446 }

   447 

   448 /* Free the memory allocated (if any) to an ECGroup object. */

   449 void

   450 ECGroup_free(ECGroup *group)

   451 {

   452         if (group == NULL)

   453                 return;

   454         GFMethod_free(group->meth);

   455         if (group->constructed == MP_NO)

   456                 return;

   457         mp_clear(&group->curvea);

   458         mp_clear(&group->curveb);

   459         mp_clear(&group->genx);

   460         mp_clear(&group->geny);

   461         mp_clear(&group->order);

   462         if (group->text != NULL)

   463 #ifdef _KERNEL

   464                 kmem_free(group->text, group->text_len);

   465 #else

   466                 free(group->text);

   467 #endif

   468         if (group->extra_free != NULL)

   469                 group->extra_free(group);

   470 #ifdef _KERNEL

   471         kmem_free(group, sizeof (ECGroup));

   472 #else

   473         free(group);

   474 #endif

   475 }