]>
Commit | Line | Data |
---|---|---|
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 | **********************************************************************/ | |
0a433ea2 | 6 | |
7a4b7691 PW |
7 | #ifndef _SECP256K1_GROUP_IMPL_H_ |
8 | #define _SECP256K1_GROUP_IMPL_H_ | |
9 | ||
f11ff5be | 10 | #include <string.h> |
607884fc | 11 | |
11ab5622 PW |
12 | #include "num.h" |
13 | #include "field.h" | |
14 | #include "group.h" | |
607884fc | 15 | |
a4a43d75 | 16 | static void secp256k1_ge_set_infinity(secp256k1_ge_t *r) { |
f11ff5be | 17 | r->infinity = 1; |
607884fc PW |
18 | } |
19 | ||
a4a43d75 | 20 | static void secp256k1_ge_set_xy(secp256k1_ge_t *r, const secp256k1_fe_t *x, const secp256k1_fe_t *y) { |
f11ff5be PW |
21 | r->infinity = 0; |
22 | r->x = *x; | |
23 | r->y = *y; | |
607884fc PW |
24 | } |
25 | ||
a4a43d75 | 26 | static int secp256k1_ge_is_infinity(const secp256k1_ge_t *a) { |
f11ff5be | 27 | return a->infinity; |
607884fc PW |
28 | } |
29 | ||
a4a43d75 | 30 | static void secp256k1_ge_neg(secp256k1_ge_t *r, const secp256k1_ge_t *a) { |
39bd94d8 | 31 | *r = *a; |
0295f0a3 | 32 | secp256k1_fe_normalize_weak(&r->y); |
39bd94d8 PW |
33 | secp256k1_fe_negate(&r->y, &r->y, 1); |
34 | } | |
35 | ||
a4a43d75 | 36 | static void secp256k1_ge_get_hex(char *r, int *rlen, const secp256k1_ge_t *a) { |
f11ff5be PW |
37 | char cx[65]; int lx=65; |
38 | char cy[65]; int ly=65; | |
39 | secp256k1_fe_get_hex(cx, &lx, &a->x); | |
40 | secp256k1_fe_get_hex(cy, &ly, &a->y); | |
41 | lx = strlen(cx); | |
42 | ly = strlen(cy); | |
43 | int len = lx + ly + 3 + 1; | |
44 | if (*rlen < len) { | |
45 | *rlen = len; | |
46 | return; | |
47 | } | |
48 | *rlen = len; | |
49 | r[0] = '('; | |
50 | memcpy(r+1, cx, lx); | |
51 | r[1+lx] = ','; | |
52 | memcpy(r+2+lx, cy, ly); | |
53 | r[2+lx+ly] = ')'; | |
54 | r[3+lx+ly] = 0; | |
55 | } | |
56 | ||
a4a43d75 | 57 | static void secp256k1_ge_set_gej(secp256k1_ge_t *r, secp256k1_gej_t *a) { |
da55986f PW |
58 | r->infinity = a->infinity; |
59 | secp256k1_fe_inv(&a->z, &a->z); | |
60 | secp256k1_fe_t z2; secp256k1_fe_sqr(&z2, &a->z); | |
61 | secp256k1_fe_t z3; secp256k1_fe_mul(&z3, &a->z, &z2); | |
62 | secp256k1_fe_mul(&a->x, &a->x, &z2); | |
63 | secp256k1_fe_mul(&a->y, &a->y, &z3); | |
64 | secp256k1_fe_set_int(&a->z, 1); | |
65 | r->x = a->x; | |
66 | r->y = a->y; | |
67 | } | |
68 | ||
a4a43d75 | 69 | static void secp256k1_ge_set_gej_var(secp256k1_ge_t *r, secp256k1_gej_t *a) { |
1136bedb PW |
70 | r->infinity = a->infinity; |
71 | if (a->infinity) { | |
72 | return; | |
73 | } | |
f11ff5be PW |
74 | secp256k1_fe_inv_var(&a->z, &a->z); |
75 | secp256k1_fe_t z2; secp256k1_fe_sqr(&z2, &a->z); | |
76 | secp256k1_fe_t z3; secp256k1_fe_mul(&z3, &a->z, &z2); | |
77 | secp256k1_fe_mul(&a->x, &a->x, &z2); | |
78 | secp256k1_fe_mul(&a->y, &a->y, &z3); | |
79 | secp256k1_fe_set_int(&a->z, 1); | |
f11ff5be PW |
80 | r->x = a->x; |
81 | r->y = a->y; | |
607884fc PW |
82 | } |
83 | ||
a4a43d75 | 84 | static void secp256k1_ge_set_all_gej_var(size_t len, secp256k1_ge_t r[len], const secp256k1_gej_t a[len]) { |
65a14abb | 85 | size_t count = 0; |
a5759c57 | 86 | secp256k1_fe_t *az = checked_malloc(sizeof(secp256k1_fe_t) * len); |
65a14abb | 87 | for (size_t i=0; i<len; i++) { |
f16be77f PD |
88 | if (!a[i].infinity) { |
89 | az[count++] = a[i].z; | |
90 | } | |
91 | } | |
92 | ||
a5759c57 | 93 | secp256k1_fe_t *azi = checked_malloc(sizeof(secp256k1_fe_t) * count); |
f16be77f | 94 | secp256k1_fe_inv_all_var(count, azi, az); |
f461b769 | 95 | free(az); |
f16be77f PD |
96 | |
97 | count = 0; | |
65a14abb | 98 | for (size_t i=0; i<len; i++) { |
f16be77f PD |
99 | r[i].infinity = a[i].infinity; |
100 | if (!a[i].infinity) { | |
101 | secp256k1_fe_t *zi = &azi[count++]; | |
102 | secp256k1_fe_t zi2; secp256k1_fe_sqr(&zi2, zi); | |
103 | secp256k1_fe_t zi3; secp256k1_fe_mul(&zi3, &zi2, zi); | |
104 | secp256k1_fe_mul(&r[i].x, &a[i].x, &zi2); | |
105 | secp256k1_fe_mul(&r[i].y, &a[i].y, &zi3); | |
106 | } | |
107 | } | |
f461b769 | 108 | free(azi); |
f16be77f PD |
109 | } |
110 | ||
a4a43d75 | 111 | static void secp256k1_gej_set_infinity(secp256k1_gej_t *r) { |
f11ff5be | 112 | r->infinity = 1; |
9338dbf7 PW |
113 | secp256k1_fe_set_int(&r->x, 0); |
114 | secp256k1_fe_set_int(&r->y, 0); | |
115 | secp256k1_fe_set_int(&r->z, 0); | |
607884fc PW |
116 | } |
117 | ||
a4a43d75 | 118 | static void secp256k1_gej_set_xy(secp256k1_gej_t *r, const secp256k1_fe_t *x, const secp256k1_fe_t *y) { |
f11ff5be PW |
119 | r->infinity = 0; |
120 | r->x = *x; | |
121 | r->y = *y; | |
122 | secp256k1_fe_set_int(&r->z, 1); | |
607884fc PW |
123 | } |
124 | ||
a4a43d75 | 125 | static void secp256k1_gej_clear(secp256k1_gej_t *r) { |
2f6c8019 GM |
126 | r->infinity = 0; |
127 | secp256k1_fe_clear(&r->x); | |
128 | secp256k1_fe_clear(&r->y); | |
129 | secp256k1_fe_clear(&r->z); | |
130 | } | |
131 | ||
a4a43d75 | 132 | static void secp256k1_ge_clear(secp256k1_ge_t *r) { |
2f6c8019 GM |
133 | r->infinity = 0; |
134 | secp256k1_fe_clear(&r->x); | |
135 | secp256k1_fe_clear(&r->y); | |
136 | } | |
137 | ||
39bd94d8 | 138 | static int secp256k1_ge_set_xo_var(secp256k1_ge_t *r, const secp256k1_fe_t *x, int odd) { |
f11ff5be PW |
139 | r->x = *x; |
140 | secp256k1_fe_t x2; secp256k1_fe_sqr(&x2, x); | |
141 | secp256k1_fe_t x3; secp256k1_fe_mul(&x3, x, &x2); | |
eb0be8ee | 142 | r->infinity = 0; |
f11ff5be PW |
143 | secp256k1_fe_t c; secp256k1_fe_set_int(&c, 7); |
144 | secp256k1_fe_add(&c, &x3); | |
39bd94d8 | 145 | if (!secp256k1_fe_sqrt_var(&r->y, &c)) |
09ca4f32 | 146 | return 0; |
39bd94d8 | 147 | secp256k1_fe_normalize_var(&r->y); |
f11ff5be PW |
148 | if (secp256k1_fe_is_odd(&r->y) != odd) |
149 | secp256k1_fe_negate(&r->y, &r->y, 1); | |
09ca4f32 | 150 | return 1; |
910d0de4 | 151 | } |
607884fc | 152 | |
a4a43d75 | 153 | static void secp256k1_gej_set_ge(secp256k1_gej_t *r, const secp256k1_ge_t *a) { |
f11ff5be PW |
154 | r->infinity = a->infinity; |
155 | r->x = a->x; | |
156 | r->y = a->y; | |
157 | secp256k1_fe_set_int(&r->z, 1); | |
910d0de4 | 158 | } |
607884fc | 159 | |
ce7eb6fb PW |
160 | static int secp256k1_gej_eq_x_var(const secp256k1_fe_t *x, const secp256k1_gej_t *a) { |
161 | VERIFY_CHECK(!a->infinity); | |
162 | secp256k1_fe_t r; secp256k1_fe_sqr(&r, &a->z); secp256k1_fe_mul(&r, &r, x); | |
eed599dd | 163 | secp256k1_fe_t r2 = a->x; secp256k1_fe_normalize_weak(&r2); |
d7174edf | 164 | return secp256k1_fe_equal_var(&r, &r2); |
910d0de4 | 165 | } |
607884fc | 166 | |
0295f0a3 | 167 | static void secp256k1_gej_neg(secp256k1_gej_t *r, const secp256k1_gej_t *a) { |
f11ff5be PW |
168 | r->infinity = a->infinity; |
169 | r->x = a->x; | |
170 | r->y = a->y; | |
171 | r->z = a->z; | |
0295f0a3 | 172 | secp256k1_fe_normalize_weak(&r->y); |
f11ff5be | 173 | secp256k1_fe_negate(&r->y, &r->y, 1); |
607884fc PW |
174 | } |
175 | ||
a4a43d75 | 176 | static int secp256k1_gej_is_infinity(const secp256k1_gej_t *a) { |
f11ff5be | 177 | return a->infinity; |
0a07e62f PW |
178 | } |
179 | ||
39bd94d8 | 180 | static int secp256k1_gej_is_valid_var(const secp256k1_gej_t *a) { |
f11ff5be | 181 | if (a->infinity) |
eb0be8ee | 182 | return 0; |
71712b27 GM |
183 | /** y^2 = x^3 + 7 |
184 | * (Y/Z^3)^2 = (X/Z^2)^3 + 7 | |
185 | * Y^2 / Z^6 = X^3 / Z^6 + 7 | |
186 | * Y^2 = X^3 + 7*Z^6 | |
187 | */ | |
f11ff5be PW |
188 | secp256k1_fe_t y2; secp256k1_fe_sqr(&y2, &a->y); |
189 | secp256k1_fe_t x3; secp256k1_fe_sqr(&x3, &a->x); secp256k1_fe_mul(&x3, &x3, &a->x); | |
190 | secp256k1_fe_t z2; secp256k1_fe_sqr(&z2, &a->z); | |
910d0de4 PW |
191 | secp256k1_fe_t z6; secp256k1_fe_sqr(&z6, &z2); secp256k1_fe_mul(&z6, &z6, &z2); |
192 | secp256k1_fe_mul_int(&z6, 7); | |
193 | secp256k1_fe_add(&x3, &z6); | |
d7174edf PW |
194 | secp256k1_fe_normalize_weak(&x3); |
195 | return secp256k1_fe_equal_var(&y2, &x3); | |
607884fc PW |
196 | } |
197 | ||
39bd94d8 | 198 | static int secp256k1_ge_is_valid_var(const secp256k1_ge_t *a) { |
764332d0 PW |
199 | if (a->infinity) |
200 | return 0; | |
71712b27 | 201 | /* y^2 = x^3 + 7 */ |
764332d0 PW |
202 | secp256k1_fe_t y2; secp256k1_fe_sqr(&y2, &a->y); |
203 | secp256k1_fe_t x3; secp256k1_fe_sqr(&x3, &a->x); secp256k1_fe_mul(&x3, &x3, &a->x); | |
204 | secp256k1_fe_t c; secp256k1_fe_set_int(&c, 7); | |
205 | secp256k1_fe_add(&x3, &c); | |
d7174edf PW |
206 | secp256k1_fe_normalize_weak(&x3); |
207 | return secp256k1_fe_equal_var(&y2, &x3); | |
764332d0 PW |
208 | } |
209 | ||
a4a43d75 | 210 | static void secp256k1_gej_double_var(secp256k1_gej_t *r, const secp256k1_gej_t *a) { |
e3d692ff PW |
211 | // For secp256k1, 2Q is infinity if and only if Q is infinity. This is because if 2Q = infinity, |
212 | // Q must equal -Q, or that Q.y == -(Q.y), or Q.y is 0. For a point on y^2 = x^3 + 7 to have | |
213 | // y=0, x^3 must be -7 mod p. However, -7 has no cube root mod p. | |
f7dc1c65 PW |
214 | r->infinity = a->infinity; |
215 | if (r->infinity) { | |
607884fc PW |
216 | return; |
217 | } | |
218 | ||
910d0de4 | 219 | secp256k1_fe_t t1,t2,t3,t4; |
be82e92f | 220 | secp256k1_fe_mul(&r->z, &a->z, &a->y); |
71712b27 | 221 | secp256k1_fe_mul_int(&r->z, 2); /* Z' = 2*Y*Z (2) */ |
f11ff5be | 222 | secp256k1_fe_sqr(&t1, &a->x); |
71712b27 GM |
223 | secp256k1_fe_mul_int(&t1, 3); /* T1 = 3*X^2 (3) */ |
224 | secp256k1_fe_sqr(&t2, &t1); /* T2 = 9*X^4 (1) */ | |
f7dc1c65 | 225 | secp256k1_fe_sqr(&t3, &a->y); |
71712b27 | 226 | secp256k1_fe_mul_int(&t3, 2); /* T3 = 2*Y^2 (2) */ |
910d0de4 | 227 | secp256k1_fe_sqr(&t4, &t3); |
71712b27 | 228 | secp256k1_fe_mul_int(&t4, 2); /* T4 = 8*Y^4 (2) */ |
be82e92f | 229 | secp256k1_fe_mul(&t3, &t3, &a->x); /* T3 = 2*X*Y^2 (1) */ |
f11ff5be | 230 | r->x = t3; |
71712b27 GM |
231 | secp256k1_fe_mul_int(&r->x, 4); /* X' = 8*X*Y^2 (4) */ |
232 | secp256k1_fe_negate(&r->x, &r->x, 4); /* X' = -8*X*Y^2 (5) */ | |
233 | secp256k1_fe_add(&r->x, &t2); /* X' = 9*X^4 - 8*X*Y^2 (6) */ | |
234 | secp256k1_fe_negate(&t2, &t2, 1); /* T2 = -9*X^4 (2) */ | |
235 | secp256k1_fe_mul_int(&t3, 6); /* T3 = 12*X*Y^2 (6) */ | |
236 | secp256k1_fe_add(&t3, &t2); /* T3 = 12*X*Y^2 - 9*X^4 (8) */ | |
237 | secp256k1_fe_mul(&r->y, &t1, &t3); /* Y' = 36*X^3*Y^2 - 27*X^6 (1) */ | |
238 | secp256k1_fe_negate(&t2, &t4, 2); /* T2 = -8*Y^4 (3) */ | |
239 | secp256k1_fe_add(&r->y, &t2); /* Y' = 36*X^3*Y^2 - 27*X^6 - 8*Y^4 (4) */ | |
607884fc PW |
240 | } |
241 | ||
a4a43d75 | 242 | static void secp256k1_gej_add_var(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_gej_t *b) { |
f11ff5be PW |
243 | if (a->infinity) { |
244 | *r = *b; | |
607884fc PW |
245 | return; |
246 | } | |
f11ff5be PW |
247 | if (b->infinity) { |
248 | *r = *a; | |
607884fc PW |
249 | return; |
250 | } | |
eb0be8ee | 251 | r->infinity = 0; |
f11ff5be PW |
252 | secp256k1_fe_t z22; secp256k1_fe_sqr(&z22, &b->z); |
253 | secp256k1_fe_t z12; secp256k1_fe_sqr(&z12, &a->z); | |
254 | secp256k1_fe_t u1; secp256k1_fe_mul(&u1, &a->x, &z22); | |
255 | secp256k1_fe_t u2; secp256k1_fe_mul(&u2, &b->x, &z12); | |
256 | secp256k1_fe_t s1; secp256k1_fe_mul(&s1, &a->y, &z22); secp256k1_fe_mul(&s1, &s1, &b->z); | |
257 | secp256k1_fe_t s2; secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &a->z); | |
eed599dd PD |
258 | secp256k1_fe_t h; secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2); |
259 | secp256k1_fe_t i; secp256k1_fe_negate(&i, &s1, 1); secp256k1_fe_add(&i, &s2); | |
260 | if (secp256k1_fe_normalizes_to_zero(&h)) { | |
261 | if (secp256k1_fe_normalizes_to_zero(&i)) { | |
da55986f | 262 | secp256k1_gej_double_var(r, a); |
607884fc | 263 | } else { |
eb0be8ee | 264 | r->infinity = 1; |
607884fc PW |
265 | } |
266 | return; | |
267 | } | |
f11ff5be | 268 | secp256k1_fe_t i2; secp256k1_fe_sqr(&i2, &i); |
910d0de4 PW |
269 | secp256k1_fe_t h2; secp256k1_fe_sqr(&h2, &h); |
270 | secp256k1_fe_t h3; secp256k1_fe_mul(&h3, &h, &h2); | |
f11ff5be | 271 | secp256k1_fe_mul(&r->z, &a->z, &b->z); secp256k1_fe_mul(&r->z, &r->z, &h); |
910d0de4 | 272 | secp256k1_fe_t t; secp256k1_fe_mul(&t, &u1, &h2); |
f11ff5be PW |
273 | r->x = t; secp256k1_fe_mul_int(&r->x, 2); secp256k1_fe_add(&r->x, &h3); secp256k1_fe_negate(&r->x, &r->x, 3); secp256k1_fe_add(&r->x, &i2); |
274 | secp256k1_fe_negate(&r->y, &r->x, 5); secp256k1_fe_add(&r->y, &t); secp256k1_fe_mul(&r->y, &r->y, &i); | |
910d0de4 | 275 | secp256k1_fe_mul(&h3, &h3, &s1); secp256k1_fe_negate(&h3, &h3, 1); |
f11ff5be | 276 | secp256k1_fe_add(&r->y, &h3); |
607884fc PW |
277 | } |
278 | ||
a4a43d75 | 279 | static void secp256k1_gej_add_ge_var(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_ge_t *b) { |
f11ff5be PW |
280 | if (a->infinity) { |
281 | r->infinity = b->infinity; | |
282 | r->x = b->x; | |
283 | r->y = b->y; | |
284 | secp256k1_fe_set_int(&r->z, 1); | |
607884fc PW |
285 | return; |
286 | } | |
f11ff5be PW |
287 | if (b->infinity) { |
288 | *r = *a; | |
607884fc PW |
289 | return; |
290 | } | |
eb0be8ee | 291 | r->infinity = 0; |
f11ff5be | 292 | secp256k1_fe_t z12; secp256k1_fe_sqr(&z12, &a->z); |
d7174edf | 293 | secp256k1_fe_t u1 = a->x; secp256k1_fe_normalize_weak(&u1); |
f11ff5be | 294 | secp256k1_fe_t u2; secp256k1_fe_mul(&u2, &b->x, &z12); |
d7174edf | 295 | secp256k1_fe_t s1 = a->y; secp256k1_fe_normalize_weak(&s1); |
f11ff5be | 296 | secp256k1_fe_t s2; secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &a->z); |
eed599dd PD |
297 | secp256k1_fe_t h; secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2); |
298 | secp256k1_fe_t i; secp256k1_fe_negate(&i, &s1, 1); secp256k1_fe_add(&i, &s2); | |
299 | if (secp256k1_fe_normalizes_to_zero(&h)) { | |
300 | if (secp256k1_fe_normalizes_to_zero(&i)) { | |
da55986f | 301 | secp256k1_gej_double_var(r, a); |
607884fc | 302 | } else { |
eb0be8ee | 303 | r->infinity = 1; |
607884fc PW |
304 | } |
305 | return; | |
306 | } | |
f11ff5be | 307 | secp256k1_fe_t i2; secp256k1_fe_sqr(&i2, &i); |
910d0de4 PW |
308 | secp256k1_fe_t h2; secp256k1_fe_sqr(&h2, &h); |
309 | secp256k1_fe_t h3; secp256k1_fe_mul(&h3, &h, &h2); | |
f11ff5be | 310 | r->z = a->z; secp256k1_fe_mul(&r->z, &r->z, &h); |
910d0de4 | 311 | secp256k1_fe_t t; secp256k1_fe_mul(&t, &u1, &h2); |
f11ff5be PW |
312 | r->x = t; secp256k1_fe_mul_int(&r->x, 2); secp256k1_fe_add(&r->x, &h3); secp256k1_fe_negate(&r->x, &r->x, 3); secp256k1_fe_add(&r->x, &i2); |
313 | secp256k1_fe_negate(&r->y, &r->x, 5); secp256k1_fe_add(&r->y, &t); secp256k1_fe_mul(&r->y, &r->y, &i); | |
910d0de4 | 314 | secp256k1_fe_mul(&h3, &h3, &s1); secp256k1_fe_negate(&h3, &h3, 1); |
f11ff5be | 315 | secp256k1_fe_add(&r->y, &h3); |
607884fc PW |
316 | } |
317 | ||
a4a43d75 | 318 | static void secp256k1_gej_add_ge(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_ge_t *b) { |
9338dbf7 PW |
319 | VERIFY_CHECK(!b->infinity); |
320 | VERIFY_CHECK(a->infinity == 0 || a->infinity == 1); | |
321 | ||
71712b27 GM |
322 | /** In: |
323 | * Eric Brier and Marc Joye, Weierstrass Elliptic Curves and Side-Channel Attacks. | |
324 | * In D. Naccache and P. Paillier, Eds., Public Key Cryptography, vol. 2274 of Lecture Notes in Computer Science, pages 335-345. Springer-Verlag, 2002. | |
325 | * we find as solution for a unified addition/doubling formula: | |
326 | * lambda = ((x1 + x2)^2 - x1 * x2 + a) / (y1 + y2), with a = 0 for secp256k1's curve equation. | |
327 | * x3 = lambda^2 - (x1 + x2) | |
328 | * 2*y3 = lambda * (x1 + x2 - 2 * x3) - (y1 + y2). | |
329 | * | |
330 | * Substituting x_i = Xi / Zi^2 and yi = Yi / Zi^3, for i=1,2,3, gives: | |
331 | * U1 = X1*Z2^2, U2 = X2*Z1^2 | |
2a54f9bc | 332 | * S1 = Y1*Z2^3, S2 = Y2*Z1^3 |
71712b27 GM |
333 | * Z = Z1*Z2 |
334 | * T = U1+U2 | |
335 | * M = S1+S2 | |
336 | * Q = T*M^2 | |
337 | * R = T^2-U1*U2 | |
338 | * X3 = 4*(R^2-Q) | |
339 | * Y3 = 4*(R*(3*Q-2*R^2)-M^4) | |
340 | * Z3 = 2*M*Z | |
341 | * (Note that the paper uses xi = Xi / Zi and yi = Yi / Zi instead.) | |
342 | */ | |
343 | ||
344 | secp256k1_fe_t zz; secp256k1_fe_sqr(&zz, &a->z); /* z = Z1^2 */ | |
0295f0a3 | 345 | secp256k1_fe_t u1 = a->x; secp256k1_fe_normalize_weak(&u1); /* u1 = U1 = X1*Z2^2 (1) */ |
71712b27 | 346 | secp256k1_fe_t u2; secp256k1_fe_mul(&u2, &b->x, &zz); /* u2 = U2 = X2*Z1^2 (1) */ |
0295f0a3 | 347 | secp256k1_fe_t s1 = a->y; secp256k1_fe_normalize_weak(&s1); /* s1 = S1 = Y1*Z2^3 (1) */ |
71712b27 GM |
348 | secp256k1_fe_t s2; secp256k1_fe_mul(&s2, &b->y, &zz); /* s2 = Y2*Z2^2 (1) */ |
349 | secp256k1_fe_mul(&s2, &s2, &a->z); /* s2 = S2 = Y2*Z1^3 (1) */ | |
350 | secp256k1_fe_t z = a->z; /* z = Z = Z1*Z2 (8) */ | |
351 | secp256k1_fe_t t = u1; secp256k1_fe_add(&t, &u2); /* t = T = U1+U2 (2) */ | |
352 | secp256k1_fe_t m = s1; secp256k1_fe_add(&m, &s2); /* m = M = S1+S2 (2) */ | |
353 | secp256k1_fe_t n; secp256k1_fe_sqr(&n, &m); /* n = M^2 (1) */ | |
354 | secp256k1_fe_t q; secp256k1_fe_mul(&q, &n, &t); /* q = Q = T*M^2 (1) */ | |
355 | secp256k1_fe_sqr(&n, &n); /* n = M^4 (1) */ | |
356 | secp256k1_fe_t rr; secp256k1_fe_sqr(&rr, &t); /* rr = T^2 (1) */ | |
357 | secp256k1_fe_mul(&t, &u1, &u2); secp256k1_fe_negate(&t, &t, 1); /* t = -U1*U2 (2) */ | |
358 | secp256k1_fe_add(&rr, &t); /* rr = R = T^2-U1*U2 (3) */ | |
359 | secp256k1_fe_sqr(&t, &rr); /* t = R^2 (1) */ | |
360 | secp256k1_fe_mul(&r->z, &m, &z); /* r->z = M*Z (1) */ | |
eed599dd | 361 | int infinity = secp256k1_fe_normalizes_to_zero(&r->z) * (1 - a->infinity); |
71712b27 GM |
362 | secp256k1_fe_mul_int(&r->z, 2 * (1 - a->infinity)); /* r->z = Z3 = 2*M*Z (2) */ |
363 | r->x = t; /* r->x = R^2 (1) */ | |
364 | secp256k1_fe_negate(&q, &q, 1); /* q = -Q (2) */ | |
365 | secp256k1_fe_add(&r->x, &q); /* r->x = R^2-Q (3) */ | |
9338dbf7 | 366 | secp256k1_fe_normalize(&r->x); |
71712b27 GM |
367 | secp256k1_fe_mul_int(&q, 3); /* q = -3*Q (6) */ |
368 | secp256k1_fe_mul_int(&t, 2); /* t = 2*R^2 (2) */ | |
369 | secp256k1_fe_add(&t, &q); /* t = 2*R^2-3*Q (8) */ | |
370 | secp256k1_fe_mul(&t, &t, &rr); /* t = R*(2*R^2-3*Q) (1) */ | |
371 | secp256k1_fe_add(&t, &n); /* t = R*(2*R^2-3*Q)+M^4 (2) */ | |
372 | secp256k1_fe_negate(&r->y, &t, 2); /* r->y = R*(3*Q-2*R^2)-M^4 (3) */ | |
0295f0a3 | 373 | secp256k1_fe_normalize_weak(&r->y); |
71712b27 GM |
374 | secp256k1_fe_mul_int(&r->x, 4 * (1 - a->infinity)); /* r->x = X3 = 4*(R^2-Q) */ |
375 | secp256k1_fe_mul_int(&r->y, 4 * (1 - a->infinity)); /* r->y = Y3 = 4*R*(3*Q-2*R^2)-4*M^4 (4) */ | |
9338dbf7 | 376 | |
71712b27 GM |
377 | /** In case a->infinity == 1, the above code results in r->x, r->y, and r->z all equal to 0. |
378 | * Add b->x to x, b->y to y, and 1 to z in that case. | |
379 | */ | |
9338dbf7 PW |
380 | t = b->x; secp256k1_fe_mul_int(&t, a->infinity); |
381 | secp256k1_fe_add(&r->x, &t); | |
382 | t = b->y; secp256k1_fe_mul_int(&t, a->infinity); | |
383 | secp256k1_fe_add(&r->y, &t); | |
384 | secp256k1_fe_set_int(&t, a->infinity); | |
385 | secp256k1_fe_add(&r->z, &t); | |
386 | r->infinity = infinity; | |
387 | } | |
388 | ||
389 | ||
390 | ||
a4a43d75 | 391 | static void secp256k1_gej_get_hex(char *r, int *rlen, const secp256k1_gej_t *a) { |
f11ff5be PW |
392 | secp256k1_gej_t c = *a; |
393 | secp256k1_ge_t t; secp256k1_ge_set_gej(&t, &c); | |
394 | secp256k1_ge_get_hex(r, rlen, &t); | |
607884fc PW |
395 | } |
396 | ||
399c03f2 | 397 | #ifdef USE_ENDOMORPHISM |
a4a43d75 | 398 | static void secp256k1_gej_mul_lambda(secp256k1_gej_t *r, const secp256k1_gej_t *a) { |
f11ff5be PW |
399 | const secp256k1_fe_t *beta = &secp256k1_ge_consts->beta; |
400 | *r = *a; | |
401 | secp256k1_fe_mul(&r->x, &r->x, beta); | |
607884fc | 402 | } |
399c03f2 | 403 | #endif |
607884fc | 404 | |
a4a43d75 | 405 | static void secp256k1_ge_start(void) { |
ff29b855 PW |
406 | static const unsigned char secp256k1_ge_consts_g_x[] = { |
407 | 0x79,0xBE,0x66,0x7E,0xF9,0xDC,0xBB,0xAC, | |
408 | 0x55,0xA0,0x62,0x95,0xCE,0x87,0x0B,0x07, | |
409 | 0x02,0x9B,0xFC,0xDB,0x2D,0xCE,0x28,0xD9, | |
410 | 0x59,0xF2,0x81,0x5B,0x16,0xF8,0x17,0x98 | |
411 | }; | |
412 | static const unsigned char secp256k1_ge_consts_g_y[] = { | |
413 | 0x48,0x3A,0xDA,0x77,0x26,0xA3,0xC4,0x65, | |
414 | 0x5D,0xA4,0xFB,0xFC,0x0E,0x11,0x08,0xA8, | |
415 | 0xFD,0x17,0xB4,0x48,0xA6,0x85,0x54,0x19, | |
416 | 0x9C,0x47,0xD0,0x8F,0xFB,0x10,0xD4,0xB8 | |
417 | }; | |
399c03f2 | 418 | #ifdef USE_ENDOMORPHISM |
71712b27 | 419 | /* properties of secp256k1's efficiently computable endomorphism */ |
ff29b855 PW |
420 | static const unsigned char secp256k1_ge_consts_beta[] = { |
421 | 0x7a,0xe9,0x6a,0x2b,0x65,0x7c,0x07,0x10, | |
422 | 0x6e,0x64,0x47,0x9e,0xac,0x34,0x34,0xe9, | |
423 | 0x9c,0xf0,0x49,0x75,0x12,0xf5,0x89,0x95, | |
424 | 0xc1,0x39,0x6c,0x28,0x71,0x95,0x01,0xee | |
425 | }; | |
399c03f2 | 426 | #endif |
f11ff5be | 427 | if (secp256k1_ge_consts == NULL) { |
a5759c57 | 428 | secp256k1_ge_consts_t *ret = (secp256k1_ge_consts_t*)checked_malloc(sizeof(secp256k1_ge_consts_t)); |
399c03f2 | 429 | #ifdef USE_ENDOMORPHISM |
d907ebc0 | 430 | VERIFY_CHECK(secp256k1_fe_set_b32(&ret->beta, secp256k1_ge_consts_beta)); |
399c03f2 | 431 | #endif |
f11ff5be | 432 | secp256k1_fe_t g_x, g_y; |
d907ebc0 PW |
433 | VERIFY_CHECK(secp256k1_fe_set_b32(&g_x, secp256k1_ge_consts_g_x)); |
434 | VERIFY_CHECK(secp256k1_fe_set_b32(&g_y, secp256k1_ge_consts_g_y)); | |
f11ff5be PW |
435 | secp256k1_ge_set_xy(&ret->g, &g_x, &g_y); |
436 | secp256k1_ge_consts = ret; | |
437 | } | |
438 | } | |
439 | ||
a4a43d75 | 440 | static void secp256k1_ge_stop(void) { |
f11ff5be PW |
441 | if (secp256k1_ge_consts != NULL) { |
442 | secp256k1_ge_consts_t *c = (secp256k1_ge_consts_t*)secp256k1_ge_consts; | |
f11ff5be PW |
443 | free((void*)c); |
444 | secp256k1_ge_consts = NULL; | |
445 | } | |
446 | } | |
7a4b7691 PW |
447 | |
448 | #endif |