• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /* LibTomCrypt, modular cryptographic library -- Tom St Denis
2  *
3  * LibTomCrypt is a library that provides various cryptographic
4  * algorithms in a highly modular and flexible manner.
5  *
6  * The library is free for all purposes without any express
7  * guarantee it works.
8  *
9  * Tom St Denis, tomstdenis@gmail.com, http://libtomcrypt.com
10  */
11 
12 /* Implements ECC over Z/pZ for curve y^2 = x^3 - 3x + b
13  *
14  * All curves taken from NIST recommendation paper of July 1999
15  * Available at http://csrc.nist.gov/cryptval/dss.htm
16  */
17 #include "tomcrypt.h"
18 
19 /**
20   @file ecc_verify_hash.c
21   ECC Crypto, Tom St Denis
22 */
23 
24 #ifdef MECC
25 
26 /* verify
27  *
28  * w  = s^-1 mod n
29  * u1 = xw
30  * u2 = rw
31  * X = u1*G + u2*Q
32  * v = X_x1 mod n
33  * accept if v == r
34  */
35 
36 /**
37    Verify an ECC signature
38    @param sig         The signature to verify
39    @param siglen      The length of the signature (octets)
40    @param hash        The hash (message digest) that was signed
41    @param hashlen     The length of the hash (octets)
42    @param stat        Result of signature, 1==valid, 0==invalid
43    @param key         The corresponding public ECC key
44    @return CRYPT_OK if successful (even if the signature is not valid)
45 */
ecc_verify_hash(const unsigned char * sig,unsigned long siglen,const unsigned char * hash,unsigned long hashlen,int * stat,ecc_key * key)46 int ecc_verify_hash(const unsigned char *sig,  unsigned long siglen,
47                     const unsigned char *hash, unsigned long hashlen,
48                     int *stat, ecc_key *key)
49 {
50    ecc_point    *mG, *mQ;
51    void          *r, *s, *v, *w, *u1, *u2, *e, *p, *m;
52    void          *mp;
53    int           err;
54 
55    LTC_ARGCHK(sig  != NULL);
56    LTC_ARGCHK(hash != NULL);
57    LTC_ARGCHK(stat != NULL);
58    LTC_ARGCHK(key  != NULL);
59 
60    /* default to invalid signature */
61    *stat = 0;
62    mp    = NULL;
63 
64    /* is the IDX valid ?  */
65    if (ltc_ecc_is_valid_idx(key->idx) != 1) {
66       return CRYPT_PK_INVALID_TYPE;
67    }
68 
69    /* allocate ints */
70    if ((err = mp_init_multi(&r, &s, &v, &w, &u1, &u2, &p, &e, &m, NULL)) != CRYPT_OK) {
71       return CRYPT_MEM;
72    }
73 
74    /* allocate points */
75    mG = ltc_ecc_new_point();
76    mQ = ltc_ecc_new_point();
77    if (mQ  == NULL || mG == NULL) {
78       err = CRYPT_MEM;
79       goto error;
80    }
81 
82    /* parse header */
83    if ((err = der_decode_sequence_multi(sig, siglen,
84                                   LTC_ASN1_INTEGER, 1UL, r,
85                                   LTC_ASN1_INTEGER, 1UL, s,
86                                   LTC_ASN1_EOL, 0UL, NULL)) != CRYPT_OK) {
87       goto error;
88    }
89 
90    /* get the order */
91    if ((err = mp_read_radix(p, (char *)key->dp->order, 16)) != CRYPT_OK)                                { goto error; }
92 
93    /* get the modulus */
94    if ((err = mp_read_radix(m, (char *)key->dp->prime, 16)) != CRYPT_OK)                                { goto error; }
95 
96    /* check for zero */
97    if (mp_iszero(r) || mp_iszero(s) || mp_cmp(r, p) != LTC_MP_LT || mp_cmp(s, p) != LTC_MP_LT) {
98       err = CRYPT_INVALID_PACKET;
99       goto error;
100    }
101 
102    /* read hash */
103    if ((err = mp_read_unsigned_bin(e, (unsigned char *)hash, (int)hashlen)) != CRYPT_OK)                { goto error; }
104 
105    /*  w  = s^-1 mod n */
106    if ((err = mp_invmod(s, p, w)) != CRYPT_OK)                                                          { goto error; }
107 
108    /* u1 = ew */
109    if ((err = mp_mulmod(e, w, p, u1)) != CRYPT_OK)                                                      { goto error; }
110 
111    /* u2 = rw */
112    if ((err = mp_mulmod(r, w, p, u2)) != CRYPT_OK)                                                      { goto error; }
113 
114    /* find mG and mQ */
115    if ((err = mp_read_radix(mG->x, (char *)key->dp->Gx, 16)) != CRYPT_OK)                               { goto error; }
116    if ((err = mp_read_radix(mG->y, (char *)key->dp->Gy, 16)) != CRYPT_OK)                               { goto error; }
117    if ((err = mp_set(mG->z, 1)) != CRYPT_OK)                                                            { goto error; }
118 
119    if ((err = mp_copy(key->pubkey.x, mQ->x)) != CRYPT_OK)                                               { goto error; }
120    if ((err = mp_copy(key->pubkey.y, mQ->y)) != CRYPT_OK)                                               { goto error; }
121    if ((err = mp_copy(key->pubkey.z, mQ->z)) != CRYPT_OK)                                               { goto error; }
122 
123    /* compute u1*mG + u2*mQ = mG */
124    if (ltc_mp.ecc_mul2add == NULL) {
125       if ((err = ltc_mp.ecc_ptmul(u1, mG, mG, m, 0)) != CRYPT_OK)                                       { goto error; }
126       if ((err = ltc_mp.ecc_ptmul(u2, mQ, mQ, m, 0)) != CRYPT_OK)                                       { goto error; }
127 
128       /* find the montgomery mp */
129       if ((err = mp_montgomery_setup(m, &mp)) != CRYPT_OK)                                              { goto error; }
130 
131       /* add them */
132       if ((err = ltc_mp.ecc_ptadd(mQ, mG, mG, m, mp)) != CRYPT_OK)                                      { goto error; }
133 
134       /* reduce */
135       if ((err = ltc_mp.ecc_map(mG, m, mp)) != CRYPT_OK)                                                { goto error; }
136    } else {
137       /* use Shamir's trick to compute u1*mG + u2*mQ using half of the doubles */
138       if ((err = ltc_mp.ecc_mul2add(mG, u1, mQ, u2, mG, m)) != CRYPT_OK)                                { goto error; }
139    }
140 
141    /* v = X_x1 mod n */
142    if ((err = mp_mod(mG->x, p, v)) != CRYPT_OK)                                                         { goto error; }
143 
144    /* does v == r */
145    if (mp_cmp(v, r) == LTC_MP_EQ) {
146       *stat = 1;
147    }
148 
149    /* clear up and return */
150    err = CRYPT_OK;
151 error:
152    ltc_ecc_del_point(mG);
153    ltc_ecc_del_point(mQ);
154    mp_clear_multi(r, s, v, w, u1, u2, p, e, m, NULL);
155    if (mp != NULL) {
156       mp_montgomery_free(mp);
157    }
158    return err;
159 }
160 
161 #endif
162 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc_verify_hash.c,v $ */
163 /* $Revision: 1.12 $ */
164 /* $Date: 2006/12/04 05:07:59 $ */
165 
166