crypto/ecdsa/ecs_ossl.c

   1 /* crypto/ecdsa/ecs_ossl.c */
   2 /* ====================================================================
   3  * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  *
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in
  14  *    the documentation and/or other materials provided with the
  15  *    distribution.
  16  *
  17  * 3. All advertising materials mentioning features or use of this
  18  *    software must display the following acknowledgment:
  19  *    "This product includes software developed by the OpenSSL Project
  20  *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
  21  *
  22  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  23  *    endorse or promote products derived from this software without
  24  *    prior written permission. For written permission, please contact
  25  *    openssl-core@OpenSSL.org.
  26  *
  27  * 5. Products derived from this software may not be called "OpenSSL"
  28  *    nor may "OpenSSL" appear in their names without prior written
  29  *    permission of the OpenSSL Project.
  30  *
  31  * 6. Redistributions of any form whatsoever must retain the following
  32  *    acknowledgment:
  33  *    "This product includes software developed by the OpenSSL Project
  34  *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
  35  *
  36  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  37  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  38  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  39  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  40  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  41  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  42  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  43  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  44  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  45  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  46  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  47  * OF THE POSSIBILITY OF SUCH DAMAGE.
  48  * ====================================================================
  49  *
  50  * This product includes cryptographic software written by Eric Young
  51  * (eay@cryptsoft.com).  This product includes software written by Tim
  52  * Hudson (tjh@cryptsoft.com).
  53  *
  54  */
  55
  56 #include "ecdsa.h"
  57 #include <openssl/err.h>
  58 #include <openssl/obj_mac.h>
  59
  60 static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dlen,
  61                 EC_KEY *eckey);
  62 static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
  63                 BIGNUM **rp);
  64 static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len,
  65                 ECDSA_SIG *sig, EC_KEY *eckey);
  66
  67 static ECDSA_METHOD openssl_ecdsa_meth = {
  68         "OpenSSL ECDSA method",
  69         ecdsa_do_sign,
  70         ecdsa_sign_setup,
  71         ecdsa_do_verify,
  72 #if 0
  73         NULL, /* init     */
  74         NULL, /* finish   */
  75 #endif
  76         0,    /* flags    */
  77         NULL  /* app_data */
  78 };
  79
  80 const ECDSA_METHOD *ECDSA_OpenSSL(void)
  81 {
  82         return &openssl_ecdsa_meth;
  83 }
  84
  85 static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
  86                 BIGNUM **rp)
  87 {
  88         BN_CTX   *ctx = NULL;
  89         BIGNUM   k,*kinv=NULL,*r=NULL,*order=NULL,*X=NULL;
  90         EC_POINT *tmp_point=NULL;
  91         int      ret = 0;
  92         if (!eckey  || !eckey->group || !eckey->pub_key || !eckey->priv_key)
  93         {
  94                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_PASSED_NULL_PARAMETER);
  95                 return 0;
  96         }
  97         if (ctx_in == NULL)
  98         {
  99                 if ((ctx=BN_CTX_new()) == NULL)
 100                 {
 101                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE);
 102                 goto err;
 103                 }
 104         }
 105         else
 106                 ctx=ctx_in;
 107
 108         if ((r = BN_new()) == NULL)
 109         {
 110                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
 111                 goto err;
 112         }
 113         if ((order = BN_new()) == NULL)
 114         {
 115                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
 116                 goto err;
 117         }
 118         if ((X = BN_new()) == NULL)
 119         {
 120                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
 121                 goto err;
 122         }
 123         if ((tmp_point = EC_POINT_new(eckey->group)) == NULL)
 124         {
 125                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
 126                 goto err;
 127         }
 128         if (!EC_GROUP_get_order(eckey->group,order,ctx))
 129         {
 130                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
 131                 goto err;
 132         }
 133
 134         do
 135         {
 136                 /* get random k */
 137                 BN_init(&k);
 138                 do
 139                         if (!BN_rand_range(&k,order))
 140                         {
 141                                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,
 142                                  ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED);
 143                                 goto err;
 144                         }
 145                 while (BN_is_zero(&k));
 146
 147                 /* compute r the x-coordinate of generator * k */
 148                 if (!EC_POINT_mul(eckey->group, tmp_point, &k, NULL, NULL, ctx))
 149                 {
 150                         ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
 151                         goto err;
 152                 }
 153                 if (EC_METHOD_get_field_type(EC_GROUP_method_of(eckey->group))
 154                         == NID_X9_62_prime_field)
 155                 {
 156                         if (!EC_POINT_get_affine_coordinates_GFp(eckey->group,
 157                                 tmp_point, X, NULL, ctx))
 158                         {
 159                                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,
 160                                         ERR_R_EC_LIB);
 161                                 goto err;
 162                         }
 163                 }
 164                 else /* NID_X9_62_characteristic_two_field */
 165                 {
 166                         if (!EC_POINT_get_affine_coordinates_GF2m(eckey->group,
 167                                 tmp_point, X, NULL, ctx))
 168                         {
 169                                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,
 170                                         ERR_R_EC_LIB);
 171                                 goto err;
 172                         }
 173                 }
 174                 if (!BN_nnmod(r,X,order,ctx))
 175                 {
 176                         ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
 177                         goto err;
 178                 }
 179         }
 180         while (BN_is_zero(r));
 181
 182         /* compute the inverse of k */
 183         if ((kinv = BN_mod_inverse(NULL,&k,order,ctx)) == NULL)
 184         {
 185                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
 186                 goto err;
 187         }
 188
 189         if (*rp == NULL)
 190                 BN_clear_free(*rp);
 191         *rp = r;
 192         if (*kinvp == NULL)
 193                 BN_clear_free(*kinvp);
 194         *kinvp = kinv;
 195         kinv = NULL;
 196         ret = 1;
 197 err:
 198         if (!ret)
 199         {
 200                 if (kinv != NULL) BN_clear_free(kinv);
 201                 if (r != NULL) BN_clear_free(r);
 202         }
 203         if (ctx_in == NULL)
 204                 BN_CTX_free(ctx);
 205         if (kinv != NULL)
 206                 BN_clear_free(kinv);
 207         if (order != NULL)
 208                 BN_clear_free(order);
 209         if (tmp_point != NULL)
 210                 EC_POINT_free(tmp_point);
 211         if (X)  BN_clear_free(X);
 212         BN_clear_free(&k);
 213         return(ret);
 214 }
 215
 216
 217 static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dgst_len,
 218                 EC_KEY *eckey)
 219 {
 220         BIGNUM *kinv=NULL,*r=NULL,*s=NULL,*m=NULL,*tmp=NULL,*order=NULL;
 221         BIGNUM xr;
 222         BN_CTX *ctx=NULL;
 223         ECDSA_SIG *ret=NULL;
 224         ECDSA_DATA *ecdsa;
 225
 226         ecdsa = ecdsa_check(eckey);
 227
 228         if (!eckey || !eckey->group || !eckey->pub_key || !eckey->priv_key
 229                 || !ecdsa)
 230         {
 231                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_PASSED_NULL_PARAMETER);
 232                 goto err;
 233         }
 234         BN_init(&xr);
 235
 236         if ((ctx = BN_CTX_new()) == NULL || (order = BN_new()) == NULL ||
 237                 (tmp = BN_new()) == NULL || (m = BN_new()) == NULL ||
 238                 (s = BN_new()) == NULL )
 239         {
 240                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE);
 241                 goto err;
 242         }
 243
 244         if (!EC_GROUP_get_order(eckey->group,order,ctx))
 245         {
 246                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_EC_LIB);
 247                 goto err;
 248         }
 249         if (dgst_len > BN_num_bytes(order))
 250         {
 251                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN,
 252                         ECDSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE);
 253                 goto err;
 254         }
 255
 256         if (BN_bin2bn(dgst,dgst_len,m) == NULL)
 257         {
 258                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
 259                 goto err;
 260         }
 261         do
 262         {
 263                 if (ecdsa->kinv == NULL || ecdsa->r == NULL)
 264                 {
 265                         if (!ECDSA_sign_setup(eckey,ctx,&kinv,&r))
 266                         {
 267                                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN,
 268                                         ERR_R_ECDSA_LIB);
 269                                 goto err;
 270                         }
 271                 }
 272                 else
 273                 {
 274                         kinv = ecdsa->kinv;
 275                         ecdsa->kinv = NULL;
 276                         r = ecdsa->r;
 277                         ecdsa->r = NULL;
 278                 }
 279
 280                 if (!BN_mod_mul(tmp,eckey->priv_key,r,order,ctx))
 281                 {
 282                         ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
 283                         goto err;
 284                 }
 285                 if (!BN_add(s,tmp,m))
 286                 {
 287                         ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
 288                         goto err;
 289                 }
 290                 if (BN_cmp(s,order) > 0)
 291                         BN_sub(s,s,order);
 292                 if (!BN_mod_mul(s,s,kinv,order,ctx))
 293                 {
 294                         ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
 295                         goto err;
 296                 }
 297         }
 298         while (BN_is_zero(s));
 299
 300         if ((ret = ECDSA_SIG_new()) == NULL)
 301         {
 302                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE);
 303                 goto err;
 304         }
 305         if (BN_copy(ret->r, r) == NULL || BN_copy(ret->s, s) == NULL)
 306         {
 307                 ECDSA_SIG_free(ret);
 308                 ret = NULL;
 309                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
 310         }
 311
 312 err:
 313         if (r)
 314                 BN_clear_free(r);
 315         if (s)
 316                 BN_clear_free(s);
 317         if (ctx)
 318                 BN_CTX_free(ctx);
 319         if (m)
 320                 BN_clear_free(m);
 321         if (tmp)
 322                 BN_clear_free(tmp);
 323         if (order)
 324                 BN_clear_free(order);
 325         if (kinv)
 326                 BN_clear_free(kinv);
 327         return(ret);
 328 }
 329
 330 static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len,
 331                 ECDSA_SIG *sig, EC_KEY *eckey)
 332 {
 333         BN_CTX *ctx;
 334         BIGNUM *order=NULL,*u1=NULL,*u2=NULL,*m=NULL,*X=NULL;
 335         EC_POINT *point=NULL;
 336         int ret = -1;
 337         if (!eckey || !eckey->group || !eckey->pub_key || !sig)
 338         {
 339                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_MISSING_PARAMETERS);
 340                 return -1;
 341         }
 342
 343         if ((ctx = BN_CTX_new()) == NULL || (order = BN_new()) == NULL ||
 344                 (u1 = BN_new()) == NULL || (u2 = BN_new()) == NULL ||
 345                 (m  = BN_new()) == NULL || (X  = BN_new()) == NULL)
 346         {
 347                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_MALLOC_FAILURE);
 348                 goto err;
 349         }
 350         if (!EC_GROUP_get_order(eckey->group, order, ctx))
 351         {
 352                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 353                 goto err;
 354         }
 355
 356         if (BN_is_zero(sig->r) || BN_get_sign(sig->r) ||
 357             BN_ucmp(sig->r, order) >= 0)
 358         {
 359                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_BAD_SIGNATURE);
 360                 ret = 0;
 361                 goto err;
 362         }
 363         if (BN_is_zero(sig->s) || BN_get_sign(sig->s) ||
 364             BN_ucmp(sig->s, order) >= 0)
 365         {
 366                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_BAD_SIGNATURE);
 367                 ret = 0;
 368                 goto err;
 369         }
 370
 371         /* calculate tmp1 = inv(S) mod order */
 372         if ((BN_mod_inverse(u2,sig->s,order,ctx)) == NULL)
 373         {
 374                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 375                 goto err;
 376         }
 377         /* digest -> m */
 378         if (BN_bin2bn(dgst,dgst_len,m) == NULL)
 379         {
 380                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 381                 goto err;
 382         }
 383         /* u1 = m * tmp mod order */
 384         if (!BN_mod_mul(u1,m,u2,order,ctx))
 385         {
 386                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 387                 goto err;
 388         }
 389         /* u2 = r * w mod q */
 390         if (!BN_mod_mul(u2,sig->r,u2,order,ctx))
 391         {
 392                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 393                 goto err;
 394         }
 395
 396         if ((point = EC_POINT_new(eckey->group)) == NULL)
 397         {
 398                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_MALLOC_FAILURE);
 399                 goto err;
 400         }
 401         if (!EC_POINT_mul(eckey->group, point, u1, eckey->pub_key, u2, ctx))
 402         {
 403                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB);
 404                 goto err;
 405         }
 406         if (EC_METHOD_get_field_type(EC_GROUP_method_of(eckey->group))
 407                 == NID_X9_62_prime_field)
 408         {
 409                 if (!EC_POINT_get_affine_coordinates_GFp(eckey->group,
 410                         point, X, NULL, ctx))
 411                 {
 412                         ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
 413                         goto err;
 414                 }
 415         }
 416         else /* NID_X9_62_characteristic_two_field */
 417         {
 418                 if (!EC_POINT_get_affine_coordinates_GF2m(eckey->group,
 419                         point, X, NULL, ctx))
 420                 {
 421                         ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
 422                         goto err;
 423                 }
 424         }
 425
 426         if (!BN_nnmod(u1,X,order,ctx))
 427         {
 428                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 429                 goto err;
 430         }
 431
 432         /*  is now in u1.  If the signature is correct, it will be
 433          * equal to R. */
 434         ret = (BN_ucmp(u1,sig->r) == 0);
 435
 436         err:
 437         if (ctx)
 438                 BN_CTX_free(ctx);
 439         if (u1)
 440                 BN_clear_free(u1);
 441         if (u2)
 442                 BN_clear_free(u2);
 443         if (m)
 444                 BN_clear_free(m);
 445         if (X)
 446                 BN_clear_free(X);
 447         if (order)
 448                 BN_clear_free(order);
 449         if (point)
 450                 EC_POINT_free(point);
 451         return(ret);
 452 }