1 /***********************************************************************
2 * Copyright (c) 2013-2015 Pieter Wuille *
3 * Distributed under the MIT software license, see the accompanying *
4 * file COPYING or https://www.opensource.org/licenses/mit-license.php.*
5 ***********************************************************************/
6
7
8 #ifndef SECP256K1_ECDSA_IMPL_H
9 #define SECP256K1_ECDSA_IMPL_H
10
11 #include "scalar.h"
12 #include "field.h"
13 #include "group.h"
14 #include "ecmult.h"
15 #include "ecmult_gen.h"
16 #include "ecdsa.h"
17
18 /** Group order for secp256k1 defined as 'n' in "Standards for Efficient Cryptography" (SEC2) 2.7.1
19 * sage: for t in xrange(1023, -1, -1):
20 * .. p = 2**256 - 2**32 - t
21 * .. if p.is_prime():
22 * .. print '%x'%p
23 * .. break
24 * 'fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f'
25 * sage: a = 0
26 * sage: b = 7
27 * sage: F = FiniteField (p)
28 * sage: '%x' % (EllipticCurve ([F (a), F (b)]).order())
29 * 'fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141'
30 */
31 static const secp256k1_fe secp256k1_ecdsa_const_order_as_fe = SECP256K1_FE_CONST(
32 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL,
33 0xBAAEDCE6UL, 0xAF48A03BUL, 0xBFD25E8CUL, 0xD0364141UL
34 );
35
36 /** Difference between field and order, values 'p' and 'n' values defined in
37 * "Standards for Efficient Cryptography" (SEC2) 2.7.1.
38 * sage: p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
39 * sage: a = 0
40 * sage: b = 7
41 * sage: F = FiniteField (p)
42 * sage: '%x' % (p - EllipticCurve ([F (a), F (b)]).order())
43 * '14551231950b75fc4402da1722fc9baee'
44 */
45 static const secp256k1_fe secp256k1_ecdsa_const_p_minus_order = SECP256K1_FE_CONST(
46 0, 0, 0, 1, 0x45512319UL, 0x50B75FC4UL, 0x402DA172UL, 0x2FC9BAEEUL
47 );
48
secp256k1_der_read_len(size_t * len,const unsigned char ** sigp,const unsigned char * sigend)49 static int secp256k1_der_read_len(size_t *len, const unsigned char **sigp, const unsigned char *sigend) {
50 size_t lenleft;
51 unsigned char b1;
52 VERIFY_CHECK(len != NULL);
53 *len = 0;
54 if (*sigp >= sigend) {
55 return 0;
56 }
57 b1 = *((*sigp)++);
58 if (b1 == 0xFF) {
59 /* X.690-0207 8.1.3.5.c the value 0xFF shall not be used. */
60 return 0;
61 }
62 if ((b1 & 0x80) == 0) {
63 /* X.690-0207 8.1.3.4 short form length octets */
64 *len = b1;
65 return 1;
66 }
67 if (b1 == 0x80) {
68 /* Indefinite length is not allowed in DER. */
69 return 0;
70 }
71 /* X.690-207 8.1.3.5 long form length octets */
72 lenleft = b1 & 0x7F; /* lenleft is at least 1 */
73 if (lenleft > (size_t)(sigend - *sigp)) {
74 return 0;
75 }
76 if (**sigp == 0) {
77 /* Not the shortest possible length encoding. */
78 return 0;
79 }
80 if (lenleft > sizeof(size_t)) {
81 /* The resulting length would exceed the range of a size_t, so
82 * certainly longer than the passed array size.
83 */
84 return 0;
85 }
86 while (lenleft > 0) {
87 *len = (*len << 8) | **sigp;
88 (*sigp)++;
89 lenleft--;
90 }
91 if (*len > (size_t)(sigend - *sigp)) {
92 /* Result exceeds the length of the passed array. */
93 return 0;
94 }
95 if (*len < 128) {
96 /* Not the shortest possible length encoding. */
97 return 0;
98 }
99 return 1;
100 }
101
secp256k1_der_parse_integer(secp256k1_scalar * r,const unsigned char ** sig,const unsigned char * sigend)102 static int secp256k1_der_parse_integer(secp256k1_scalar *r, const unsigned char **sig, const unsigned char *sigend) {
103 int overflow = 0;
104 unsigned char ra[32] = {0};
105 size_t rlen;
106
107 if (*sig == sigend || **sig != 0x02) {
108 /* Not a primitive integer (X.690-0207 8.3.1). */
109 return 0;
110 }
111 (*sig)++;
112 if (secp256k1_der_read_len(&rlen, sig, sigend) == 0) {
113 return 0;
114 }
115 if (rlen == 0 || *sig + rlen > sigend) {
116 /* Exceeds bounds or not at least length 1 (X.690-0207 8.3.1). */
117 return 0;
118 }
119 if (**sig == 0x00 && rlen > 1 && (((*sig)[1]) & 0x80) == 0x00) {
120 /* Excessive 0x00 padding. */
121 return 0;
122 }
123 if (**sig == 0xFF && rlen > 1 && (((*sig)[1]) & 0x80) == 0x80) {
124 /* Excessive 0xFF padding. */
125 return 0;
126 }
127 if ((**sig & 0x80) == 0x80) {
128 /* Negative. */
129 overflow = 1;
130 }
131 /* There is at most one leading zero byte:
132 * if there were two leading zero bytes, we would have failed and returned 0
133 * because of excessive 0x00 padding already. */
134 if (rlen > 0 && **sig == 0) {
135 /* Skip leading zero byte */
136 rlen--;
137 (*sig)++;
138 }
139 if (rlen > 32) {
140 overflow = 1;
141 }
142 if (!overflow) {
143 memcpy(ra + 32 - rlen, *sig, rlen);
144 secp256k1_scalar_set_b32(r, ra, &overflow);
145 }
146 if (overflow) {
147 secp256k1_scalar_set_int(r, 0);
148 }
149 (*sig) += rlen;
150 return 1;
151 }
152
secp256k1_ecdsa_sig_parse(secp256k1_scalar * rr,secp256k1_scalar * rs,const unsigned char * sig,size_t size)153 static int secp256k1_ecdsa_sig_parse(secp256k1_scalar *rr, secp256k1_scalar *rs, const unsigned char *sig, size_t size) {
154 const unsigned char *sigend = sig + size;
155 size_t rlen;
156 if (sig == sigend || *(sig++) != 0x30) {
157 /* The encoding doesn't start with a constructed sequence (X.690-0207 8.9.1). */
158 return 0;
159 }
160 if (secp256k1_der_read_len(&rlen, &sig, sigend) == 0) {
161 return 0;
162 }
163 if (rlen != (size_t)(sigend - sig)) {
164 /* Tuple exceeds bounds or garage after tuple. */
165 return 0;
166 }
167
168 if (!secp256k1_der_parse_integer(rr, &sig, sigend)) {
169 return 0;
170 }
171 if (!secp256k1_der_parse_integer(rs, &sig, sigend)) {
172 return 0;
173 }
174
175 if (sig != sigend) {
176 /* Trailing garbage inside tuple. */
177 return 0;
178 }
179
180 return 1;
181 }
182
secp256k1_ecdsa_sig_serialize(unsigned char * sig,size_t * size,const secp256k1_scalar * ar,const secp256k1_scalar * as)183 static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, size_t *size, const secp256k1_scalar* ar, const secp256k1_scalar* as) {
184 unsigned char r[33] = {0}, s[33] = {0};
185 unsigned char *rp = r, *sp = s;
186 size_t lenR = 33, lenS = 33;
187 secp256k1_scalar_get_b32(&r[1], ar);
188 secp256k1_scalar_get_b32(&s[1], as);
189 while (lenR > 1 && rp[0] == 0 && rp[1] < 0x80) { lenR--; rp++; }
190 while (lenS > 1 && sp[0] == 0 && sp[1] < 0x80) { lenS--; sp++; }
191 if (*size < 6+lenS+lenR) {
192 *size = 6 + lenS + lenR;
193 return 0;
194 }
195 *size = 6 + lenS + lenR;
196 sig[0] = 0x30;
197 sig[1] = 4 + lenS + lenR;
198 sig[2] = 0x02;
199 sig[3] = lenR;
200 memcpy(sig+4, rp, lenR);
201 sig[4+lenR] = 0x02;
202 sig[5+lenR] = lenS;
203 memcpy(sig+lenR+6, sp, lenS);
204 return 1;
205 }
206
secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context * ctx,const secp256k1_scalar * sigr,const secp256k1_scalar * sigs,const secp256k1_ge * pubkey,const secp256k1_scalar * message)207 static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context *ctx, const secp256k1_scalar *sigr, const secp256k1_scalar *sigs, const secp256k1_ge *pubkey, const secp256k1_scalar *message) {
208 unsigned char c[32];
209 secp256k1_scalar sn, u1, u2;
210 #if !defined(EXHAUSTIVE_TEST_ORDER)
211 secp256k1_fe xr;
212 #endif
213 secp256k1_gej pubkeyj;
214 secp256k1_gej pr;
215
216 if (secp256k1_scalar_is_zero(sigr) || secp256k1_scalar_is_zero(sigs)) {
217 return 0;
218 }
219
220 secp256k1_scalar_inverse_var(&sn, sigs);
221 secp256k1_scalar_mul(&u1, &sn, message);
222 secp256k1_scalar_mul(&u2, &sn, sigr);
223 secp256k1_gej_set_ge(&pubkeyj, pubkey);
224 secp256k1_ecmult(ctx, &pr, &pubkeyj, &u2, &u1);
225 if (secp256k1_gej_is_infinity(&pr)) {
226 return 0;
227 }
228
229 #if defined(EXHAUSTIVE_TEST_ORDER)
230 {
231 secp256k1_scalar computed_r;
232 secp256k1_ge pr_ge;
233 secp256k1_ge_set_gej(&pr_ge, &pr);
234 secp256k1_fe_normalize(&pr_ge.x);
235
236 secp256k1_fe_get_b32(c, &pr_ge.x);
237 secp256k1_scalar_set_b32(&computed_r, c, NULL);
238 return secp256k1_scalar_eq(sigr, &computed_r);
239 }
240 #else
241 secp256k1_scalar_get_b32(c, sigr);
242 secp256k1_fe_set_b32(&xr, c);
243
244 /** We now have the recomputed R point in pr, and its claimed x coordinate (modulo n)
245 * in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p),
246 * compute the remainder modulo n, and compare it to xr. However:
247 *
248 * xr == X(pr) mod n
249 * <=> exists h. (xr + h * n < p && xr + h * n == X(pr))
250 * [Since 2 * n > p, h can only be 0 or 1]
251 * <=> (xr == X(pr)) || (xr + n < p && xr + n == X(pr))
252 * [In Jacobian coordinates, X(pr) is pr.x / pr.z^2 mod p]
253 * <=> (xr == pr.x / pr.z^2 mod p) || (xr + n < p && xr + n == pr.x / pr.z^2 mod p)
254 * [Multiplying both sides of the equations by pr.z^2 mod p]
255 * <=> (xr * pr.z^2 mod p == pr.x) || (xr + n < p && (xr + n) * pr.z^2 mod p == pr.x)
256 *
257 * Thus, we can avoid the inversion, but we have to check both cases separately.
258 * secp256k1_gej_eq_x implements the (xr * pr.z^2 mod p == pr.x) test.
259 */
260 if (secp256k1_gej_eq_x_var(&xr, &pr)) {
261 /* xr * pr.z^2 mod p == pr.x, so the signature is valid. */
262 return 1;
263 }
264 if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
265 /* xr + n >= p, so we can skip testing the second case. */
266 return 0;
267 }
268 secp256k1_fe_add(&xr, &secp256k1_ecdsa_const_order_as_fe);
269 if (secp256k1_gej_eq_x_var(&xr, &pr)) {
270 /* (xr + n) * pr.z^2 mod p == pr.x, so the signature is valid. */
271 return 1;
272 }
273 return 0;
274 #endif
275 }
276
secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context * ctx,secp256k1_scalar * sigr,secp256k1_scalar * sigs,const secp256k1_scalar * seckey,const secp256k1_scalar * message,const secp256k1_scalar * nonce,int * recid)277 static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context *ctx, secp256k1_scalar *sigr, secp256k1_scalar *sigs, const secp256k1_scalar *seckey, const secp256k1_scalar *message, const secp256k1_scalar *nonce, int *recid) {
278 unsigned char b[32];
279 secp256k1_gej rp;
280 secp256k1_ge r;
281 secp256k1_scalar n;
282 int overflow = 0;
283 int high;
284
285 secp256k1_ecmult_gen(ctx, &rp, nonce);
286 secp256k1_ge_set_gej(&r, &rp);
287 secp256k1_fe_normalize(&r.x);
288 secp256k1_fe_normalize(&r.y);
289 secp256k1_fe_get_b32(b, &r.x);
290 secp256k1_scalar_set_b32(sigr, b, &overflow);
291 if (recid) {
292 /* The overflow condition is cryptographically unreachable as hitting it requires finding the discrete log
293 * of some P where P.x >= order, and only 1 in about 2^127 points meet this criteria.
294 */
295 *recid = (overflow << 1) | secp256k1_fe_is_odd(&r.y);
296 }
297 secp256k1_scalar_mul(&n, sigr, seckey);
298 secp256k1_scalar_add(&n, &n, message);
299 secp256k1_scalar_inverse(sigs, nonce);
300 secp256k1_scalar_mul(sigs, sigs, &n);
301 secp256k1_scalar_clear(&n);
302 secp256k1_gej_clear(&rp);
303 secp256k1_ge_clear(&r);
304 high = secp256k1_scalar_is_high(sigs);
305 secp256k1_scalar_cond_negate(sigs, high);
306 if (recid) {
307 *recid ^= high;
308 }
309 /* P.x = order is on the curve, so technically sig->r could end up being zero, which would be an invalid signature.
310 * This is cryptographically unreachable as hitting it requires finding the discrete log of P.x = N.
311 */
312 return !secp256k1_scalar_is_zero(sigr) & !secp256k1_scalar_is_zero(sigs);
313 }
314
315 #endif /* SECP256K1_ECDSA_IMPL_H */
316