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