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 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  56  * All rights reserved.
  57  *
  58  * This package is an SSL implementation written
  59  * by Eric Young (eay@cryptsoft.com).
  60  * The implementation was written so as to conform with Netscapes SSL.
  61  *
  62  * This library is free for commercial and non-commercial use as long as
  63  * the following conditions are aheared to.  The following conditions
  64  * apply to all code found in this distribution, be it the RC4, RSA,
  65  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  66  * included with this distribution is covered by the same copyright terms
  67  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  68  *
  69  * Copyright remains Eric Young's, and as such any Copyright notices in
  70  * the code are not to be removed.
  71  * If this package is used in a product, Eric Young should be given attribution
  72  * as the author of the parts of the library used.
  73  * This can be in the form of a textual message at program startup or
  74  * in documentation (online or textual) provided with the package.
  75  *
  76  * Redistribution and use in source and binary forms, with or without
  77  * modification, are permitted provided that the following conditions
  78  * are met:
  79  * 1. Redistributions of source code must retain the copyright
  80  *    notice, this list of conditions and the following disclaimer.
  81  * 2. Redistributions in binary form must reproduce the above copyright
  82  *    notice, this list of conditions and the following disclaimer in the
  83  *    documentation and/or other materials provided with the distribution.
  84  * 3. All advertising materials mentioning features or use of this software
  85  *    must display the following acknowledgement:
  86  *    "This product includes cryptographic software written by
  87  *     Eric Young (eay@cryptsoft.com)"
  88  *    The word 'cryptographic' can be left out if the rouines from the library
  89  *    being used are not cryptographic related :-).
  90  * 4. If you include any Windows specific code (or a derivative thereof) from
  91  *    the apps directory (application code) you must include an acknowledgement:
  92  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  93  *
  94  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  95  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  96  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  97  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  98  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  99  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 100  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 101  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 102  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 103  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 104  * SUCH DAMAGE.
 105  *
 106  * The licence and distribution terms for any publically available version or
 107  * derivative of this code cannot be changed.  i.e. this code cannot simply be
 108  * copied and put under another distribution licence
 109  * [including the GNU Public Licence.]
 110  */
 111 #include "cryptlib.h"
 112 #include <openssl/ecdsa.h>
 113
 114 /* TODO : general case */
 115 #define EC_POINT_get_affine_coordinates EC_POINT_get_affine_coordinates_GFp
 116
 117 static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dlen, ECDSA *ecdsa);
 118 static int ecdsa_sign_setup(ECDSA *ecdsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp);
 119 static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, ECDSA_SIG *sig,
 120                            ECDSA *ecdsa);
 121
 122 static ECDSA_METHOD openssl_ecdsa_meth = {
 123 "OpenSSL ECDSA method",
 124 ecdsa_do_sign,
 125 ecdsa_sign_setup,
 126 ecdsa_do_verify,
 127 0,
 128 NULL
 129 };
 130
 131 const ECDSA_METHOD *ECDSA_OpenSSL(void)
 132 {
 133         return &openssl_ecdsa_meth;
 134 }
 135
 136 static int ecdsa_sign_setup(ECDSA *ecdsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
 137 {
 138         BN_CTX   *ctx = NULL;
 139         BIGNUM   k,*kinv=NULL,*r=NULL,*order=NULL,*X=NULL;
 140         EC_POINT *tmp_point=NULL;
 141         int      ret = 0,reason = ERR_R_BN_LIB;
 142         if (!ecdsa  || !ecdsa->group || !ecdsa->pub_key || !ecdsa->priv_key)
 143         {
 144                 reason = ECDSA_R_MISSING_PARAMETERS;
 145                 return 0;
 146         }
 147         if (ctx_in == NULL)
 148         {
 149                 if ((ctx=BN_CTX_new()) == NULL) goto err;
 150         }
 151         else
 152                 ctx=ctx_in;
 153
 154         if ((r = BN_new()) == NULL) goto err;
 155         if ((order = BN_new()) == NULL) goto err;
 156         if ((X = BN_new()) == NULL) goto err;
 157         if ((tmp_point = EC_POINT_new(ecdsa->group)) == NULL)
 158         {
 159                 reason = ERR_R_EC_LIB;
 160                 goto err;
 161         }
 162         if (!EC_POINT_copy(tmp_point,EC_GROUP_get0_generator(ecdsa->group)))
 163         {
 164                 reason = ERR_R_EC_LIB;
 165                 goto err;
 166         }
 167         if (!EC_GROUP_get_order(ecdsa->group,order,ctx))
 168         {
 169                 reason = ERR_R_EC_LIB;
 170                 goto err;
 171         }
 172
 173         do
 174         {
 175                 /* get random k */
 176                 BN_init(&k);
 177                 do
 178                         if (!BN_rand_range(&k,order))
 179                         {
 180                                 reason = ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED;
 181                                 goto err;
 182                         }
 183                 while (BN_is_zero(&k));
 184
 185                 /* compute r the x-coordinate of generator * k */
 186                 if (!EC_POINT_mul(ecdsa->group,tmp_point,&k,NULL,NULL,ctx)
 187                     || !EC_POINT_get_affine_coordinates(ecdsa->group,tmp_point,X,NULL,ctx))
 188                 {
 189                         reason = ERR_R_EC_LIB;
 190                         goto err;
 191                 }
 192                 if (!BN_nnmod(r,X,order,ctx)) goto err;
 193         }
 194         while (BN_is_zero(r));
 195
 196         /* compute the inverse of k */
 197         if ((kinv = BN_mod_inverse(NULL,&k,order,ctx)) == NULL) goto err;
 198
 199         if (*rp == NULL)
 200                 BN_clear_free(*rp);
 201         *rp = r;
 202         if (*kinvp == NULL)
 203                 BN_clear_free(*kinvp);
 204         *kinvp = kinv;
 205         kinv = NULL;
 206         ret = 1;
 207 err:
 208         if (!ret)
 209         {
 210                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,reason);
 211                 if (kinv != NULL) BN_clear_free(kinv);
 212                 if (r != NULL) BN_clear_free(r);
 213         }
 214         if (ctx_in == NULL)
 215                 BN_CTX_free(ctx);
 216         if (kinv != NULL)
 217                 BN_clear_free(kinv);
 218         if (order != NULL)
 219                 BN_clear_free(order);
 220         if (tmp_point != NULL)
 221                 EC_POINT_free(tmp_point);
 222         if (X)  BN_clear_free(X);
 223         BN_clear_free(&k);
 224         return(ret);
 225 }
 226
 227
 228 static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dgst_len, ECDSA *ecdsa)
 229 {
 230         BIGNUM *kinv=NULL,*r=NULL,*s=NULL,*m=NULL,*tmp=NULL,*order=NULL;
 231         BIGNUM xr;
 232         BN_CTX *ctx=NULL;
 233         int reason=ERR_R_BN_LIB;
 234         ECDSA_SIG *ret=NULL;
 235
 236         if (!ecdsa || !ecdsa->group || !ecdsa->pub_key || !ecdsa->priv_key)
 237         {
 238                 reason = ECDSA_R_MISSING_PARAMETERS;
 239                 goto err;
 240         }
 241         BN_init(&xr);
 242
 243         if ((ctx = BN_CTX_new()) == NULL) goto err;
 244         if ((order = BN_new()) == NULL) goto err;
 245         if ((tmp = BN_new()) == NULL) goto err;
 246         if ((m = BN_new()) == NULL) goto err;
 247         if ((s = BN_new()) == NULL) goto err;
 248
 249         if (!EC_GROUP_get_order(ecdsa->group,order,ctx))
 250         {
 251                 reason = ECDSA_R_ERR_EC_LIB;
 252                 goto err;
 253         }
 254         if (dgst_len > BN_num_bytes(order))
 255         {
 256                 reason = ECDSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE;
 257                 goto err;
 258         }
 259
 260         if (BN_bin2bn(dgst,dgst_len,m) == NULL) goto err;
 261         do
 262         {
 263                 if ((ecdsa->kinv == NULL) || (ecdsa->r == NULL))
 264                 {
 265                         if (!ECDSA_sign_setup(ecdsa,ctx,&kinv,&r)) goto err;
 266                 }
 267                 else
 268                 {
 269                         kinv = ecdsa->kinv;
 270                         ecdsa->kinv = NULL;
 271                         r = ecdsa->r;
 272                         ecdsa->r = NULL;
 273                 }
 274
 275                 if (!BN_mod_mul(tmp,ecdsa->priv_key,r,order,ctx)) goto err;
 276                 if (!BN_add(s,tmp,m)) goto err;
 277                 if (BN_cmp(s,order) > 0)
 278                         BN_sub(s,s,order);
 279                 if (!BN_mod_mul(s,s,kinv,order,ctx)) goto err;
 280         }
 281         while (BN_is_zero(s));
 282
 283         if ((ret = ECDSA_SIG_new()) == NULL)
 284         {
 285                 reason = ECDSA_R_SIGNATURE_MALLOC_FAILED;
 286                 goto err;
 287         }
 288         ret->r = r;
 289         ret->s = s;
 290
 291 err:
 292         if (!ret)
 293                 {
 294                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN,reason);
 295                 BN_free(r);
 296                 BN_free(s);
 297                 }
 298         if (ctx   != NULL) BN_CTX_free(ctx);
 299         if (m     != NULL) BN_clear_free(m);
 300         if (tmp   != NULL) BN_clear_free(tmp);
 301         if (order != NULL) BN_clear_free(order);
 302         if (kinv  != NULL) BN_clear_free(kinv);
 303         return(ret);
 304 }
 305
 306 static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, ECDSA_SIG *sig,
 307                            ECDSA *ecdsa)
 308 {
 309         BN_CTX *ctx;
 310         BIGNUM *order=NULL,*u1=NULL,*u2=NULL,*m=NULL,*X=NULL;
 311         EC_POINT *point=NULL;
 312         int ret = -1,reason = ERR_R_BN_LIB;
 313         if (!ecdsa || !ecdsa->group || !ecdsa->pub_key || !sig)
 314         {
 315                 reason = ECDSA_R_MISSING_PARAMETERS;
 316                 return -1;
 317         }
 318
 319         if ((ctx = BN_CTX_new()) == NULL) goto err;
 320         if ((order = BN_new()) == NULL) goto err;
 321         if ((u1 = BN_new()) == NULL) goto err;
 322         if ((u2 = BN_new()) == NULL) goto err;
 323         if ((m  = BN_new()) == NULL) goto err;
 324         if ((X  = BN_new()) == NULL) goto err;
 325         if (!EC_GROUP_get_order(ecdsa->group,order,ctx)) goto err;
 326
 327         if (BN_is_zero(sig->r) || sig->r->neg || BN_ucmp(sig->r, order) >= 0)
 328         {
 329                 reason = ECDSA_R_BAD_SIGNATURE;
 330                 ret = 0;
 331                 goto err;
 332         }
 333         if (BN_is_zero(sig->s) || sig->s->neg || BN_ucmp(sig->s, order) >= 0)
 334         {
 335                 reason = ECDSA_R_BAD_SIGNATURE;
 336                 ret = 0;
 337                 goto err;
 338         }
 339
 340         /* calculate tmp1 = inv(S) mod order */
 341         if ((BN_mod_inverse(u2,sig->s,order,ctx)) == NULL) goto err;
 342         /* digest -> m */
 343         if (BN_bin2bn(dgst,dgst_len,m) == NULL) goto err;
 344         /* u1 = m * tmp mod order */
 345         if (!BN_mod_mul(u1,m,u2,order,ctx)) goto err;
 346         /* u2 = r * w mod q */
 347         if (!BN_mod_mul(u2,sig->r,u2,order,ctx)) goto err;
 348
 349         if ((point = EC_POINT_new(ecdsa->group)) == NULL)
 350         {
 351                 reason = ERR_R_EC_LIB;
 352                 goto err;
 353         }
 354         if (!EC_POINT_copy(point,EC_GROUP_get0_generator(ecdsa->group)))
 355         {
 356                 reason = ERR_R_EC_LIB;
 357                 goto err;
 358         }
 359         if (!EC_POINT_mul(ecdsa->group,point,u1,ecdsa->pub_key,u2,ctx)
 360             || !EC_POINT_get_affine_coordinates(ecdsa->group,point,X,NULL,ctx))
 361         {
 362                 reason = ERR_R_EC_LIB;
 363                 goto err;
 364         }
 365         if (!BN_nnmod(u1,X,order,ctx)) goto err;
 366
 367         /*  is now in u1.  If the signature is correct, it will be
 368          * equal to R. */
 369         ret = (BN_ucmp(u1,sig->r) == 0);
 370
 371         err:
 372         if (ret != 1) ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY,reason);
 373         if (ctx != NULL) BN_CTX_free(ctx);
 374         if (u1  != NULL) BN_clear_free(u1);
 375         if (u2  != NULL) BN_clear_free(u2);
 376         if (m   != NULL) BN_clear_free(m);
 377         if (X   != NULL) BN_clear_free(X);
 378         if (order != NULL) BN_clear_free(order);
 379         if (point != NULL) EC_POINT_free(point);
 380         return(ret);
 381 }