Mercurial > dropbear

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

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
379:b66a00272a90 382:0cbe8f6dbf9e
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