diff libtomcrypt/src/pk/ecc/ecc_verify_hash.c @ 382:0cbe8f6dbf9e

propagate from branch 'au.asn.ucc.matt.ltc.dropbear' (head 2af22fb4e878750b88f80f90d439b316d229796f) to branch 'au.asn.ucc.matt.dropbear' (head 02c413252c90e9de8e03d91e9939dde3029f5c0a)
author Matt Johnston <matt@ucc.asn.au>
date Thu, 11 Jan 2007 02:41:05 +0000
parents
children ac2158e3e403
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/libtomcrypt/src/pk/ecc/ecc_verify_hash.c	Thu Jan 11 02:41:05 2007 +0000
@@ -0,0 +1,165 @@
+/* LibTomCrypt, modular cryptographic library -- Tom St Denis
+ *
+ * LibTomCrypt is a library that provides various cryptographic
+ * algorithms in a highly modular and flexible manner.
+ *
+ * The library is free for all purposes without any express
+ * guarantee it works.
+ *
+ * Tom St Denis, [email protected], http://libtomcrypt.com
+ */
+
+/* Implements ECC over Z/pZ for curve y^2 = x^3 - 3x + b
+ *
+ * All curves taken from NIST recommendation paper of July 1999
+ * Available at http://csrc.nist.gov/cryptval/dss.htm
+ */
+#include "tomcrypt.h"
+
+/**
+  @file ecc_verify_hash.c
+  ECC Crypto, Tom St Denis
+*/  
+
+#ifdef MECC
+
+/* verify 
+ *
+ * w  = s^-1 mod n
+ * u1 = xw 
+ * u2 = rw
+ * X = u1*G + u2*Q
+ * v = X_x1 mod n
+ * accept if v == r
+ */
+
+/**
+   Verify an ECC signature
+   @param sig         The signature to verify
+   @param siglen      The length of the signature (octets)
+   @param hash        The hash (message digest) that was signed
+   @param hashlen     The length of the hash (octets)
+   @param stat        Result of signature, 1==valid, 0==invalid
+   @param key         The corresponding public ECC key
+   @return CRYPT_OK if successful (even if the signature is not valid)
+*/
+int ecc_verify_hash(const unsigned char *sig,  unsigned long siglen,
+                    const unsigned char *hash, unsigned long hashlen, 
+                    int *stat, ecc_key *key)
+{
+   ecc_point    *mG, *mQ;
+   void          *r, *s, *v, *w, *u1, *u2, *e, *p, *m;
+   void          *mp;
+   int           err;
+
+   LTC_ARGCHK(sig  != NULL);
+   LTC_ARGCHK(hash != NULL);
+   LTC_ARGCHK(stat != NULL);
+   LTC_ARGCHK(key  != NULL);
+
+   /* default to invalid signature */
+   *stat = 0;
+   mp    = NULL;
+
+   /* is the IDX valid ?  */
+   if (ltc_ecc_is_valid_idx(key->idx) != 1) {
+      return CRYPT_PK_INVALID_TYPE;
+   }
+
+   /* allocate ints */
+   if ((err = mp_init_multi(&r, &s, &v, &w, &u1, &u2, &p, &e, &m, NULL)) != CRYPT_OK) {
+      return CRYPT_MEM;
+   }
+
+   /* allocate points */
+   mG = ltc_ecc_new_point();
+   mQ = ltc_ecc_new_point();
+   if (mQ  == NULL || mG == NULL) {
+      err = CRYPT_MEM;
+      goto error;
+   }
+
+   /* parse header */
+   if ((err = der_decode_sequence_multi(sig, siglen,
+                                  LTC_ASN1_INTEGER, 1UL, r,
+                                  LTC_ASN1_INTEGER, 1UL, s,
+                                  LTC_ASN1_EOL, 0UL, NULL)) != CRYPT_OK) {
+      goto error;
+   }
+
+   /* get the order */
+   if ((err = mp_read_radix(p, (char *)key->dp->order, 16)) != CRYPT_OK)                                { goto error; }
+
+   /* get the modulus */
+   if ((err = mp_read_radix(m, (char *)key->dp->prime, 16)) != CRYPT_OK)                                { goto error; }
+
+   /* check for zero */
+   if (mp_iszero(r) || mp_iszero(s) || mp_cmp(r, p) != LTC_MP_LT || mp_cmp(s, p) != LTC_MP_LT) {
+      err = CRYPT_INVALID_PACKET;
+      goto error;
+   }
+
+   /* read hash */
+   if ((err = mp_read_unsigned_bin(e, (unsigned char *)hash, (int)hashlen)) != CRYPT_OK)                { goto error; }
+
+   /*  w  = s^-1 mod n */
+   if ((err = mp_invmod(s, p, w)) != CRYPT_OK)                                                          { goto error; }
+
+   /* u1 = ew */
+   if ((err = mp_mulmod(e, w, p, u1)) != CRYPT_OK)                                                      { goto error; }
+
+   /* u2 = rw */
+   if ((err = mp_mulmod(r, w, p, u2)) != CRYPT_OK)                                                      { goto error; }
+
+   /* find mG and mQ */
+   if ((err = mp_read_radix(mG->x, (char *)key->dp->Gx, 16)) != CRYPT_OK)                               { goto error; }
+   if ((err = mp_read_radix(mG->y, (char *)key->dp->Gy, 16)) != CRYPT_OK)                               { goto error; }
+   if ((err = mp_set(mG->z, 1)) != CRYPT_OK)                                                            { goto error; }
+
+   if ((err = mp_copy(key->pubkey.x, mQ->x)) != CRYPT_OK)                                               { goto error; }
+   if ((err = mp_copy(key->pubkey.y, mQ->y)) != CRYPT_OK)                                               { goto error; }
+   if ((err = mp_copy(key->pubkey.z, mQ->z)) != CRYPT_OK)                                               { goto error; }
+
+   /* compute u1*mG + u2*mQ = mG */
+   if (ltc_mp.ecc_mul2add == NULL) {
+      if ((err = ltc_mp.ecc_ptmul(u1, mG, mG, m, 0)) != CRYPT_OK)                                       { goto error; }
+      if ((err = ltc_mp.ecc_ptmul(u2, mQ, mQ, m, 0)) != CRYPT_OK)                                       { goto error; }
+  
+      /* find the montgomery mp */
+      if ((err = mp_montgomery_setup(m, &mp)) != CRYPT_OK)                                              { goto error; }
+
+      /* add them */
+      if ((err = ltc_mp.ecc_ptadd(mQ, mG, mG, m, mp)) != CRYPT_OK)                                      { goto error; }
+   
+      /* reduce */
+      if ((err = ltc_mp.ecc_map(mG, m, mp)) != CRYPT_OK)                                                { goto error; }
+   } else {
+      /* use Shamir's trick to compute u1*mG + u2*mQ using half of the doubles */
+      if ((err = ltc_mp.ecc_mul2add(mG, u1, mQ, u2, mG, m)) != CRYPT_OK)                                { goto error; }
+   }
+
+   /* v = X_x1 mod n */
+   if ((err = mp_mod(mG->x, p, v)) != CRYPT_OK)                                                         { goto error; }
+
+   /* does v == r */
+   if (mp_cmp(v, r) == LTC_MP_EQ) {
+      *stat = 1;
+   }
+
+   /* clear up and return */
+   err = CRYPT_OK;
+error:
+   ltc_ecc_del_point(mG);
+   ltc_ecc_del_point(mQ);
+   mp_clear_multi(r, s, v, w, u1, u2, p, e, m, NULL);
+   if (mp != NULL) { 
+      mp_montgomery_free(mp);
+   }
+   return err;
+}
+
+#endif
+/* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc_verify_hash.c,v $ */
+/* $Revision: 1.12 $ */
+/* $Date: 2006/12/04 05:07:59 $ */
+