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
  59 /* TODO : general case */
  60 #define EC_POINT_get_affine_coordinates EC_POINT_get_affine_coordinates_GFp
  61
  62 static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dlen, ECDSA *ecdsa);
  63 static int ecdsa_sign_setup(ECDSA *ecdsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp);
  64 static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, ECDSA_SIG *sig,
  65                            ECDSA *ecdsa);
  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 0,
  73 NULL
  74 };
  75
  76 const ECDSA_METHOD *ECDSA_OpenSSL(void)
  77 {
  78         return &openssl_ecdsa_meth;
  79 }
  80
  81 static int ecdsa_sign_setup(ECDSA *ecdsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
  82 {
  83         BN_CTX   *ctx = NULL;
  84         BIGNUM   k,*kinv=NULL,*r=NULL,*order=NULL,*X=NULL;
  85         EC_POINT *tmp_point=NULL;
  86         int      ret = 0,reason = ERR_R_BN_LIB;
  87         if (!ecdsa  || !ecdsa->group || !ecdsa->pub_key || !ecdsa->priv_key)
  88         {
  89                 reason = ECDSA_R_MISSING_PARAMETERS;
  90                 return 0;
  91         }
  92         if (ctx_in == NULL)
  93         {
  94                 if ((ctx=BN_CTX_new()) == NULL) goto err;
  95         }
  96         else
  97                 ctx=ctx_in;
  98
  99         if ((r = BN_new()) == NULL) goto err;
 100         if ((order = BN_new()) == NULL) goto err;
 101         if ((X = BN_new()) == NULL) goto err;
 102         if ((tmp_point = EC_POINT_new(ecdsa->group)) == NULL)
 103         {
 104                 reason = ERR_R_EC_LIB;
 105                 goto err;
 106         }
 107         if (!EC_GROUP_get_order(ecdsa->group,order,ctx))
 108         {
 109                 reason = ERR_R_EC_LIB;
 110                 goto err;
 111         }
 112
 113         do
 114         {
 115                 /* get random k */
 116                 BN_init(&k);
 117                 do
 118                         if (!BN_rand_range(&k,order))
 119                         {
 120                                 reason = ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED;
 121                                 goto err;
 122                         }
 123                 while (BN_is_zero(&k));
 124
 125                 /* compute r the x-coordinate of generator * k */
 126                 if (!EC_POINT_mul(ecdsa->group,tmp_point,&k,NULL,NULL,ctx)
 127                     || !EC_POINT_get_affine_coordinates(ecdsa->group,tmp_point,X,NULL,ctx))
 128                 {
 129                         reason = ERR_R_EC_LIB;
 130                         goto err;
 131                 }
 132                 if (!BN_nnmod(r,X,order,ctx)) goto err;
 133         }
 134         while (BN_is_zero(r));
 135
 136         /* compute the inverse of k */
 137         if ((kinv = BN_mod_inverse(NULL,&k,order,ctx)) == NULL) goto err;
 138
 139         if (*rp == NULL)
 140                 BN_clear_free(*rp);
 141         *rp = r;
 142         if (*kinvp == NULL)
 143                 BN_clear_free(*kinvp);
 144         *kinvp = kinv;
 145         kinv = NULL;
 146         ret = 1;
 147 err:
 148         if (!ret)
 149         {
 150                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,reason);
 151                 if (kinv != NULL) BN_clear_free(kinv);
 152                 if (r != NULL) BN_clear_free(r);
 153         }
 154         if (ctx_in == NULL)
 155                 BN_CTX_free(ctx);
 156         if (kinv != NULL)
 157                 BN_clear_free(kinv);
 158         if (order != NULL)
 159                 BN_clear_free(order);
 160         if (tmp_point != NULL)
 161                 EC_POINT_free(tmp_point);
 162         if (X)  BN_clear_free(X);
 163         BN_clear_free(&k);
 164         return(ret);
 165 }
 166
 167
 168 static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dgst_len, ECDSA *ecdsa)
 169 {
 170         BIGNUM *kinv=NULL,*r=NULL,*s=NULL,*m=NULL,*tmp=NULL,*order=NULL;
 171         BIGNUM xr;
 172         BN_CTX *ctx=NULL;
 173         int reason=ERR_R_BN_LIB;
 174         ECDSA_SIG *ret=NULL;
 175
 176         if (!ecdsa || !ecdsa->group || !ecdsa->pub_key || !ecdsa->priv_key)
 177         {
 178                 reason = ECDSA_R_MISSING_PARAMETERS;
 179                 goto err;
 180         }
 181         BN_init(&xr);
 182
 183         if ((ctx = BN_CTX_new()) == NULL) goto err;
 184         if ((order = BN_new()) == NULL) goto err;
 185         if ((tmp = BN_new()) == NULL) goto err;
 186         if ((m = BN_new()) == NULL) goto err;
 187         if ((s = BN_new()) == NULL) goto err;
 188
 189         if (!EC_GROUP_get_order(ecdsa->group,order,ctx))
 190         {
 191                 reason = ECDSA_R_ERR_EC_LIB;
 192                 goto err;
 193         }
 194         if (dgst_len > BN_num_bytes(order))
 195         {
 196                 reason = ECDSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE;
 197                 goto err;
 198         }
 199
 200         if (BN_bin2bn(dgst,dgst_len,m) == NULL) goto err;
 201         do
 202         {
 203                 if ((ecdsa->kinv == NULL) || (ecdsa->r == NULL))
 204                 {
 205                         if (!ECDSA_sign_setup(ecdsa,ctx,&kinv,&r)) goto err;
 206                 }
 207                 else
 208                 {
 209                         kinv = ecdsa->kinv;
 210                         ecdsa->kinv = NULL;
 211                         r = ecdsa->r;
 212                         ecdsa->r = NULL;
 213                 }
 214
 215                 if (!BN_mod_mul(tmp,ecdsa->priv_key,r,order,ctx)) goto err;
 216                 if (!BN_add(s,tmp,m)) goto err;
 217                 if (BN_cmp(s,order) > 0)
 218                         BN_sub(s,s,order);
 219                 if (!BN_mod_mul(s,s,kinv,order,ctx)) goto err;
 220         }
 221         while (BN_is_zero(s));
 222
 223         if ((ret = ECDSA_SIG_new()) == NULL)
 224         {
 225                 reason = ECDSA_R_SIGNATURE_MALLOC_FAILED;
 226                 goto err;
 227         }
 228         if (BN_copy(ret->r, r) == NULL || BN_copy(ret->s, s) == NULL)
 229         {
 230                 ECDSA_SIG_free(ret);
 231                 ret = NULL;
 232                 reason = ERR_R_BN_LIB;
 233         }
 234
 235 err:
 236         if (!ret)
 237                 {
 238                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN,reason);
 239                 }
 240         if (r     != NULL) BN_clear_free(r);
 241         if (s     != NULL) BN_clear_free(s);
 242         if (ctx   != NULL) BN_CTX_free(ctx);
 243         if (m     != NULL) BN_clear_free(m);
 244         if (tmp   != NULL) BN_clear_free(tmp);
 245         if (order != NULL) BN_clear_free(order);
 246         if (kinv  != NULL) BN_clear_free(kinv);
 247         return(ret);
 248 }
 249
 250 static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, ECDSA_SIG *sig,
 251                            ECDSA *ecdsa)
 252 {
 253         BN_CTX *ctx;
 254         BIGNUM *order=NULL,*u1=NULL,*u2=NULL,*m=NULL,*X=NULL;
 255         EC_POINT *point=NULL;
 256         int ret = -1,reason = ERR_R_BN_LIB;
 257         if (!ecdsa || !ecdsa->group || !ecdsa->pub_key || !sig)
 258         {
 259                 reason = ECDSA_R_MISSING_PARAMETERS;
 260                 return -1;
 261         }
 262
 263         if ((ctx = BN_CTX_new()) == NULL) goto err;
 264         if ((order = BN_new()) == NULL) goto err;
 265         if ((u1 = BN_new()) == NULL) goto err;
 266         if ((u2 = BN_new()) == NULL) goto err;
 267         if ((m  = BN_new()) == NULL) goto err;
 268         if ((X  = BN_new()) == NULL) goto err;
 269         if (!EC_GROUP_get_order(ecdsa->group,order,ctx)) goto err;
 270
 271         if (BN_is_zero(sig->r) || sig->r->neg || BN_ucmp(sig->r, order) >= 0)
 272         {
 273                 reason = ECDSA_R_BAD_SIGNATURE;
 274                 ret = 0;
 275                 goto err;
 276         }
 277         if (BN_is_zero(sig->s) || sig->s->neg || BN_ucmp(sig->s, order) >= 0)
 278         {
 279                 reason = ECDSA_R_BAD_SIGNATURE;
 280                 ret = 0;
 281                 goto err;
 282         }
 283
 284         /* calculate tmp1 = inv(S) mod order */
 285         if ((BN_mod_inverse(u2,sig->s,order,ctx)) == NULL) goto err;
 286         /* digest -> m */
 287         if (BN_bin2bn(dgst,dgst_len,m) == NULL) goto err;
 288         /* u1 = m * tmp mod order */
 289         if (!BN_mod_mul(u1,m,u2,order,ctx)) goto err;
 290         /* u2 = r * w mod q */
 291         if (!BN_mod_mul(u2,sig->r,u2,order,ctx)) goto err;
 292
 293         if ((point = EC_POINT_new(ecdsa->group)) == NULL)
 294         {
 295                 reason = ERR_R_EC_LIB;
 296                 goto err;
 297         }
 298         if (!EC_POINT_mul(ecdsa->group,point,u1,ecdsa->pub_key,u2,ctx)
 299             || !EC_POINT_get_affine_coordinates(ecdsa->group,point,X,NULL,ctx))
 300         {
 301                 reason = ERR_R_EC_LIB;
 302                 goto err;
 303         }
 304         if (!BN_nnmod(u1,X,order,ctx)) goto err;
 305
 306         /*  is now in u1.  If the signature is correct, it will be
 307          * equal to R. */
 308         ret = (BN_ucmp(u1,sig->r) == 0);
 309
 310         err:
 311         if (ret != 1) ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY,reason);
 312         if (ctx != NULL) BN_CTX_free(ctx);
 313         if (u1  != NULL) BN_clear_free(u1);
 314         if (u2  != NULL) BN_clear_free(u2);
 315         if (m   != NULL) BN_clear_free(m);
 316         if (X   != NULL) BN_clear_free(X);
 317         if (order != NULL) BN_clear_free(order);
 318         if (point != NULL) EC_POINT_free(point);
 319         return(ret);
 320 }