1/* 2 * Copyright (c) 2007, 2017, 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: May 2017 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 */ 72PRBool 73ec_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 */ 88SECStatus 89ec_points_mul(const ECParams *params, const mp_int *k1, const mp_int *k2, 90 const SECItem *pointP, SECItem *pointQ, int kmflag, int timing) 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, timing) ); 203 } else { 204 CHECK_MPI_OK( ECPoints_mul(group, k1, NULL, NULL, NULL, &Qx, &Qy, timing) ); 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 223cleanup: 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 */ 247SECStatus 248ec_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*)NULL; 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 /* key generation does not support timing mitigation */ 337 rv = ec_points_mul(ecParams, &k, NULL, NULL, &(key->publicValue), kmflag, /*timing*/ 0); 338 if (rv != SECSuccess) goto cleanup; 339 *privKey = key; 340 341cleanup: 342 mp_clear(&k); 343 if (rv) { 344 PORT_FreeArena(arena, PR_TRUE); 345 } 346 347#if EC_DEBUG 348 printf("ec_NewKey returning %s\n", 349 (rv == SECSuccess) ? "success" : "failure"); 350#endif 351 352 return rv; 353 354} 355 356/* Generates a new EC key pair. The private key is a supplied 357 * random value (in seed) and the public key is the result of 358 * performing a scalar point multiplication of that value with 359 * the curve's base point. 360 */ 361SECStatus 362EC_NewKeyFromSeed(ECParams *ecParams, ECPrivateKey **privKey, 363 const unsigned char *seed, int seedlen, int kmflag) 364{ 365 SECStatus rv = SECFailure; 366 rv = ec_NewKey(ecParams, privKey, seed, seedlen, kmflag); 367 return rv; 368} 369 370/* Generate a random private key using the algorithm A.4.1 of ANSI X9.62, 371 * modified a la FIPS 186-2 Change Notice 1 to eliminate the bias in the 372 * random number generator. 373 * 374 * Parameters 375 * - order: a buffer that holds the curve's group order 376 * - len: the length in octets of the order buffer 377 * - random: a buffer of 2 * len random bytes 378 * - randomlen: the length in octets of the random buffer 379 * 380 * Return Value 381 * Returns a buffer of len octets that holds the private key. The caller 382 * is responsible for freeing the buffer with PORT_ZFree. 383 */ 384static unsigned char * 385ec_GenerateRandomPrivateKey(const unsigned char *order, int len, 386 const unsigned char *random, int randomlen, int kmflag) 387{ 388 SECStatus rv = SECSuccess; 389 mp_err err; 390 unsigned char *privKeyBytes = NULL; 391 mp_int privKeyVal, order_1, one; 392 393 MP_DIGITS(&privKeyVal) = 0; 394 MP_DIGITS(&order_1) = 0; 395 MP_DIGITS(&one) = 0; 396 CHECK_MPI_OK( mp_init(&privKeyVal, kmflag) ); 397 CHECK_MPI_OK( mp_init(&order_1, kmflag) ); 398 CHECK_MPI_OK( mp_init(&one, kmflag) ); 399 400 /* 401 * Reduces the 2*len buffer of random bytes modulo the group order. 402 */ 403 if ((privKeyBytes = PORT_Alloc(2*len, kmflag)) == NULL) goto cleanup; 404 if (randomlen != 2 * len) { 405 randomlen = 2 * len; 406 } 407 /* No need to generate - random bytes are now supplied */ 408 /* CHECK_SEC_OK( RNG_GenerateGlobalRandomBytes(privKeyBytes, 2*len) );*/ 409 memcpy(privKeyBytes, random, randomlen); 410 411 CHECK_MPI_OK( mp_read_unsigned_octets(&privKeyVal, privKeyBytes, 2*len) ); 412 CHECK_MPI_OK( mp_read_unsigned_octets(&order_1, order, len) ); 413 CHECK_MPI_OK( mp_set_int(&one, 1) ); 414 CHECK_MPI_OK( mp_sub(&order_1, &one, &order_1) ); 415 CHECK_MPI_OK( mp_mod(&privKeyVal, &order_1, &privKeyVal) ); 416 CHECK_MPI_OK( mp_add(&privKeyVal, &one, &privKeyVal) ); 417 CHECK_MPI_OK( mp_to_fixlen_octets(&privKeyVal, privKeyBytes, len) ); 418 memset(privKeyBytes+len, 0, len); 419cleanup: 420 mp_clear(&privKeyVal); 421 mp_clear(&order_1); 422 mp_clear(&one); 423 if (err < MP_OKAY) { 424 MP_TO_SEC_ERROR(err); 425 rv = SECFailure; 426 } 427 if (rv != SECSuccess && privKeyBytes) { 428#ifdef _KERNEL 429 kmem_free(privKeyBytes, 2*len); 430#else 431 free(privKeyBytes); 432#endif 433 privKeyBytes = NULL; 434 } 435 return privKeyBytes; 436} 437 438/* Generates a new EC key pair. The private key is a random value and 439 * the public key is the result of performing a scalar point multiplication 440 * of that value with the curve's base point. 441 */ 442SECStatus 443EC_NewKey(ECParams *ecParams, ECPrivateKey **privKey, 444 const unsigned char* random, int randomlen, int kmflag) 445{ 446 SECStatus rv = SECFailure; 447 int len; 448 unsigned char *privKeyBytes = NULL; 449 450 if (!ecParams) { 451 PORT_SetError(SEC_ERROR_INVALID_ARGS); 452 return SECFailure; 453 } 454 455 len = ecParams->order.len; 456 privKeyBytes = ec_GenerateRandomPrivateKey(ecParams->order.data, len, 457 random, randomlen, kmflag); 458 if (privKeyBytes == NULL) goto cleanup; 459 /* generate public key */ 460 CHECK_SEC_OK( ec_NewKey(ecParams, privKey, privKeyBytes, len, kmflag) ); 461 462cleanup: 463 if (privKeyBytes) { 464 PORT_ZFree(privKeyBytes, len * 2); 465 } 466#if EC_DEBUG 467 printf("EC_NewKey returning %s\n", 468 (rv == SECSuccess) ? "success" : "failure"); 469#endif 470 471 return rv; 472} 473 474/* Validates an EC public key as described in Section 5.2.2 of 475 * X9.62. The ECDH primitive when used without the cofactor does 476 * not address small subgroup attacks, which may occur when the 477 * public key is not valid. These attacks can be prevented by 478 * validating the public key before using ECDH. 479 */ 480SECStatus 481EC_ValidatePublicKey(ECParams *ecParams, SECItem *publicValue, int kmflag) 482{ 483 mp_int Px, Py; 484 ECGroup *group = NULL; 485 SECStatus rv = SECFailure; 486 mp_err err = MP_OKAY; 487 unsigned int len; 488 489 if (!ecParams || !publicValue) { 490 PORT_SetError(SEC_ERROR_INVALID_ARGS); 491 return SECFailure; 492 } 493 494 /* NOTE: We only support uncompressed points for now */ 495 len = (ecParams->fieldID.size + 7) >> 3; 496 if (publicValue->data[0] != EC_POINT_FORM_UNCOMPRESSED) { 497 PORT_SetError(SEC_ERROR_UNSUPPORTED_EC_POINT_FORM); 498 return SECFailure; 499 } else if (publicValue->len != (2 * len + 1)) { 500 PORT_SetError(SEC_ERROR_BAD_KEY); 501 return SECFailure; 502 } 503 504 MP_DIGITS(&Px) = 0; 505 MP_DIGITS(&Py) = 0; 506 CHECK_MPI_OK( mp_init(&Px, kmflag) ); 507 CHECK_MPI_OK( mp_init(&Py, kmflag) ); 508 509 /* Initialize Px and Py */ 510 CHECK_MPI_OK( mp_read_unsigned_octets(&Px, publicValue->data + 1, (mp_size) len) ); 511 CHECK_MPI_OK( mp_read_unsigned_octets(&Py, publicValue->data + 1 + len, (mp_size) len) ); 512 513 /* construct from named params */ 514 group = ECGroup_fromName(ecParams->name, kmflag); 515 if (group == NULL) { 516 /* 517 * ECGroup_fromName fails if ecParams->name is not a valid 518 * ECCurveName value, or if we run out of memory, or perhaps 519 * for other reasons. Unfortunately if ecParams->name is a 520 * valid ECCurveName value, we don't know what the right error 521 * code should be because ECGroup_fromName doesn't return an 522 * error code to the caller. Set err to MP_UNDEF because 523 * that's what ECGroup_fromName uses internally. 524 */ 525 if ((ecParams->name <= ECCurve_noName) || 526 (ecParams->name >= ECCurve_pastLastCurve)) { 527 err = MP_BADARG; 528 } else { 529 err = MP_UNDEF; 530 } 531 goto cleanup; 532 } 533 534 /* validate public point */ 535 if ((err = ECPoint_validate(group, &Px, &Py)) < MP_YES) { 536 if (err == MP_NO) { 537 PORT_SetError(SEC_ERROR_BAD_KEY); 538 rv = SECFailure; 539 err = MP_OKAY; /* don't change the error code */ 540 } 541 goto cleanup; 542 } 543 544 rv = SECSuccess; 545 546cleanup: 547 ECGroup_free(group); 548 mp_clear(&Px); 549 mp_clear(&Py); 550 if (err) { 551 MP_TO_SEC_ERROR(err); 552 rv = SECFailure; 553 } 554 return rv; 555} 556 557/* 558** Performs an ECDH key derivation by computing the scalar point 559** multiplication of privateValue and publicValue (with or without the 560** cofactor) and returns the x-coordinate of the resulting elliptic 561** curve point in derived secret. If successful, derivedSecret->data 562** is set to the address of the newly allocated buffer containing the 563** derived secret, and derivedSecret->len is the size of the secret 564** produced. It is the caller's responsibility to free the allocated 565** buffer containing the derived secret. 566*/ 567SECStatus 568ECDH_Derive(SECItem *publicValue, 569 ECParams *ecParams, 570 SECItem *privateValue, 571 PRBool withCofactor, 572 SECItem *derivedSecret, 573 int kmflag) 574{ 575 SECStatus rv = SECFailure; 576 unsigned int len = 0; 577 SECItem pointQ = {siBuffer, NULL, 0}; 578 mp_int k; /* to hold the private value */ 579 mp_int cofactor; 580 mp_err err = MP_OKAY; 581#if EC_DEBUG 582 int i; 583#endif 584 585 if (!publicValue || !ecParams || !privateValue || 586 !derivedSecret) { 587 PORT_SetError(SEC_ERROR_INVALID_ARGS); 588 return SECFailure; 589 } 590 591 if (EC_ValidatePublicKey(ecParams, publicValue, kmflag) != SECSuccess) { 592 return SECFailure; 593 } 594 595 memset(derivedSecret, 0, sizeof *derivedSecret); 596 len = (ecParams->fieldID.size + 7) >> 3; 597 pointQ.len = 2*len + 1; 598 if ((pointQ.data = PORT_Alloc(2*len + 1, kmflag)) == NULL) goto cleanup; 599 600 MP_DIGITS(&k) = 0; 601 CHECK_MPI_OK( mp_init(&k, kmflag) ); 602 CHECK_MPI_OK( mp_read_unsigned_octets(&k, privateValue->data, 603 (mp_size) privateValue->len) ); 604 605 if (withCofactor && (ecParams->cofactor != 1)) { 606 /* multiply k with the cofactor */ 607 MP_DIGITS(&cofactor) = 0; 608 CHECK_MPI_OK( mp_init(&cofactor, kmflag) ); 609 mp_set(&cofactor, ecParams->cofactor); 610 CHECK_MPI_OK( mp_mul(&k, &cofactor, &k) ); 611 } 612 613 /* Multiply our private key and peer's public point */ 614 /* ECDH doesn't support timing mitigation */ 615 if ((ec_points_mul(ecParams, NULL, &k, publicValue, &pointQ, kmflag, /*timing*/ 0) != SECSuccess) || 616 ec_point_at_infinity(&pointQ)) 617 goto cleanup; 618 619 /* Allocate memory for the derived secret and copy 620 * the x co-ordinate of pointQ into it. 621 */ 622 SECITEM_AllocItem(NULL, derivedSecret, len, kmflag); 623 memcpy(derivedSecret->data, pointQ.data + 1, len); 624 625 rv = SECSuccess; 626 627#if EC_DEBUG 628 printf("derived_secret:\n"); 629 for (i = 0; i < derivedSecret->len; i++) 630 printf("%02x:", derivedSecret->data[i]); 631 printf("\n"); 632#endif 633 634cleanup: 635 mp_clear(&k); 636 637 if (pointQ.data) { 638 PORT_ZFree(pointQ.data, 2*len + 1); 639 } 640 641 return rv; 642} 643 644/* Computes the ECDSA signature (a concatenation of two values r and s) 645 * on the digest using the given key and the random value kb (used in 646 * computing s). 647 */ 648SECStatus 649ECDSA_SignDigestWithSeed(ECPrivateKey *key, SECItem *signature, 650 const SECItem *digest, const unsigned char *kb, const int kblen, int kmflag, 651 int timing) 652{ 653 SECStatus rv = SECFailure; 654 mp_int x1; 655 mp_int d, k; /* private key, random integer */ 656 mp_int r, s; /* tuple (r, s) is the signature */ 657 mp_int n; 658 mp_err err = MP_OKAY; 659 ECParams *ecParams = NULL; 660 SECItem kGpoint = { siBuffer, NULL, 0}; 661 int flen = 0; /* length in bytes of the field size */ 662 unsigned olen; /* length in bytes of the base point order */ 663 664#if EC_DEBUG 665 char mpstr[256]; 666#endif 667 668 /* Initialize MPI integers. */ 669 /* must happen before the first potential call to cleanup */ 670 MP_DIGITS(&x1) = 0; 671 MP_DIGITS(&d) = 0; 672 MP_DIGITS(&k) = 0; 673 MP_DIGITS(&r) = 0; 674 MP_DIGITS(&s) = 0; 675 MP_DIGITS(&n) = 0; 676 677 /* Check args */ 678 if (!key || !signature || !digest || !kb || (kblen < 0)) { 679 PORT_SetError(SEC_ERROR_INVALID_ARGS); 680 goto cleanup; 681 } 682 683 ecParams = &(key->ecParams); 684 flen = (ecParams->fieldID.size + 7) >> 3; 685 olen = ecParams->order.len; 686 if (signature->data == NULL) { 687 /* a call to get the signature length only */ 688 goto finish; 689 } 690 if (signature->len < 2*olen) { 691 PORT_SetError(SEC_ERROR_OUTPUT_LEN); 692 rv = SECBufferTooSmall; 693 goto cleanup; 694 } 695 696 697 CHECK_MPI_OK( mp_init(&x1, kmflag) ); 698 CHECK_MPI_OK( mp_init(&d, kmflag) ); 699 CHECK_MPI_OK( mp_init(&k, kmflag) ); 700 CHECK_MPI_OK( mp_init(&r, kmflag) ); 701 CHECK_MPI_OK( mp_init(&s, kmflag) ); 702 CHECK_MPI_OK( mp_init(&n, kmflag) ); 703 704 SECITEM_TO_MPINT( ecParams->order, &n ); 705 SECITEM_TO_MPINT( key->privateValue, &d ); 706 CHECK_MPI_OK( mp_read_unsigned_octets(&k, kb, kblen) ); 707 /* Make sure k is in the interval [1, n-1] */ 708 if ((mp_cmp_z(&k) <= 0) || (mp_cmp(&k, &n) >= 0)) { 709#if EC_DEBUG 710 printf("k is outside [1, n-1]\n"); 711 mp_tohex(&k, mpstr); 712 printf("k : %s \n", mpstr); 713 mp_tohex(&n, mpstr); 714 printf("n : %s \n", mpstr); 715#endif 716 PORT_SetError(SEC_ERROR_NEED_RANDOM); 717 goto cleanup; 718 } 719 720 /* 721 ** ANSI X9.62, Section 5.3.2, Step 2 722 ** 723 ** Compute kG 724 */ 725 kGpoint.len = 2*flen + 1; 726 kGpoint.data = PORT_Alloc(2*flen + 1, kmflag); 727 if ((kGpoint.data == NULL) || 728 (ec_points_mul(ecParams, &k, NULL, NULL, &kGpoint, kmflag, timing) 729 != SECSuccess)) 730 goto cleanup; 731 732 /* 733 ** ANSI X9.62, Section 5.3.3, Step 1 734 ** 735 ** Extract the x co-ordinate of kG into x1 736 */ 737 CHECK_MPI_OK( mp_read_unsigned_octets(&x1, kGpoint.data + 1, 738 (mp_size) flen) ); 739 740 /* 741 ** ANSI X9.62, Section 5.3.3, Step 2 742 ** 743 ** r = x1 mod n NOTE: n is the order of the curve 744 */ 745 CHECK_MPI_OK( mp_mod(&x1, &n, &r) ); 746 747 /* 748 ** ANSI X9.62, Section 5.3.3, Step 3 749 ** 750 ** verify r != 0 751 */ 752 if (mp_cmp_z(&r) == 0) { 753 PORT_SetError(SEC_ERROR_NEED_RANDOM); 754 goto cleanup; 755 } 756 757 /* 758 ** ANSI X9.62, Section 5.3.3, Step 4 759 ** 760 ** s = (k**-1 * (HASH(M) + d*r)) mod n 761 */ 762 SECITEM_TO_MPINT(*digest, &s); /* s = HASH(M) */ 763 764 /* In the definition of EC signing, digests are truncated 765 * to the length of n in bits. 766 * (see SEC 1 "Elliptic Curve Digit Signature Algorithm" section 4.1.*/ 767 if (digest->len*8 > (unsigned int)ecParams->fieldID.size) { 768 mpl_rsh(&s,&s,digest->len*8 - ecParams->fieldID.size); 769 } 770 771#if EC_DEBUG 772 mp_todecimal(&n, mpstr); 773 printf("n : %s (dec)\n", mpstr); 774 mp_todecimal(&d, mpstr); 775 printf("d : %s (dec)\n", mpstr); 776 mp_tohex(&x1, mpstr); 777 printf("x1: %s\n", mpstr); 778 mp_todecimal(&s, mpstr); 779 printf("digest: %s (decimal)\n", mpstr); 780 mp_todecimal(&r, mpstr); 781 printf("r : %s (dec)\n", mpstr); 782 mp_tohex(&r, mpstr); 783 printf("r : %s\n", mpstr); 784#endif 785 786 CHECK_MPI_OK( mp_invmod(&k, &n, &k) ); /* k = k**-1 mod n */ 787 CHECK_MPI_OK( mp_mulmod(&d, &r, &n, &d) ); /* d = d * r mod n */ 788 CHECK_MPI_OK( mp_addmod(&s, &d, &n, &s) ); /* s = s + d mod n */ 789 CHECK_MPI_OK( mp_mulmod(&s, &k, &n, &s) ); /* s = s * k mod n */ 790 791#if EC_DEBUG 792 mp_todecimal(&s, mpstr); 793 printf("s : %s (dec)\n", mpstr); 794 mp_tohex(&s, mpstr); 795 printf("s : %s\n", mpstr); 796#endif 797 798 /* 799 ** ANSI X9.62, Section 5.3.3, Step 5 800 ** 801 ** verify s != 0 802 */ 803 if (mp_cmp_z(&s) == 0) { 804 PORT_SetError(SEC_ERROR_NEED_RANDOM); 805 goto cleanup; 806 } 807 808 /* 809 ** 810 ** Signature is tuple (r, s) 811 */ 812 CHECK_MPI_OK( mp_to_fixlen_octets(&r, signature->data, olen) ); 813 CHECK_MPI_OK( mp_to_fixlen_octets(&s, signature->data + olen, olen) ); 814finish: 815 signature->len = 2*olen; 816 817 rv = SECSuccess; 818 err = MP_OKAY; 819cleanup: 820 mp_clear(&x1); 821 mp_clear(&d); 822 mp_clear(&k); 823 mp_clear(&r); 824 mp_clear(&s); 825 mp_clear(&n); 826 827 if (kGpoint.data) { 828 PORT_ZFree(kGpoint.data, 2*flen + 1); 829 } 830 831 if (err) { 832 MP_TO_SEC_ERROR(err); 833 rv = SECFailure; 834 } 835 836#if EC_DEBUG 837 printf("ECDSA signing with seed %s\n", 838 (rv == SECSuccess) ? "succeeded" : "failed"); 839#endif 840 841 return rv; 842} 843 844/* 845** Computes the ECDSA signature on the digest using the given key 846** and a random seed. 847*/ 848SECStatus 849ECDSA_SignDigest(ECPrivateKey *key, SECItem *signature, const SECItem *digest, 850 const unsigned char* random, int randomLen, int kmflag, int timing) 851{ 852 SECStatus rv = SECFailure; 853 int len; 854 unsigned char *kBytes= NULL; 855 856 if (!key) { 857 PORT_SetError(SEC_ERROR_INVALID_ARGS); 858 return SECFailure; 859 } 860 861 /* Generate random value k */ 862 len = key->ecParams.order.len; 863 kBytes = ec_GenerateRandomPrivateKey(key->ecParams.order.data, len, 864 random, randomLen, kmflag); 865 if (kBytes == NULL) goto cleanup; 866 867 /* Generate ECDSA signature with the specified k value */ 868 rv = ECDSA_SignDigestWithSeed(key, signature, digest, kBytes, len, kmflag, timing); 869 870cleanup: 871 if (kBytes) { 872 PORT_ZFree(kBytes, len * 2); 873 } 874 875#if EC_DEBUG 876 printf("ECDSA signing %s\n", 877 (rv == SECSuccess) ? "succeeded" : "failed"); 878#endif 879 880 return rv; 881} 882 883/* 884** Checks the signature on the given digest using the key provided. 885*/ 886SECStatus 887ECDSA_VerifyDigest(ECPublicKey *key, const SECItem *signature, 888 const SECItem *digest, int kmflag) 889{ 890 SECStatus rv = SECFailure; 891 mp_int r_, s_; /* tuple (r', s') is received signature) */ 892 mp_int c, u1, u2, v; /* intermediate values used in verification */ 893 mp_int x1; 894 mp_int n; 895 mp_err err = MP_OKAY; 896 ECParams *ecParams = NULL; 897 SECItem pointC = { siBuffer, NULL, 0 }; 898 int slen; /* length in bytes of a half signature (r or s) */ 899 int flen; /* length in bytes of the field size */ 900 unsigned olen; /* length in bytes of the base point order */ 901 902#if EC_DEBUG 903 char mpstr[256]; 904 printf("ECDSA verification called\n"); 905#endif 906 907 /* Initialize MPI integers. */ 908 /* must happen before the first potential call to cleanup */ 909 MP_DIGITS(&r_) = 0; 910 MP_DIGITS(&s_) = 0; 911 MP_DIGITS(&c) = 0; 912 MP_DIGITS(&u1) = 0; 913 MP_DIGITS(&u2) = 0; 914 MP_DIGITS(&x1) = 0; 915 MP_DIGITS(&v) = 0; 916 MP_DIGITS(&n) = 0; 917 918 /* Check args */ 919 if (!key || !signature || !digest) { 920 PORT_SetError(SEC_ERROR_INVALID_ARGS); 921 goto cleanup; 922 } 923 924 ecParams = &(key->ecParams); 925 flen = (ecParams->fieldID.size + 7) >> 3; 926 olen = ecParams->order.len; 927 if (signature->len == 0 || signature->len%2 != 0 || 928 signature->len > 2*olen) { 929 PORT_SetError(SEC_ERROR_INPUT_LEN); 930 goto cleanup; 931 } 932 slen = signature->len/2; 933 934 SECITEM_AllocItem(NULL, &pointC, 2*flen + 1, kmflag); 935 if (pointC.data == NULL) 936 goto cleanup; 937 938 CHECK_MPI_OK( mp_init(&r_, kmflag) ); 939 CHECK_MPI_OK( mp_init(&s_, kmflag) ); 940 CHECK_MPI_OK( mp_init(&c, kmflag) ); 941 CHECK_MPI_OK( mp_init(&u1, kmflag) ); 942 CHECK_MPI_OK( mp_init(&u2, kmflag) ); 943 CHECK_MPI_OK( mp_init(&x1, kmflag) ); 944 CHECK_MPI_OK( mp_init(&v, kmflag) ); 945 CHECK_MPI_OK( mp_init(&n, kmflag) ); 946 947 /* 948 ** Convert received signature (r', s') into MPI integers. 949 */ 950 CHECK_MPI_OK( mp_read_unsigned_octets(&r_, signature->data, slen) ); 951 CHECK_MPI_OK( mp_read_unsigned_octets(&s_, signature->data + slen, slen) ); 952 953 /* 954 ** ANSI X9.62, Section 5.4.2, Steps 1 and 2 955 ** 956 ** Verify that 0 < r' < n and 0 < s' < n 957 */ 958 SECITEM_TO_MPINT(ecParams->order, &n); 959 if (mp_cmp_z(&r_) <= 0 || mp_cmp_z(&s_) <= 0 || 960 mp_cmp(&r_, &n) >= 0 || mp_cmp(&s_, &n) >= 0) { 961 PORT_SetError(SEC_ERROR_BAD_SIGNATURE); 962 goto cleanup; /* will return rv == SECFailure */ 963 } 964 965 /* 966 ** ANSI X9.62, Section 5.4.2, Step 3 967 ** 968 ** c = (s')**-1 mod n 969 */ 970 CHECK_MPI_OK( mp_invmod(&s_, &n, &c) ); /* c = (s')**-1 mod n */ 971 972 /* 973 ** ANSI X9.62, Section 5.4.2, Step 4 974 ** 975 ** u1 = ((HASH(M')) * c) mod n 976 */ 977 SECITEM_TO_MPINT(*digest, &u1); /* u1 = HASH(M) */ 978 979 /* In the definition of EC signing, digests are truncated 980 * to the length of n in bits. 981 * (see SEC 1 "Elliptic Curve Digit Signature Algorithm" section 4.1.*/ 982 /* u1 = HASH(M') */ 983 if (digest->len*8 > (unsigned int)ecParams->fieldID.size) { 984 mpl_rsh(&u1,&u1,digest->len*8- ecParams->fieldID.size); 985 } 986 987#if EC_DEBUG 988 mp_todecimal(&r_, mpstr); 989 printf("r_: %s (dec)\n", mpstr); 990 mp_todecimal(&s_, mpstr); 991 printf("s_: %s (dec)\n", mpstr); 992 mp_todecimal(&c, mpstr); 993 printf("c : %s (dec)\n", mpstr); 994 mp_todecimal(&u1, mpstr); 995 printf("digest: %s (dec)\n", mpstr); 996#endif 997 998 CHECK_MPI_OK( mp_mulmod(&u1, &c, &n, &u1) ); /* u1 = u1 * c mod n */ 999 1000 /* 1001 ** ANSI X9.62, Section 5.4.2, Step 4 1002 ** 1003 ** u2 = ((r') * c) mod n 1004 */ 1005 CHECK_MPI_OK( mp_mulmod(&r_, &c, &n, &u2) ); 1006 1007 /* 1008 ** ANSI X9.62, Section 5.4.3, Step 1 1009 ** 1010 ** Compute u1*G + u2*Q 1011 ** Here, A = u1.G B = u2.Q and C = A + B 1012 ** If the result, C, is the point at infinity, reject the signature 1013 */ 1014 /* verification does not support timing mitigation */ 1015 if (ec_points_mul(ecParams, &u1, &u2, &key->publicValue, &pointC, kmflag, /*timing*/ 0) 1016 != SECSuccess) { 1017 rv = SECFailure; 1018 goto cleanup; 1019 } 1020 if (ec_point_at_infinity(&pointC)) { 1021 PORT_SetError(SEC_ERROR_BAD_SIGNATURE); 1022 rv = SECFailure; 1023 goto cleanup; 1024 } 1025 1026 CHECK_MPI_OK( mp_read_unsigned_octets(&x1, pointC.data + 1, flen) ); 1027 1028 /* 1029 ** ANSI X9.62, Section 5.4.4, Step 2 1030 ** 1031 ** v = x1 mod n 1032 */ 1033 CHECK_MPI_OK( mp_mod(&x1, &n, &v) ); 1034 1035#if EC_DEBUG 1036 mp_todecimal(&r_, mpstr); 1037 printf("r_: %s (dec)\n", mpstr); 1038 mp_todecimal(&v, mpstr); 1039 printf("v : %s (dec)\n", mpstr); 1040#endif 1041 1042 /* 1043 ** ANSI X9.62, Section 5.4.4, Step 3 1044 ** 1045 ** Verification: v == r' 1046 */ 1047 if (mp_cmp(&v, &r_)) { 1048 PORT_SetError(SEC_ERROR_BAD_SIGNATURE); 1049 rv = SECFailure; /* Signature failed to verify. */ 1050 } else { 1051 rv = SECSuccess; /* Signature verified. */ 1052 } 1053 1054#if EC_DEBUG 1055 mp_todecimal(&u1, mpstr); 1056 printf("u1: %s (dec)\n", mpstr); 1057 mp_todecimal(&u2, mpstr); 1058 printf("u2: %s (dec)\n", mpstr); 1059 mp_tohex(&x1, mpstr); 1060 printf("x1: %s\n", mpstr); 1061 mp_todecimal(&v, mpstr); 1062 printf("v : %s (dec)\n", mpstr); 1063#endif 1064 1065cleanup: 1066 mp_clear(&r_); 1067 mp_clear(&s_); 1068 mp_clear(&c); 1069 mp_clear(&u1); 1070 mp_clear(&u2); 1071 mp_clear(&x1); 1072 mp_clear(&v); 1073 mp_clear(&n); 1074 1075 if (pointC.data) SECITEM_FreeItem(&pointC, PR_FALSE); 1076 if (err) { 1077 MP_TO_SEC_ERROR(err); 1078 rv = SECFailure; 1079 } 1080 1081#if EC_DEBUG 1082 printf("ECDSA verification %s\n", 1083 (rv == SECSuccess) ? "succeeded" : "failed"); 1084#endif 1085 1086 return rv; 1087} 1088