mozilla/security/nss/lib/freebl/ecl/ecl.c

   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 #include "mpi.h"
  40 #include "mplogic.h"
  41 #include "ecl.h"
  42 #include "ecl-priv.h"
  43 #include "ec2.h"
  44 #include "ecp.h"
  45 #include <stdlib.h>
  46 #include <string.h>
  47
  48 /* Allocate memory for a new ECGroup object. */
  49 ECGroup *
  50 ECGroup_new()
  51 {
  52         mp_err res = MP_OKAY;
  53         ECGroup *group;
  54         group = (ECGroup *) malloc(sizeof(ECGroup));
  55         if (group == NULL)
  56                 return NULL;
  57         group->constructed = MP_YES;
  58         group->meth = NULL;
  59         group->text = NULL;
  60         MP_DIGITS(&group->curvea) = 0;
  61         MP_DIGITS(&group->curveb) = 0;
  62         MP_DIGITS(&group->genx) = 0;
  63         MP_DIGITS(&group->geny) = 0;
  64         MP_DIGITS(&group->order) = 0;
  65         group->base_point_mul = NULL;
  66         group->points_mul = NULL;
  67         group->validate_point = NULL;
  68         group->extra1 = NULL;
  69         group->extra2 = NULL;
  70         group->extra_free = NULL;
  71         MP_CHECKOK(mp_init(&group->curvea));
  72         MP_CHECKOK(mp_init(&group->curveb));
  73         MP_CHECKOK(mp_init(&group->genx));
  74         MP_CHECKOK(mp_init(&group->geny));
  75         MP_CHECKOK(mp_init(&group->order));
  76
  77   CLEANUP:
  78         if (res != MP_OKAY) {
  79                 ECGroup_free(group);
  80                 return NULL;
  81         }
  82         return group;
  83 }
  84
  85 /* Construct a generic ECGroup for elliptic curves over prime fields. */
  86 ECGroup *
  87 ECGroup_consGFp(const mp_int *irr, const mp_int *curvea,
  88                                 const mp_int *curveb, const mp_int *genx,
  89                                 const mp_int *geny, const mp_int *order, int cofactor)
  90 {
  91         mp_err res = MP_OKAY;
  92         ECGroup *group = NULL;
  93
  94         group = ECGroup_new();
  95         if (group == NULL)
  96                 return NULL;
  97
  98         group->meth = GFMethod_consGFp(irr);
  99         if (group->meth == NULL) {
 100                 res = MP_MEM;
 101                 goto CLEANUP;
 102         }
 103         MP_CHECKOK(mp_copy(curvea, &group->curvea));
 104         MP_CHECKOK(mp_copy(curveb, &group->curveb));
 105         MP_CHECKOK(mp_copy(genx, &group->genx));
 106         MP_CHECKOK(mp_copy(geny, &group->geny));
 107         MP_CHECKOK(mp_copy(order, &group->order));
 108         group->cofactor = cofactor;
 109         group->point_add = &ec_GFp_pt_add_aff;
 110         group->point_sub = &ec_GFp_pt_sub_aff;
 111         group->point_dbl = &ec_GFp_pt_dbl_aff;
 112         group->point_mul = &ec_GFp_pt_mul_jm_wNAF;
 113         group->base_point_mul = NULL;
 114         group->points_mul = &ec_GFp_pts_mul_jac;
 115         group->validate_point = &ec_GFp_validate_point;
 116
 117   CLEANUP:
 118         if (res != MP_OKAY) {
 119                 ECGroup_free(group);
 120                 return NULL;
 121         }
 122         return group;
 123 }
 124
 125 /* Construct a generic ECGroup for elliptic curves over prime fields with
 126  * field arithmetic implemented in Montgomery coordinates. */
 127 ECGroup *
 128 ECGroup_consGFp_mont(const mp_int *irr, const mp_int *curvea,
 129                                          const mp_int *curveb, const mp_int *genx,
 130                                          const mp_int *geny, const mp_int *order, int cofactor)
 131 {
 132         mp_err res = MP_OKAY;
 133         ECGroup *group = NULL;
 134
 135         group = ECGroup_new();
 136         if (group == NULL)
 137                 return NULL;
 138
 139         group->meth = GFMethod_consGFp_mont(irr);
 140         if (group->meth == NULL) {
 141                 res = MP_MEM;
 142                 goto CLEANUP;
 143         }
 144         MP_CHECKOK(group->meth->
 145                            field_enc(curvea, &group->curvea, group->meth));
 146         MP_CHECKOK(group->meth->
 147                            field_enc(curveb, &group->curveb, group->meth));
 148         MP_CHECKOK(group->meth->field_enc(genx, &group->genx, group->meth));
 149         MP_CHECKOK(group->meth->field_enc(geny, &group->geny, group->meth));
 150         MP_CHECKOK(mp_copy(order, &group->order));
 151         group->cofactor = cofactor;
 152         group->point_add = &ec_GFp_pt_add_aff;
 153         group->point_sub = &ec_GFp_pt_sub_aff;
 154         group->point_dbl = &ec_GFp_pt_dbl_aff;
 155         group->point_mul = &ec_GFp_pt_mul_jm_wNAF;
 156         group->base_point_mul = NULL;
 157         group->points_mul = &ec_GFp_pts_mul_jac;
 158         group->validate_point = &ec_GFp_validate_point;
 159
 160   CLEANUP:
 161         if (res != MP_OKAY) {
 162                 ECGroup_free(group);
 163                 return NULL;
 164         }
 165         return group;
 166 }
 167
 168 #ifdef NSS_ECC_MORE_THAN_SUITE_B
 169 /* Construct a generic ECGroup for elliptic curves over binary polynomial
 170  * fields. */
 171 ECGroup *
 172 ECGroup_consGF2m(const mp_int *irr, const unsigned int irr_arr[5],
 173                                  const mp_int *curvea, const mp_int *curveb,
 174                                  const mp_int *genx, const mp_int *geny,
 175                                  const mp_int *order, int cofactor)
 176 {
 177         mp_err res = MP_OKAY;
 178         ECGroup *group = NULL;
 179
 180         group = ECGroup_new();
 181         if (group == NULL)
 182                 return NULL;
 183
 184         group->meth = GFMethod_consGF2m(irr, irr_arr);
 185         if (group->meth == NULL) {
 186                 res = MP_MEM;
 187                 goto CLEANUP;
 188         }
 189         MP_CHECKOK(mp_copy(curvea, &group->curvea));
 190         MP_CHECKOK(mp_copy(curveb, &group->curveb));
 191         MP_CHECKOK(mp_copy(genx, &group->genx));
 192         MP_CHECKOK(mp_copy(geny, &group->geny));
 193         MP_CHECKOK(mp_copy(order, &group->order));
 194         group->cofactor = cofactor;
 195         group->point_add = &ec_GF2m_pt_add_aff;
 196         group->point_sub = &ec_GF2m_pt_sub_aff;
 197         group->point_dbl = &ec_GF2m_pt_dbl_aff;
 198         group->point_mul = &ec_GF2m_pt_mul_mont;
 199         group->base_point_mul = NULL;
 200         group->points_mul = &ec_pts_mul_basic;
 201         group->validate_point = &ec_GF2m_validate_point;
 202
 203   CLEANUP:
 204         if (res != MP_OKAY) {
 205                 ECGroup_free(group);
 206                 return NULL;
 207         }
 208         return group;
 209 }
 210 #endif
 211
 212 /* Construct ECGroup from hex parameters and name, if any. Called by
 213  * ECGroup_fromHex and ECGroup_fromName. */
 214 ECGroup *
 215 ecgroup_fromNameAndHex(const ECCurveName name,
 216                                            const ECCurveParams * params)
 217 {
 218         mp_int irr, curvea, curveb, genx, geny, order;
 219         int bits;
 220         ECGroup *group = NULL;
 221         mp_err res = MP_OKAY;
 222
 223         /* initialize values */
 224         MP_DIGITS(&irr) = 0;
 225         MP_DIGITS(&curvea) = 0;
 226         MP_DIGITS(&curveb) = 0;
 227         MP_DIGITS(&genx) = 0;
 228         MP_DIGITS(&geny) = 0;
 229         MP_DIGITS(&order) = 0;
 230         MP_CHECKOK(mp_init(&irr));
 231         MP_CHECKOK(mp_init(&curvea));
 232         MP_CHECKOK(mp_init(&curveb));
 233         MP_CHECKOK(mp_init(&genx));
 234         MP_CHECKOK(mp_init(&geny));
 235         MP_CHECKOK(mp_init(&order));
 236         MP_CHECKOK(mp_read_radix(&irr, params->irr, 16));
 237         MP_CHECKOK(mp_read_radix(&curvea, params->curvea, 16));
 238         MP_CHECKOK(mp_read_radix(&curveb, params->curveb, 16));
 239         MP_CHECKOK(mp_read_radix(&genx, params->genx, 16));
 240         MP_CHECKOK(mp_read_radix(&geny, params->geny, 16));
 241         MP_CHECKOK(mp_read_radix(&order, params->order, 16));
 242
 243         /* determine number of bits */
 244         bits = mpl_significant_bits(&irr) - 1;
 245         if (bits < MP_OKAY) {
 246                 res = bits;
 247                 goto CLEANUP;
 248         }
 249
 250         /* determine which optimizations (if any) to use */
 251         if (params->field == ECField_GFp) {
 252 #ifdef NSS_ECC_MORE_THAN_SUITE_B
 253             switch (name) {
 254 #ifdef ECL_USE_FP
 255                 case ECCurve_SECG_PRIME_160R1:
 256                         group =
 257                                 ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
 258                                                                 &order, params->cofactor);
 259                         if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
 260                         MP_CHECKOK(ec_group_set_secp160r1_fp(group));
 261                         break;
 262 #endif
 263                 case ECCurve_SECG_PRIME_192R1:
 264 #ifdef ECL_USE_FP
 265                         group =
 266                                 ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
 267                                                                 &order, params->cofactor);
 268                         if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
 269                         MP_CHECKOK(ec_group_set_nistp192_fp(group));
 270 #else
 271                         group =
 272                                 ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
 273                                                                 &order, params->cofactor);
 274                         if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
 275                         MP_CHECKOK(ec_group_set_gfp192(group, name));
 276 #endif
 277                         break;
 278                 case ECCurve_SECG_PRIME_224R1:
 279 #ifdef ECL_USE_FP
 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_nistp224_fp(group));
 285 #else
 286                         group =
 287                                 ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
 288                                                                 &order, params->cofactor);
 289                         if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
 290                         MP_CHECKOK(ec_group_set_gfp224(group, name));
 291 #endif
 292                         break;
 293                 case ECCurve_SECG_PRIME_256R1:
 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_gfp256(group, name));
 299                         break;
 300                 case ECCurve_SECG_PRIME_521R1:
 301                         group =
 302                                 ECGroup_consGFp(&irr, &curvea, &curveb, &genx, &geny,
 303                                                                 &order, params->cofactor);
 304                         if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
 305                         MP_CHECKOK(ec_group_set_gfp521(group, name));
 306                         break;
 307                 default:
 308                         /* use generic arithmetic */
 309 #endif
 310                         group =
 311                                 ECGroup_consGFp_mont(&irr, &curvea, &curveb, &genx, &geny,
 312                                                                          &order, params->cofactor);
 313                         if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
 314 #ifdef NSS_ECC_MORE_THAN_SUITE_B
 315                 }
 316         } else if (params->field == ECField_GF2m) {
 317                 group = ECGroup_consGF2m(&irr, NULL, &curvea, &curveb, &genx, &geny, &order, params->cofactor);
 318                 if (group == NULL) { res = MP_UNDEF; goto CLEANUP; }
 319                 if ((name == ECCurve_NIST_K163) ||
 320                     (name == ECCurve_NIST_B163) ||
 321                     (name == ECCurve_SECG_CHAR2_163R1)) {
 322                         MP_CHECKOK(ec_group_set_gf2m163(group, name));
 323                 } else if ((name == ECCurve_SECG_CHAR2_193R1) ||
 324                            (name == ECCurve_SECG_CHAR2_193R2)) {
 325                         MP_CHECKOK(ec_group_set_gf2m193(group, name));
 326                 } else if ((name == ECCurve_NIST_K233) ||
 327                            (name == ECCurve_NIST_B233)) {
 328                         MP_CHECKOK(ec_group_set_gf2m233(group, name));
 329                 }
 330 #endif
 331         } else {
 332                 res = MP_UNDEF;
 333                 goto CLEANUP;
 334         }
 335
 336         /* set name, if any */
 337         if ((group != NULL) && (params->text != NULL)) {
 338                 group->text = strdup(params->text);
 339                 if (group->text == NULL) {
 340                         res = MP_MEM;
 341                 }
 342         }
 343
 344   CLEANUP:
 345         mp_clear(&irr);
 346         mp_clear(&curvea);
 347         mp_clear(&curveb);
 348         mp_clear(&genx);
 349         mp_clear(&geny);
 350         mp_clear(&order);
 351         if (res != MP_OKAY) {
 352                 ECGroup_free(group);
 353                 return NULL;
 354         }
 355         return group;
 356 }
 357
 358 /* Construct ECGroup from hexadecimal representations of parameters. */
 359 ECGroup *
 360 ECGroup_fromHex(const ECCurveParams * params)
 361 {
 362         return ecgroup_fromNameAndHex(ECCurve_noName, params);
 363 }
 364
 365 /* Construct ECGroup from named parameters. */
 366 ECGroup *
 367 ECGroup_fromName(const ECCurveName name)
 368 {
 369         ECGroup *group = NULL;
 370         ECCurveParams *params = NULL;
 371         mp_err res = MP_OKAY;
 372
 373         params = EC_GetNamedCurveParams(name);
 374         if (params == NULL) {
 375                 res = MP_UNDEF;
 376                 goto CLEANUP;
 377         }
 378
 379         /* construct actual group */
 380         group = ecgroup_fromNameAndHex(name, params);
 381         if (group == NULL) {
 382                 res = MP_UNDEF;
 383                 goto CLEANUP;
 384         }
 385
 386   CLEANUP:
 387         EC_FreeCurveParams(params);
 388         if (res != MP_OKAY) {
 389                 ECGroup_free(group);
 390                 return NULL;
 391         }
 392         return group;
 393 }
 394
 395 /* Validates an EC public key as described in Section 5.2.2 of X9.62. */
 396 mp_err ECPoint_validate(const ECGroup *group, const mp_int *px, const
 397                                         mp_int *py)
 398 {
 399     /* 1: Verify that publicValue is not the point at infinity */
 400     /* 2: Verify that the coordinates of publicValue are elements
 401      *    of the field.
 402      */
 403     /* 3: Verify that publicValue is on the curve. */
 404     /* 4: Verify that the order of the curve times the publicValue
 405      *    is the point at infinity.
 406      */
 407         return group->validate_point(px, py, group);
 408 }
 409
 410 /* Free the memory allocated (if any) to an ECGroup object. */
 411 void
 412 ECGroup_free(ECGroup *group)
 413 {
 414         if (group == NULL)
 415                 return;
 416         GFMethod_free(group->meth);
 417         if (group->constructed == MP_NO)
 418                 return;
 419         mp_clear(&group->curvea);
 420         mp_clear(&group->curveb);
 421         mp_clear(&group->genx);
 422         mp_clear(&group->geny);
 423         mp_clear(&group->order);
 424         if (group->text != NULL)
 425                 free(group->text);
 426         if (group->extra_free != NULL)
 427                 group->extra_free(group);
 428         free(group);
 429 }