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
  98         BN_init(&k);
  99
 100         if (ctx_in == NULL)
 101         {
 102                 if ((ctx=BN_CTX_new()) == NULL)
 103                 {
 104                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE);
 105                 goto err;
 106                 }
 107         }
 108         else
 109                 ctx=ctx_in;
 110
 111         if ((r = BN_new()) == NULL)
 112         {
 113                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
 114                 goto err;
 115         }
 116         if ((order = BN_new()) == NULL)
 117         {
 118                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
 119                 goto err;
 120         }
 121         if ((X = BN_new()) == NULL)
 122         {
 123                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
 124                 goto err;
 125         }
 126         if ((tmp_point = EC_POINT_new(eckey->group)) == NULL)
 127         {
 128                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
 129                 goto err;
 130         }
 131         if (!EC_GROUP_get_order(eckey->group,order,ctx))
 132         {
 133                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
 134                 goto err;
 135         }
 136
 137         do
 138         {
 139                 /* get random k */
 140                 do
 141                         if (!BN_rand_range(&k,order))
 142                         {
 143                                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,
 144                                  ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED);
 145                                 goto err;
 146                         }
 147                 while (BN_is_zero(&k));
 148
 149                 /* compute r the x-coordinate of generator * k */
 150                 if (!EC_POINT_mul(eckey->group, tmp_point, &k, NULL, NULL, ctx))
 151                 {
 152                         ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
 153                         goto err;
 154                 }
 155                 if (EC_METHOD_get_field_type(EC_GROUP_method_of(eckey->group))
 156                         == NID_X9_62_prime_field)
 157                 {
 158                         if (!EC_POINT_get_affine_coordinates_GFp(eckey->group,
 159                                 tmp_point, X, NULL, ctx))
 160                         {
 161                                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,
 162                                         ERR_R_EC_LIB);
 163                                 goto err;
 164                         }
 165                 }
 166                 else /* NID_X9_62_characteristic_two_field */
 167                 {
 168                         if (!EC_POINT_get_affine_coordinates_GF2m(eckey->group,
 169                                 tmp_point, X, NULL, ctx))
 170                         {
 171                                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,
 172                                         ERR_R_EC_LIB);
 173                                 goto err;
 174                         }
 175                 }
 176                 if (!BN_nnmod(r,X,order,ctx))
 177                 {
 178                         ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
 179                         goto err;
 180                 }
 181         }
 182         while (BN_is_zero(r));
 183
 184         /* compute the inverse of k */
 185         if ((kinv = BN_mod_inverse(NULL,&k,order,ctx)) == NULL)
 186         {
 187                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
 188                 goto err;
 189         }
 190
 191         if (*rp == NULL)
 192                 BN_clear_free(*rp);
 193         *rp = r;
 194         if (*kinvp == NULL)
 195                 BN_clear_free(*kinvp);
 196         *kinvp = kinv;
 197         kinv = NULL;
 198         ret = 1;
 199 err:
 200         if (!ret)
 201         {
 202                 if (kinv != NULL) BN_clear_free(kinv);
 203                 if (r != NULL) BN_clear_free(r);
 204         }
 205         if (ctx_in == NULL)
 206                 BN_CTX_free(ctx);
 207         if (kinv != NULL)
 208                 BN_clear_free(kinv);
 209         if (order != NULL)
 210                 BN_clear_free(order);
 211         if (tmp_point != NULL)
 212                 EC_POINT_free(tmp_point);
 213         if (X)  BN_clear_free(X);
 214         BN_clear_free(&k);
 215         return(ret);
 216 }
 217
 218
 219 static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dgst_len,
 220                 EC_KEY *eckey)
 221 {
 222         BIGNUM *kinv=NULL,*r=NULL,*s=NULL,*m=NULL,*tmp=NULL,*order=NULL;
 223         BIGNUM xr;
 224         BN_CTX *ctx=NULL;
 225         ECDSA_SIG *ret=NULL;
 226         ECDSA_DATA *ecdsa;
 227
 228         BN_init(&xr);
 229
 230         ecdsa = ecdsa_check(eckey);
 231
 232         if (!eckey || !eckey->group || !eckey->pub_key || !eckey->priv_key
 233                 || !ecdsa)
 234         {
 235                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_PASSED_NULL_PARAMETER);
 236                 goto err;
 237         }
 238
 239         if ((ctx = BN_CTX_new()) == NULL || (order = BN_new()) == NULL ||
 240                 (tmp = BN_new()) == NULL || (m = BN_new()) == NULL ||
 241                 (s = BN_new()) == NULL )
 242         {
 243                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE);
 244                 goto err;
 245         }
 246
 247         if (!EC_GROUP_get_order(eckey->group,order,ctx))
 248         {
 249                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_EC_LIB);
 250                 goto err;
 251         }
 252         if (dgst_len > BN_num_bytes(order))
 253         {
 254                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN,
 255                         ECDSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE);
 256                 goto err;
 257         }
 258
 259         if (BN_bin2bn(dgst,dgst_len,m) == NULL)
 260         {
 261                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
 262                 goto err;
 263         }
 264         do
 265         {
 266                 if (ecdsa->kinv == NULL || ecdsa->r == NULL)
 267                 {
 268                         if (!ECDSA_sign_setup(eckey,ctx,&kinv,&r))
 269                         {
 270                                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN,
 271                                         ERR_R_ECDSA_LIB);
 272                                 goto err;
 273                         }
 274                 }
 275                 else
 276                 {
 277                         kinv = ecdsa->kinv;
 278                         ecdsa->kinv = NULL;
 279                         r = ecdsa->r;
 280                         ecdsa->r = NULL;
 281                 }
 282
 283                 if (!BN_mod_mul(tmp,eckey->priv_key,r,order,ctx))
 284                 {
 285                         ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
 286                         goto err;
 287                 }
 288                 if (!BN_add(s,tmp,m))
 289                 {
 290                         ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
 291                         goto err;
 292                 }
 293                 if (BN_cmp(s,order) > 0)
 294                         BN_sub(s,s,order);
 295                 if (!BN_mod_mul(s,s,kinv,order,ctx))
 296                 {
 297                         ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
 298                         goto err;
 299                 }
 300         }
 301         while (BN_is_zero(s));
 302
 303         if ((ret = ECDSA_SIG_new()) == NULL)
 304         {
 305                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE);
 306                 goto err;
 307         }
 308         if (BN_copy(ret->r, r) == NULL || BN_copy(ret->s, s) == NULL)
 309         {
 310                 ECDSA_SIG_free(ret);
 311                 ret = NULL;
 312                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
 313         }
 314
 315 err:
 316         if (r)
 317                 BN_clear_free(r);
 318         if (s)
 319                 BN_clear_free(s);
 320         if (ctx)
 321                 BN_CTX_free(ctx);
 322         if (m)
 323                 BN_clear_free(m);
 324         if (tmp)
 325                 BN_clear_free(tmp);
 326         if (order)
 327                 BN_clear_free(order);
 328         if (kinv)
 329                 BN_clear_free(kinv);
 330         return(ret);
 331 }
 332
 333 static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len,
 334                 ECDSA_SIG *sig, EC_KEY *eckey)
 335 {
 336         BN_CTX *ctx;
 337         BIGNUM *order=NULL,*u1=NULL,*u2=NULL,*m=NULL,*X=NULL;
 338         EC_POINT *point=NULL;
 339         int ret = -1;
 340         if (!eckey || !eckey->group || !eckey->pub_key || !sig)
 341         {
 342                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_MISSING_PARAMETERS);
 343                 return -1;
 344         }
 345
 346         if ((ctx = BN_CTX_new()) == NULL || (order = BN_new()) == NULL ||
 347                 (u1 = BN_new()) == NULL || (u2 = BN_new()) == NULL ||
 348                 (m  = BN_new()) == NULL || (X  = BN_new()) == NULL)
 349         {
 350                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_MALLOC_FAILURE);
 351                 goto err;
 352         }
 353         if (!EC_GROUP_get_order(eckey->group, order, ctx))
 354         {
 355                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 356                 goto err;
 357         }
 358
 359         if (BN_is_zero(sig->r) || BN_get_sign(sig->r) ||
 360             BN_ucmp(sig->r, order) >= 0)
 361         {
 362                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_BAD_SIGNATURE);
 363                 ret = 0;
 364                 goto err;
 365         }
 366         if (BN_is_zero(sig->s) || BN_get_sign(sig->s) ||
 367             BN_ucmp(sig->s, order) >= 0)
 368         {
 369                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_BAD_SIGNATURE);
 370                 ret = 0;
 371                 goto err;
 372         }
 373
 374         /* calculate tmp1 = inv(S) mod order */
 375         if ((BN_mod_inverse(u2,sig->s,order,ctx)) == NULL)
 376         {
 377                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 378                 goto err;
 379         }
 380         /* digest -> m */
 381         if (BN_bin2bn(dgst,dgst_len,m) == NULL)
 382         {
 383                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 384                 goto err;
 385         }
 386         /* u1 = m * tmp mod order */
 387         if (!BN_mod_mul(u1,m,u2,order,ctx))
 388         {
 389                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 390                 goto err;
 391         }
 392         /* u2 = r * w mod q */
 393         if (!BN_mod_mul(u2,sig->r,u2,order,ctx))
 394         {
 395                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 396                 goto err;
 397         }
 398
 399         if ((point = EC_POINT_new(eckey->group)) == NULL)
 400         {
 401                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_MALLOC_FAILURE);
 402                 goto err;
 403         }
 404         if (!EC_POINT_mul(eckey->group, point, u1, eckey->pub_key, u2, ctx))
 405         {
 406                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB);
 407                 goto err;
 408         }
 409         if (EC_METHOD_get_field_type(EC_GROUP_method_of(eckey->group))
 410                 == NID_X9_62_prime_field)
 411         {
 412                 if (!EC_POINT_get_affine_coordinates_GFp(eckey->group,
 413                         point, X, NULL, ctx))
 414                 {
 415                         ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
 416                         goto err;
 417                 }
 418         }
 419         else /* NID_X9_62_characteristic_two_field */
 420         {
 421                 if (!EC_POINT_get_affine_coordinates_GF2m(eckey->group,
 422                         point, X, NULL, ctx))
 423                 {
 424                         ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
 425                         goto err;
 426                 }
 427         }
 428
 429         if (!BN_nnmod(u1,X,order,ctx))
 430         {
 431                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 432                 goto err;
 433         }
 434
 435         /*  is now in u1.  If the signature is correct, it will be
 436          * equal to R. */
 437         ret = (BN_ucmp(u1,sig->r) == 0);
 438
 439         err:
 440         if (ctx)
 441                 BN_CTX_free(ctx);
 442         if (u1)
 443                 BN_clear_free(u1);
 444         if (u2)
 445                 BN_clear_free(u2);
 446         if (m)
 447                 BN_clear_free(m);
 448         if (X)
 449                 BN_clear_free(X);
 450         if (order)
 451                 BN_clear_free(order);
 452         if (point)
 453                 EC_POINT_free(point);
 454         return(ret);
 455 }