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