ecs_ossl.c revision 160814
1160814Ssimon/* crypto/ecdsa/ecs_ossl.c */ 2160814Ssimon/* 3160814Ssimon * Written by Nils Larsch for the OpenSSL project 4160814Ssimon */ 5160814Ssimon/* ==================================================================== 6160814Ssimon * Copyright (c) 1998-2004 The OpenSSL Project. All rights reserved. 7160814Ssimon * 8160814Ssimon * Redistribution and use in source and binary forms, with or without 9160814Ssimon * modification, are permitted provided that the following conditions 10160814Ssimon * are met: 11160814Ssimon * 12160814Ssimon * 1. Redistributions of source code must retain the above copyright 13160814Ssimon * notice, this list of conditions and the following disclaimer. 14160814Ssimon * 15160814Ssimon * 2. Redistributions in binary form must reproduce the above copyright 16160814Ssimon * notice, this list of conditions and the following disclaimer in 17160814Ssimon * the documentation and/or other materials provided with the 18160814Ssimon * distribution. 19160814Ssimon * 20160814Ssimon * 3. All advertising materials mentioning features or use of this 21160814Ssimon * software must display the following acknowledgment: 22160814Ssimon * "This product includes software developed by the OpenSSL Project 23160814Ssimon * for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)" 24160814Ssimon * 25160814Ssimon * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 26160814Ssimon * endorse or promote products derived from this software without 27160814Ssimon * prior written permission. For written permission, please contact 28160814Ssimon * openssl-core@OpenSSL.org. 29160814Ssimon * 30160814Ssimon * 5. Products derived from this software may not be called "OpenSSL" 31160814Ssimon * nor may "OpenSSL" appear in their names without prior written 32160814Ssimon * permission of the OpenSSL Project. 33160814Ssimon * 34160814Ssimon * 6. Redistributions of any form whatsoever must retain the following 35160814Ssimon * acknowledgment: 36160814Ssimon * "This product includes software developed by the OpenSSL Project 37160814Ssimon * for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)" 38160814Ssimon * 39160814Ssimon * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 40160814Ssimon * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 41160814Ssimon * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 42160814Ssimon * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 43160814Ssimon * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 44160814Ssimon * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 45160814Ssimon * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 46160814Ssimon * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47160814Ssimon * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 48160814Ssimon * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 49160814Ssimon * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 50160814Ssimon * OF THE POSSIBILITY OF SUCH DAMAGE. 51160814Ssimon * ==================================================================== 52160814Ssimon * 53160814Ssimon * This product includes cryptographic software written by Eric Young 54160814Ssimon * (eay@cryptsoft.com). This product includes software written by Tim 55160814Ssimon * Hudson (tjh@cryptsoft.com). 56160814Ssimon * 57160814Ssimon */ 58160814Ssimon 59160814Ssimon#include "ecs_locl.h" 60160814Ssimon#include <openssl/err.h> 61160814Ssimon#include <openssl/obj_mac.h> 62160814Ssimon#include <openssl/bn.h> 63160814Ssimon 64160814Ssimonstatic ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dlen, 65160814Ssimon const BIGNUM *, const BIGNUM *, EC_KEY *eckey); 66160814Ssimonstatic int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, 67160814Ssimon BIGNUM **rp); 68160814Ssimonstatic int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, 69160814Ssimon const ECDSA_SIG *sig, EC_KEY *eckey); 70160814Ssimon 71160814Ssimonstatic ECDSA_METHOD openssl_ecdsa_meth = { 72160814Ssimon "OpenSSL ECDSA method", 73160814Ssimon ecdsa_do_sign, 74160814Ssimon ecdsa_sign_setup, 75160814Ssimon ecdsa_do_verify, 76160814Ssimon#if 0 77160814Ssimon NULL, /* init */ 78160814Ssimon NULL, /* finish */ 79160814Ssimon#endif 80160814Ssimon 0, /* flags */ 81160814Ssimon NULL /* app_data */ 82160814Ssimon}; 83160814Ssimon 84160814Ssimonconst ECDSA_METHOD *ECDSA_OpenSSL(void) 85160814Ssimon{ 86160814Ssimon return &openssl_ecdsa_meth; 87160814Ssimon} 88160814Ssimon 89160814Ssimonstatic int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, 90160814Ssimon BIGNUM **rp) 91160814Ssimon{ 92160814Ssimon BN_CTX *ctx = NULL; 93160814Ssimon BIGNUM *k = NULL, *r = NULL, *order = NULL, *X = NULL; 94160814Ssimon EC_POINT *tmp_point=NULL; 95160814Ssimon const EC_GROUP *group; 96160814Ssimon int ret = 0; 97160814Ssimon 98160814Ssimon if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) 99160814Ssimon { 100160814Ssimon ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_PASSED_NULL_PARAMETER); 101160814Ssimon return 0; 102160814Ssimon } 103160814Ssimon 104160814Ssimon if (ctx_in == NULL) 105160814Ssimon { 106160814Ssimon if ((ctx = BN_CTX_new()) == NULL) 107160814Ssimon { 108160814Ssimon ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,ERR_R_MALLOC_FAILURE); 109160814Ssimon return 0; 110160814Ssimon } 111160814Ssimon } 112160814Ssimon else 113160814Ssimon ctx = ctx_in; 114160814Ssimon 115160814Ssimon k = BN_new(); /* this value is later returned in *kinvp */ 116160814Ssimon r = BN_new(); /* this value is later returned in *rp */ 117160814Ssimon order = BN_new(); 118160814Ssimon X = BN_new(); 119160814Ssimon if (!k || !r || !order || !X) 120160814Ssimon { 121160814Ssimon ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE); 122160814Ssimon goto err; 123160814Ssimon } 124160814Ssimon if ((tmp_point = EC_POINT_new(group)) == NULL) 125160814Ssimon { 126160814Ssimon ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); 127160814Ssimon goto err; 128160814Ssimon } 129160814Ssimon if (!EC_GROUP_get_order(group, order, ctx)) 130160814Ssimon { 131160814Ssimon ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); 132160814Ssimon goto err; 133160814Ssimon } 134160814Ssimon 135160814Ssimon do 136160814Ssimon { 137160814Ssimon /* get random k */ 138160814Ssimon do 139160814Ssimon if (!BN_rand_range(k, order)) 140160814Ssimon { 141160814Ssimon ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, 142160814Ssimon ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED); 143160814Ssimon goto err; 144160814Ssimon } 145160814Ssimon while (BN_is_zero(k)); 146160814Ssimon 147160814Ssimon /* compute r the x-coordinate of generator * k */ 148160814Ssimon if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) 149160814Ssimon { 150160814Ssimon ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); 151160814Ssimon goto err; 152160814Ssimon } 153160814Ssimon if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) == NID_X9_62_prime_field) 154160814Ssimon { 155160814Ssimon if (!EC_POINT_get_affine_coordinates_GFp(group, 156160814Ssimon tmp_point, X, NULL, ctx)) 157160814Ssimon { 158160814Ssimon ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,ERR_R_EC_LIB); 159160814Ssimon goto err; 160160814Ssimon } 161160814Ssimon } 162160814Ssimon else /* NID_X9_62_characteristic_two_field */ 163160814Ssimon { 164160814Ssimon if (!EC_POINT_get_affine_coordinates_GF2m(group, 165160814Ssimon tmp_point, X, NULL, ctx)) 166160814Ssimon { 167160814Ssimon ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,ERR_R_EC_LIB); 168160814Ssimon goto err; 169160814Ssimon } 170160814Ssimon } 171160814Ssimon if (!BN_nnmod(r, X, order, ctx)) 172160814Ssimon { 173160814Ssimon ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); 174160814Ssimon goto err; 175160814Ssimon } 176160814Ssimon } 177160814Ssimon while (BN_is_zero(r)); 178160814Ssimon 179160814Ssimon /* compute the inverse of k */ 180160814Ssimon if (!BN_mod_inverse(k, k, order, ctx)) 181160814Ssimon { 182160814Ssimon ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); 183160814Ssimon goto err; 184160814Ssimon } 185160814Ssimon /* clear old values if necessary */ 186160814Ssimon if (*rp != NULL) 187160814Ssimon BN_clear_free(*rp); 188160814Ssimon if (*kinvp != NULL) 189160814Ssimon BN_clear_free(*kinvp); 190160814Ssimon /* save the pre-computed values */ 191160814Ssimon *rp = r; 192160814Ssimon *kinvp = k; 193160814Ssimon ret = 1; 194160814Ssimonerr: 195160814Ssimon if (!ret) 196160814Ssimon { 197160814Ssimon if (k != NULL) BN_clear_free(k); 198160814Ssimon if (r != NULL) BN_clear_free(r); 199160814Ssimon } 200160814Ssimon if (ctx_in == NULL) 201160814Ssimon BN_CTX_free(ctx); 202160814Ssimon if (order != NULL) 203160814Ssimon BN_free(order); 204160814Ssimon if (tmp_point != NULL) 205160814Ssimon EC_POINT_free(tmp_point); 206160814Ssimon if (X) 207160814Ssimon BN_clear_free(X); 208160814Ssimon return(ret); 209160814Ssimon} 210160814Ssimon 211160814Ssimon 212160814Ssimonstatic ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dgst_len, 213160814Ssimon const BIGNUM *in_kinv, const BIGNUM *in_r, EC_KEY *eckey) 214160814Ssimon{ 215160814Ssimon int ok = 0; 216160814Ssimon BIGNUM *kinv=NULL, *s, *m=NULL,*tmp=NULL,*order=NULL; 217160814Ssimon const BIGNUM *ckinv; 218160814Ssimon BN_CTX *ctx = NULL; 219160814Ssimon const EC_GROUP *group; 220160814Ssimon ECDSA_SIG *ret; 221160814Ssimon ECDSA_DATA *ecdsa; 222160814Ssimon const BIGNUM *priv_key; 223160814Ssimon 224160814Ssimon ecdsa = ecdsa_check(eckey); 225160814Ssimon group = EC_KEY_get0_group(eckey); 226160814Ssimon priv_key = EC_KEY_get0_private_key(eckey); 227160814Ssimon 228160814Ssimon if (group == NULL || priv_key == NULL || ecdsa == NULL) 229160814Ssimon { 230160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_PASSED_NULL_PARAMETER); 231160814Ssimon return NULL; 232160814Ssimon } 233160814Ssimon 234160814Ssimon ret = ECDSA_SIG_new(); 235160814Ssimon if (!ret) 236160814Ssimon { 237160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE); 238160814Ssimon return NULL; 239160814Ssimon } 240160814Ssimon s = ret->s; 241160814Ssimon 242160814Ssimon if ((ctx = BN_CTX_new()) == NULL || (order = BN_new()) == NULL || 243160814Ssimon (tmp = BN_new()) == NULL || (m = BN_new()) == NULL) 244160814Ssimon { 245160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE); 246160814Ssimon goto err; 247160814Ssimon } 248160814Ssimon 249160814Ssimon if (!EC_GROUP_get_order(group, order, ctx)) 250160814Ssimon { 251160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_EC_LIB); 252160814Ssimon goto err; 253160814Ssimon } 254160814Ssimon if (dgst_len > BN_num_bytes(order)) 255160814Ssimon { 256160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, 257160814Ssimon ECDSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE); 258160814Ssimon goto err; 259160814Ssimon } 260160814Ssimon 261160814Ssimon if (!BN_bin2bn(dgst, dgst_len, m)) 262160814Ssimon { 263160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); 264160814Ssimon goto err; 265160814Ssimon } 266160814Ssimon do 267160814Ssimon { 268160814Ssimon if (in_kinv == NULL || in_r == NULL) 269160814Ssimon { 270160814Ssimon if (!ECDSA_sign_setup(eckey, ctx, &kinv, &ret->r)) 271160814Ssimon { 272160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_SIGN,ERR_R_ECDSA_LIB); 273160814Ssimon goto err; 274160814Ssimon } 275160814Ssimon ckinv = kinv; 276160814Ssimon } 277160814Ssimon else 278160814Ssimon { 279160814Ssimon ckinv = in_kinv; 280160814Ssimon if (BN_copy(ret->r, in_r) == NULL) 281160814Ssimon { 282160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE); 283160814Ssimon goto err; 284160814Ssimon } 285160814Ssimon } 286160814Ssimon 287160814Ssimon if (!BN_mod_mul(tmp, priv_key, ret->r, order, ctx)) 288160814Ssimon { 289160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); 290160814Ssimon goto err; 291160814Ssimon } 292160814Ssimon if (!BN_mod_add_quick(s, tmp, m, order)) 293160814Ssimon { 294160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); 295160814Ssimon goto err; 296160814Ssimon } 297160814Ssimon if (!BN_mod_mul(s, s, ckinv, order, ctx)) 298160814Ssimon { 299160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); 300160814Ssimon goto err; 301160814Ssimon } 302160814Ssimon } 303160814Ssimon while (BN_is_zero(s)); 304160814Ssimon 305160814Ssimon ok = 1; 306160814Ssimonerr: 307160814Ssimon if (!ok) 308160814Ssimon { 309160814Ssimon ECDSA_SIG_free(ret); 310160814Ssimon ret = NULL; 311160814Ssimon } 312160814Ssimon if (ctx) 313160814Ssimon BN_CTX_free(ctx); 314160814Ssimon if (m) 315160814Ssimon BN_clear_free(m); 316160814Ssimon if (tmp) 317160814Ssimon BN_clear_free(tmp); 318160814Ssimon if (order) 319160814Ssimon BN_free(order); 320160814Ssimon if (kinv) 321160814Ssimon BN_clear_free(kinv); 322160814Ssimon return ret; 323160814Ssimon} 324160814Ssimon 325160814Ssimonstatic int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, 326160814Ssimon const ECDSA_SIG *sig, EC_KEY *eckey) 327160814Ssimon{ 328160814Ssimon int ret = -1; 329160814Ssimon BN_CTX *ctx; 330160814Ssimon BIGNUM *order, *u1, *u2, *m, *X; 331160814Ssimon EC_POINT *point = NULL; 332160814Ssimon const EC_GROUP *group; 333160814Ssimon const EC_POINT *pub_key; 334160814Ssimon 335160814Ssimon /* check input values */ 336160814Ssimon if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL || 337160814Ssimon (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || sig == NULL) 338160814Ssimon { 339160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_MISSING_PARAMETERS); 340160814Ssimon return -1; 341160814Ssimon } 342160814Ssimon 343160814Ssimon ctx = BN_CTX_new(); 344160814Ssimon if (!ctx) 345160814Ssimon { 346160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_MALLOC_FAILURE); 347160814Ssimon return -1; 348160814Ssimon } 349160814Ssimon BN_CTX_start(ctx); 350160814Ssimon order = BN_CTX_get(ctx); 351160814Ssimon u1 = BN_CTX_get(ctx); 352160814Ssimon u2 = BN_CTX_get(ctx); 353160814Ssimon m = BN_CTX_get(ctx); 354160814Ssimon X = BN_CTX_get(ctx); 355160814Ssimon if (!X) 356160814Ssimon { 357160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 358160814Ssimon goto err; 359160814Ssimon } 360160814Ssimon 361160814Ssimon if (!EC_GROUP_get_order(group, order, ctx)) 362160814Ssimon { 363160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB); 364160814Ssimon goto err; 365160814Ssimon } 366160814Ssimon 367160814Ssimon if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || 368160814Ssimon BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s) || 369160814Ssimon BN_is_negative(sig->s) || BN_ucmp(sig->s, order) >= 0) 370160814Ssimon { 371160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_BAD_SIGNATURE); 372160814Ssimon ret = 0; /* signature is invalid */ 373160814Ssimon goto err; 374160814Ssimon } 375160814Ssimon /* calculate tmp1 = inv(S) mod order */ 376160814Ssimon if (!BN_mod_inverse(u2, sig->s, order, ctx)) 377160814Ssimon { 378160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 379160814Ssimon goto err; 380160814Ssimon } 381160814Ssimon /* digest -> m */ 382160814Ssimon if (!BN_bin2bn(dgst, dgst_len, m)) 383160814Ssimon { 384160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 385160814Ssimon goto err; 386160814Ssimon } 387160814Ssimon /* u1 = m * tmp mod order */ 388160814Ssimon if (!BN_mod_mul(u1, m, u2, order, ctx)) 389160814Ssimon { 390160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 391160814Ssimon goto err; 392160814Ssimon } 393160814Ssimon /* u2 = r * w mod q */ 394160814Ssimon if (!BN_mod_mul(u2, sig->r, u2, order, ctx)) 395160814Ssimon { 396160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 397160814Ssimon goto err; 398160814Ssimon } 399160814Ssimon 400160814Ssimon if ((point = EC_POINT_new(group)) == NULL) 401160814Ssimon { 402160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_MALLOC_FAILURE); 403160814Ssimon goto err; 404160814Ssimon } 405160814Ssimon if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx)) 406160814Ssimon { 407160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB); 408160814Ssimon goto err; 409160814Ssimon } 410160814Ssimon if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) == NID_X9_62_prime_field) 411160814Ssimon { 412160814Ssimon if (!EC_POINT_get_affine_coordinates_GFp(group, 413160814Ssimon point, X, NULL, ctx)) 414160814Ssimon { 415160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB); 416160814Ssimon goto err; 417160814Ssimon } 418160814Ssimon } 419160814Ssimon else /* NID_X9_62_characteristic_two_field */ 420160814Ssimon { 421160814Ssimon if (!EC_POINT_get_affine_coordinates_GF2m(group, 422160814Ssimon point, X, NULL, ctx)) 423160814Ssimon { 424160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB); 425160814Ssimon goto err; 426160814Ssimon } 427160814Ssimon } 428160814Ssimon 429160814Ssimon if (!BN_nnmod(u1, X, order, ctx)) 430160814Ssimon { 431160814Ssimon ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 432160814Ssimon goto err; 433160814Ssimon } 434160814Ssimon /* if the signature is correct u1 is equal to sig->r */ 435160814Ssimon ret = (BN_ucmp(u1, sig->r) == 0); 436160814Ssimonerr: 437160814Ssimon BN_CTX_end(ctx); 438160814Ssimon BN_CTX_free(ctx); 439160814Ssimon if (point) 440160814Ssimon EC_POINT_free(point); 441160814Ssimon return ret; 442160814Ssimon} 443