Back to index

lightning-sunbird  0.9+nobinonly
ecl.c
Go to the documentation of this file.
00001 /* 
00002  * ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is the elliptic curve math library.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Sun Microsystems, Inc.
00019  * Portions created by the Initial Developer are Copyright (C) 2003
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either the GNU General Public License Version 2 or later (the "GPL"), or
00027  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00028  * in which case the provisions of the GPL or the LGPL are applicable instead
00029  * of those above. If you wish to allow use of your version of this file only
00030  * under the terms of either the GPL or the LGPL, and not to allow others to
00031  * use your version of this file under the terms of the MPL, indicate your
00032  * decision by deleting the provisions above and replace them with the notice
00033  * and other provisions required by the GPL or the LGPL. If you do not delete
00034  * the provisions above, a recipient may use your version of this file under
00035  * the terms of any one of the MPL, the GPL or the LGPL.
00036  *
00037  * ***** END LICENSE BLOCK ***** */
00038 
00039 #include "mpi.h"
00040 #include "mplogic.h"
00041 #include "ecl.h"
00042 #include "ecl-priv.h"
00043 #include "ec2.h"
00044 #include "ecp.h"
00045 #include <stdlib.h>
00046 #include <string.h>
00047 
00048 /* Allocate memory for a new ECGroup object. */
00049 ECGroup *
00050 ECGroup_new()
00051 {
00052        mp_err res = MP_OKAY;
00053        ECGroup *group;
00054        group = (ECGroup *) malloc(sizeof(ECGroup));
00055        if (group == NULL)
00056               return NULL;
00057        group->constructed = MP_YES;
00058         group->meth = NULL;
00059        group->text = NULL;
00060        MP_DIGITS(&group->curvea) = 0;
00061        MP_DIGITS(&group->curveb) = 0;
00062        MP_DIGITS(&group->genx) = 0;
00063        MP_DIGITS(&group->geny) = 0;
00064        MP_DIGITS(&group->order) = 0;
00065        group->base_point_mul = NULL;
00066        group->points_mul = NULL;
00067        group->validate_point = NULL;
00068        group->extra1 = NULL;
00069        group->extra2 = NULL;
00070        group->extra_free = NULL;
00071        MP_CHECKOK(mp_init(&group->curvea));
00072        MP_CHECKOK(mp_init(&group->curveb));
00073        MP_CHECKOK(mp_init(&group->genx));
00074        MP_CHECKOK(mp_init(&group->geny));
00075        MP_CHECKOK(mp_init(&group->order));
00076 
00077   CLEANUP:
00078        if (res != MP_OKAY) {
00079               ECGroup_free(group);
00080               return NULL;
00081        }
00082        return group;
00083 }
00084 
00085 /* Construct a generic ECGroup for elliptic curves over prime fields. */
00086 ECGroup *
00087 ECGroup_consGFp(const mp_int *irr, const mp_int *curvea,
00088                             const mp_int *curveb, const mp_int *genx,
00089                             const mp_int *geny, const mp_int *order, int cofactor)
00090 {
00091        mp_err res = MP_OKAY;
00092        ECGroup *group = NULL;
00093 
00094        group = ECGroup_new();
00095        if (group == NULL)
00096               return NULL;
00097 
00098        group->meth = GFMethod_consGFp(irr);
00099        if (group->meth == NULL) {
00100               res = MP_MEM;
00101               goto CLEANUP;
00102        }
00103        MP_CHECKOK(mp_copy(curvea, &group->curvea));
00104        MP_CHECKOK(mp_copy(curveb, &group->curveb));
00105        MP_CHECKOK(mp_copy(genx, &group->genx));
00106        MP_CHECKOK(mp_copy(geny, &group->geny));
00107        MP_CHECKOK(mp_copy(order, &group->order));
00108        group->cofactor = cofactor;
00109        group->point_add = &ec_GFp_pt_add_aff;
00110        group->point_sub = &ec_GFp_pt_sub_aff;
00111        group->point_dbl = &ec_GFp_pt_dbl_aff;
00112        group->point_mul = &ec_GFp_pt_mul_jm_wNAF;
00113        group->base_point_mul = NULL;
00114        group->points_mul = &ec_GFp_pts_mul_jac;
00115        group->validate_point = &ec_GFp_validate_point;
00116 
00117   CLEANUP:
00118        if (res != MP_OKAY) {
00119               ECGroup_free(group);
00120               return NULL;
00121        }
00122        return group;
00123 }
00124 
00125 /* Construct a generic ECGroup for elliptic curves over prime fields with
00126  * field arithmetic implemented in Montgomery coordinates. */
00127 ECGroup *
00128 ECGroup_consGFp_mont(const mp_int *irr, const mp_int *curvea,
00129                                     const mp_int *curveb, const mp_int *genx,
00130                                     const mp_int *geny, const mp_int *order, int cofactor)
00131 {
00132        mp_err res = MP_OKAY;
00133        ECGroup *group = NULL;
00134 
00135        group = ECGroup_new();
00136        if (group == NULL)
00137               return NULL;
00138 
00139        group->meth = GFMethod_consGFp_mont(irr);
00140        if (group->meth == NULL) {
00141               res = MP_MEM;
00142               goto CLEANUP;
00143        }
00144        MP_CHECKOK(group->meth->
00145                         field_enc(curvea, &group->curvea, group->meth));
00146        MP_CHECKOK(group->meth->
00147                         field_enc(curveb, &group->curveb, group->meth));
00148        MP_CHECKOK(group->meth->field_enc(genx, &group->genx, group->meth));
00149        MP_CHECKOK(group->meth->field_enc(geny, &group->geny, group->meth));
00150        MP_CHECKOK(mp_copy(order, &group->order));
00151        group->cofactor = cofactor;
00152        group->point_add = &ec_GFp_pt_add_aff;
00153        group->point_sub = &ec_GFp_pt_sub_aff;
00154        group->point_dbl = &ec_GFp_pt_dbl_aff;
00155        group->point_mul = &ec_GFp_pt_mul_jm_wNAF;
00156        group->base_point_mul = NULL;
00157        group->points_mul = &ec_GFp_pts_mul_jac;
00158        group->validate_point = &ec_GFp_validate_point;
00159 
00160   CLEANUP:
00161        if (res != MP_OKAY) {
00162               ECGroup_free(group);
00163               return NULL;
00164        }
00165        return group;
00166 }
00167 
00168 #ifdef NSS_ECC_MORE_THAN_SUITE_B
00169 /* Construct a generic ECGroup for elliptic curves over binary polynomial
00170  * fields. */
00171 ECGroup *
00172 ECGroup_consGF2m(const mp_int *irr, const unsigned int irr_arr[5],
00173                              const mp_int *curvea, const mp_int *curveb,
00174                              const mp_int *genx, const mp_int *geny,
00175                              const mp_int *order, int cofactor)
00176 {
00177        mp_err res = MP_OKAY;
00178        ECGroup *group = NULL;
00179 
00180        group = ECGroup_new();
00181        if (group == NULL)
00182               return NULL;
00183 
00184        group->meth = GFMethod_consGF2m(irr, irr_arr);
00185        if (group->meth == NULL) {
00186               res = MP_MEM;
00187               goto CLEANUP;
00188        }
00189        MP_CHECKOK(mp_copy(curvea, &group->curvea));
00190        MP_CHECKOK(mp_copy(curveb, &group->curveb));
00191        MP_CHECKOK(mp_copy(genx, &group->genx));
00192        MP_CHECKOK(mp_copy(geny, &group->geny));
00193        MP_CHECKOK(mp_copy(order, &group->order));
00194        group->cofactor = cofactor;
00195        group->point_add = &ec_GF2m_pt_add_aff;
00196        group->point_sub = &ec_GF2m_pt_sub_aff;
00197        group->point_dbl = &ec_GF2m_pt_dbl_aff;
00198        group->point_mul = &ec_GF2m_pt_mul_mont;
00199        group->base_point_mul = NULL;
00200        group->points_mul = &ec_pts_mul_basic;
00201        group->validate_point = &ec_GF2m_validate_point;
00202 
00203   CLEANUP:
00204        if (res != MP_OKAY) {
00205               ECGroup_free(group);
00206               return NULL;
00207        }
00208        return group;
00209 }
00210 #endif
00211 
00212 /* Construct ECGroup from hex parameters and name, if any. Called by
00213  * ECGroup_fromHex and ECGroup_fromName. */
00214 ECGroup *
00215 ecgroup_fromNameAndHex(const ECCurveName name,
00216                                       const ECCurveParams * params)
00217 {
00218        mp_int irr, curvea, curveb, genx, geny, order;
00219        int bits;
00220        ECGroup *group = NULL;
00221        mp_err res = MP_OKAY;
00222 
00223        /* initialize values */
00224        MP_DIGITS(&irr) = 0;
00225        MP_DIGITS(&curvea) = 0;
00226        MP_DIGITS(&curveb) = 0;
00227        MP_DIGITS(&genx) = 0;
00228        MP_DIGITS(&geny) = 0;
00229        MP_DIGITS(&order) = 0;
00230        MP_CHECKOK(mp_init(&irr));
00231        MP_CHECKOK(mp_init(&curvea));
00232        MP_CHECKOK(mp_init(&curveb));
00233        MP_CHECKOK(mp_init(&genx));
00234        MP_CHECKOK(mp_init(&geny));
00235        MP_CHECKOK(mp_init(&order));
00236        MP_CHECKOK(mp_read_radix(&irr, params->irr, 16));
00237        MP_CHECKOK(mp_read_radix(&curvea, params->curvea, 16));
00238        MP_CHECKOK(mp_read_radix(&curveb, params->curveb, 16));
00239        MP_CHECKOK(mp_read_radix(&genx, params->genx, 16));
00240        MP_CHECKOK(mp_read_radix(&geny, params->geny, 16));
00241        MP_CHECKOK(mp_read_radix(&order, params->order, 16));
00242 
00243        /* determine number of bits */
00244        bits = mpl_significant_bits(&irr) - 1;
00245        if (bits < MP_OKAY) {
00246               res = bits;
00247               goto CLEANUP;
00248        }
00249 
00250        /* determine which optimizations (if any) to use */
00251        if (params->field == ECField_GFp) {
00252 #ifdef NSS_ECC_MORE_THAN_SUITE_B
00253            switch (name) {
00254 #ifdef ECL_USE_FP
00255               case ECCurve_SECG_PRIME_160R1:
00256                      group =
00257                             ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
00258                                                         &order, params->cofactor);
00259                      if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
00260                      MP_CHECKOK(ec_group_set_secp160r1_fp(group));
00261                      break;
00262 #endif
00263               case ECCurve_SECG_PRIME_192R1:
00264 #ifdef ECL_USE_FP
00265                      group =
00266                             ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
00267                                                         &order, params->cofactor);
00268                      if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
00269                      MP_CHECKOK(ec_group_set_nistp192_fp(group));
00270 #else
00271                      group =
00272                             ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
00273                                                         &order, params->cofactor);
00274                      if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
00275                      MP_CHECKOK(ec_group_set_gfp192(group, name));
00276 #endif
00277                      break;
00278               case ECCurve_SECG_PRIME_224R1:
00279 #ifdef ECL_USE_FP
00280                      group =
00281                             ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
00282                                                         &order, params->cofactor);
00283                      if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
00284                      MP_CHECKOK(ec_group_set_nistp224_fp(group));
00285 #else
00286                      group =
00287                             ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
00288                                                         &order, params->cofactor);
00289                      if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
00290                      MP_CHECKOK(ec_group_set_gfp224(group, name));
00291 #endif
00292                      break;
00293               case ECCurve_SECG_PRIME_256R1:
00294                      group =
00295                             ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
00296                                                         &order, params->cofactor);
00297                      if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
00298                      MP_CHECKOK(ec_group_set_gfp256(group, name));
00299                      break;
00300               case ECCurve_SECG_PRIME_521R1:
00301                      group =
00302                             ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
00303                                                         &order, params->cofactor);
00304                      if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
00305                      MP_CHECKOK(ec_group_set_gfp521(group, name));
00306                      break;
00307               default:
00308                      /* use generic arithmetic */
00309 #endif
00310                      group =
00311                             ECGroup_consGFp_mont(&irr, &curvea, &curveb, &genx, &geny,
00312                                                                 &order, params->cofactor);
00313                      if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
00314 #ifdef NSS_ECC_MORE_THAN_SUITE_B
00315               }
00316        } else if (params->field == ECField_GF2m) {
00317               group = ECGroup_consGF2m(&irr, NULL, &curvea, &curveb, &genx, &geny, &order, params->cofactor);
00318               if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
00319               if ((name == ECCurve_NIST_K163) ||
00320                   (name == ECCurve_NIST_B163) ||
00321                   (name == ECCurve_SECG_CHAR2_163R1)) {
00322                      MP_CHECKOK(ec_group_set_gf2m163(group, name));
00323               } else if ((name == ECCurve_SECG_CHAR2_193R1) ||
00324                          (name == ECCurve_SECG_CHAR2_193R2)) {
00325                      MP_CHECKOK(ec_group_set_gf2m193(group, name));
00326               } else if ((name == ECCurve_NIST_K233) ||
00327                          (name == ECCurve_NIST_B233)) {
00328                      MP_CHECKOK(ec_group_set_gf2m233(group, name));
00329               }
00330 #endif
00331        }
00332 
00333        /* set name, if any */
00334        if (params->text != NULL) {
00335               group->text = strdup(params->text);
00336               if (group->text == NULL) {
00337                      res = MP_MEM;
00338               }
00339        }
00340 
00341   CLEANUP:
00342        mp_clear(&irr);
00343        mp_clear(&curvea);
00344        mp_clear(&curveb);
00345        mp_clear(&genx);
00346        mp_clear(&geny);
00347        mp_clear(&order);
00348        if (res != MP_OKAY) {
00349               ECGroup_free(group);
00350               return NULL;
00351        }
00352        return group;
00353 }
00354 
00355 /* Construct ECGroup from hexadecimal representations of parameters. */
00356 ECGroup *
00357 ECGroup_fromHex(const ECCurveParams * params)
00358 {
00359        return ecgroup_fromNameAndHex(ECCurve_noName, params);
00360 }
00361 
00362 /* Construct ECGroup from named parameters. */
00363 ECGroup *
00364 ECGroup_fromName(const ECCurveName name)
00365 {
00366        ECGroup *group = NULL;
00367        ECCurveParams *params = NULL;
00368        mp_err res = MP_OKAY;
00369 
00370        params = EC_GetNamedCurveParams(name);
00371        if (params == NULL) {
00372               res = MP_UNDEF;
00373               goto CLEANUP;
00374        }
00375 
00376        /* construct actual group */
00377        group = ecgroup_fromNameAndHex(name, params);
00378        if (group == NULL) {
00379               res = MP_UNDEF;
00380               goto CLEANUP;
00381        }
00382 
00383   CLEANUP:
00384        EC_FreeCurveParams(params);
00385        if (res != MP_OKAY) {
00386               ECGroup_free(group);
00387               return NULL;
00388        }
00389        return group;
00390 }
00391 
00392 /* Validates an EC public key as described in Section 5.2.2 of X9.62. */
00393 mp_err ECPoint_validate(const ECGroup *group, const mp_int *px, const 
00394                                    mp_int *py)
00395 {
00396     /* 1: Verify that publicValue is not the point at infinity */
00397     /* 2: Verify that the coordinates of publicValue are elements 
00398      *    of the field.
00399      */
00400     /* 3: Verify that publicValue is on the curve. */
00401     /* 4: Verify that the order of the curve times the publicValue
00402      *    is the point at infinity.
00403      */
00404        return group->validate_point(px, py, group);
00405 }
00406 
00407 /* Free the memory allocated (if any) to an ECGroup object. */
00408 void
00409 ECGroup_free(ECGroup *group)
00410 {
00411        if (group == NULL)
00412               return;
00413        GFMethod_free(group->meth);
00414        if (group->constructed == MP_NO)
00415               return;
00416        mp_clear(&group->curvea);
00417        mp_clear(&group->curveb);
00418        mp_clear(&group->genx);
00419        mp_clear(&group->geny);
00420        mp_clear(&group->order);
00421        if (group->text != NULL)
00422               free(group->text);
00423        if (group->extra_free != NULL)
00424               group->extra_free(group);
00425        free(group);
00426 }