Back to index

lightning-sunbird  0.9+nobinonly
ec.c
Go to the documentation of this file.
00001 /*
00002  * ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is the Elliptic Curve Cryptography library.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Sun Microsystems, Inc.
00019  * Portions created by the Initial Developer are Copyright (C) 2003
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   Dr Vipul Gupta <vipul.gupta@sun.com> and
00024  *   Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
00025  *
00026  * Alternatively, the contents of this file may be used under the terms of
00027  * either the GNU General Public License Version 2 or later (the "GPL"), or
00028  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00029  * in which case the provisions of the GPL or the LGPL are applicable instead
00030  * of those above. If you wish to allow use of your version of this file only
00031  * under the terms of either the GPL or the LGPL, and not to allow others to
00032  * use your version of this file under the terms of the MPL, indicate your
00033  * decision by deleting the provisions above and replace them with the notice
00034  * and other provisions required by the GPL or the LGPL. If you do not delete
00035  * the provisions above, a recipient may use your version of this file under
00036  * the terms of any one of the MPL, the GPL or the LGPL.
00037  *
00038  * ***** END LICENSE BLOCK ***** */
00039 
00040 #include "blapi.h"
00041 #include "prerr.h"
00042 #include "secerr.h"
00043 #include "secmpi.h"
00044 #include "secitem.h"
00045 #include "mplogic.h"
00046 #include "ec.h"
00047 #include "ecl.h"
00048 
00049 #ifdef NSS_ENABLE_ECC
00050 
00051 /* 
00052  * Returns true if pointP is the point at infinity, false otherwise
00053  */
00054 PRBool
00055 ec_point_at_infinity(SECItem *pointP)
00056 {
00057     unsigned int i;
00058 
00059     for (i = 1; i < pointP->len; i++) {
00060        if (pointP->data[i] != 0x00) return PR_FALSE;
00061     }
00062 
00063     return PR_TRUE;
00064 }
00065 
00066 /* 
00067  * Computes scalar point multiplication pointQ = k1 * G + k2 * pointP for
00068  * the curve whose parameters are encoded in params with base point G.
00069  */
00070 SECStatus 
00071 ec_points_mul(const ECParams *params, const mp_int *k1, const mp_int *k2,
00072              const SECItem *pointP, SECItem *pointQ)
00073 {
00074     mp_int Px, Py, Qx, Qy;
00075     mp_int Gx, Gy, order, irreducible, a, b;
00076 #if 0 /* currently don't support non-named curves */
00077     unsigned int irr_arr[5];
00078 #endif
00079     ECGroup *group = NULL;
00080     SECStatus rv = SECFailure;
00081     mp_err err = MP_OKAY;
00082     int len;
00083 
00084 #if EC_DEBUG
00085     int i;
00086     char mpstr[256];
00087 
00088     printf("ec_points_mul: params [len=%d]:", params->DEREncoding.len);
00089     for (i = 0; i < params->DEREncoding.len; i++) 
00090            printf("%02x:", params->DEREncoding.data[i]);
00091     printf("\n");
00092 
00093        if (k1 != NULL) {
00094               mp_tohex(k1, mpstr);
00095               printf("ec_points_mul: scalar k1: %s\n", mpstr);
00096               mp_todecimal(k1, mpstr);
00097               printf("ec_points_mul: scalar k1: %s (dec)\n", mpstr);
00098        }
00099 
00100        if (k2 != NULL) {
00101               mp_tohex(k2, mpstr);
00102               printf("ec_points_mul: scalar k2: %s\n", mpstr);
00103               mp_todecimal(k2, mpstr);
00104               printf("ec_points_mul: scalar k2: %s (dec)\n", mpstr);
00105        }
00106 
00107        if (pointP != NULL) {
00108               printf("ec_points_mul: pointP [len=%d]:", pointP->len);
00109               for (i = 0; i < pointP->len; i++) 
00110                      printf("%02x:", pointP->data[i]);
00111               printf("\n");
00112        }
00113 #endif
00114 
00115        /* NOTE: We only support uncompressed points for now */
00116        len = (params->fieldID.size + 7) >> 3;
00117        if (pointP != NULL) {
00118               if ((pointP->data[0] != EC_POINT_FORM_UNCOMPRESSED) ||
00119                      (pointP->len != (2 * len + 1))) {
00120                      return SECFailure;
00121               };
00122        }
00123 
00124        MP_DIGITS(&Px) = 0;
00125        MP_DIGITS(&Py) = 0;
00126        MP_DIGITS(&Qx) = 0;
00127        MP_DIGITS(&Qy) = 0;
00128        MP_DIGITS(&Gx) = 0;
00129        MP_DIGITS(&Gy) = 0;
00130        MP_DIGITS(&order) = 0;
00131        MP_DIGITS(&irreducible) = 0;
00132        MP_DIGITS(&a) = 0;
00133        MP_DIGITS(&b) = 0;
00134        CHECK_MPI_OK( mp_init(&Px) );
00135        CHECK_MPI_OK( mp_init(&Py) );
00136        CHECK_MPI_OK( mp_init(&Qx) );
00137        CHECK_MPI_OK( mp_init(&Qy) );
00138        CHECK_MPI_OK( mp_init(&Gx) );
00139        CHECK_MPI_OK( mp_init(&Gy) );
00140        CHECK_MPI_OK( mp_init(&order) );
00141        CHECK_MPI_OK( mp_init(&irreducible) );
00142        CHECK_MPI_OK( mp_init(&a) );
00143        CHECK_MPI_OK( mp_init(&b) );
00144 
00145        if ((k2 != NULL) && (pointP != NULL)) {
00146               /* Initialize Px and Py */
00147               CHECK_MPI_OK( mp_read_unsigned_octets(&Px, pointP->data + 1, (mp_size) len) );
00148               CHECK_MPI_OK( mp_read_unsigned_octets(&Py, pointP->data + 1 + len, (mp_size) len) );
00149        }
00150 
00151        /* construct from named params, if possible */
00152        if (params->name != ECCurve_noName) {
00153               group = ECGroup_fromName(params->name);
00154        }
00155 
00156 #if 0 /* currently don't support non-named curves */
00157        if (group == NULL) {
00158               /* Set up mp_ints containing the curve coefficients */
00159               CHECK_MPI_OK( mp_read_unsigned_octets(&Gx, params->base.data + 1, 
00160                                                                         (mp_size) len) );
00161               CHECK_MPI_OK( mp_read_unsigned_octets(&Gy, params->base.data + 1 + len, 
00162                                                                         (mp_size) len) );
00163               SECITEM_TO_MPINT( params->order, &order );
00164               SECITEM_TO_MPINT( params->curve.a, &a );
00165               SECITEM_TO_MPINT( params->curve.b, &b );
00166               if (params->fieldID.type == ec_field_GFp) {
00167                      SECITEM_TO_MPINT( params->fieldID.u.prime, &irreducible );
00168                      group = ECGroup_consGFp(&irreducible, &a, &b, &Gx, &Gy, &order, params->cofactor);
00169               } else {
00170                      SECITEM_TO_MPINT( params->fieldID.u.poly, &irreducible );
00171                      irr_arr[0] = params->fieldID.size;
00172                      irr_arr[1] = params->fieldID.k1;
00173                      irr_arr[2] = params->fieldID.k2;
00174                      irr_arr[3] = params->fieldID.k3;
00175                      irr_arr[4] = 0;
00176                      group = ECGroup_consGF2m(&irreducible, irr_arr, &a, &b, &Gx, &Gy, &order, params->cofactor);
00177               }
00178        }
00179 #endif
00180        if (group == NULL)
00181               goto cleanup;
00182 
00183        if ((k2 != NULL) && (pointP != NULL)) {
00184               CHECK_MPI_OK( ECPoints_mul(group, k1, k2, &Px, &Py, &Qx, &Qy) );
00185        } else {
00186               CHECK_MPI_OK( ECPoints_mul(group, k1, NULL, NULL, NULL, &Qx, &Qy) );
00187     }
00188 
00189     /* Construct the SECItem representation of point Q */
00190     pointQ->data[0] = EC_POINT_FORM_UNCOMPRESSED;
00191     CHECK_MPI_OK( mp_to_fixlen_octets(&Qx, pointQ->data + 1,
00192                                      (mp_size) len) );
00193     CHECK_MPI_OK( mp_to_fixlen_octets(&Qy, pointQ->data + 1 + len,
00194                                      (mp_size) len) );
00195 
00196     rv = SECSuccess;
00197 
00198 #if EC_DEBUG
00199     printf("ec_points_mul: pointQ [len=%d]:", pointQ->len);
00200     for (i = 0; i < pointQ->len; i++) 
00201            printf("%02x:", pointQ->data[i]);
00202     printf("\n");
00203 #endif
00204 
00205 cleanup:
00206     ECGroup_free(group);
00207     mp_clear(&Px);
00208     mp_clear(&Py);
00209     mp_clear(&Qx);
00210     mp_clear(&Qy);
00211     mp_clear(&Gx);
00212     mp_clear(&Gy);
00213     mp_clear(&order);
00214     mp_clear(&irreducible);
00215     mp_clear(&a);
00216     mp_clear(&b);
00217     if (err) {
00218        MP_TO_SEC_ERROR(err);
00219        rv = SECFailure;
00220     }
00221 
00222     return rv;
00223 }
00224 #endif /* NSS_ENABLE_ECC */
00225 
00226 /* Generates a new EC key pair. The private key is a supplied
00227  * value and the public key is the result of performing a scalar 
00228  * point multiplication of that value with the curve's base point.
00229  */
00230 SECStatus 
00231 ec_NewKey(ECParams *ecParams, ECPrivateKey **privKey, 
00232     const unsigned char *privKeyBytes, int privKeyLen)
00233 {
00234     SECStatus rv = SECFailure;
00235 #ifdef NSS_ENABLE_ECC
00236     PRArenaPool *arena;
00237     ECPrivateKey *key;
00238     mp_int k;
00239     mp_err err = MP_OKAY;
00240     int len;
00241 
00242 #if EC_DEBUG
00243     printf("ec_NewKey called\n");
00244 #endif
00245 
00246     if (!ecParams || !privKey || !privKeyBytes || (privKeyLen < 0)) {
00247        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00248        return SECFailure;
00249     }
00250 
00251     /* Initialize an arena for the EC key. */
00252     if (!(arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE)))
00253        return SECFailure;
00254 
00255     key = (ECPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(ECPrivateKey));
00256     if (!key) {
00257        PORT_FreeArena(arena, PR_TRUE);
00258        return SECFailure;
00259     }
00260 
00261     /* Set the version number (SEC 1 section C.4 says it should be 1) */
00262     SECITEM_AllocItem(arena, &key->version, 1);
00263     key->version.data[0] = 1;
00264 
00265     /* Copy all of the fields from the ECParams argument to the
00266      * ECParams structure within the private key.
00267      */
00268     key->ecParams.arena = arena;
00269     key->ecParams.type = ecParams->type;
00270     key->ecParams.fieldID.size = ecParams->fieldID.size;
00271     key->ecParams.fieldID.type = ecParams->fieldID.type;
00272     if (ecParams->fieldID.type == ec_field_GFp) {
00273        CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.fieldID.u.prime,
00274            &ecParams->fieldID.u.prime));
00275     } else {
00276        CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.fieldID.u.poly,
00277            &ecParams->fieldID.u.poly));
00278     }
00279     key->ecParams.fieldID.k1 = ecParams->fieldID.k1;
00280     key->ecParams.fieldID.k2 = ecParams->fieldID.k2;
00281     key->ecParams.fieldID.k3 = ecParams->fieldID.k3;
00282     CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.curve.a,
00283        &ecParams->curve.a));
00284     CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.curve.b,
00285        &ecParams->curve.b));
00286     CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.curve.seed,
00287        &ecParams->curve.seed));
00288     CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.base,
00289        &ecParams->base));
00290     CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.order,
00291        &ecParams->order));
00292     key->ecParams.cofactor = ecParams->cofactor;
00293     CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.DEREncoding,
00294        &ecParams->DEREncoding));
00295     key->ecParams.name = ecParams->name;
00296     CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.curveOID,
00297        &ecParams->curveOID));
00298 
00299     len = (ecParams->fieldID.size + 7) >> 3;
00300     SECITEM_AllocItem(arena, &key->publicValue, 2*len + 1);
00301     len = ecParams->order.len;
00302     SECITEM_AllocItem(arena, &key->privateValue, len);
00303 
00304     /* Copy private key */
00305     if (privKeyLen >= len) {
00306        memcpy(key->privateValue.data, privKeyBytes, len);
00307     } else {
00308        memset(key->privateValue.data, 0, (len - privKeyLen));
00309        memcpy(key->privateValue.data + (len - privKeyLen), privKeyBytes, privKeyLen);
00310     }
00311 
00312     /* Compute corresponding public key */
00313     MP_DIGITS(&k) = 0;
00314     CHECK_MPI_OK( mp_init(&k) );
00315     CHECK_MPI_OK( mp_read_unsigned_octets(&k, key->privateValue.data, 
00316        (mp_size) len) );
00317 
00318     rv = ec_points_mul(ecParams, &k, NULL, NULL, &(key->publicValue));
00319     if (rv != SECSuccess) goto cleanup;
00320     *privKey = key;
00321 
00322 cleanup:
00323     mp_clear(&k);
00324     if (rv)
00325        PORT_FreeArena(arena, PR_TRUE);
00326 
00327 #if EC_DEBUG
00328     printf("ec_NewKey returning %s\n", 
00329        (rv == SECSuccess) ? "success" : "failure");
00330 #endif
00331 #else
00332     PORT_SetError(SEC_ERROR_UNSUPPORTED_KEYALG);
00333 #endif /* NSS_ENABLE_ECC */
00334 
00335     return rv;
00336 
00337 }
00338 
00339 /* Generates a new EC key pair. The private key is a supplied
00340  * random value (in seed) and the public key is the result of 
00341  * performing a scalar point multiplication of that value with 
00342  * the curve's base point.
00343  */
00344 SECStatus 
00345 EC_NewKeyFromSeed(ECParams *ecParams, ECPrivateKey **privKey, 
00346     const unsigned char *seed, int seedlen)
00347 {
00348     SECStatus rv = SECFailure;
00349 #ifdef NSS_ENABLE_ECC
00350     rv = ec_NewKey(ecParams, privKey, seed, seedlen);
00351 #else
00352     PORT_SetError(SEC_ERROR_UNSUPPORTED_KEYALG);
00353 #endif /* NSS_ENABLE_ECC */
00354     return rv;
00355 }
00356 
00357 /* Generate a random private key using the algorithm A.4.1 of ANSI X9.62,
00358  * modified a la FIPS 186-2 Change Notice 1 to eliminate the bias in the
00359  * random number generator.
00360  *
00361  * Parameters
00362  * - order: a buffer that holds the curve's group order
00363  * - len: the length in octets of the order buffer
00364  *
00365  * Return Value
00366  * Returns a buffer of len octets that holds the private key. The caller
00367  * is responsible for freeing the buffer with PORT_ZFree.
00368  */
00369 static unsigned char *
00370 ec_GenerateRandomPrivateKey(const unsigned char *order, int len)
00371 {
00372     SECStatus rv = SECSuccess;
00373     mp_err err;
00374     unsigned char *privKeyBytes = NULL;
00375     mp_int privKeyVal, order_1, one;
00376 
00377     MP_DIGITS(&privKeyVal) = 0;
00378     MP_DIGITS(&order_1) = 0;
00379     MP_DIGITS(&one) = 0;
00380     CHECK_MPI_OK( mp_init(&privKeyVal) );
00381     CHECK_MPI_OK( mp_init(&order_1) );
00382     CHECK_MPI_OK( mp_init(&one) );
00383 
00384     /* Generates 2*len random bytes using the global random bit generator
00385      * (which implements Algorithm 1 of FIPS 186-2 Change Notice 1) then
00386      * reduces modulo the group order.
00387      */
00388     if ((privKeyBytes = PORT_Alloc(2*len)) == NULL) goto cleanup;
00389     CHECK_SEC_OK( RNG_GenerateGlobalRandomBytes(privKeyBytes, 2*len) );
00390     CHECK_MPI_OK( mp_read_unsigned_octets(&privKeyVal, privKeyBytes, 2*len) );
00391     CHECK_MPI_OK( mp_read_unsigned_octets(&order_1, order, len) );
00392     CHECK_MPI_OK( mp_set_int(&one, 1) );
00393     CHECK_MPI_OK( mp_sub(&order_1, &one, &order_1) );
00394     CHECK_MPI_OK( mp_mod(&privKeyVal, &order_1, &privKeyVal) );
00395     CHECK_MPI_OK( mp_add(&privKeyVal, &one, &privKeyVal) );
00396     CHECK_MPI_OK( mp_to_fixlen_octets(&privKeyVal, privKeyBytes, len) );
00397     memset(privKeyBytes+len, 0, len);
00398 cleanup:
00399     mp_clear(&privKeyVal);
00400     mp_clear(&order_1);
00401     mp_clear(&one);
00402     if (err < MP_OKAY) {
00403        MP_TO_SEC_ERROR(err);
00404        rv = SECFailure;
00405     }
00406     if (rv != SECSuccess && privKeyBytes) {
00407        PORT_Free(privKeyBytes);
00408        privKeyBytes = NULL;
00409     }
00410     return privKeyBytes;
00411 }
00412 
00413 /* Generates a new EC key pair. The private key is a random value and
00414  * the public key is the result of performing a scalar point multiplication
00415  * of that value with the curve's base point.
00416  */
00417 SECStatus 
00418 EC_NewKey(ECParams *ecParams, ECPrivateKey **privKey)
00419 {
00420     SECStatus rv = SECFailure;
00421 #ifdef NSS_ENABLE_ECC
00422     int len;
00423     unsigned char *privKeyBytes = NULL;
00424 
00425     if (!ecParams) {
00426        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00427        return SECFailure;
00428     }
00429 
00430     len = ecParams->order.len;
00431     privKeyBytes = ec_GenerateRandomPrivateKey(ecParams->order.data, len);
00432     if (privKeyBytes == NULL) goto cleanup;
00433     /* generate public key */
00434     CHECK_SEC_OK( ec_NewKey(ecParams, privKey, privKeyBytes, len) );
00435 
00436 cleanup:
00437     if (privKeyBytes) {
00438        PORT_ZFree(privKeyBytes, len);
00439     }
00440 #if EC_DEBUG
00441     printf("EC_NewKey returning %s\n", 
00442        (rv == SECSuccess) ? "success" : "failure");
00443 #endif
00444 #else
00445     PORT_SetError(SEC_ERROR_UNSUPPORTED_KEYALG);
00446 #endif /* NSS_ENABLE_ECC */
00447     
00448     return rv;
00449 }
00450 
00451 /* Validates an EC public key as described in Section 5.2.2 of
00452  * X9.62. The ECDH primitive when used without the cofactor does
00453  * not address small subgroup attacks, which may occur when the
00454  * public key is not valid. These attacks can be prevented by 
00455  * validating the public key before using ECDH.
00456  */
00457 SECStatus 
00458 EC_ValidatePublicKey(ECParams *ecParams, SECItem *publicValue)
00459 {
00460 #ifdef NSS_ENABLE_ECC
00461     mp_int Px, Py;
00462     ECGroup *group = NULL;
00463     SECStatus rv = SECFailure;
00464     mp_err err = MP_OKAY;
00465     int len;
00466 
00467     if (!ecParams || !publicValue) {
00468        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00469        return SECFailure;
00470     }
00471        
00472     /* NOTE: We only support uncompressed points for now */
00473     len = (ecParams->fieldID.size + 7) >> 3;
00474     if (publicValue->data[0] != EC_POINT_FORM_UNCOMPRESSED) {
00475        PORT_SetError(SEC_ERROR_UNSUPPORTED_EC_POINT_FORM);
00476        return SECFailure;
00477     } else if (publicValue->len != (2 * len + 1)) {
00478        PORT_SetError(SEC_ERROR_BAD_KEY);
00479        return SECFailure;
00480     }
00481 
00482     MP_DIGITS(&Px) = 0;
00483     MP_DIGITS(&Py) = 0;
00484     CHECK_MPI_OK( mp_init(&Px) );
00485     CHECK_MPI_OK( mp_init(&Py) );
00486 
00487     /* Initialize Px and Py */
00488     CHECK_MPI_OK( mp_read_unsigned_octets(&Px, publicValue->data + 1, (mp_size) len) );
00489     CHECK_MPI_OK( mp_read_unsigned_octets(&Py, publicValue->data + 1 + len, (mp_size) len) );
00490 
00491     /* construct from named params */
00492     group = ECGroup_fromName(ecParams->name);
00493     if (group == NULL) {
00494        /*
00495         * ECGroup_fromName fails if ecParams->name is not a valid
00496         * ECCurveName value, or if we run out of memory, or perhaps
00497         * for other reasons.  Unfortunately if ecParams->name is a
00498         * valid ECCurveName value, we don't know what the right error
00499         * code should be because ECGroup_fromName doesn't return an
00500         * error code to the caller.  Set err to MP_UNDEF because
00501         * that's what ECGroup_fromName uses internally.
00502         */
00503        if ((ecParams->name <= ECCurve_noName) ||
00504            (ecParams->name >= ECCurve_pastLastCurve)) {
00505            err = MP_BADARG;
00506        } else {
00507            err = MP_UNDEF;
00508        }
00509        goto cleanup;
00510     }
00511 
00512     /* validate public point */
00513     if ((err = ECPoint_validate(group, &Px, &Py)) < MP_YES) {
00514        if (err == MP_NO) {
00515            PORT_SetError(SEC_ERROR_BAD_KEY);
00516            rv = SECFailure;
00517            err = MP_OKAY;  /* don't change the error code */
00518        }
00519        goto cleanup;
00520     }
00521 
00522     rv = SECSuccess;
00523 
00524 cleanup:
00525     ECGroup_free(group);
00526     mp_clear(&Px);
00527     mp_clear(&Py);
00528     if (err) {
00529        MP_TO_SEC_ERROR(err);
00530        rv = SECFailure;
00531     }
00532     return rv;
00533 #else
00534     PORT_SetError(SEC_ERROR_UNSUPPORTED_KEYALG);
00535     return SECFailure;
00536 #endif /* NSS_ENABLE_ECC */
00537 }
00538 
00539 /* 
00540 ** Performs an ECDH key derivation by computing the scalar point
00541 ** multiplication of privateValue and publicValue (with or without the
00542 ** cofactor) and returns the x-coordinate of the resulting elliptic
00543 ** curve point in derived secret.  If successful, derivedSecret->data
00544 ** is set to the address of the newly allocated buffer containing the
00545 ** derived secret, and derivedSecret->len is the size of the secret
00546 ** produced. It is the caller's responsibility to free the allocated
00547 ** buffer containing the derived secret.
00548 */
00549 SECStatus 
00550 ECDH_Derive(SECItem  *publicValue, 
00551             ECParams *ecParams,
00552             SECItem  *privateValue,
00553             PRBool    withCofactor,
00554             SECItem  *derivedSecret)
00555 {
00556     SECStatus rv = SECFailure;
00557 #ifdef NSS_ENABLE_ECC
00558     unsigned int len = 0;
00559     SECItem pointQ = {siBuffer, NULL, 0};
00560     mp_int k; /* to hold the private value */
00561     mp_int cofactor;
00562     mp_err err = MP_OKAY;
00563 #if EC_DEBUG
00564     int i;
00565 #endif
00566 
00567     if (!publicValue || !ecParams || !privateValue || 
00568        !derivedSecret) {
00569        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00570        return SECFailure;
00571     }
00572 
00573     memset(derivedSecret, 0, sizeof *derivedSecret);
00574     len = (ecParams->fieldID.size + 7) >> 3;  
00575     pointQ.len = 2*len + 1;
00576     if ((pointQ.data = PORT_Alloc(2*len + 1)) == NULL) goto cleanup;
00577 
00578     MP_DIGITS(&k) = 0;
00579     CHECK_MPI_OK( mp_init(&k) );
00580     CHECK_MPI_OK( mp_read_unsigned_octets(&k, privateValue->data, 
00581                                          (mp_size) privateValue->len) );
00582 
00583     if (withCofactor && (ecParams->cofactor != 1)) {
00584            /* multiply k with the cofactor */
00585            MP_DIGITS(&cofactor) = 0;
00586            CHECK_MPI_OK( mp_init(&cofactor) );
00587            mp_set(&cofactor, ecParams->cofactor);
00588            CHECK_MPI_OK( mp_mul(&k, &cofactor, &k) );
00589     }
00590 
00591     /* Multiply our private key and peer's public point */
00592     if ((ec_points_mul(ecParams, NULL, &k, publicValue, &pointQ) != SECSuccess) ||
00593        ec_point_at_infinity(&pointQ))
00594        goto cleanup;
00595 
00596     /* Allocate memory for the derived secret and copy
00597      * the x co-ordinate of pointQ into it.
00598      */
00599     SECITEM_AllocItem(NULL, derivedSecret, len);
00600     memcpy(derivedSecret->data, pointQ.data + 1, len);
00601 
00602     rv = SECSuccess;
00603 
00604 #if EC_DEBUG
00605     printf("derived_secret:\n");
00606     for (i = 0; i < derivedSecret->len; i++) 
00607        printf("%02x:", derivedSecret->data[i]);
00608     printf("\n");
00609 #endif
00610 
00611 cleanup:
00612     mp_clear(&k);
00613 
00614     if (pointQ.data) {
00615        PORT_ZFree(pointQ.data, 2*len + 1);
00616     }
00617 #else
00618     PORT_SetError(SEC_ERROR_UNSUPPORTED_KEYALG);
00619 #endif /* NSS_ENABLE_ECC */
00620 
00621     return rv;
00622 }
00623 
00624 /* Computes the ECDSA signature (a concatenation of two values r and s)
00625  * on the digest using the given key and the random value kb (used in
00626  * computing s).
00627  */
00628 SECStatus 
00629 ECDSA_SignDigestWithSeed(ECPrivateKey *key, SECItem *signature, 
00630     const SECItem *digest, const unsigned char *kb, const int kblen)
00631 {
00632     SECStatus rv = SECFailure;
00633 #ifdef NSS_ENABLE_ECC
00634     mp_int x1;
00635     mp_int d, k;     /* private key, random integer */
00636     mp_int r, s;     /* tuple (r, s) is the signature */
00637     mp_int n;
00638     mp_err err = MP_OKAY;
00639     ECParams *ecParams = NULL;
00640     SECItem kGpoint = { siBuffer, NULL, 0};
00641     int flen = 0;    /* length in bytes of the field size */
00642     unsigned olen;   /* length in bytes of the base point order */
00643 
00644 #if EC_DEBUG
00645     char mpstr[256];
00646 #endif
00647 
00648     /* Initialize MPI integers. */
00649     /* must happen before the first potential call to cleanup */
00650     MP_DIGITS(&x1) = 0;
00651     MP_DIGITS(&d) = 0;
00652     MP_DIGITS(&k) = 0;
00653     MP_DIGITS(&r) = 0;
00654     MP_DIGITS(&s) = 0;
00655     MP_DIGITS(&n) = 0;
00656 
00657     /* Check args */
00658     if (!key || !signature || !digest || !kb || (kblen < 0)) {
00659        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00660        goto cleanup;
00661     }
00662 
00663     ecParams = &(key->ecParams);
00664     flen = (ecParams->fieldID.size + 7) >> 3;
00665     olen = ecParams->order.len;  
00666     if (signature->data == NULL) {
00667        /* a call to get the signature length only */
00668        goto finish;
00669     }
00670     if (signature->len < 2*olen) {
00671        PORT_SetError(SEC_ERROR_OUTPUT_LEN);
00672        goto cleanup;
00673     }
00674 
00675 
00676     CHECK_MPI_OK( mp_init(&x1) );
00677     CHECK_MPI_OK( mp_init(&d) );
00678     CHECK_MPI_OK( mp_init(&k) );
00679     CHECK_MPI_OK( mp_init(&r) );
00680     CHECK_MPI_OK( mp_init(&s) );
00681     CHECK_MPI_OK( mp_init(&n) );
00682 
00683     SECITEM_TO_MPINT( ecParams->order, &n );
00684     SECITEM_TO_MPINT( key->privateValue, &d );
00685     CHECK_MPI_OK( mp_read_unsigned_octets(&k, kb, kblen) );
00686     /* Make sure k is in the interval [1, n-1] */
00687     if ((mp_cmp_z(&k) <= 0) || (mp_cmp(&k, &n) >= 0)) {
00688 #if EC_DEBUG
00689         printf("k is outside [1, n-1]\n");
00690         mp_tohex(&k, mpstr);
00691        printf("k : %s \n", mpstr);
00692         mp_tohex(&n, mpstr);
00693        printf("n : %s \n", mpstr);
00694 #endif
00695        PORT_SetError(SEC_ERROR_NEED_RANDOM);
00696        goto cleanup;
00697     }
00698 
00699     /* 
00700     ** ANSI X9.62, Section 5.3.2, Step 2
00701     **
00702     ** Compute kG
00703     */
00704     kGpoint.len = 2*flen + 1;
00705     kGpoint.data = PORT_Alloc(2*flen + 1);
00706     if ((kGpoint.data == NULL) ||
00707        (ec_points_mul(ecParams, &k, NULL, NULL, &kGpoint)
00708            != SECSuccess))
00709        goto cleanup;
00710 
00711     /* 
00712     ** ANSI X9.62, Section 5.3.3, Step 1
00713     **
00714     ** Extract the x co-ordinate of kG into x1
00715     */
00716     CHECK_MPI_OK( mp_read_unsigned_octets(&x1, kGpoint.data + 1, 
00717                                          (mp_size) flen) );
00718 
00719     /* 
00720     ** ANSI X9.62, Section 5.3.3, Step 2
00721     **
00722     ** r = x1 mod n  NOTE: n is the order of the curve
00723     */
00724     CHECK_MPI_OK( mp_mod(&x1, &n, &r) );
00725 
00726     /*
00727     ** ANSI X9.62, Section 5.3.3, Step 3
00728     **
00729     ** verify r != 0 
00730     */
00731     if (mp_cmp_z(&r) == 0) {
00732        PORT_SetError(SEC_ERROR_NEED_RANDOM);
00733        goto cleanup;
00734     }
00735 
00736     /*                                  
00737     ** ANSI X9.62, Section 5.3.3, Step 4
00738     **
00739     ** s = (k**-1 * (HASH(M) + d*r)) mod n 
00740     */
00741     SECITEM_TO_MPINT(*digest, &s);        /* s = HASH(M)     */
00742 
00743     /* In the definition of EC signing, digests are truncated
00744      * to the length of n in bits. 
00745      * (see SEC 1 "Elliptic Curve Digit Signature Algorithm" section 4.1.*/
00746     if (digest->len*8 > ecParams->fieldID.size) {
00747        mpl_rsh(&s,&s,digest->len*8 - ecParams->fieldID.size);
00748     }
00749 
00750 #if EC_DEBUG
00751     mp_todecimal(&n, mpstr);
00752     printf("n : %s (dec)\n", mpstr);
00753     mp_todecimal(&d, mpstr);
00754     printf("d : %s (dec)\n", mpstr);
00755     mp_tohex(&x1, mpstr);
00756     printf("x1: %s\n", mpstr);
00757     mp_todecimal(&s, mpstr);
00758     printf("digest: %s (decimal)\n", mpstr);
00759     mp_todecimal(&r, mpstr);
00760     printf("r : %s (dec)\n", mpstr);
00761     mp_tohex(&r, mpstr);
00762     printf("r : %s\n", mpstr);
00763 #endif
00764 
00765     CHECK_MPI_OK( mp_invmod(&k, &n, &k) );      /* k = k**-1 mod n */
00766     CHECK_MPI_OK( mp_mulmod(&d, &r, &n, &d) );  /* d = d * r mod n */
00767     CHECK_MPI_OK( mp_addmod(&s, &d, &n, &s) );  /* s = s + d mod n */
00768     CHECK_MPI_OK( mp_mulmod(&s, &k, &n, &s) );  /* s = s * k mod n */
00769 
00770 #if EC_DEBUG
00771     mp_todecimal(&s, mpstr);
00772     printf("s : %s (dec)\n", mpstr);
00773     mp_tohex(&s, mpstr);
00774     printf("s : %s\n", mpstr);
00775 #endif
00776 
00777     /*
00778     ** ANSI X9.62, Section 5.3.3, Step 5
00779     **
00780     ** verify s != 0
00781     */
00782     if (mp_cmp_z(&s) == 0) {
00783        PORT_SetError(SEC_ERROR_NEED_RANDOM);
00784        goto cleanup;
00785     }
00786 
00787    /*
00788     **
00789     ** Signature is tuple (r, s)
00790     */
00791     CHECK_MPI_OK( mp_to_fixlen_octets(&r, signature->data, olen) );
00792     CHECK_MPI_OK( mp_to_fixlen_octets(&s, signature->data + olen, olen) );
00793 finish:
00794     signature->len = 2*olen;
00795 
00796     rv = SECSuccess;
00797     err = MP_OKAY;
00798 cleanup:
00799     mp_clear(&x1);
00800     mp_clear(&d);
00801     mp_clear(&k);
00802     mp_clear(&r);
00803     mp_clear(&s);
00804     mp_clear(&n);
00805 
00806     if (kGpoint.data) {
00807        PORT_ZFree(kGpoint.data, 2*flen + 1);
00808     }
00809 
00810     if (err) {
00811        MP_TO_SEC_ERROR(err);
00812        rv = SECFailure;
00813     }
00814 
00815 #if EC_DEBUG
00816     printf("ECDSA signing with seed %s\n",
00817        (rv == SECSuccess) ? "succeeded" : "failed");
00818 #endif
00819 #else
00820     PORT_SetError(SEC_ERROR_UNSUPPORTED_KEYALG);
00821 #endif /* NSS_ENABLE_ECC */
00822 
00823    return rv;
00824 }
00825 
00826 /*
00827 ** Computes the ECDSA signature on the digest using the given key 
00828 ** and a random seed.
00829 */
00830 SECStatus 
00831 ECDSA_SignDigest(ECPrivateKey *key, SECItem *signature, const SECItem *digest)
00832 {
00833     SECStatus rv = SECFailure;
00834 #ifdef NSS_ENABLE_ECC
00835     int len;
00836     unsigned char *kBytes= NULL;
00837 
00838     if (!key) {
00839        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00840        return SECFailure;
00841     }
00842 
00843     /* Generate random value k */
00844     len = key->ecParams.order.len;
00845     kBytes = ec_GenerateRandomPrivateKey(key->ecParams.order.data, len);
00846     if (kBytes == NULL) goto cleanup;
00847 
00848     /* Generate ECDSA signature with the specified k value */
00849     rv = ECDSA_SignDigestWithSeed(key, signature, digest, kBytes, len);
00850 
00851 cleanup:    
00852     if (kBytes) {
00853        PORT_ZFree(kBytes, len);
00854     }
00855 
00856 #if EC_DEBUG
00857     printf("ECDSA signing %s\n",
00858        (rv == SECSuccess) ? "succeeded" : "failed");
00859 #endif
00860 #else
00861     PORT_SetError(SEC_ERROR_UNSUPPORTED_KEYALG);
00862 #endif /* NSS_ENABLE_ECC */
00863 
00864     return rv;
00865 }
00866 
00867 /*
00868 ** Checks the signature on the given digest using the key provided.
00869 */
00870 SECStatus 
00871 ECDSA_VerifyDigest(ECPublicKey *key, const SECItem *signature, 
00872                  const SECItem *digest)
00873 {
00874     SECStatus rv = SECFailure;
00875 #ifdef NSS_ENABLE_ECC
00876     mp_int r_, s_;           /* tuple (r', s') is received signature) */
00877     mp_int c, u1, u2, v;     /* intermediate values used in verification */
00878     mp_int x1;
00879     mp_int n;
00880     mp_err err = MP_OKAY;
00881     ECParams *ecParams = NULL;
00882     SECItem pointC = { siBuffer, NULL, 0 };
00883     int slen;       /* length in bytes of a half signature (r or s) */
00884     int flen;       /* length in bytes of the field size */
00885     unsigned olen;  /* length in bytes of the base point order */
00886 
00887 #if EC_DEBUG
00888     char mpstr[256];
00889     printf("ECDSA verification called\n");
00890 #endif
00891 
00892     /* Initialize MPI integers. */
00893     /* must happen before the first potential call to cleanup */
00894     MP_DIGITS(&r_) = 0;
00895     MP_DIGITS(&s_) = 0;
00896     MP_DIGITS(&c) = 0;
00897     MP_DIGITS(&u1) = 0;
00898     MP_DIGITS(&u2) = 0;
00899     MP_DIGITS(&x1) = 0;
00900     MP_DIGITS(&v)  = 0;
00901     MP_DIGITS(&n)  = 0;
00902 
00903     /* Check args */
00904     if (!key || !signature || !digest) {
00905        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00906        goto cleanup;
00907     }
00908 
00909     ecParams = &(key->ecParams);
00910     flen = (ecParams->fieldID.size + 7) >> 3;  
00911     olen = ecParams->order.len;  
00912     if (signature->len == 0 || signature->len%2 != 0 ||
00913        signature->len > 2*olen) {
00914        PORT_SetError(SEC_ERROR_INPUT_LEN);
00915        goto cleanup;
00916     }
00917     slen = signature->len/2;
00918 
00919     SECITEM_AllocItem(NULL, &pointC, 2*flen + 1);
00920     if (pointC.data == NULL)
00921        goto cleanup;
00922 
00923     CHECK_MPI_OK( mp_init(&r_) );
00924     CHECK_MPI_OK( mp_init(&s_) );
00925     CHECK_MPI_OK( mp_init(&c)  );
00926     CHECK_MPI_OK( mp_init(&u1) );
00927     CHECK_MPI_OK( mp_init(&u2) );
00928     CHECK_MPI_OK( mp_init(&x1)  );
00929     CHECK_MPI_OK( mp_init(&v)  );
00930     CHECK_MPI_OK( mp_init(&n)  );
00931 
00932     /*
00933     ** Convert received signature (r', s') into MPI integers.
00934     */
00935     CHECK_MPI_OK( mp_read_unsigned_octets(&r_, signature->data, slen) );
00936     CHECK_MPI_OK( mp_read_unsigned_octets(&s_, signature->data + slen, slen) );
00937                                           
00938     /* 
00939     ** ANSI X9.62, Section 5.4.2, Steps 1 and 2
00940     **
00941     ** Verify that 0 < r' < n and 0 < s' < n
00942     */
00943     SECITEM_TO_MPINT(ecParams->order, &n);
00944     if (mp_cmp_z(&r_) <= 0 || mp_cmp_z(&s_) <= 0 ||
00945         mp_cmp(&r_, &n) >= 0 || mp_cmp(&s_, &n) >= 0) {
00946        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
00947        goto cleanup; /* will return rv == SECFailure */
00948     }
00949 
00950     /*
00951     ** ANSI X9.62, Section 5.4.2, Step 3
00952     **
00953     ** c = (s')**-1 mod n
00954     */
00955     CHECK_MPI_OK( mp_invmod(&s_, &n, &c) );      /* c = (s')**-1 mod n */
00956 
00957     /*
00958     ** ANSI X9.62, Section 5.4.2, Step 4
00959     **
00960     ** u1 = ((HASH(M')) * c) mod n
00961     */
00962     SECITEM_TO_MPINT(*digest, &u1);                  /* u1 = HASH(M)     */
00963 
00964     /* In the definition of EC signing, digests are truncated
00965      * to the length of n in bits. 
00966      * (see SEC 1 "Elliptic Curve Digit Signature Algorithm" section 4.1.*/
00967     if (digest->len*8 > ecParams->fieldID.size) {  /* u1 = HASH(M')     */
00968        mpl_rsh(&u1,&u1,digest->len*8- ecParams->fieldID.size);
00969     }
00970 
00971 #if EC_DEBUG
00972     mp_todecimal(&r_, mpstr);
00973     printf("r_: %s (dec)\n", mpstr);
00974     mp_todecimal(&s_, mpstr);
00975     printf("s_: %s (dec)\n", mpstr);
00976     mp_todecimal(&c, mpstr);
00977     printf("c : %s (dec)\n", mpstr);
00978     mp_todecimal(&u1, mpstr);
00979     printf("digest: %s (dec)\n", mpstr);
00980 #endif
00981 
00982     CHECK_MPI_OK( mp_mulmod(&u1, &c, &n, &u1) );  /* u1 = u1 * c mod n */
00983 
00984     /*
00985     ** ANSI X9.62, Section 5.4.2, Step 4
00986     **
00987     ** u2 = ((r') * c) mod n
00988     */
00989     CHECK_MPI_OK( mp_mulmod(&r_, &c, &n, &u2) );
00990 
00991     /*
00992     ** ANSI X9.62, Section 5.4.3, Step 1
00993     **
00994     ** Compute u1*G + u2*Q
00995     ** Here, A = u1.G     B = u2.Q    and   C = A + B
00996     ** If the result, C, is the point at infinity, reject the signature
00997     */
00998     if (ec_points_mul(ecParams, &u1, &u2, &key->publicValue, &pointC)
00999        != SECSuccess) {
01000        rv = SECFailure;
01001        goto cleanup;
01002     }
01003     if (ec_point_at_infinity(&pointC)) {
01004        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
01005        rv = SECFailure;
01006        goto cleanup;
01007     }
01008 
01009     CHECK_MPI_OK( mp_read_unsigned_octets(&x1, pointC.data + 1, flen) );
01010 
01011     /*
01012     ** ANSI X9.62, Section 5.4.4, Step 2
01013     **
01014     ** v = x1 mod n
01015     */
01016     CHECK_MPI_OK( mp_mod(&x1, &n, &v) );
01017 
01018 #if EC_DEBUG
01019     mp_todecimal(&r_, mpstr);
01020     printf("r_: %s (dec)\n", mpstr);
01021     mp_todecimal(&v, mpstr);
01022     printf("v : %s (dec)\n", mpstr);
01023 #endif
01024 
01025     /*
01026     ** ANSI X9.62, Section 5.4.4, Step 3
01027     **
01028     ** Verification:  v == r'
01029     */
01030     if (mp_cmp(&v, &r_)) {
01031        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
01032        rv = SECFailure; /* Signature failed to verify. */
01033     } else {
01034        rv = SECSuccess; /* Signature verified. */
01035     }
01036 
01037 #if EC_DEBUG
01038     mp_todecimal(&u1, mpstr);
01039     printf("u1: %s (dec)\n", mpstr);
01040     mp_todecimal(&u2, mpstr);
01041     printf("u2: %s (dec)\n", mpstr);
01042     mp_tohex(&x1, mpstr);
01043     printf("x1: %s\n", mpstr);
01044     mp_todecimal(&v, mpstr);
01045     printf("v : %s (dec)\n", mpstr);
01046 #endif
01047 
01048 cleanup:
01049     mp_clear(&r_);
01050     mp_clear(&s_);
01051     mp_clear(&c);
01052     mp_clear(&u1);
01053     mp_clear(&u2);
01054     mp_clear(&x1);
01055     mp_clear(&v);
01056     mp_clear(&n);
01057 
01058     if (pointC.data) SECITEM_FreeItem(&pointC, PR_FALSE);
01059     if (err) {
01060        MP_TO_SEC_ERROR(err);
01061        rv = SECFailure;
01062     }
01063 
01064 #if EC_DEBUG
01065     printf("ECDSA verification %s\n",
01066        (rv == SECSuccess) ? "succeeded" : "failed");
01067 #endif
01068 #else
01069     PORT_SetError(SEC_ERROR_UNSUPPORTED_KEYALG);
01070 #endif /* NSS_ENABLE_ECC */
01071 
01072     return rv;
01073 }
01074