1 /*
   2  * Copyright (c) 2007, 2015, 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: April 2015
  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 }