]> Git Repo - secp256k1.git/blob - src/ecdsa_impl.h
Merge pull request #137
[secp256k1.git] / src / ecdsa_impl.h
1 /**********************************************************************
2  * Copyright (c) 2013, 2014 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
18 typedef struct {
19     secp256k1_fe_t order_as_fe;
20     secp256k1_fe_t p_minus_order;
21 } secp256k1_ecdsa_consts_t;
22
23 static const secp256k1_ecdsa_consts_t *secp256k1_ecdsa_consts = NULL;
24
25 static void secp256k1_ecdsa_start(void) {
26     if (secp256k1_ecdsa_consts != NULL)
27         return;
28
29     /* Allocate. */
30     secp256k1_ecdsa_consts_t *ret = (secp256k1_ecdsa_consts_t*)checked_malloc(sizeof(secp256k1_ecdsa_consts_t));
31
32     static const unsigned char order[] = {
33         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
34         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
35         0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
36         0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x41
37     };
38
39     secp256k1_fe_set_b32(&ret->order_as_fe, order);
40     secp256k1_fe_negate(&ret->p_minus_order, &ret->order_as_fe, 1);
41     secp256k1_fe_normalize_var(&ret->p_minus_order);
42
43     /* Set the global pointer. */
44     secp256k1_ecdsa_consts = ret;
45 }
46
47 static void secp256k1_ecdsa_stop(void) {
48     if (secp256k1_ecdsa_consts == NULL)
49         return;
50
51     secp256k1_ecdsa_consts_t *c = (secp256k1_ecdsa_consts_t*)secp256k1_ecdsa_consts;
52     secp256k1_ecdsa_consts = NULL;
53     free(c);
54 }
55
56 static int secp256k1_ecdsa_sig_parse(secp256k1_ecdsa_sig_t *r, const unsigned char *sig, int size) {
57     if (sig[0] != 0x30) return 0;
58     int lenr = sig[3];
59     if (5+lenr >= size) return 0;
60     int lens = sig[lenr+5];
61     if (sig[1] != lenr+lens+4) return 0;
62     if (lenr+lens+6 > size) return 0;
63     if (sig[2] != 0x02) return 0;
64     if (lenr == 0) return 0;
65     if (sig[lenr+4] != 0x02) return 0;
66     if (lens == 0) return 0;
67     const unsigned char *sp = sig + 6 + lenr;
68     while (lens > 0 && sp[0] == 0) {
69         lens--;
70         sp++;
71     }
72     if (lens > 32) return 0;
73     const unsigned char *rp = sig + 4;
74     while (lenr > 0 && rp[0] == 0) {
75         lenr--;
76         rp++;
77     }
78     if (lenr > 32) return 0;
79     unsigned char ra[32] = {0}, sa[32] = {0};
80     memcpy(ra + 32 - lenr, rp, lenr);
81     memcpy(sa + 32 - lens, sp, lens);
82     int overflow = 0;
83     secp256k1_scalar_set_b32(&r->r, ra, &overflow);
84     if (overflow) return 0;
85     secp256k1_scalar_set_b32(&r->s, sa, &overflow);
86     if (overflow) return 0;
87     return 1;
88 }
89
90 static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, int *size, const secp256k1_ecdsa_sig_t *a) {
91     unsigned char r[33] = {0}, s[33] = {0};
92     secp256k1_scalar_get_b32(&r[1], &a->r);
93     secp256k1_scalar_get_b32(&s[1], &a->s);
94     unsigned char *rp = r, *sp = s;
95     int lenR = 33, lenS = 33;
96     while (lenR > 1 && rp[0] == 0 && rp[1] < 0x80) { lenR--; rp++; }
97     while (lenS > 1 && sp[0] == 0 && sp[1] < 0x80) { lenS--; sp++; }
98     if (*size < 6+lenS+lenR)
99         return 0;
100     *size = 6 + lenS + lenR;
101     sig[0] = 0x30;
102     sig[1] = 4 + lenS + lenR;
103     sig[2] = 0x02;
104     sig[3] = lenR;
105     memcpy(sig+4, rp, lenR);
106     sig[4+lenR] = 0x02;
107     sig[5+lenR] = lenS;
108     memcpy(sig+lenR+6, sp, lenS);
109     return 1;
110 }
111
112 static int secp256k1_ecdsa_sig_recompute(secp256k1_scalar_t *r2, const secp256k1_ecdsa_sig_t *sig, const secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message) {
113     if (secp256k1_scalar_is_zero(&sig->r) || secp256k1_scalar_is_zero(&sig->s))
114         return 0;
115
116     int ret = 0;
117     secp256k1_scalar_t sn, u1, u2;
118     secp256k1_scalar_inverse_var(&sn, &sig->s);
119     secp256k1_scalar_mul(&u1, &sn, message);
120     secp256k1_scalar_mul(&u2, &sn, &sig->r);
121     secp256k1_gej_t pubkeyj; secp256k1_gej_set_ge(&pubkeyj, pubkey);
122     secp256k1_gej_t pr; secp256k1_ecmult(&pr, &pubkeyj, &u2, &u1);
123     if (!secp256k1_gej_is_infinity(&pr)) {
124         secp256k1_fe_t xr; secp256k1_gej_get_x_var(&xr, &pr);
125         secp256k1_fe_normalize_var(&xr);
126         unsigned char xrb[32]; secp256k1_fe_get_b32(xrb, &xr);
127         secp256k1_scalar_set_b32(r2, xrb, NULL);
128         ret = 1;
129     }
130     return ret;
131 }
132
133 static int secp256k1_ecdsa_sig_recover(const secp256k1_ecdsa_sig_t *sig, secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message, int recid) {
134     if (secp256k1_scalar_is_zero(&sig->r) || secp256k1_scalar_is_zero(&sig->s))
135         return 0;
136
137     unsigned char brx[32];
138     secp256k1_scalar_get_b32(brx, &sig->r);
139     secp256k1_fe_t fx;
140     VERIFY_CHECK(secp256k1_fe_set_b32(&fx, brx)); /* brx comes from a scalar, so is less than the order; certainly less than p */
141     if (recid & 2) {
142         if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_consts->p_minus_order) >= 0)
143             return 0;
144         secp256k1_fe_add(&fx, &secp256k1_ecdsa_consts->order_as_fe);
145     }
146     secp256k1_ge_t x;
147     if (!secp256k1_ge_set_xo_var(&x, &fx, recid & 1))
148         return 0;
149     secp256k1_gej_t xj;
150     secp256k1_gej_set_ge(&xj, &x);
151     secp256k1_scalar_t rn, u1, u2;
152     secp256k1_scalar_inverse_var(&rn, &sig->r);
153     secp256k1_scalar_mul(&u1, &rn, message);
154     secp256k1_scalar_negate(&u1, &u1);
155     secp256k1_scalar_mul(&u2, &rn, &sig->s);
156     secp256k1_gej_t qj;
157     secp256k1_ecmult(&qj, &xj, &u2, &u1);
158     secp256k1_ge_set_gej_var(pubkey, &qj);
159     return !secp256k1_gej_is_infinity(&qj);
160 }
161
162 static int secp256k1_ecdsa_sig_verify(const secp256k1_ecdsa_sig_t *sig, const secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message) {
163     secp256k1_scalar_t r2;
164     int ret = 0;
165     ret = secp256k1_ecdsa_sig_recompute(&r2, sig, pubkey, message) && secp256k1_scalar_eq(&sig->r, &r2);
166     return ret;
167 }
168
169 static int secp256k1_ecdsa_sig_sign(secp256k1_ecdsa_sig_t *sig, const secp256k1_scalar_t *seckey, const secp256k1_scalar_t *message, const secp256k1_scalar_t *nonce, int *recid) {
170     secp256k1_gej_t rp;
171     secp256k1_ecmult_gen(&rp, nonce);
172     secp256k1_ge_t r;
173     secp256k1_ge_set_gej(&r, &rp);
174     unsigned char b[32];
175     secp256k1_fe_normalize(&r.x);
176     secp256k1_fe_normalize(&r.y);
177     secp256k1_fe_get_b32(b, &r.x);
178     int overflow = 0;
179     secp256k1_scalar_set_b32(&sig->r, b, &overflow);
180     if (recid)
181         *recid = (overflow ? 2 : 0) | (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
182     secp256k1_scalar_t n;
183     secp256k1_scalar_mul(&n, &sig->r, seckey);
184     secp256k1_scalar_add(&n, &n, message);
185     secp256k1_scalar_inverse(&sig->s, nonce);
186     secp256k1_scalar_mul(&sig->s, &sig->s, &n);
187     secp256k1_scalar_clear(&n);
188     secp256k1_gej_clear(&rp);
189     secp256k1_ge_clear(&r);
190     if (secp256k1_scalar_is_zero(&sig->s))
191         return 0;
192     if (secp256k1_scalar_is_high(&sig->s)) {
193         secp256k1_scalar_negate(&sig->s, &sig->s);
194         if (recid)
195             *recid ^= 1;
196     }
197     return 1;
198 }
199
200 static void secp256k1_ecdsa_sig_set_rs(secp256k1_ecdsa_sig_t *sig, const secp256k1_scalar_t *r, const secp256k1_scalar_t *s) {
201     sig->r = *r;
202     sig->s = *s;
203 }
204
205 #endif
This page took 0.033996 seconds and 4 git commands to generate.