1 /* LibTomCrypt, modular cryptographic library -- Tom St Denis */
2 /* SPDX-License-Identifier: Unlicense */
3
4 #include "tomcrypt_private.h"
5
6 #ifdef LTC_MECC
7
8 #ifdef LTC_ECC_SHAMIR
9
10 /**
11 @file ecc_recover_key.c
12 ECC Crypto, Russ Williams
13 */
14
15 /**
16 Recover ECC public key from signature and hash
17 @param sig The signature to verify
18 @param siglen The length of the signature (octets)
19 @param hash The hash (message digest) that was signed
20 @param hashlen The length of the hash (octets)
21 @param recid The recovery ID ("v"), can be -1 if signature contains it
22 @param sigformat The format of the signature (ecc_signature_type)
23 @param key The recovered public ECC key
24 @return CRYPT_OK if successful (even if the signature is not valid)
25 */
ecc_recover_key(const unsigned char * sig,unsigned long siglen,const unsigned char * hash,unsigned long hashlen,int recid,ecc_signature_type sigformat,ecc_key * key)26 int ecc_recover_key(const unsigned char *sig, unsigned long siglen,
27 const unsigned char *hash, unsigned long hashlen,
28 int recid, ecc_signature_type sigformat, ecc_key *key)
29 {
30 ecc_point *mG = NULL, *mQ = NULL, *mR = NULL;
31 void *p, *m, *a, *b;
32 void *r, *s, *v, *w, *t1, *t2, *u1, *u2, *v1, *v2, *e, *x, *y, *a_plus3;
33 void *mu = NULL, *ma = NULL;
34 void *mp = NULL;
35 int err;
36 unsigned long pbits, pbytes, i, shift_right;
37 unsigned char ch, buf[MAXBLOCKSIZE];
38
39 LTC_ARGCHK(sig != NULL);
40 LTC_ARGCHK(hash != NULL);
41 LTC_ARGCHK(key != NULL);
42
43 /* BEWARE: requires sqrtmod_prime */
44 if (ltc_mp.sqrtmod_prime == NULL) {
45 return CRYPT_ERROR;
46 }
47
48 /* allocate ints */
49 if ((err = mp_init_multi(&r, &s, &v, &w, &t1, &t2, &u1, &u2, &v1, &v2, &e, &x, &y, &a_plus3, LTC_NULL)) != CRYPT_OK) {
50 return err;
51 }
52
53 p = key->dp.order;
54 m = key->dp.prime;
55 a = key->dp.A;
56 b = key->dp.B;
57 if ((err = mp_add_d(a, 3, a_plus3)) != CRYPT_OK) {
58 goto error;
59 }
60
61 /* allocate points */
62 mG = ltc_ecc_new_point();
63 mQ = ltc_ecc_new_point();
64 mR = ltc_ecc_new_point();
65 if (mR == NULL || mQ == NULL || mG == NULL) {
66 err = CRYPT_MEM;
67 goto error;
68 }
69
70 if (sigformat == LTC_ECCSIG_ANSIX962) {
71 /* ANSI X9.62 format - ASN.1 encoded SEQUENCE{ INTEGER(r), INTEGER(s) } */
72 if ((err = der_decode_sequence_multi_ex(sig, siglen, LTC_DER_SEQ_SEQUENCE | LTC_DER_SEQ_STRICT,
73 LTC_ASN1_INTEGER, 1UL, r,
74 LTC_ASN1_INTEGER, 1UL, s,
75 LTC_ASN1_EOL, 0UL, LTC_NULL)) != CRYPT_OK) { goto error; }
76 }
77 else if (sigformat == LTC_ECCSIG_RFC7518) {
78 /* RFC7518 format - raw (r,s) */
79 i = mp_unsigned_bin_size(key->dp.order);
80 if (siglen != (2*i)) {
81 err = CRYPT_INVALID_PACKET;
82 goto error;
83 }
84 if ((err = mp_read_unsigned_bin(r, (unsigned char *)sig, i)) != CRYPT_OK) { goto error; }
85 if ((err = mp_read_unsigned_bin(s, (unsigned char *)sig+i, i)) != CRYPT_OK) { goto error; }
86 }
87 else if (sigformat == LTC_ECCSIG_ETH27) {
88 /* Ethereum (v,r,s) format */
89 if (pk_oid_cmp_with_ulong("1.3.132.0.10", key->dp.oid, key->dp.oidlen) != CRYPT_OK) {
90 /* Only valid for secp256k1 - OID 1.3.132.0.10 */
91 err = CRYPT_ERROR; goto error;
92 }
93 if (siglen != 65) { /* Only secp256k1 curves use this format, so must be 65 bytes long */
94 err = CRYPT_INVALID_PACKET;
95 goto error;
96 }
97 i = (unsigned long)sig[64];
98 if ((i>=27) && (i<31)) i -= 27; /* Ethereum adds 27 to recovery ID */
99 if (recid >= 0 && ((unsigned long)recid != i)) {
100 /* Recovery ID specified, but doesn't match signature */
101 err = CRYPT_INVALID_PACKET;
102 goto error;
103 }
104 recid = i;
105 if ((err = mp_read_unsigned_bin(r, (unsigned char *)sig, 32)) != CRYPT_OK) { goto error; }
106 if ((err = mp_read_unsigned_bin(s, (unsigned char *)sig+32, 32)) != CRYPT_OK) { goto error; }
107 }
108 #ifdef LTC_SSH
109 else if (sigformat == LTC_ECCSIG_RFC5656) {
110 char name[64], name2[64];
111 unsigned long namelen = sizeof(name);
112 unsigned long name2len = sizeof(name2);
113
114 /* Decode as SSH data sequence, per RFC4251 */
115 if ((err = ssh_decode_sequence_multi(sig, &siglen,
116 LTC_SSHDATA_STRING, name, &namelen,
117 LTC_SSHDATA_MPINT, r,
118 LTC_SSHDATA_MPINT, s,
119 LTC_SSHDATA_EOL, NULL)) != CRYPT_OK) { goto error; }
120
121
122 /* Check curve matches identifier string */
123 if ((err = ecc_ssh_ecdsa_encode_name(name2, &name2len, key)) != CRYPT_OK) { goto error; }
124 if ((namelen != name2len) || (XSTRCMP(name, name2) != 0)) {
125 err = CRYPT_INVALID_ARG;
126 goto error;
127 }
128 }
129 #endif
130 else {
131 /* Unknown signature format */
132 err = CRYPT_ERROR;
133 goto error;
134 }
135
136 if (recid < 0 || (unsigned long)recid >= 2*(key->dp.cofactor+1)) {
137 /* Recovery ID is out of range, reject it */
138 err = CRYPT_INVALID_ARG;
139 goto error;
140 }
141
142 /* check for zero */
143 if (mp_cmp_d(r, 0) != LTC_MP_GT || mp_cmp_d(s, 0) != LTC_MP_GT ||
144 mp_cmp(r, p) != LTC_MP_LT || mp_cmp(s, p) != LTC_MP_LT) {
145 err = CRYPT_INVALID_PACKET;
146 goto error;
147 }
148
149 /* read hash - truncate if needed */
150 pbits = mp_count_bits(p);
151 pbytes = (pbits+7) >> 3;
152 if (pbits > hashlen*8) {
153 if ((err = mp_read_unsigned_bin(e, (unsigned char *)hash, hashlen)) != CRYPT_OK) { goto error; }
154 }
155 else if (pbits % 8 == 0) {
156 if ((err = mp_read_unsigned_bin(e, (unsigned char *)hash, pbytes)) != CRYPT_OK) { goto error; }
157 }
158 else {
159 shift_right = 8 - pbits % 8;
160 for (i=0, ch=0; i<pbytes; i++) {
161 buf[i] = ch;
162 ch = (hash[i] << (8-shift_right));
163 buf[i] = buf[i] ^ (hash[i] >> shift_right);
164 }
165 if ((err = mp_read_unsigned_bin(e, (unsigned char *)buf, pbytes)) != CRYPT_OK) { goto error; }
166 }
167
168 /* decompress point from r=(x mod p) - BEWARE: requires sqrtmod_prime */
169 /* x = r + p*(recid/2) */
170 if ((err = mp_set(x, recid/2)) != CRYPT_OK) { goto error; }
171 if ((err = mp_mulmod(p, x, m, x)) != CRYPT_OK) { goto error; }
172 if ((err = mp_add(x, r, x)) != CRYPT_OK) { goto error; }
173 /* compute x^3 */
174 if ((err = mp_sqr(x, t1)) != CRYPT_OK) { goto error; }
175 if ((err = mp_mulmod(t1, x, m, t1)) != CRYPT_OK) { goto error; }
176 /* compute x^3 + a*x */
177 if ((err = mp_mulmod(a, x, m, t2)) != CRYPT_OK) { goto error; }
178 if ((err = mp_add(t1, t2, t1)) != CRYPT_OK) { goto error; }
179 /* compute x^3 + a*x + b */
180 if ((err = mp_add(t1, b, t1)) != CRYPT_OK) { goto error; }
181 /* compute sqrt(x^3 + a*x + b) */
182 if ((err = mp_sqrtmod_prime(t1, m, t2)) != CRYPT_OK) { goto error; }
183
184 /* fill in mR */
185 if ((err = mp_copy(x, mR->x)) != CRYPT_OK) { goto error; }
186 if ((mp_isodd(t2) && (recid%2)) || (!mp_isodd(t2) && !(recid%2))) {
187 if ((err = mp_mod(t2, m, mR->y)) != CRYPT_OK) { goto error; }
188 }
189 else {
190 if ((err = mp_submod(m, t2, m, mR->y)) != CRYPT_OK) { goto error; }
191 }
192 if ((err = mp_set(mR->z, 1)) != CRYPT_OK) { goto error; }
193
194 /* w = r^-1 mod n */
195 if ((err = mp_invmod(r, p, w)) != CRYPT_OK) { goto error; }
196 /* v1 = sw */
197 if ((err = mp_mulmod(s, w, p, v1)) != CRYPT_OK) { goto error; }
198 /* v2 = -ew */
199 if ((err = mp_mulmod(e, w, p, v2)) != CRYPT_OK) { goto error; }
200 if ((err = mp_submod(p, v2, p, v2)) != CRYPT_OK) { goto error; }
201
202 /* w = s^-1 mod n */
203 if ((err = mp_invmod(s, p, w)) != CRYPT_OK) { goto error; }
204 /* u1 = ew */
205 if ((err = mp_mulmod(e, w, p, u1)) != CRYPT_OK) { goto error; }
206 /* u2 = rw */
207 if ((err = mp_mulmod(r, w, p, u2)) != CRYPT_OK) { goto error; }
208
209 /* find mG */
210 if ((err = ltc_ecc_copy_point(&key->dp.base, mG)) != CRYPT_OK) { goto error; }
211
212 /* find the montgomery mp */
213 if ((err = mp_montgomery_setup(m, &mp)) != CRYPT_OK) { goto error; }
214
215 /* for curves with a == -3 keep ma == NULL */
216 if (mp_cmp(a_plus3, m) != LTC_MP_EQ) {
217 if ((err = mp_init_multi(&mu, &ma, LTC_NULL)) != CRYPT_OK) { goto error; }
218 if ((err = mp_montgomery_normalization(mu, m)) != CRYPT_OK) { goto error; }
219 if ((err = mp_mulmod(a, mu, m, ma)) != CRYPT_OK) { goto error; }
220 }
221
222 /* recover mQ from mR */
223 /* compute v1*mR + v2*mG = mQ using Shamir's trick */
224 if ((err = ltc_mp.ecc_mul2add(mR, v1, mG, v2, mQ, ma, m)) != CRYPT_OK) { goto error; }
225
226 /* compute u1*mG + u2*mQ = mG using Shamir's trick */
227 if ((err = ltc_mp.ecc_mul2add(mG, u1, mQ, u2, mG, ma, m)) != CRYPT_OK) { goto error; }
228
229 /* v = X_x1 mod n */
230 if ((err = mp_mod(mG->x, p, v)) != CRYPT_OK) { goto error; }
231
232 /* does v == r */
233 if (mp_cmp(v, r) == LTC_MP_EQ) {
234 /* found public key which verifies signature */
235 if ((err = ltc_ecc_copy_point(mQ, &key->pubkey)) != CRYPT_OK) { goto error; }
236 /* point on the curve + other checks */
237 if ((err = ltc_ecc_verify_key(key)) != CRYPT_OK) { goto error; }
238
239 key->type = PK_PUBLIC;
240
241 err = CRYPT_OK;
242 }
243 else {
244 /* not found - recid is wrong or we're unable to calculate public key for some other reason */
245 err = CRYPT_INVALID_ARG;
246 }
247
248 error:
249 if (ma != NULL) mp_clear(ma);
250 if (mu != NULL) mp_clear(mu);
251 if (mp != NULL) mp_montgomery_free(mp);
252 if (mR != NULL) ltc_ecc_del_point(mR);
253 if (mQ != NULL) ltc_ecc_del_point(mQ);
254 if (mG != NULL) ltc_ecc_del_point(mG);
255 mp_clear_multi(a_plus3, y, x, e, v2, v1, u2, u1, t2, t1, w, v, s, r, LTC_NULL);
256 return err;
257 }
258
259 #endif
260 #endif
261