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