|
380
|
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, [email protected], 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 */ |
|
|
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 |
