Bitcoin Core  0.20.99
P2P Digital Currency
ecdsa_impl.h
Go to the documentation of this file.
1 /**********************************************************************
2  * Copyright (c) 2013-2015 Pieter Wuille *
3  * Distributed under the MIT software license, see the accompanying *
4  * file COPYING or http://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 
32  0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL,
33  0xBAAEDCE6UL, 0xAF48A03BUL, 0xBFD25E8CUL, 0xD0364141UL
34 );
35 
46  0, 0, 0, 1, 0x45512319UL, 0x50B75FC4UL, 0x402DA172UL, 0x2FC9BAEEUL
47 );
48 
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 
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) {
148  }
149  (*sig) += rlen;
150  return 1;
151 }
152 
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 
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 
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 
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 
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 
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;
282  int overflow = 0;
283  int high;
284 
285  secp256k1_ecmult_gen(ctx, &rp, nonce);
286  secp256k1_ge_set_gej(&r, &rp);
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);
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 */
static int secp256k1_scalar_eq(const secp256k1_scalar *a, const secp256k1_scalar *b)
Compare two scalars.
static void secp256k1_scalar_mul(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
Multiply two scalars (modulo the group order).
#define VERIFY_CHECK(cond)
Definition: util.h:68
static int secp256k1_gej_is_infinity(const secp256k1_gej *a)
Check whether a group element is the point at infinity.
static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp256k1_gej *r, const secp256k1_scalar *a)
Multiply with the generator: R = a*G.
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)
Definition: ecdsa_impl.h:207
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)
Definition: ecdsa_impl.h:277
static int secp256k1_scalar_is_zero(const secp256k1_scalar *a)
Check whether a scalar equals zero.
static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, size_t *size, const secp256k1_scalar *ar, const secp256k1_scalar *as)
Definition: ecdsa_impl.h:183
static void secp256k1_ecmult(const secp256k1_ecmult_context *ctx, secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng)
Double multiply: R = na*A + ng*G.
static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *bin, int *overflow)
Set a scalar from a big endian byte array.
A group element of the secp256k1 curve, in jacobian coordinates.
Definition: group.h:24
static int secp256k1_der_read_len(size_t *len, const unsigned char **sigp, const unsigned char *sigend)
Definition: ecdsa_impl.h:49
static const secp256k1_fe secp256k1_ecdsa_const_order_as_fe
Group order for secp256k1 defined as &#39;n&#39; in "Standards for Efficient Cryptography" (SEC2) 2...
Definition: ecdsa_impl.h:31
#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0)
Definition: field_10x26.h:40
static int secp256k1_ecdsa_sig_parse(secp256k1_scalar *rr, secp256k1_scalar *rs, const unsigned char *sig, size_t size)
Definition: ecdsa_impl.h:153
static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a)
Adds a field element to another.
static int secp256k1_fe_is_odd(const secp256k1_fe *a)
Check the "oddness" of a field element.
static void secp256k1_scalar_inverse(secp256k1_scalar *r, const secp256k1_scalar *a)
Compute the inverse of a scalar (modulo the group order).
static int secp256k1_der_parse_integer(secp256k1_scalar *r, const unsigned char **sig, const unsigned char *sigend)
Definition: ecdsa_impl.h:102
static secp256k1_context * ctx
Definition: tests.c:36
static void secp256k1_ge_set_gej(secp256k1_ge *r, secp256k1_gej *a)
Set a group element equal to another which is given in jacobian coordinates.
static void secp256k1_gej_clear(secp256k1_gej *r)
Clear a secp256k1_gej to prevent leaking sensitive information.
static int secp256k1_scalar_is_high(const secp256k1_scalar *a)
Check whether a scalar is higher than the group order divided by 2.
static void secp256k1_scalar_clear(secp256k1_scalar *r)
Clear a scalar to prevent the leak of sensitive data.
A group element of the secp256k1 curve, in affine coordinates.
Definition: group.h:14
secp256k1_fe x
Definition: group.h:15
static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a)
Compare the X coordinate of a group element (jacobian).
static void secp256k1_ge_clear(secp256k1_ge *r)
Clear a secp256k1_ge to prevent leaking sensitive information.
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13
static int secp256k1_scalar_cond_negate(secp256k1_scalar *a, int flag)
Conditionally negate a number, in constant time.
static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar *a)
Convert a scalar to a byte array.
static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a)
Set a field element equal to 32-byte big endian value.
static int secp256k1_fe_cmp_var(const secp256k1_fe *a, const secp256k1_fe *b)
Compare two field elements.
static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
Add two scalars together (modulo the group order).
static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v)
Set a scalar to an unsigned integer.
static void secp256k1_scalar_inverse_var(secp256k1_scalar *r, const secp256k1_scalar *a)
Compute the inverse of a scalar (modulo the group order), without constant-time guarantee.
void * memcpy(void *a, const void *b, size_t c)
static void secp256k1_fe_normalize(secp256k1_fe *r)
Field element module.
static void secp256k1_fe_get_b32(unsigned char *r, const secp256k1_fe *a)
Convert a field element to a 32-byte big endian value.
static void secp256k1_gej_set_ge(secp256k1_gej *r, const secp256k1_ge *a)
Set a group element (jacobian) equal to another which is given in affine coordinates.
secp256k1_fe y
Definition: group.h:16
static const secp256k1_fe secp256k1_ecdsa_const_p_minus_order
Difference between field and order, values &#39;p&#39; and &#39;n&#39; values defined in "Standards for Efficient Cry...
Definition: ecdsa_impl.h:45