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 } 464