]> Git Repo - secp256k1.git/blame - src/ecdsa_impl.h
Remove unused secp256k1_fe_inner_{start, stop} functions
[secp256k1.git] / src / ecdsa_impl.h
CommitLineData
71712b27
GM
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
0a433ea2 7
7a4b7691
PW
8#ifndef _SECP256K1_ECDSA_IMPL_H_
9#define _SECP256K1_ECDSA_IMPL_H_
10
f24041d6 11#include "scalar.h"
11ab5622
PW
12#include "field.h"
13#include "group.h"
14#include "ecmult.h"
949c1ebb 15#include "ecmult_gen.h"
11ab5622 16#include "ecdsa.h"
607884fc 17
f24041d6
PW
18typedef struct {
19 secp256k1_fe_t order_as_fe;
20 secp256k1_fe_t p_minus_order;
21} secp256k1_ecdsa_consts_t;
22
23static const secp256k1_ecdsa_consts_t *secp256k1_ecdsa_consts = NULL;
24
25static void secp256k1_ecdsa_start(void) {
26 if (secp256k1_ecdsa_consts != NULL)
27 return;
28
29 /* Allocate. */
a5759c57 30 secp256k1_ecdsa_consts_t *ret = (secp256k1_ecdsa_consts_t*)checked_malloc(sizeof(secp256k1_ecdsa_consts_t));
f24041d6 31
659b554d
PW
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);
f24041d6 40 secp256k1_fe_negate(&ret->p_minus_order, &ret->order_as_fe, 1);
39bd94d8 41 secp256k1_fe_normalize_var(&ret->p_minus_order);
f24041d6
PW
42
43 /* Set the global pointer. */
44 secp256k1_ecdsa_consts = ret;
45}
46
47static void secp256k1_ecdsa_stop(void) {
48 if (secp256k1_ecdsa_consts == NULL)
49 return;
50
ee3eb4be 51 secp256k1_ecdsa_consts_t *c = (secp256k1_ecdsa_consts_t*)secp256k1_ecdsa_consts;
f24041d6
PW
52 secp256k1_ecdsa_consts = NULL;
53 free(c);
54}
55
a4a43d75 56static int secp256k1_ecdsa_sig_parse(secp256k1_ecdsa_sig_t *r, const unsigned char *sig, int size) {
d41e93a5 57 if (sig[0] != 0x30) return 0;
607884fc 58 int lenr = sig[3];
d41e93a5 59 if (5+lenr >= size) return 0;
607884fc 60 int lens = sig[lenr+5];
d41e93a5
PW
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;
f24041d6
PW
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;
d41e93a5 87 return 1;
607884fc
PW
88}
89
a4a43d75 90static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, int *size, const secp256k1_ecdsa_sig_t *a) {
f24041d6
PW
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++; }
0a07e62f 98 if (*size < 6+lenS+lenR)
d41e93a5 99 return 0;
0a07e62f
PW
100 *size = 6 + lenS + lenR;
101 sig[0] = 0x30;
102 sig[1] = 4 + lenS + lenR;
103 sig[2] = 0x02;
104 sig[3] = lenR;
f24041d6 105 memcpy(sig+4, rp, lenR);
0a07e62f
PW
106 sig[4+lenR] = 0x02;
107 sig[5+lenR] = lenS;
f24041d6 108 memcpy(sig+lenR+6, sp, lenS);
d41e93a5 109 return 1;
0a07e62f
PW
110}
111
ce7eb6fb 112static int secp256k1_ecdsa_sig_verify(const secp256k1_ecdsa_sig_t *sig, const secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message) {
f24041d6 113 if (secp256k1_scalar_is_zero(&sig->r) || secp256k1_scalar_is_zero(&sig->s))
d41e93a5 114 return 0;
607884fc 115
f24041d6
PW
116 secp256k1_scalar_t sn, u1, u2;
117 secp256k1_scalar_inverse_var(&sn, &sig->s);
118 secp256k1_scalar_mul(&u1, &sn, message);
119 secp256k1_scalar_mul(&u2, &sn, &sig->r);
764332d0
PW
120 secp256k1_gej_t pubkeyj; secp256k1_gej_set_ge(&pubkeyj, pubkey);
121 secp256k1_gej_t pr; secp256k1_ecmult(&pr, &pubkeyj, &u2, &u1);
ce7eb6fb
PW
122 if (secp256k1_gej_is_infinity(&pr)) {
123 return 0;
124 }
125 unsigned char c[32];
126 secp256k1_scalar_get_b32(c, &sig->r);
127 secp256k1_fe_t xr;
128 secp256k1_fe_set_b32(&xr, c);
13278f64
PW
129
130 // We now have the recomputed R point in pr, and its claimed x coordinate (modulo n)
131 // in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p),
132 // compute the remainder modulo n, and compare it to xr. However:
133 //
134 // xr == X(pr) mod n
135 // <=> exists h. (xr + h * n < p && xr + h * n == X(pr))
136 // [Since 2 * n > p, h can only be 0 or 1]
137 // <=> (xr == X(pr)) || (xr + n < p && xr + n == X(pr))
138 // [In Jacobian coordinates, X(pr) is pr.x / pr.z^2 mod p]
139 // <=> (xr == pr.x / pr.z^2 mod p) || (xr + n < p && xr + n == pr.x / pr.z^2 mod p)
140 // [Multiplying both sides of the equations by pr.z^2 mod p]
141 // <=> (xr * pr.z^2 mod p == pr.x) || (xr + n < p && (xr + n) * pr.z^2 mod p == pr.x)
142 //
143 // Thus, we can avoid the inversion, but we have to check both cases separately.
144 // secp256k1_gej_eq_x implements the (xr * pr.z^2 mod p == pr.x) test.
ce7eb6fb 145 if (secp256k1_gej_eq_x_var(&xr, &pr)) {
13278f64 146 // xr.x == xr * xr.z^2 mod p, so the signature is valid.
ce7eb6fb
PW
147 return 1;
148 }
149 if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_consts->p_minus_order) >= 0) {
13278f64 150 // xr + p >= n, so we can skip testing the second case.
ce7eb6fb 151 return 0;
4adf6b2a 152 }
ce7eb6fb
PW
153 secp256k1_fe_add(&xr, &secp256k1_ecdsa_consts->order_as_fe);
154 if (secp256k1_gej_eq_x_var(&xr, &pr)) {
13278f64 155 // (xr + n) * pr.z^2 mod p == pr.x, so the signature is valid.
ce7eb6fb
PW
156 return 1;
157 }
158 return 0;
607884fc
PW
159}
160
f24041d6
PW
161static int secp256k1_ecdsa_sig_recover(const secp256k1_ecdsa_sig_t *sig, secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message, int recid) {
162 if (secp256k1_scalar_is_zero(&sig->r) || secp256k1_scalar_is_zero(&sig->s))
50eb498e
PW
163 return 0;
164
f24041d6
PW
165 unsigned char brx[32];
166 secp256k1_scalar_get_b32(brx, &sig->r);
167 secp256k1_fe_t fx;
168 VERIFY_CHECK(secp256k1_fe_set_b32(&fx, brx)); /* brx comes from a scalar, so is less than the order; certainly less than p */
ad52495d 169 if (recid & 2) {
f24041d6 170 if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_consts->p_minus_order) >= 0)
ad52495d 171 return 0;
f24041d6 172 secp256k1_fe_add(&fx, &secp256k1_ecdsa_consts->order_as_fe);
ad52495d 173 }
50eb498e 174 secp256k1_ge_t x;
39bd94d8 175 if (!secp256k1_ge_set_xo_var(&x, &fx, recid & 1))
50eb498e
PW
176 return 0;
177 secp256k1_gej_t xj;
178 secp256k1_gej_set_ge(&xj, &x);
f24041d6
PW
179 secp256k1_scalar_t rn, u1, u2;
180 secp256k1_scalar_inverse_var(&rn, &sig->r);
181 secp256k1_scalar_mul(&u1, &rn, message);
182 secp256k1_scalar_negate(&u1, &u1);
183 secp256k1_scalar_mul(&u2, &rn, &sig->s);
50eb498e
PW
184 secp256k1_gej_t qj;
185 secp256k1_ecmult(&qj, &xj, &u2, &u1);
da55986f 186 secp256k1_ge_set_gej_var(pubkey, &qj);
4861f836 187 return !secp256k1_gej_is_infinity(&qj);
50eb498e
PW
188}
189
a4a43d75 190static 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) {
f11ff5be 191 secp256k1_gej_t rp;
d41e93a5 192 secp256k1_ecmult_gen(&rp, nonce);
50eb498e
PW
193 secp256k1_ge_t r;
194 secp256k1_ge_set_gej(&r, &rp);
0a07e62f 195 unsigned char b[32];
50eb498e
PW
196 secp256k1_fe_normalize(&r.x);
197 secp256k1_fe_normalize(&r.y);
198 secp256k1_fe_get_b32(b, &r.x);
a9f5c8b8 199 int overflow = 0;
f24041d6 200 secp256k1_scalar_set_b32(&sig->r, b, &overflow);
d26e26f2
GM
201 if (secp256k1_scalar_is_zero(&sig->r)) {
202 /* P.x = order is on the curve, so technically sig->r could end up zero, which would be an invalid signature. */
203 secp256k1_gej_clear(&rp);
204 secp256k1_ge_clear(&r);
205 return 0;
206 }
50eb498e 207 if (recid)
a9f5c8b8
PW
208 *recid = (overflow ? 2 : 0) | (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
209 secp256k1_scalar_t n;
f24041d6 210 secp256k1_scalar_mul(&n, &sig->r, seckey);
a9f5c8b8 211 secp256k1_scalar_add(&n, &n, message);
f24041d6
PW
212 secp256k1_scalar_inverse(&sig->s, nonce);
213 secp256k1_scalar_mul(&sig->s, &sig->s, &n);
a9f5c8b8 214 secp256k1_scalar_clear(&n);
2f6c8019
GM
215 secp256k1_gej_clear(&rp);
216 secp256k1_ge_clear(&r);
f24041d6 217 if (secp256k1_scalar_is_zero(&sig->s))
d41e93a5 218 return 0;
f24041d6
PW
219 if (secp256k1_scalar_is_high(&sig->s)) {
220 secp256k1_scalar_negate(&sig->s, &sig->s);
50eb498e
PW
221 if (recid)
222 *recid ^= 1;
223 }
eb0be8ee 224 return 1;
0a07e62f
PW
225}
226
f24041d6
PW
227static void secp256k1_ecdsa_sig_set_rs(secp256k1_ecdsa_sig_t *sig, const secp256k1_scalar_t *r, const secp256k1_scalar_t *s) {
228 sig->r = *r;
229 sig->s = *s;
607884fc 230}
7a4b7691
PW
231
232#endif
This page took 0.065526 seconds and 4 git commands to generate.