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 Cryptography 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 * Dr Vipul Gupta <vipul.gupta@sun.com> and 24 * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories 25 * 26 * Alternatively, the contents of this file may be used under the terms of 27 * either the GNU General Public License Version 2 or later (the "GPL"), or 28 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), 29 * in which case the provisions of the GPL or the LGPL are applicable instead 30 * of those above. If you wish to allow use of your version of this file only 31 * under the terms of either the GPL or the LGPL, and not to allow others to 32 * use your version of this file under the terms of the MPL, indicate your 33 * decision by deleting the provisions above and replace them with the notice 34 * and other provisions required by the GPL or the LGPL. If you do not delete 35 * the provisions above, a recipient may use your version of this file under 36 * the terms of any one of the MPL, the GPL or the LGPL. 37 * 38 * ***** END LICENSE BLOCK ***** */ 39 /* 40 * Copyright 2007 Sun Microsystems, Inc. All rights reserved. 41 * Use is subject to license terms. 42 * 43 * Sun elects to use this software under the MPL license. 44 */ 45 46 #pragma ident "%Z%%M% %I% %E% SMI" 47 48 #include "mplogic.h" 49 #include "ec.h" 50 #include "ecl.h" 51 52 #include <sys/types.h> 53 #ifndef _KERNEL 54 #include <stdlib.h> 55 #include <string.h> 56 #include <strings.h> 57 #endif 58 #include "ecl-exp.h" 59 #include "mpi.h" 60 #include "ecc_impl.h" 61 62 #ifdef _KERNEL 63 #define PORT_ZFree(p, l) bzero((p), (l)); kmem_free((p), (l)) 64 #else 65 #define PORT_ZFree(p, l) bzero((p), (l)); free((p)) 66 #endif 67 68 /* 69 * Returns true if pointP is the point at infinity, false otherwise 70 */ 71 PRBool 72 ec_point_at_infinity(SECItem *pointP) 73 { 74 unsigned int i; 75 76 for (i = 1; i < pointP->len; i++) { 77 if (pointP->data[i] != 0x00) return PR_FALSE; 78 } 79 80 return PR_TRUE; 81 } 82 83 /* 84 * Computes scalar point multiplication pointQ = k1 * G + k2 * pointP for 85 * the curve whose parameters are encoded in params with base point G. 86 */ 87 SECStatus 88 ec_points_mul(const ECParams *params, const mp_int *k1, const mp_int *k2, 89 const SECItem *pointP, SECItem *pointQ, int kmflag) 90 { 91 mp_int Px, Py, Qx, Qy; 92 mp_int Gx, Gy, order, irreducible, a, b; 93 #if 0 /* currently don't support non-named curves */ 94 unsigned int irr_arr[5]; 95 #endif 96 ECGroup *group = NULL; 97 SECStatus rv = SECFailure; 98 mp_err err = MP_OKAY; 99 int len; 100 101 #if EC_DEBUG 102 int i; 103 char mpstr[256]; 104 105 printf("ec_points_mul: params [len=%d]:", params->DEREncoding.len); 106 for (i = 0; i < params->DEREncoding.len; i++) 107 printf("%02x:", params->DEREncoding.data[i]); 108 printf("\n"); 109 110 if (k1 != NULL) { 111 mp_tohex(k1, mpstr); 112 printf("ec_points_mul: scalar k1: %s\n", mpstr); 113 mp_todecimal(k1, mpstr); 114 printf("ec_points_mul: scalar k1: %s (dec)\n", mpstr); 115 } 116 117 if (k2 != NULL) { 118 mp_tohex(k2, mpstr); 119 printf("ec_points_mul: scalar k2: %s\n", mpstr); 120 mp_todecimal(k2, mpstr); 121 printf("ec_points_mul: scalar k2: %s (dec)\n", mpstr); 122 } 123 124 if (pointP != NULL) { 125 printf("ec_points_mul: pointP [len=%d]:", pointP->len); 126 for (i = 0; i < pointP->len; i++) 127 printf("%02x:", pointP->data[i]); 128 printf("\n"); 129 } 130 #endif 131 132 /* NOTE: We only support uncompressed points for now */ 133 len = (params->fieldID.size + 7) >> 3; 134 if (pointP != NULL) { 135 if ((pointP->data[0] != EC_POINT_FORM_UNCOMPRESSED) || 136 (pointP->len != (2 * len + 1))) { 137 return SECFailure; 138 }; 139 } 140 141 MP_DIGITS(&Px) = 0; 142 MP_DIGITS(&Py) = 0; 143 MP_DIGITS(&Qx) = 0; 144 MP_DIGITS(&Qy) = 0; 145 MP_DIGITS(&Gx) = 0; 146 MP_DIGITS(&Gy) = 0; 147 MP_DIGITS(&order) = 0; 148 MP_DIGITS(&irreducible) = 0; 149 MP_DIGITS(&a) = 0; 150 MP_DIGITS(&b) = 0; 151 CHECK_MPI_OK( mp_init(&Px, kmflag) ); 152 CHECK_MPI_OK( mp_init(&Py, kmflag) ); 153 CHECK_MPI_OK( mp_init(&Qx, kmflag) ); 154 CHECK_MPI_OK( mp_init(&Qy, kmflag) ); 155 CHECK_MPI_OK( mp_init(&Gx, kmflag) ); 156 CHECK_MPI_OK( mp_init(&Gy, kmflag) ); 157 CHECK_MPI_OK( mp_init(&order, kmflag) ); 158 CHECK_MPI_OK( mp_init(&irreducible, kmflag) ); 159 CHECK_MPI_OK( mp_init(&a, kmflag) ); 160 CHECK_MPI_OK( mp_init(&b, kmflag) ); 161 162 if ((k2 != NULL) && (pointP != NULL)) { 163 /* Initialize Px and Py */ 164 CHECK_MPI_OK( mp_read_unsigned_octets(&Px, pointP->data + 1, (mp_size) len) ); 165 CHECK_MPI_OK( mp_read_unsigned_octets(&Py, pointP->data + 1 + len, (mp_size) len) ); 166 } 167 168 /* construct from named params, if possible */ 169 if (params->name != ECCurve_noName) { 170 group = ECGroup_fromName(params->name, kmflag); 171 } 172 173 #if 0 /* currently don't support non-named curves */ 174 if (group == NULL) { 175 /* Set up mp_ints containing the curve coefficients */ 176 CHECK_MPI_OK( mp_read_unsigned_octets(&Gx, params->base.data + 1, 177 (mp_size) len) ); 178 CHECK_MPI_OK( mp_read_unsigned_octets(&Gy, params->base.data + 1 + len, 179 (mp_size) len) ); 180 SECITEM_TO_MPINT( params->order, &order ); 181 SECITEM_TO_MPINT( params->curve.a, &a ); 182 SECITEM_TO_MPINT( params->curve.b, &b ); 183 if (params->fieldID.type == ec_field_GFp) { 184 SECITEM_TO_MPINT( params->fieldID.u.prime, &irreducible ); 185 group = ECGroup_consGFp(&irreducible, &a, &b, &Gx, &Gy, &order, params->cofactor); 186 } else { 187 SECITEM_TO_MPINT( params->fieldID.u.poly, &irreducible ); 188 irr_arr[0] = params->fieldID.size; 189 irr_arr[1] = params->fieldID.k1; 190 irr_arr[2] = params->fieldID.k2; 191 irr_arr[3] = params->fieldID.k3; 192 irr_arr[4] = 0; 193 group = ECGroup_consGF2m(&irreducible, irr_arr, &a, &b, &Gx, &Gy, &order, params->cofactor); 194 } 195 } 196 #endif 197 if (group == NULL) 198 goto cleanup; 199 200 if ((k2 != NULL) && (pointP != NULL)) { 201 CHECK_MPI_OK( ECPoints_mul(group, k1, k2, &Px, &Py, &Qx, &Qy) ); 202 } else { 203 CHECK_MPI_OK( ECPoints_mul(group, k1, NULL, NULL, NULL, &Qx, &Qy) ); 204 } 205 206 /* Construct the SECItem representation of point Q */ 207 pointQ->data[0] = EC_POINT_FORM_UNCOMPRESSED; 208 CHECK_MPI_OK( mp_to_fixlen_octets(&Qx, pointQ->data + 1, 209 (mp_size) len) ); 210 CHECK_MPI_OK( mp_to_fixlen_octets(&Qy, pointQ->data + 1 + len, 211 (mp_size) len) ); 212 213 rv = SECSuccess; 214 215 #if EC_DEBUG 216 printf("ec_points_mul: pointQ [len=%d]:", pointQ->len); 217 for (i = 0; i < pointQ->len; i++) 218 printf("%02x:", pointQ->data[i]); 219 printf("\n"); 220 #endif 221 222 cleanup: 223 ECGroup_free(group); 224 mp_clear(&Px); 225 mp_clear(&Py); 226 mp_clear(&Qx); 227 mp_clear(&Qy); 228 mp_clear(&Gx); 229 mp_clear(&Gy); 230 mp_clear(&order); 231 mp_clear(&irreducible); 232 mp_clear(&a); 233 mp_clear(&b); 234 if (err) { 235 MP_TO_SEC_ERROR(err); 236 rv = SECFailure; 237 } 238 239 return rv; 240 } 241 242 /* Generates a new EC key pair. The private key is a supplied 243 * value and the public key is the result of performing a scalar 244 * point multiplication of that value with the curve's base point. 245 */ 246 SECStatus 247 ec_NewKey(ECParams *ecParams, ECPrivateKey **privKey, 248 const unsigned char *privKeyBytes, int privKeyLen, int kmflag) 249 { 250 SECStatus rv = SECFailure; 251 PRArenaPool *arena; 252 ECPrivateKey *key; 253 mp_int k; 254 mp_err err = MP_OKAY; 255 int len; 256 257 #if EC_DEBUG 258 printf("ec_NewKey called\n"); 259 #endif 260 261 int printf(); 262 if (!ecParams || !privKey || !privKeyBytes || (privKeyLen < 0)) { 263 PORT_SetError(SEC_ERROR_INVALID_ARGS); 264 return SECFailure; 265 } 266 267 /* Initialize an arena for the EC key. */ 268 if (!(arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE))) 269 return SECFailure; 270 271 key = (ECPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(ECPrivateKey), 272 kmflag); 273 if (!key) { 274 PORT_FreeArena(arena, PR_TRUE); 275 return SECFailure; 276 } 277 278 /* Set the version number (SEC 1 section C.4 says it should be 1) */ 279 SECITEM_AllocItem(arena, &key->version, 1, kmflag); 280 key->version.data[0] = 1; 281 282 /* Copy all of the fields from the ECParams argument to the 283 * ECParams structure within the private key. 284 */ 285 key->ecParams.arena = arena; 286 key->ecParams.type = ecParams->type; 287 key->ecParams.fieldID.size = ecParams->fieldID.size; 288 key->ecParams.fieldID.type = ecParams->fieldID.type; 289 if (ecParams->fieldID.type == ec_field_GFp) { 290 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.fieldID.u.prime, 291 &ecParams->fieldID.u.prime, kmflag)); 292 } else { 293 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.fieldID.u.poly, 294 &ecParams->fieldID.u.poly, kmflag)); 295 } 296 key->ecParams.fieldID.k1 = ecParams->fieldID.k1; 297 key->ecParams.fieldID.k2 = ecParams->fieldID.k2; 298 key->ecParams.fieldID.k3 = ecParams->fieldID.k3; 299 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.curve.a, 300 &ecParams->curve.a, kmflag)); 301 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.curve.b, 302 &ecParams->curve.b, kmflag)); 303 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.curve.seed, 304 &ecParams->curve.seed, kmflag)); 305 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.base, 306 &ecParams->base, kmflag)); 307 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.order, 308 &ecParams->order, kmflag)); 309 key->ecParams.cofactor = ecParams->cofactor; 310 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.DEREncoding, 311 &ecParams->DEREncoding, kmflag)); 312 key->ecParams.name = ecParams->name; 313 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.curveOID, 314 &ecParams->curveOID, kmflag)); 315 316 len = (ecParams->fieldID.size + 7) >> 3; 317 SECITEM_AllocItem(arena, &key->publicValue, 2*len + 1, kmflag); 318 len = ecParams->order.len; 319 SECITEM_AllocItem(arena, &key->privateValue, len, kmflag); 320 321 /* Copy private key */ 322 if (privKeyLen >= len) { 323 memcpy(key->privateValue.data, privKeyBytes, len); 324 } else { 325 memset(key->privateValue.data, 0, (len - privKeyLen)); 326 memcpy(key->privateValue.data + (len - privKeyLen), privKeyBytes, privKeyLen); 327 } 328 329 /* Compute corresponding public key */ 330 MP_DIGITS(&k) = 0; 331 CHECK_MPI_OK( mp_init(&k, kmflag) ); 332 CHECK_MPI_OK( mp_read_unsigned_octets(&k, key->privateValue.data, 333 (mp_size) len) ); 334 335 rv = ec_points_mul(ecParams, &k, NULL, NULL, &(key->publicValue), kmflag); 336 if (rv != SECSuccess) goto cleanup; 337 *privKey = key; 338 339 cleanup: 340 mp_clear(&k); 341 if (rv) 342 PORT_FreeArena(arena, PR_TRUE); 343 344 #if EC_DEBUG 345 printf("ec_NewKey returning %s\n", 346 (rv == SECSuccess) ? "success" : "failure"); 347 #endif 348 349 return rv; 350 351 } 352 353 /* Generates a new EC key pair. The private key is a supplied 354 * random value (in seed) and the public key is the result of 355 * performing a scalar point multiplication of that value with 356 * the curve's base point. 357 */ 358 SECStatus 359 EC_NewKeyFromSeed(ECParams *ecParams, ECPrivateKey **privKey, 360 const unsigned char *seed, int seedlen, int kmflag) 361 { 362 SECStatus rv = SECFailure; 363 rv = ec_NewKey(ecParams, privKey, seed, seedlen, kmflag); 364 return rv; 365 } 366 367 /* Generate a random private key using the algorithm A.4.1 of ANSI X9.62, 368 * modified a la FIPS 186-2 Change Notice 1 to eliminate the bias in the 369 * random number generator. 370 * 371 * Parameters 372 * - order: a buffer that holds the curve's group order 373 * - len: the length in octets of the order buffer 374 * 375 * Return Value 376 * Returns a buffer of len octets that holds the private key. The caller 377 * is responsible for freeing the buffer with PORT_ZFree. 378 */ 379 static unsigned char * 380 ec_GenerateRandomPrivateKey(const unsigned char *order, int len, int kmflag) 381 { 382 SECStatus rv = SECSuccess; 383 mp_err err; 384 unsigned char *privKeyBytes = NULL; 385 mp_int privKeyVal, order_1, one; 386 387 MP_DIGITS(&privKeyVal) = 0; 388 MP_DIGITS(&order_1) = 0; 389 MP_DIGITS(&one) = 0; 390 CHECK_MPI_OK( mp_init(&privKeyVal, kmflag) ); 391 CHECK_MPI_OK( mp_init(&order_1, kmflag) ); 392 CHECK_MPI_OK( mp_init(&one, kmflag) ); 393 394 /* Generates 2*len random bytes using the global random bit generator 395 * (which implements Algorithm 1 of FIPS 186-2 Change Notice 1) then 396 * reduces modulo the group order. 397 */ 398 if ((privKeyBytes = PORT_Alloc(2*len, kmflag)) == NULL) goto cleanup; 399 CHECK_SEC_OK( RNG_GenerateGlobalRandomBytes(privKeyBytes, 2*len) ); 400 CHECK_MPI_OK( mp_read_unsigned_octets(&privKeyVal, privKeyBytes, 2*len) ); 401 CHECK_MPI_OK( mp_read_unsigned_octets(&order_1, order, len) ); 402 CHECK_MPI_OK( mp_set_int(&one, 1) ); 403 CHECK_MPI_OK( mp_sub(&order_1, &one, &order_1) ); 404 CHECK_MPI_OK( mp_mod(&privKeyVal, &order_1, &privKeyVal) ); 405 CHECK_MPI_OK( mp_add(&privKeyVal, &one, &privKeyVal) ); 406 CHECK_MPI_OK( mp_to_fixlen_octets(&privKeyVal, privKeyBytes, len) ); 407 memset(privKeyBytes+len, 0, len); 408 cleanup: 409 mp_clear(&privKeyVal); 410 mp_clear(&order_1); 411 mp_clear(&one); 412 if (err < MP_OKAY) { 413 MP_TO_SEC_ERROR(err); 414 rv = SECFailure; 415 } 416 if (rv != SECSuccess && privKeyBytes) { 417 #ifdef _KERNEL 418 kmem_free(privKeyBytes, 2*len); 419 #else 420 free(privKeyBytes); 421 #endif 422 privKeyBytes = NULL; 423 } 424 return privKeyBytes; 425 } 426 427 /* Generates a new EC key pair. The private key is a random value and 428 * the public key is the result of performing a scalar point multiplication 429 * of that value with the curve's base point. 430 */ 431 SECStatus 432 EC_NewKey(ECParams *ecParams, ECPrivateKey **privKey, int kmflag) 433 { 434 SECStatus rv = SECFailure; 435 int len; 436 unsigned char *privKeyBytes = NULL; 437 438 if (!ecParams) { 439 PORT_SetError(SEC_ERROR_INVALID_ARGS); 440 return SECFailure; 441 } 442 443 len = ecParams->order.len; 444 privKeyBytes = ec_GenerateRandomPrivateKey(ecParams->order.data, len, 445 kmflag); 446 if (privKeyBytes == NULL) goto cleanup; 447 /* generate public key */ 448 CHECK_SEC_OK( ec_NewKey(ecParams, privKey, privKeyBytes, len, kmflag) ); 449 450 cleanup: 451 if (privKeyBytes) { 452 PORT_ZFree(privKeyBytes, len * 2); 453 } 454 #if EC_DEBUG 455 printf("EC_NewKey returning %s\n", 456 (rv == SECSuccess) ? "success" : "failure"); 457 #endif 458 459 return rv; 460 } 461 462 /* Validates an EC public key as described in Section 5.2.2 of 463 * X9.62. The ECDH primitive when used without the cofactor does 464 * not address small subgroup attacks, which may occur when the 465 * public key is not valid. These attacks can be prevented by 466 * validating the public key before using ECDH. 467 */ 468 SECStatus 469 EC_ValidatePublicKey(ECParams *ecParams, SECItem *publicValue, int kmflag) 470 { 471 mp_int Px, Py; 472 ECGroup *group = NULL; 473 SECStatus rv = SECFailure; 474 mp_err err = MP_OKAY; 475 int len; 476 477 if (!ecParams || !publicValue) { 478 PORT_SetError(SEC_ERROR_INVALID_ARGS); 479 return SECFailure; 480 } 481 482 /* NOTE: We only support uncompressed points for now */ 483 len = (ecParams->fieldID.size + 7) >> 3; 484 if (publicValue->data[0] != EC_POINT_FORM_UNCOMPRESSED) { 485 PORT_SetError(SEC_ERROR_UNSUPPORTED_EC_POINT_FORM); 486 return SECFailure; 487 } else if (publicValue->len != (2 * len + 1)) { 488 PORT_SetError(SEC_ERROR_BAD_KEY); 489 return SECFailure; 490 } 491 492 MP_DIGITS(&Px) = 0; 493 MP_DIGITS(&Py) = 0; 494 CHECK_MPI_OK( mp_init(&Px, kmflag) ); 495 CHECK_MPI_OK( mp_init(&Py, kmflag) ); 496 497 /* Initialize Px and Py */ 498 CHECK_MPI_OK( mp_read_unsigned_octets(&Px, publicValue->data + 1, (mp_size) len) ); 499 CHECK_MPI_OK( mp_read_unsigned_octets(&Py, publicValue->data + 1 + len, (mp_size) len) ); 500 501 /* construct from named params */ 502 group = ECGroup_fromName(ecParams->name, kmflag); 503 if (group == NULL) { 504 /* 505 * ECGroup_fromName fails if ecParams->name is not a valid 506 * ECCurveName value, or if we run out of memory, or perhaps 507 * for other reasons. Unfortunately if ecParams->name is a 508 * valid ECCurveName value, we don't know what the right error 509 * code should be because ECGroup_fromName doesn't return an 510 * error code to the caller. Set err to MP_UNDEF because 511 * that's what ECGroup_fromName uses internally. 512 */ 513 if ((ecParams->name <= ECCurve_noName) || 514 (ecParams->name >= ECCurve_pastLastCurve)) { 515 err = MP_BADARG; 516 } else { 517 err = MP_UNDEF; 518 } 519 goto cleanup; 520 } 521 522 /* validate public point */ 523 if ((err = ECPoint_validate(group, &Px, &Py)) < MP_YES) { 524 if (err == MP_NO) { 525 PORT_SetError(SEC_ERROR_BAD_KEY); 526 rv = SECFailure; 527 err = MP_OKAY; /* don't change the error code */ 528 } 529 goto cleanup; 530 } 531 532 rv = SECSuccess; 533 534 cleanup: 535 ECGroup_free(group); 536 mp_clear(&Px); 537 mp_clear(&Py); 538 if (err) { 539 MP_TO_SEC_ERROR(err); 540 rv = SECFailure; 541 } 542 return rv; 543 } 544 545 /* 546 ** Performs an ECDH key derivation by computing the scalar point 547 ** multiplication of privateValue and publicValue (with or without the 548 ** cofactor) and returns the x-coordinate of the resulting elliptic 549 ** curve point in derived secret. If successful, derivedSecret->data 550 ** is set to the address of the newly allocated buffer containing the 551 ** derived secret, and derivedSecret->len is the size of the secret 552 ** produced. It is the caller's responsibility to free the allocated 553 ** buffer containing the derived secret. 554 */ 555 SECStatus 556 ECDH_Derive(SECItem *publicValue, 557 ECParams *ecParams, 558 SECItem *privateValue, 559 PRBool withCofactor, 560 SECItem *derivedSecret, 561 int kmflag) 562 { 563 SECStatus rv = SECFailure; 564 unsigned int len = 0; 565 SECItem pointQ = {siBuffer, NULL, 0}; 566 mp_int k; /* to hold the private value */ 567 mp_int cofactor; 568 mp_err err = MP_OKAY; 569 #if EC_DEBUG 570 int i; 571 #endif 572 573 if (!publicValue || !ecParams || !privateValue || 574 !derivedSecret) { 575 PORT_SetError(SEC_ERROR_INVALID_ARGS); 576 return SECFailure; 577 } 578 579 memset(derivedSecret, 0, sizeof *derivedSecret); 580 len = (ecParams->fieldID.size + 7) >> 3; 581 pointQ.len = 2*len + 1; 582 if ((pointQ.data = PORT_Alloc(2*len + 1, kmflag)) == NULL) goto cleanup; 583 584 MP_DIGITS(&k) = 0; 585 CHECK_MPI_OK( mp_init(&k, kmflag) ); 586 CHECK_MPI_OK( mp_read_unsigned_octets(&k, privateValue->data, 587 (mp_size) privateValue->len) ); 588 589 if (withCofactor && (ecParams->cofactor != 1)) { 590 /* multiply k with the cofactor */ 591 MP_DIGITS(&cofactor) = 0; 592 CHECK_MPI_OK( mp_init(&cofactor, kmflag) ); 593 mp_set(&cofactor, ecParams->cofactor); 594 CHECK_MPI_OK( mp_mul(&k, &cofactor, &k) ); 595 } 596 597 /* Multiply our private key and peer's public point */ 598 if ((ec_points_mul(ecParams, NULL, &k, publicValue, &pointQ, kmflag) != SECSuccess) || 599 ec_point_at_infinity(&pointQ)) 600 goto cleanup; 601 602 /* Allocate memory for the derived secret and copy 603 * the x co-ordinate of pointQ into it. 604 */ 605 SECITEM_AllocItem(NULL, derivedSecret, len, kmflag); 606 memcpy(derivedSecret->data, pointQ.data + 1, len); 607 608 rv = SECSuccess; 609 610 #if EC_DEBUG 611 printf("derived_secret:\n"); 612 for (i = 0; i < derivedSecret->len; i++) 613 printf("%02x:", derivedSecret->data[i]); 614 printf("\n"); 615 #endif 616 617 cleanup: 618 mp_clear(&k); 619 620 if (pointQ.data) { 621 PORT_ZFree(pointQ.data, 2*len + 1); 622 } 623 624 return rv; 625 } 626 627 /* Computes the ECDSA signature (a concatenation of two values r and s) 628 * on the digest using the given key and the random value kb (used in 629 * computing s). 630 */ 631 SECStatus 632 ECDSA_SignDigestWithSeed(ECPrivateKey *key, SECItem *signature, 633 const SECItem *digest, const unsigned char *kb, const int kblen, int kmflag) 634 { 635 SECStatus rv = SECFailure; 636 mp_int x1; 637 mp_int d, k; /* private key, random integer */ 638 mp_int r, s; /* tuple (r, s) is the signature */ 639 mp_int n; 640 mp_err err = MP_OKAY; 641 ECParams *ecParams = NULL; 642 SECItem kGpoint = { siBuffer, NULL, 0}; 643 int flen = 0; /* length in bytes of the field size */ 644 unsigned olen; /* length in bytes of the base point order */ 645 646 #if EC_DEBUG 647 char mpstr[256]; 648 #endif 649 650 /* Initialize MPI integers. */ 651 /* must happen before the first potential call to cleanup */ 652 MP_DIGITS(&x1) = 0; 653 MP_DIGITS(&d) = 0; 654 MP_DIGITS(&k) = 0; 655 MP_DIGITS(&r) = 0; 656 MP_DIGITS(&s) = 0; 657 MP_DIGITS(&n) = 0; 658 659 /* Check args */ 660 if (!key || !signature || !digest || !kb || (kblen < 0)) { 661 PORT_SetError(SEC_ERROR_INVALID_ARGS); 662 goto cleanup; 663 } 664 665 ecParams = &(key->ecParams); 666 flen = (ecParams->fieldID.size + 7) >> 3; 667 olen = ecParams->order.len; 668 if (signature->data == NULL) { 669 /* a call to get the signature length only */ 670 goto finish; 671 } 672 if (signature->len < 2*olen) { 673 PORT_SetError(SEC_ERROR_OUTPUT_LEN); 674 rv = SECBufferTooSmall; 675 goto cleanup; 676 } 677 678 679 CHECK_MPI_OK( mp_init(&x1, kmflag) ); 680 CHECK_MPI_OK( mp_init(&d, kmflag) ); 681 CHECK_MPI_OK( mp_init(&k, kmflag) ); 682 CHECK_MPI_OK( mp_init(&r, kmflag) ); 683 CHECK_MPI_OK( mp_init(&s, kmflag) ); 684 CHECK_MPI_OK( mp_init(&n, kmflag) ); 685 686 SECITEM_TO_MPINT( ecParams->order, &n ); 687 SECITEM_TO_MPINT( key->privateValue, &d ); 688 CHECK_MPI_OK( mp_read_unsigned_octets(&k, kb, kblen) ); 689 /* Make sure k is in the interval [1, n-1] */ 690 if ((mp_cmp_z(&k) <= 0) || (mp_cmp(&k, &n) >= 0)) { 691 #if EC_DEBUG 692 printf("k is outside [1, n-1]\n"); 693 mp_tohex(&k, mpstr); 694 printf("k : %s \n", mpstr); 695 mp_tohex(&n, mpstr); 696 printf("n : %s \n", mpstr); 697 #endif 698 PORT_SetError(SEC_ERROR_NEED_RANDOM); 699 goto cleanup; 700 } 701 702 /* 703 ** ANSI X9.62, Section 5.3.2, Step 2 704 ** 705 ** Compute kG 706 */ 707 kGpoint.len = 2*flen + 1; 708 kGpoint.data = PORT_Alloc(2*flen + 1, kmflag); 709 if ((kGpoint.data == NULL) || 710 (ec_points_mul(ecParams, &k, NULL, NULL, &kGpoint, kmflag) 711 != SECSuccess)) 712 goto cleanup; 713 714 /* 715 ** ANSI X9.62, Section 5.3.3, Step 1 716 ** 717 ** Extract the x co-ordinate of kG into x1 718 */ 719 CHECK_MPI_OK( mp_read_unsigned_octets(&x1, kGpoint.data + 1, 720 (mp_size) flen) ); 721 722 /* 723 ** ANSI X9.62, Section 5.3.3, Step 2 724 ** 725 ** r = x1 mod n NOTE: n is the order of the curve 726 */ 727 CHECK_MPI_OK( mp_mod(&x1, &n, &r) ); 728 729 /* 730 ** ANSI X9.62, Section 5.3.3, Step 3 731 ** 732 ** verify r != 0 733 */ 734 if (mp_cmp_z(&r) == 0) { 735 PORT_SetError(SEC_ERROR_NEED_RANDOM); 736 goto cleanup; 737 } 738 739 /* 740 ** ANSI X9.62, Section 5.3.3, Step 4 741 ** 742 ** s = (k**-1 * (HASH(M) + d*r)) mod n 743 */ 744 SECITEM_TO_MPINT(*digest, &s); /* s = HASH(M) */ 745 746 /* In the definition of EC signing, digests are truncated 747 * to the length of n in bits. 748 * (see SEC 1 "Elliptic Curve Digit Signature Algorithm" section 4.1.*/ 749 if (digest->len*8 > ecParams->fieldID.size) { 750 mpl_rsh(&s,&s,digest->len*8 - ecParams->fieldID.size); 751 } 752 753 #if EC_DEBUG 754 mp_todecimal(&n, mpstr); 755 printf("n : %s (dec)\n", mpstr); 756 mp_todecimal(&d, mpstr); 757 printf("d : %s (dec)\n", mpstr); 758 mp_tohex(&x1, mpstr); 759 printf("x1: %s\n", mpstr); 760 mp_todecimal(&s, mpstr); 761 printf("digest: %s (decimal)\n", mpstr); 762 mp_todecimal(&r, mpstr); 763 printf("r : %s (dec)\n", mpstr); 764 mp_tohex(&r, mpstr); 765 printf("r : %s\n", mpstr); 766 #endif 767 768 CHECK_MPI_OK( mp_invmod(&k, &n, &k) ); /* k = k**-1 mod n */ 769 CHECK_MPI_OK( mp_mulmod(&d, &r, &n, &d) ); /* d = d * r mod n */ 770 CHECK_MPI_OK( mp_addmod(&s, &d, &n, &s) ); /* s = s + d mod n */ 771 CHECK_MPI_OK( mp_mulmod(&s, &k, &n, &s) ); /* s = s * k mod n */ 772 773 #if EC_DEBUG 774 mp_todecimal(&s, mpstr); 775 printf("s : %s (dec)\n", mpstr); 776 mp_tohex(&s, mpstr); 777 printf("s : %s\n", mpstr); 778 #endif 779 780 /* 781 ** ANSI X9.62, Section 5.3.3, Step 5 782 ** 783 ** verify s != 0 784 */ 785 if (mp_cmp_z(&s) == 0) { 786 PORT_SetError(SEC_ERROR_NEED_RANDOM); 787 goto cleanup; 788 } 789 790 /* 791 ** 792 ** Signature is tuple (r, s) 793 */ 794 CHECK_MPI_OK( mp_to_fixlen_octets(&r, signature->data, olen) ); 795 CHECK_MPI_OK( mp_to_fixlen_octets(&s, signature->data + olen, olen) ); 796 finish: 797 signature->len = 2*olen; 798 799 rv = SECSuccess; 800 err = MP_OKAY; 801 cleanup: 802 mp_clear(&x1); 803 mp_clear(&d); 804 mp_clear(&k); 805 mp_clear(&r); 806 mp_clear(&s); 807 mp_clear(&n); 808 809 if (kGpoint.data) { 810 PORT_ZFree(kGpoint.data, 2*flen + 1); 811 } 812 813 if (err) { 814 MP_TO_SEC_ERROR(err); 815 rv = SECFailure; 816 } 817 818 #if EC_DEBUG 819 printf("ECDSA signing with seed %s\n", 820 (rv == SECSuccess) ? "succeeded" : "failed"); 821 #endif 822 823 return rv; 824 } 825 826 /* 827 ** Computes the ECDSA signature on the digest using the given key 828 ** and a random seed. 829 */ 830 SECStatus 831 ECDSA_SignDigest(ECPrivateKey *key, SECItem *signature, const SECItem *digest, 832 int kmflag) 833 { 834 SECStatus rv = SECFailure; 835 int len; 836 unsigned char *kBytes= NULL; 837 838 if (!key) { 839 PORT_SetError(SEC_ERROR_INVALID_ARGS); 840 return SECFailure; 841 } 842 843 /* Generate random value k */ 844 len = key->ecParams.order.len; 845 kBytes = ec_GenerateRandomPrivateKey(key->ecParams.order.data, len, 846 kmflag); 847 if (kBytes == NULL) goto cleanup; 848 849 /* Generate ECDSA signature with the specified k value */ 850 rv = ECDSA_SignDigestWithSeed(key, signature, digest, kBytes, len, kmflag); 851 852 cleanup: 853 if (kBytes) { 854 PORT_ZFree(kBytes, len * 2); 855 } 856 857 #if EC_DEBUG 858 printf("ECDSA signing %s\n", 859 (rv == SECSuccess) ? "succeeded" : "failed"); 860 #endif 861 862 return rv; 863 } 864 865 /* 866 ** Checks the signature on the given digest using the key provided. 867 */ 868 SECStatus 869 ECDSA_VerifyDigest(ECPublicKey *key, const SECItem *signature, 870 const SECItem *digest, int kmflag) 871 { 872 SECStatus rv = SECFailure; 873 mp_int r_, s_; /* tuple (r', s') is received signature) */ 874 mp_int c, u1, u2, v; /* intermediate values used in verification */ 875 mp_int x1; 876 mp_int n; 877 mp_err err = MP_OKAY; 878 ECParams *ecParams = NULL; 879 SECItem pointC = { siBuffer, NULL, 0 }; 880 int slen; /* length in bytes of a half signature (r or s) */ 881 int flen; /* length in bytes of the field size */ 882 unsigned olen; /* length in bytes of the base point order */ 883 884 #if EC_DEBUG 885 char mpstr[256]; 886 printf("ECDSA verification called\n"); 887 #endif 888 889 /* Initialize MPI integers. */ 890 /* must happen before the first potential call to cleanup */ 891 MP_DIGITS(&r_) = 0; 892 MP_DIGITS(&s_) = 0; 893 MP_DIGITS(&c) = 0; 894 MP_DIGITS(&u1) = 0; 895 MP_DIGITS(&u2) = 0; 896 MP_DIGITS(&x1) = 0; 897 MP_DIGITS(&v) = 0; 898 MP_DIGITS(&n) = 0; 899 900 /* Check args */ 901 if (!key || !signature || !digest) { 902 PORT_SetError(SEC_ERROR_INVALID_ARGS); 903 goto cleanup; 904 } 905 906 ecParams = &(key->ecParams); 907 flen = (ecParams->fieldID.size + 7) >> 3; 908 olen = ecParams->order.len; 909 if (signature->len == 0 || signature->len%2 != 0 || 910 signature->len > 2*olen) { 911 PORT_SetError(SEC_ERROR_INPUT_LEN); 912 goto cleanup; 913 } 914 slen = signature->len/2; 915 916 SECITEM_AllocItem(NULL, &pointC, 2*flen + 1, kmflag); 917 if (pointC.data == NULL) 918 goto cleanup; 919 920 CHECK_MPI_OK( mp_init(&r_, kmflag) ); 921 CHECK_MPI_OK( mp_init(&s_, kmflag) ); 922 CHECK_MPI_OK( mp_init(&c, kmflag) ); 923 CHECK_MPI_OK( mp_init(&u1, kmflag) ); 924 CHECK_MPI_OK( mp_init(&u2, kmflag) ); 925 CHECK_MPI_OK( mp_init(&x1, kmflag) ); 926 CHECK_MPI_OK( mp_init(&v, kmflag) ); 927 CHECK_MPI_OK( mp_init(&n, kmflag) ); 928 929 /* 930 ** Convert received signature (r', s') into MPI integers. 931 */ 932 CHECK_MPI_OK( mp_read_unsigned_octets(&r_, signature->data, slen) ); 933 CHECK_MPI_OK( mp_read_unsigned_octets(&s_, signature->data + slen, slen) ); 934 935 /* 936 ** ANSI X9.62, Section 5.4.2, Steps 1 and 2 937 ** 938 ** Verify that 0 < r' < n and 0 < s' < n 939 */ 940 SECITEM_TO_MPINT(ecParams->order, &n); 941 if (mp_cmp_z(&r_) <= 0 || mp_cmp_z(&s_) <= 0 || 942 mp_cmp(&r_, &n) >= 0 || mp_cmp(&s_, &n) >= 0) { 943 PORT_SetError(SEC_ERROR_BAD_SIGNATURE); 944 goto cleanup; /* will return rv == SECFailure */ 945 } 946 947 /* 948 ** ANSI X9.62, Section 5.4.2, Step 3 949 ** 950 ** c = (s')**-1 mod n 951 */ 952 CHECK_MPI_OK( mp_invmod(&s_, &n, &c) ); /* c = (s')**-1 mod n */ 953 954 /* 955 ** ANSI X9.62, Section 5.4.2, Step 4 956 ** 957 ** u1 = ((HASH(M')) * c) mod n 958 */ 959 SECITEM_TO_MPINT(*digest, &u1); /* u1 = HASH(M) */ 960 961 /* In the definition of EC signing, digests are truncated 962 * to the length of n in bits. 963 * (see SEC 1 "Elliptic Curve Digit Signature Algorithm" section 4.1.*/ 964 if (digest->len*8 > ecParams->fieldID.size) { /* u1 = HASH(M') */ 965 mpl_rsh(&u1,&u1,digest->len*8- ecParams->fieldID.size); 966 } 967 968 #if EC_DEBUG 969 mp_todecimal(&r_, mpstr); 970 printf("r_: %s (dec)\n", mpstr); 971 mp_todecimal(&s_, mpstr); 972 printf("s_: %s (dec)\n", mpstr); 973 mp_todecimal(&c, mpstr); 974 printf("c : %s (dec)\n", mpstr); 975 mp_todecimal(&u1, mpstr); 976 printf("digest: %s (dec)\n", mpstr); 977 #endif 978 979 CHECK_MPI_OK( mp_mulmod(&u1, &c, &n, &u1) ); /* u1 = u1 * c mod n */ 980 981 /* 982 ** ANSI X9.62, Section 5.4.2, Step 4 983 ** 984 ** u2 = ((r') * c) mod n 985 */ 986 CHECK_MPI_OK( mp_mulmod(&r_, &c, &n, &u2) ); 987 988 /* 989 ** ANSI X9.62, Section 5.4.3, Step 1 990 ** 991 ** Compute u1*G + u2*Q 992 ** Here, A = u1.G B = u2.Q and C = A + B 993 ** If the result, C, is the point at infinity, reject the signature 994 */ 995 if (ec_points_mul(ecParams, &u1, &u2, &key->publicValue, &pointC, kmflag) 996 != SECSuccess) { 997 rv = SECFailure; 998 goto cleanup; 999 } 1000 if (ec_point_at_infinity(&pointC)) { 1001 PORT_SetError(SEC_ERROR_BAD_SIGNATURE); 1002 rv = SECFailure; 1003 goto cleanup; 1004 } 1005 1006 CHECK_MPI_OK( mp_read_unsigned_octets(&x1, pointC.data + 1, flen) ); 1007 1008 /* 1009 ** ANSI X9.62, Section 5.4.4, Step 2 1010 ** 1011 ** v = x1 mod n 1012 */ 1013 CHECK_MPI_OK( mp_mod(&x1, &n, &v) ); 1014 1015 #if EC_DEBUG 1016 mp_todecimal(&r_, mpstr); 1017 printf("r_: %s (dec)\n", mpstr); 1018 mp_todecimal(&v, mpstr); 1019 printf("v : %s (dec)\n", mpstr); 1020 #endif 1021 1022 /* 1023 ** ANSI X9.62, Section 5.4.4, Step 3 1024 ** 1025 ** Verification: v == r' 1026 */ 1027 if (mp_cmp(&v, &r_)) { 1028 PORT_SetError(SEC_ERROR_BAD_SIGNATURE); 1029 rv = SECFailure; /* Signature failed to verify. */ 1030 } else { 1031 rv = SECSuccess; /* Signature verified. */ 1032 } 1033 1034 #if EC_DEBUG 1035 mp_todecimal(&u1, mpstr); 1036 printf("u1: %s (dec)\n", mpstr); 1037 mp_todecimal(&u2, mpstr); 1038 printf("u2: %s (dec)\n", mpstr); 1039 mp_tohex(&x1, mpstr); 1040 printf("x1: %s\n", mpstr); 1041 mp_todecimal(&v, mpstr); 1042 printf("v : %s (dec)\n", mpstr); 1043 #endif 1044 1045 cleanup: 1046 mp_clear(&r_); 1047 mp_clear(&s_); 1048 mp_clear(&c); 1049 mp_clear(&u1); 1050 mp_clear(&u2); 1051 mp_clear(&x1); 1052 mp_clear(&v); 1053 mp_clear(&n); 1054 1055 if (pointC.data) SECITEM_FreeItem(&pointC, PR_FALSE); 1056 if (err) { 1057 MP_TO_SEC_ERROR(err); 1058 rv = SECFailure; 1059 } 1060 1061 #if EC_DEBUG 1062 printf("ECDSA verification %s\n", 1063 (rv == SECSuccess) ? "succeeded" : "failed"); 1064 #endif 1065 1066 return rv; 1067 } 1068 1069