lib/nettle/ecc_verify_hash.c

   1 /*
   2  * Copyright (C) 2011-2012 Free Software Foundation, Inc.
   3  *
   4  * This file is part of GNUTLS.
   5  *
   6  * The GNUTLS library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public License
   8  * as published by the Free Software Foundation; either version 3 of
   9  * the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public License
  17  * along with this program.  If not, see <http://www.gnu.org/licenses/>
  18  *
  19  */
  20
  21 /* Based on public domain code of LibTomCrypt by Tom St Denis.
  22  * Adapted to gmp and nettle by Nikos Mavrogiannopoulos.
  23  */
  24
  25 #include "ecc.h"
  26
  27 /*
  28   @file ecc_verify_hash.c
  29   ECC Crypto, Tom St Denis
  30 */
  31
  32 /* verify
  33  *
  34  * w  = s^-1 mod n
  35  * u1 = xw
  36  * u2 = rw
  37  * X = u1*G + u2*Q
  38  * v = X_x1 mod n
  39  * accept if v == r
  40  */
  41
  42 /*
  43    Verify an ECC signature
  44    @param signature         The signature to verify
  45    @param hash        The hash (message digest) that was signed
  46    @param hashlen     The length of the hash (octets)
  47    @param stat        Result of signature, 1==valid, 0==invalid
  48    @param key         The corresponding public ECC key
  49    @param curve_id    The id of the curve we are working with
  50    @return 0 if successful (even if the signature is not valid)
  51 */
  52 int
  53 ecc_verify_hash (struct dsa_signature *signature,
  54                  const unsigned char *hash, unsigned long hashlen,
  55                  int *stat, ecc_key * key, gnutls_ecc_curve_t curve_id)
  56 {
  57   ecc_point *mG, *mQ;
  58   mpz_t v, w, u1, u2, e;
  59   int err;
  60
  61   if (signature == NULL || hash == NULL || stat == NULL || key == NULL)
  62     return -1;
  63
  64   /* default to invalid signature */
  65   *stat = 0;
  66
  67   /* allocate ints */
  68   if ((err = mp_init_multi (&v, &w, &u1, &u2, &e, NULL)) != 0)
  69     {
  70       return -1;
  71     }
  72
  73   /* allocate points */
  74   mG = ecc_new_point ();
  75   mQ = ecc_new_point ();
  76   if (mQ == NULL || mG == NULL)
  77     {
  78       err = -1;
  79       goto error;
  80     }
  81
  82   /* check for (0) */
  83   if (mpz_cmp_ui (signature->r, 0) == 0 || mpz_cmp_ui (signature->s, 0) == 0
  84       || mpz_cmp (signature->r, key->order) >= 0
  85       || mpz_cmp (signature->s, key->order) >= 0)
  86     {
  87       err = -1;
  88       goto error;
  89     }
  90
  91   /* read hash */
  92   nettle_mpz_set_str_256_u (e, hashlen, hash);
  93
  94   /*  w  = s^-1 mod n */
  95   mpz_invert (w, signature->s, key->order);
  96
  97   /* u1 = ew */
  98   mpz_mul (u1, e, w);
  99   mpz_mod (u1, u1, key->order);
 100
 101   /* u2 = rw */
 102   mpz_mul (u2, signature->r, w);
 103   mpz_mod (u2, u2, key->order);
 104
 105   /* find mG and mQ */
 106   mpz_set (mG->x, key->Gx);
 107   mpz_set (mG->y, key->Gy);
 108   mpz_set_ui (mG->z, 1);
 109
 110   mpz_set (mQ->x, key->pubkey.x);
 111   mpz_set (mQ->y, key->pubkey.y);
 112   mpz_set (mQ->z, key->pubkey.z);
 113
 114   /* compute u1*mG + u2*mQ = mG */
 115   if ((err = ecc_mulmod_cached (u1, curve_id, mG, key->A, key->prime, 0)) != 0)
 116     {
 117       goto error;
 118     }
 119   if ((err = ecc_mulmod (u2, mQ, mQ, key->A, key->prime, 0)) != 0)
 120     {
 121       goto error;
 122     }
 123
 124   /* add them */
 125   if ((err =
 126        ecc_projective_add_point (mQ, mG, mG, key->A, key->prime)) != 0)
 127     {
 128       goto error;
 129     }
 130
 131   /* reduce */
 132   if ((err = ecc_map (mG, key->prime)) != 0)
 133     {
 134       goto error;
 135     }
 136
 137   /* v = X_x1 mod n */
 138   mpz_mod (v, mG->x, key->order);
 139
 140   /* does v == r */
 141   if (mpz_cmp (v, signature->r) == 0)
 142     {
 143       *stat = 1;
 144     }
 145
 146   /* clear up and return */
 147   err = 0;
 148 error:
 149   ecc_del_point (mG);
 150   ecc_del_point (mQ);
 151   mp_clear_multi (&v, &w, &u1, &u2, &e, NULL);
 152   return err;
 153 }
 154
 155 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc_verify_hash.c,v $ */
 156 /* $Revision: 1.14 $ */
 157 /* $Date: 2007/05/12 14:32:35 $ */