ecs_ossl.c revision 167613
14Srgrimes/* crypto/ecdsa/ecs_ossl.c */ 24Srgrimes/* 3209371Smav * Written by Nils Larsch for the OpenSSL project 44Srgrimes */ 54Srgrimes/* ==================================================================== 64Srgrimes * Copyright (c) 1998-2004 The OpenSSL Project. All rights reserved. 74Srgrimes * 84Srgrimes * Redistribution and use in source and binary forms, with or without 94Srgrimes * modification, are permitted provided that the following conditions 104Srgrimes * are met: 114Srgrimes * 124Srgrimes * 1. Redistributions of source code must retain the above copyright 134Srgrimes * notice, this list of conditions and the following disclaimer. 144Srgrimes * 154Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 164Srgrimes * notice, this list of conditions and the following disclaimer in 174Srgrimes * the documentation and/or other materials provided with the 184Srgrimes * distribution. 194Srgrimes * 204Srgrimes * 3. All advertising materials mentioning features or use of this 214Srgrimes * software must display the following acknowledgment: 224Srgrimes * "This product includes software developed by the OpenSSL Project 234Srgrimes * for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)" 244Srgrimes * 254Srgrimes * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 264Srgrimes * endorse or promote products derived from this software without 274Srgrimes * prior written permission. For written permission, please contact 284Srgrimes * openssl-core@OpenSSL.org. 294Srgrimes * 304Srgrimes * 5. Products derived from this software may not be called "OpenSSL" 314Srgrimes * nor may "OpenSSL" appear in their names without prior written 324Srgrimes * permission of the OpenSSL Project. 33619Srgrimes * 344Srgrimes * 6. Redistributions of any form whatsoever must retain the following 354Srgrimes * acknowledgment: 36115703Sobrien * "This product includes software developed by the OpenSSL Project 37115703Sobrien * for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)" 38115703Sobrien * 393185Ssos * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 4019173Sbde * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4119173Sbde * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 4219173Sbde * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 4316299Spst * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 4489980Sbde * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 4571797Speter * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 4613228Swollman * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 472056Swollman * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 482056Swollman * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 4961994Smsmith * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 5074914Sjhb * OF THE POSSIBILITY OF SUCH DAMAGE. 51131938Smarcel * ==================================================================== 5267356Sjhb * 5365557Sjasone * This product includes cryptographic software written by Eric Young 542056Swollman * (eay@cryptsoft.com). This product includes software written by Tim 55129876Sphk * Hudson (tjh@cryptsoft.com). 56209371Smav * 57153384Speter */ 58191745Smav 5915508Sbde#include "ecs_locl.h" 60209371Smav#include <openssl/err.h> 61209371Smav#include <openssl/obj_mac.h> 6215508Sbde#include <openssl/bn.h> 634180Sbde 64153666Sjhbstatic ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dlen, 65121986Sjhb const BIGNUM *, const BIGNUM *, EC_KEY *eckey); 66146211Snyanstatic int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, 67146211Snyan BIGNUM **rp); 6815508Sbdestatic int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, 69209979Smav const ECDSA_SIG *sig, EC_KEY *eckey); 70209979Smav 71209979Smavstatic ECDSA_METHOD openssl_ecdsa_meth = { 7247642Sdfr "OpenSSL ECDSA method", 73209979Smav ecdsa_do_sign, 7489980Sbde ecdsa_sign_setup, 75209979Smav ecdsa_do_verify, 76209979Smav#if 0 77209979Smav NULL, /* init */ 78146211Snyan NULL, /* finish */ 79209979Smav#endif 8061994Smsmith 0, /* flags */ 8189980Sbde NULL /* app_data */ 824Srgrimes}; 8371797Speter 84112551Smdoddconst ECDSA_METHOD *ECDSA_OpenSSL(void) 8550823Smdodd{ 8650823Smdodd return &openssl_ecdsa_meth; 8747588Sbde} 8833690Sphk 89209979Smavstatic int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, 90209979Smav BIGNUM **rp) 91209979Smav{ 9233690Sphk BN_CTX *ctx = NULL; 9333690Sphk BIGNUM *k = NULL, *r = NULL, *order = NULL, *X = NULL; 94209979Smav EC_POINT *tmp_point=NULL; 95177631Sphk const EC_GROUP *group; 96177631Sphk int ret = 0; 97177631Sphk 98212778Smav if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) 991390Ssos { 100178193Sphk ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_PASSED_NULL_PARAMETER); 101128695Sjhb return 0; 102209371Smav } 103209371Smav 104128695Sjhb if (ctx_in == NULL) 10533690Sphk { 10617231Sjoerg if ((ctx = BN_CTX_new()) == NULL) 107209371Smav { 108209371Smav ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,ERR_R_MALLOC_FAILURE); 109209927Smav return 0; 110209927Smav } 111209371Smav } 112209979Smav else 113209979Smav ctx = ctx_in; 114209979Smav 115209979Smav k = BN_new(); /* this value is later returned in *kinvp */ 116209371Smav r = BN_new(); /* this value is later returned in *rp */ 117209371Smav order = BN_new(); 118209371Smav X = BN_new(); 119212778Smav if (!k || !r || !order || !X) 120212778Smav { 121212778Smav ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE); 122212778Smav goto err; 123212778Smav } 124209371Smav if ((tmp_point = EC_POINT_new(group)) == NULL) 125209371Smav { 126209371Smav ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); 127212812Smav goto err; 128212812Smav } 12917231Sjoerg if (!EC_GROUP_get_order(group, order, ctx)) 13017236Sjoerg { 13117236Sjoerg ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); 13217236Sjoerg goto err; 13317236Sjoerg } 13417231Sjoerg 13517231Sjoerg do 1364180Sbde { 13792765Salfred /* get random k */ 138212778Smav do 13917353Sbde if (!BN_rand_range(k, order)) 140166901Spiso { 141209371Smav ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, 1422074Swollman ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED); 143209371Smav goto err; 14465557Sjasone } 145212778Smav while (BN_is_zero(k)); 14672200Sbmilekic 14747588Sbde /* compute r the x-coordinate of generator * k */ 14839503Sbde if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) 14947588Sbde { 150177631Sphk ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); 15139503Sbde goto err; 15239503Sbde } 15347588Sbde if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) == NID_X9_62_prime_field) 15472200Sbmilekic { 15539503Sbde if (!EC_POINT_get_affine_coordinates_GFp(group, 156179278Sjb tmp_point, X, NULL, ctx)) 157212778Smav { 158209990Smav ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,ERR_R_EC_LIB); 159179278Sjb goto err; 16071797Speter } 16150823Smdodd } 16250823Smdodd else /* NID_X9_62_characteristic_two_field */ 16350823Smdodd { 16450823Smdodd if (!EC_POINT_get_affine_coordinates_GF2m(group, 165166901Spiso tmp_point, X, NULL, ctx)) 1661390Ssos { 1671390Ssos ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,ERR_R_EC_LIB); 168120404Simp goto err; 169177642Sphk } 1701390Ssos } 171177642Sphk if (!BN_nnmod(r, X, order, ctx)) 17217231Sjoerg { 173209979Smav ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); 174209979Smav goto err; 175209979Smav } 176177642Sphk } 177209979Smav while (BN_is_zero(r)); 178177642Sphk 17917231Sjoerg /* compute the inverse of k */ 18017231Sjoerg if (!BN_mod_inverse(k, k, order, ctx)) 18117231Sjoerg { 18217236Sjoerg ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); 18317236Sjoerg goto err; 18417236Sjoerg } 18517236Sjoerg /* clear old values if necessary */ 18617236Sjoerg if (*rp != NULL) 18717236Sjoerg BN_clear_free(*rp); 18817236Sjoerg if (*kinvp != NULL) 18917236Sjoerg BN_clear_free(*kinvp); 190209979Smav /* save the pre-computed values */ 191209979Smav *rp = r; 192209979Smav *kinvp = k; 19317236Sjoerg ret = 1; 194209979Smaverr: 195177642Sphk if (!ret) 19617231Sjoerg { 1971390Ssos if (k != NULL) BN_clear_free(k); 1981390Ssos if (r != NULL) BN_clear_free(r); 199120404Simp } 200177642Sphk if (ctx_in == NULL) 2011390Ssos BN_CTX_free(ctx); 20217231Sjoerg if (order != NULL) 20317231Sjoerg BN_free(order); 20417231Sjoerg if (tmp_point != NULL) 20517231Sjoerg EC_POINT_free(tmp_point); 206209979Smav if (X) 207209979Smav BN_clear_free(X); 208209979Smav return(ret); 20917236Sjoerg} 210209979Smav 211177642Sphk 21217231Sjoergstatic ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dgst_len, 2131390Ssos const BIGNUM *in_kinv, const BIGNUM *in_r, EC_KEY *eckey) 2141390Ssos{ 215177642Sphk int ok = 0; 216177642Sphk BIGNUM *kinv=NULL, *s, *m=NULL,*tmp=NULL,*order=NULL; 217177642Sphk const BIGNUM *ckinv; 218177642Sphk BN_CTX *ctx = NULL; 219177642Sphk const EC_GROUP *group; 220177642Sphk ECDSA_SIG *ret; 221209979Smav ECDSA_DATA *ecdsa; 222209979Smav const BIGNUM *priv_key; 223209979Smav 224209979Smav ecdsa = ecdsa_check(eckey); 225177642Sphk group = EC_KEY_get0_group(eckey); 226177642Sphk priv_key = EC_KEY_get0_private_key(eckey); 227209979Smav 228177642Sphk if (group == NULL || priv_key == NULL || ecdsa == NULL) 229177642Sphk { 230177642Sphk ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_PASSED_NULL_PARAMETER); 231166901Spiso return NULL; 23210268Sbde } 2331390Ssos 23466716Sjhb ret = ECDSA_SIG_new(); 2351390Ssos if (!ret) 236131991Smarcel { 23716428Sbde ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE); 23816428Sbde return NULL; 23919173Sbde } 24016428Sbde s = ret->s; 2411390Ssos 2421390Ssos if ((ctx = BN_CTX_new()) == NULL || (order = BN_new()) == NULL || 24316428Sbde (tmp = BN_new()) == NULL || (m = BN_new()) == NULL) 244131991Smarcel { 2451390Ssos ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE); 2461390Ssos goto err; 2471390Ssos } 2482017Swollman 2491390Ssos if (!EC_GROUP_get_order(group, order, ctx)) 250177631Sphk { 2511390Ssos ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_EC_LIB); 2521390Ssos goto err; 2531390Ssos } 2541390Ssos if (dgst_len > BN_num_bytes(order)) 2551390Ssos { 25622106Sbde ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, 2571390Ssos ECDSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE); 2581390Ssos goto err; 2591390Ssos } 2601390Ssos 2611390Ssos if (!BN_bin2bn(dgst, dgst_len, m)) 262153384Speter { 2631390Ssos ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); 264153384Speter goto err; 265153384Speter } 266153384Speter do 267153384Speter { 268153384Speter if (in_kinv == NULL || in_r == NULL) 269153384Speter { 270153384Speter if (!ECDSA_sign_setup(eckey, ctx, &kinv, &ret->r)) 271175405Sjhb { 272153384Speter ECDSAerr(ECDSA_F_ECDSA_DO_SIGN,ERR_R_ECDSA_LIB); 273153384Speter goto err; 274153384Speter } 275153384Speter ckinv = kinv; 276153384Speter } 277153384Speter else 2781390Ssos { 2791390Ssos ckinv = in_kinv; 2801390Ssos if (BN_copy(ret->r, in_r) == NULL) 2811390Ssos { 2821390Ssos ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE); 2831390Ssos goto err; 2841390Ssos } 2851390Ssos } 2861390Ssos 2871390Ssos if (!BN_mod_mul(tmp, priv_key, ret->r, order, ctx)) 2881390Ssos { 2891390Ssos ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); 2901390Ssos goto err; 2911390Ssos } 2921390Ssos if (!BN_mod_add_quick(s, tmp, m, order)) 293131991Smarcel { 294131991Smarcel ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); 295131991Smarcel goto err; 296131991Smarcel } 297131991Smarcel if (!BN_mod_mul(s, s, ckinv, order, ctx)) 2981390Ssos { 299131991Smarcel ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); 300131991Smarcel goto err; 301131991Smarcel } 302131991Smarcel if (BN_is_zero(s)) 303131991Smarcel { 304131991Smarcel /* if kinv and r have been supplied by the caller 30522106Sbde * don't to generate new kinv and r values */ 3061390Ssos if (in_kinv != NULL && in_r != NULL) 307177631Sphk { 3081390Ssos ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ECDSA_R_NEED_NEW_SETUP_VALUES); 3091390Ssos goto err; 31022106Sbde } 31122106Sbde } 31222106Sbde else 31322106Sbde /* s != 0 => we have a valid signature */ 31422106Sbde break; 31522106Sbde } 31622106Sbde while (1); 31722106Sbde 31822106Sbde ok = 1; 31922106Sbdeerr: 32022106Sbde if (!ok) 32122106Sbde { 32222106Sbde ECDSA_SIG_free(ret); 32322106Sbde ret = NULL; 32422106Sbde } 32522106Sbde if (ctx) 32622106Sbde BN_CTX_free(ctx); 327177631Sphk if (m) 32822106Sbde BN_clear_free(m); 3291390Ssos if (tmp) 3301390Ssos BN_clear_free(tmp); 331131991Smarcel if (order) 332131991Smarcel BN_free(order); 333209979Smav if (kinv) 334209979Smav BN_clear_free(kinv); 335209979Smav return ret; 336131991Smarcel} 337209979Smav 338131991Smarcelstatic int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, 339131991Smarcel const ECDSA_SIG *sig, EC_KEY *eckey) 340177631Sphk{ 341131991Smarcel int ret = -1; 342131991Smarcel BN_CTX *ctx; 343131991Smarcel BIGNUM *order, *u1, *u2, *m, *X; 3441390Ssos EC_POINT *point = NULL; 3451390Ssos const EC_GROUP *group; 3461390Ssos const EC_POINT *pub_key; 34721783Sbde 3481390Ssos /* check input values */ 34921783Sbde if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL || 350177631Sphk (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || sig == NULL) 35121783Sbde { 352177631Sphk ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_MISSING_PARAMETERS); 35321783Sbde return -1; 354177631Sphk } 35521783Sbde 35621783Sbde ctx = BN_CTX_new(); 35721783Sbde if (!ctx) 35821783Sbde { 35921783Sbde ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_MALLOC_FAILURE); 36021783Sbde return -1; 3611390Ssos } 3621390Ssos BN_CTX_start(ctx); 3631390Ssos order = BN_CTX_get(ctx); 3641390Ssos u1 = BN_CTX_get(ctx); 3651390Ssos u2 = BN_CTX_get(ctx); 3661390Ssos m = BN_CTX_get(ctx); 3671390Ssos X = BN_CTX_get(ctx); 3681390Ssos if (!X) 36915508Sbde { 370212778Smav ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 37115508Sbde goto err; 372212812Smav } 37315508Sbde 37472200Sbmilekic if (!EC_GROUP_get_order(group, order, ctx)) 375212812Smav { 376212812Smav ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB); 377212812Smav goto err; 378212812Smav } 379212812Smav 380212812Smav if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || 381212812Smav BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s) || 382212812Smav BN_is_negative(sig->s) || BN_ucmp(sig->s, order) >= 0) 383212812Smav { 384212812Smav ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_BAD_SIGNATURE); 385212812Smav ret = 0; /* signature is invalid */ 386212812Smav goto err; 387212812Smav } 388212812Smav /* calculate tmp1 = inv(S) mod order */ 389212778Smav if (!BN_mod_inverse(u2, sig->s, order, ctx)) 390212778Smav { 391212778Smav ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 392212812Smav goto err; 393212812Smav } 394212778Smav /* digest -> m */ 395212778Smav if (!BN_bin2bn(dgst, dgst_len, m)) 396147727Sjhb { 397212812Smav ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 398212812Smav goto err; 399212778Smav } 400212778Smav /* u1 = m * tmp mod order */ 401212778Smav if (!BN_mod_mul(u1, m, u2, order, ctx)) 402212812Smav { 403212812Smav ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 404212778Smav goto err; 40533309Sbde } 406212812Smav /* u2 = r * w mod q */ 40772200Sbmilekic if (!BN_mod_mul(u2, sig->r, u2, order, ctx)) 40815508Sbde { 40915508Sbde ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 41082971Siwasaki goto err; 41152669Siwasaki } 41252669Siwasaki 41352669Siwasaki if ((point = EC_POINT_new(group)) == NULL) 414212812Smav { 415212812Smav ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_MALLOC_FAILURE); 416212778Smav goto err; 417212778Smav } 418212778Smav if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx)) 41952669Siwasaki { 42052669Siwasaki ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB); 421204309Sattilio goto err; 42252669Siwasaki } 423105328Siwasaki if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) == NID_X9_62_prime_field) 424105328Siwasaki { 425105328Siwasaki if (!EC_POINT_get_affine_coordinates_GFp(group, 426105328Siwasaki point, X, NULL, ctx)) 427105328Siwasaki { 428204309Sattilio ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB); 429204309Sattilio goto err; 43082971Siwasaki } 43182971Siwasaki } 43282971Siwasaki else /* NID_X9_62_characteristic_two_field */ 43382971Siwasaki { 43482971Siwasaki if (!EC_POINT_get_affine_coordinates_GF2m(group, 435177631Sphk point, X, NULL, ctx)) 436209979Smav { 437178193Sphk ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB); 438209979Smav goto err; 43982971Siwasaki } 440204309Sattilio } 44182971Siwasaki 442166186Sbde if (!BN_nnmod(u1, X, order, ctx)) 4431390Ssos { 444166186Sbde ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 445166186Sbde goto err; 446166186Sbde } 447166186Sbde /* if the signature is correct u1 is equal to sig->r */ 448209979Smav ret = (BN_ucmp(u1, sig->r) == 0); 449209979Smaverr: 450209979Smav BN_CTX_end(ctx); 451209979Smav BN_CTX_free(ctx); 452212778Smav if (point) 453166186Sbde EC_POINT_free(point); 454166186Sbde return ret; 455166186Sbde} 4568876Srgrimes