Bitcoin Core  0.19.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(const unsigned char **sigp, const unsigned char *sigend) {
50  int lenleft, b1;
51  size_t ret = 0;
52  if (*sigp >= sigend) {
53  return -1;
54  }
55  b1 = *((*sigp)++);
56  if (b1 == 0xFF) {
57  /* X.690-0207 8.1.3.5.c the value 0xFF shall not be used. */
58  return -1;
59  }
60  if ((b1 & 0x80) == 0) {
61  /* X.690-0207 8.1.3.4 short form length octets */
62  return b1;
63  }
64  if (b1 == 0x80) {
65  /* Indefinite length is not allowed in DER. */
66  return -1;
67  }
68  /* X.690-207 8.1.3.5 long form length octets */
69  lenleft = b1 & 0x7F;
70  if (lenleft > sigend - *sigp) {
71  return -1;
72  }
73  if (**sigp == 0) {
74  /* Not the shortest possible length encoding. */
75  return -1;
76  }
77  if ((size_t)lenleft > sizeof(size_t)) {
78  /* The resulting length would exceed the range of a size_t, so
79  * certainly longer than the passed array size.
80  */
81  return -1;
82  }
83  while (lenleft > 0) {
84  ret = (ret << 8) | **sigp;
85  if (ret + lenleft > (size_t)(sigend - *sigp)) {
86  /* Result exceeds the length of the passed array. */
87  return -1;
88  }
89  (*sigp)++;
90  lenleft--;
91  }
92  if (ret < 128) {
93  /* Not the shortest possible length encoding. */
94  return -1;
95  }
96  return ret;
97 }
98 
99 static int secp256k1_der_parse_integer(secp256k1_scalar *r, const unsigned char **sig, const unsigned char *sigend) {
100  int overflow = 0;
101  unsigned char ra[32] = {0};
102  int rlen;
103 
104  if (*sig == sigend || **sig != 0x02) {
105  /* Not a primitive integer (X.690-0207 8.3.1). */
106  return 0;
107  }
108  (*sig)++;
109  rlen = secp256k1_der_read_len(sig, sigend);
110  if (rlen <= 0 || (*sig) + rlen > sigend) {
111  /* Exceeds bounds or not at least length 1 (X.690-0207 8.3.1). */
112  return 0;
113  }
114  if (**sig == 0x00 && rlen > 1 && (((*sig)[1]) & 0x80) == 0x00) {
115  /* Excessive 0x00 padding. */
116  return 0;
117  }
118  if (**sig == 0xFF && rlen > 1 && (((*sig)[1]) & 0x80) == 0x80) {
119  /* Excessive 0xFF padding. */
120  return 0;
121  }
122  if ((**sig & 0x80) == 0x80) {
123  /* Negative. */
124  overflow = 1;
125  }
126  while (rlen > 0 && **sig == 0) {
127  /* Skip leading zero bytes */
128  rlen--;
129  (*sig)++;
130  }
131  if (rlen > 32) {
132  overflow = 1;
133  }
134  if (!overflow) {
135  memcpy(ra + 32 - rlen, *sig, rlen);
136  secp256k1_scalar_set_b32(r, ra, &overflow);
137  }
138  if (overflow) {
140  }
141  (*sig) += rlen;
142  return 1;
143 }
144 
145 static int secp256k1_ecdsa_sig_parse(secp256k1_scalar *rr, secp256k1_scalar *rs, const unsigned char *sig, size_t size) {
146  const unsigned char *sigend = sig + size;
147  int rlen;
148  if (sig == sigend || *(sig++) != 0x30) {
149  /* The encoding doesn't start with a constructed sequence (X.690-0207 8.9.1). */
150  return 0;
151  }
152  rlen = secp256k1_der_read_len(&sig, sigend);
153  if (rlen < 0 || sig + rlen > sigend) {
154  /* Tuple exceeds bounds */
155  return 0;
156  }
157  if (sig + rlen != sigend) {
158  /* Garbage after tuple. */
159  return 0;
160  }
161 
162  if (!secp256k1_der_parse_integer(rr, &sig, sigend)) {
163  return 0;
164  }
165  if (!secp256k1_der_parse_integer(rs, &sig, sigend)) {
166  return 0;
167  }
168 
169  if (sig != sigend) {
170  /* Trailing garbage inside tuple. */
171  return 0;
172  }
173 
174  return 1;
175 }
176 
177 static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, size_t *size, const secp256k1_scalar* ar, const secp256k1_scalar* as) {
178  unsigned char r[33] = {0}, s[33] = {0};
179  unsigned char *rp = r, *sp = s;
180  size_t lenR = 33, lenS = 33;
181  secp256k1_scalar_get_b32(&r[1], ar);
182  secp256k1_scalar_get_b32(&s[1], as);
183  while (lenR > 1 && rp[0] == 0 && rp[1] < 0x80) { lenR--; rp++; }
184  while (lenS > 1 && sp[0] == 0 && sp[1] < 0x80) { lenS--; sp++; }
185  if (*size < 6+lenS+lenR) {
186  *size = 6 + lenS + lenR;
187  return 0;
188  }
189  *size = 6 + lenS + lenR;
190  sig[0] = 0x30;
191  sig[1] = 4 + lenS + lenR;
192  sig[2] = 0x02;
193  sig[3] = lenR;
194  memcpy(sig+4, rp, lenR);
195  sig[4+lenR] = 0x02;
196  sig[5+lenR] = lenS;
197  memcpy(sig+lenR+6, sp, lenS);
198  return 1;
199 }
200 
201 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) {
202  unsigned char c[32];
203  secp256k1_scalar sn, u1, u2;
204 #if !defined(EXHAUSTIVE_TEST_ORDER)
205  secp256k1_fe xr;
206 #endif
207  secp256k1_gej pubkeyj;
208  secp256k1_gej pr;
209 
211  return 0;
212  }
213 
214  secp256k1_scalar_inverse_var(&sn, sigs);
215  secp256k1_scalar_mul(&u1, &sn, message);
216  secp256k1_scalar_mul(&u2, &sn, sigr);
217  secp256k1_gej_set_ge(&pubkeyj, pubkey);
218  secp256k1_ecmult(ctx, &pr, &pubkeyj, &u2, &u1);
219  if (secp256k1_gej_is_infinity(&pr)) {
220  return 0;
221  }
222 
223 #if defined(EXHAUSTIVE_TEST_ORDER)
224 {
225  secp256k1_scalar computed_r;
226  secp256k1_ge pr_ge;
227  secp256k1_ge_set_gej(&pr_ge, &pr);
228  secp256k1_fe_normalize(&pr_ge.x);
229 
230  secp256k1_fe_get_b32(c, &pr_ge.x);
231  secp256k1_scalar_set_b32(&computed_r, c, NULL);
232  return secp256k1_scalar_eq(sigr, &computed_r);
233 }
234 #else
235  secp256k1_scalar_get_b32(c, sigr);
236  secp256k1_fe_set_b32(&xr, c);
237 
254  if (secp256k1_gej_eq_x_var(&xr, &pr)) {
255  /* xr * pr.z^2 mod p == pr.x, so the signature is valid. */
256  return 1;
257  }
258  if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
259  /* xr + n >= p, so we can skip testing the second case. */
260  return 0;
261  }
262  secp256k1_fe_add(&xr, &secp256k1_ecdsa_const_order_as_fe);
263  if (secp256k1_gej_eq_x_var(&xr, &pr)) {
264  /* (xr + n) * pr.z^2 mod p == pr.x, so the signature is valid. */
265  return 1;
266  }
267  return 0;
268 #endif
269 }
270 
271 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) {
272  unsigned char b[32];
273  secp256k1_gej rp;
274  secp256k1_ge r;
276  int overflow = 0;
277 
278  secp256k1_ecmult_gen(ctx, &rp, nonce);
279  secp256k1_ge_set_gej(&r, &rp);
282  secp256k1_fe_get_b32(b, &r.x);
283  secp256k1_scalar_set_b32(sigr, b, &overflow);
284  /* These two conditions should be checked before calling */
286  VERIFY_CHECK(overflow == 0);
287 
288  if (recid) {
289  /* The overflow condition is cryptographically unreachable as hitting it requires finding the discrete log
290  * of some P where P.x >= order, and only 1 in about 2^127 points meet this criteria.
291  */
292  *recid = (overflow ? 2 : 0) | (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
293  }
294  secp256k1_scalar_mul(&n, sigr, seckey);
295  secp256k1_scalar_add(&n, &n, message);
296  secp256k1_scalar_inverse(sigs, nonce);
297  secp256k1_scalar_mul(sigs, sigs, &n);
299  secp256k1_gej_clear(&rp);
300  secp256k1_ge_clear(&r);
301  if (secp256k1_scalar_is_zero(sigs)) {
302  return 0;
303  }
304  if (secp256k1_scalar_is_high(sigs)) {
305  secp256k1_scalar_negate(sigs, sigs);
306  if (recid) {
307  *recid ^= 1;
308  }
309  }
310  return 1;
311 }
312 
313 #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:67
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:201
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:271
static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a)
Compute the complement of a scalar (modulo the group order).
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:177
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 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:145
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 int secp256k1_der_read_len(const unsigned char **sigp, const unsigned char *sigend)
Definition: ecdsa_impl.h:49
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:99
static secp256k1_context * ctx
Definition: tests.c:46
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 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