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