Mercurial > dropbear

comparison libtomcrypt/src/pk/ecc/ecc_verify_hash.c @ 1471:6dba84798cd5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update to libtomcrypt 1.18.1, merged with Dropbear changes
author Matt Johnston <matt@ucc.asn.au>
date Fri, 09 Feb 2018 21:44:05 +0800
parents f849a5ca2efc
children 8305ebe45940
comparison
equal deleted inserted replaced
1470:8bba51a55704 1471:6dba84798cd5
3 * LibTomCrypt is a library that provides various cryptographic 3 * LibTomCrypt is a library that provides various cryptographic
4 * algorithms in a highly modular and flexible manner. 4 * algorithms in a highly modular and flexible manner.
5 * 5 *
6 * The library is free for all purposes without any express 6 * The library is free for all purposes without any express
7 * guarantee it works. 7 * guarantee it works.
8 *
9 * Tom St Denis, [email protected], http://libtom.org
10 */ 8 */
11 9
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" 10 #include "tomcrypt.h"
11
12 #ifdef LTC_MECC
18 13
19 /** 14 /**
20 @file ecc_verify_hash.c 15 @file ecc_verify_hash.c
21 ECC Crypto, Tom St Denis 16 ECC Crypto, Tom St Denis
22 */ 17 */
23 18
24 #if defined(LTC_MECC) && defined(LTC_DER) 19 static int _ecc_verify_hash(const unsigned char *sig, unsigned long siglen,
25 20 const unsigned char *hash, unsigned long hashlen,
26 /* verify 21 int *stat, ecc_key *key, int sigformat)
27 * 22 {
28 * w = s^-1 mod n 23 ecc_point *mG, *mQ;
29 * u1 = xw 24 void *r, *s, *v, *w, *u1, *u2, *e, *p, *m;
30 * u2 = rw 25 void *mp;
31 * X = u1*G + u2*Q 26 int err;
32 * v = X_x1 mod n 27 unsigned long pbits, pbytes, i, shift_right;
33 * accept if v == r 28 unsigned char ch, buf[MAXBLOCKSIZE];
34 */ 29
30 LTC_ARGCHK(sig != NULL);
31 LTC_ARGCHK(hash != NULL);
32 LTC_ARGCHK(stat != NULL);
33 LTC_ARGCHK(key != NULL);
34
35 /* default to invalid signature */
36 *stat = 0;
37 mp = NULL;
38
39 /* is the IDX valid ? */
40 if (ltc_ecc_is_valid_idx(key->idx) != 1) {
41 return CRYPT_PK_INVALID_TYPE;
42 }
43
44 /* allocate ints */
45 if ((err = mp_init_multi(&r, &s, &v, &w, &u1, &u2, &p, &e, &m, NULL)) != CRYPT_OK) {
46 return CRYPT_MEM;
47 }
48
49 /* allocate points */
50 mG = ltc_ecc_new_point();
51 mQ = ltc_ecc_new_point();
52 if (mQ == NULL || mG == NULL) {
53 err = CRYPT_MEM;
54 goto error;
55 }
56
57 if (sigformat == 1) {
58 /* RFC7518 format */
59 if ((siglen % 2) == 1) {
60 err = CRYPT_INVALID_PACKET;
61 goto error;
62 }
63 i = siglen / 2;
64 if ((err = mp_read_unsigned_bin(r, (unsigned char *)sig, i)) != CRYPT_OK) { goto error; }
65 if ((err = mp_read_unsigned_bin(s, (unsigned char *)sig+i, i)) != CRYPT_OK) { goto error; }
66 }
67 else {
68 /* ASN.1 format */
69 if ((err = der_decode_sequence_multi(sig, siglen,
70 LTC_ASN1_INTEGER, 1UL, r,
71 LTC_ASN1_INTEGER, 1UL, s,
72 LTC_ASN1_EOL, 0UL, NULL)) != CRYPT_OK) { goto error; }
73 }
74
75 /* get the order */
76 if ((err = mp_read_radix(p, (char *)key->dp->order, 16)) != CRYPT_OK) { goto error; }
77
78 /* get the modulus */
79 if ((err = mp_read_radix(m, (char *)key->dp->prime, 16)) != CRYPT_OK) { goto error; }
80
81 /* check for zero */
82 if (mp_iszero(r) || mp_iszero(s) || mp_cmp(r, p) != LTC_MP_LT || mp_cmp(s, p) != LTC_MP_LT) {
83 err = CRYPT_INVALID_PACKET;
84 goto error;
85 }
86
87 /* read hash - truncate if needed */
88 pbits = mp_count_bits(p);
89 pbytes = (pbits+7) >> 3;
90 if (pbits > hashlen*8) {
91 if ((err = mp_read_unsigned_bin(e, (unsigned char *)hash, hashlen)) != CRYPT_OK) { goto error; }
92 }
93 else if (pbits % 8 == 0) {
94 if ((err = mp_read_unsigned_bin(e, (unsigned char *)hash, pbytes)) != CRYPT_OK) { goto error; }
95 }
96 else {
97 shift_right = 8 - pbits % 8;
98 for (i=0, ch=0; i<pbytes; i++) {
99 buf[i] = ch;
100 ch = (hash[i] << (8-shift_right));
101 buf[i] = buf[i] ^ (hash[i] >> shift_right);
102 }
103 if ((err = mp_read_unsigned_bin(e, (unsigned char *)buf, pbytes)) != CRYPT_OK) { goto error; }
104 }
105
106 /* w = s^-1 mod n */
107 if ((err = mp_invmod(s, p, w)) != CRYPT_OK) { goto error; }
108
109 /* u1 = ew */
110 if ((err = mp_mulmod(e, w, p, u1)) != CRYPT_OK) { goto error; }
111
112 /* u2 = rw */
113 if ((err = mp_mulmod(r, w, p, u2)) != CRYPT_OK) { goto error; }
114
115 /* find mG and mQ */
116 if ((err = mp_read_radix(mG->x, (char *)key->dp->Gx, 16)) != CRYPT_OK) { goto error; }
117 if ((err = mp_read_radix(mG->y, (char *)key->dp->Gy, 16)) != CRYPT_OK) { goto error; }
118 if ((err = mp_set(mG->z, 1)) != CRYPT_OK) { goto error; }
119
120 if ((err = mp_copy(key->pubkey.x, mQ->x)) != CRYPT_OK) { goto error; }
121 if ((err = mp_copy(key->pubkey.y, mQ->y)) != CRYPT_OK) { goto error; }
122 if ((err = mp_copy(key->pubkey.z, mQ->z)) != CRYPT_OK) { goto error; }
123
124 /* compute u1*mG + u2*mQ = mG */
125 if (ltc_mp.ecc_mul2add == NULL) {
126 if ((err = ltc_mp.ecc_ptmul(u1, mG, mG, m, 0)) != CRYPT_OK) { goto error; }
127 if ((err = ltc_mp.ecc_ptmul(u2, mQ, mQ, m, 0)) != CRYPT_OK) { goto error; }
128
129 /* find the montgomery mp */
130 if ((err = mp_montgomery_setup(m, &mp)) != CRYPT_OK) { goto error; }
131
132 /* add them */
133 if ((err = ltc_mp.ecc_ptadd(mQ, mG, mG, m, mp)) != CRYPT_OK) { goto error; }
134
135 /* reduce */
136 if ((err = ltc_mp.ecc_map(mG, m, mp)) != CRYPT_OK) { goto error; }
137 } else {
138 /* use Shamir's trick to compute u1*mG + u2*mQ using half of the doubles */
139 if ((err = ltc_mp.ecc_mul2add(mG, u1, mQ, u2, mG, m)) != CRYPT_OK) { goto error; }
140 }
141
142 /* v = X_x1 mod n */
143 if ((err = mp_mod(mG->x, p, v)) != CRYPT_OK) { goto error; }
144
145 /* does v == r */
146 if (mp_cmp(v, r) == LTC_MP_EQ) {
147 *stat = 1;
148 }
149
150 /* clear up and return */
151 err = CRYPT_OK;
152 error:
153 ltc_ecc_del_point(mG);
154 ltc_ecc_del_point(mQ);
155 mp_clear_multi(r, s, v, w, u1, u2, p, e, m, NULL);
156 if (mp != NULL) {
157 mp_montgomery_free(mp);
158 }
159 return err;
160 }
35 161
36 /** 162 /**
37 Verify an ECC signature 163 Verify an ECC signature
38 @param sig The signature to verify 164 @param sig The signature to verify
39 @param siglen The length of the signature (octets) 165 @param siglen The length of the signature (octets)
42 @param stat Result of signature, 1==valid, 0==invalid 168 @param stat Result of signature, 1==valid, 0==invalid
43 @param key The corresponding public ECC key 169 @param key The corresponding public ECC key
44 @return CRYPT_OK if successful (even if the signature is not valid) 170 @return CRYPT_OK if successful (even if the signature is not valid)
45 */ 171 */
46 int ecc_verify_hash(const unsigned char *sig, unsigned long siglen, 172 int ecc_verify_hash(const unsigned char *sig, unsigned long siglen,
47 const unsigned char *hash, unsigned long hashlen, 173 const unsigned char *hash, unsigned long hashlen,
48 int *stat, ecc_key *key) 174 int *stat, ecc_key *key)
49 { 175 {
50 ecc_point *mG, *mQ; 176 return _ecc_verify_hash(sig, siglen, hash, hashlen, stat, key, 0);
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 } 177 }
160 178
179 /**
180 Verify an ECC signature in RFC7518 format
181 @param sig The signature to verify
182 @param siglen The length of the signature (octets)
183 @param hash The hash (message digest) that was signed
184 @param hashlen The length of the hash (octets)
185 @param stat Result of signature, 1==valid, 0==invalid
186 @param key The corresponding public ECC key
187 @return CRYPT_OK if successful (even if the signature is not valid)
188 */
189 int ecc_verify_hash_rfc7518(const unsigned char *sig, unsigned long siglen,
190 const unsigned char *hash, unsigned long hashlen,
191 int *stat, ecc_key *key)
192 {
193 return _ecc_verify_hash(sig, siglen, hash, hashlen, stat, key, 1);
194 }
195
161 #endif 196 #endif
162 /* $Source$ */ 197
163 /* $Revision$ */ 198 /* ref: $Format:%D$ */
164 /* $Date$ */ 199 /* git commit: $Format:%H$ */
165 200 /* commit time: $Format:%ai$ */