Line data Source code
1 : /* secp256k1 square root and group arithmetic, shared by both backends.
2 : Included by fd_secp256k1_private.h after the backend (fd_secp256k1_s2n.c
3 : or fd_secp256k1_ref.c) has defined the fd_secp256k1_fp_* and
4 : fd_secp256k1_scalar_* primitives. */
5 :
6 : /*
7 : Returns NULL if a is not a square.
8 : r may NOT alias a
9 :
10 : r = a^((p + 1) / 4) mod p
11 :
12 : We know that a^((p-1)/2) = 1 when a is a quadratic residue.
13 : So for a valid square, we can show that re-squaring recovers a with:
14 : (a^((p+1)/4))^2 = a^((p+1)/1)
15 : = a * a^((p-1)/2)
16 : = a (if a is a square)
17 :
18 : We use a more optimal addition-chain which takes advantage that quite
19 : a few of the powers consist of all 1s when in binary form. We build up:
20 : x2 = a^3
21 : x3 = a^7
22 : x6 = a^63
23 : x9 = a^511
24 : x11 = a^2047
25 : x22 = a^(2^22 − 1) # All of these are all 1s
26 : x44 = a^(2^44 − 1)
27 : x88 = a^(2^88 − 1)
28 : x176 = a^(2^176 − 1)
29 : x220 = a^(2^220 − 1)
30 : x223 = a^(2^223 − 1)
31 :
32 : These "all 1s" exponents are convenient because:
33 : (2^k - 1)*(2^m)+(2^m - 1) = 2^(k+m) - 1
34 : Allowing us to quickly build them.
35 :
36 : If a is NOT a square, then
37 : a^((p-1)/2) = -1
38 : and the result will fail the final verification.
39 : */
40 : static inline fd_secp256k1_fp_t *
41 : fd_secp256k1_fp_sqrt( fd_secp256k1_fp_t * restrict r,
42 2254 : fd_secp256k1_fp_t const * restrict a ) {
43 2254 : fd_secp256k1_fp_t x2;
44 2254 : fd_secp256k1_fp_t x3;
45 :
46 2254 : fd_secp256k1_fp_sqr( &x2, a );
47 2254 : fd_secp256k1_fp_mul( &x2, &x2, a );
48 :
49 2254 : fd_secp256k1_fp_sqr( &x3, &x2 );
50 2254 : fd_secp256k1_fp_mul( &x3, &x3, a );
51 :
52 2254 : fd_secp256k1_fp_t x6 = x3;
53 9014 : for( int j=0; j<3; j++ ) fd_secp256k1_fp_sqr( &x6, &x6 );
54 2254 : fd_secp256k1_fp_mul( &x6, &x6, &x3 );
55 :
56 2254 : fd_secp256k1_fp_t x9 = x6;
57 9011 : for( int j=0; j<3; j++ ) fd_secp256k1_fp_sqr( &x9, &x9 );
58 2254 : fd_secp256k1_fp_mul( &x9, &x9, &x3 );
59 :
60 2254 : fd_secp256k1_fp_t x11 = x9;
61 6761 : for( int j=0; j<2; j++ ) fd_secp256k1_fp_sqr( &x11, &x11 );
62 2254 : fd_secp256k1_fp_mul( &x11, &x11, &x2 );
63 :
64 2254 : fd_secp256k1_fp_t x22 = x11;
65 27028 : for( int j=0; j<11; j++ ) fd_secp256k1_fp_sqr( &x22, &x22 );
66 2254 : fd_secp256k1_fp_mul( &x22, &x22, &x11 );
67 :
68 2254 : fd_secp256k1_fp_t x44 = x22;
69 51723 : for( int j=0; j<22; j++ ) fd_secp256k1_fp_sqr( &x44, &x44 );
70 2254 : fd_secp256k1_fp_mul( &x44, &x44, &x22 );
71 :
72 2254 : fd_secp256k1_fp_t x88 = x44;
73 101071 : for( int j=0; j<44; j++ ) fd_secp256k1_fp_sqr( &x88, &x88 );
74 2254 : fd_secp256k1_fp_mul( &x88, &x88, &x44 );
75 :
76 2254 : fd_secp256k1_fp_t x176 = x88;
77 199233 : for( int j=0; j<88; j++ ) fd_secp256k1_fp_sqr( &x176, &x176 );
78 2254 : fd_secp256k1_fp_mul( &x176, &x176, &x88 );
79 :
80 2254 : fd_secp256k1_fp_t x220 = x176;
81 101073 : for( int j=0; j<44; j++ ) fd_secp256k1_fp_sqr( &x220, &x220 );
82 2254 : fd_secp256k1_fp_mul( &x220, &x220, &x44 );
83 :
84 2254 : fd_secp256k1_fp_t x223 = x220;
85 9012 : for( int j=0; j<3; j++ ) fd_secp256k1_fp_sqr( &x223, &x223 );
86 2254 : fd_secp256k1_fp_mul( &x223, &x223, &x3 );
87 :
88 2254 : fd_secp256k1_fp_t t1 = x223;
89 53968 : for( int j=0; j<23; j++ ) fd_secp256k1_fp_sqr( &t1, &t1 );
90 2254 : fd_secp256k1_fp_mul( &t1, &t1, &x22 );
91 :
92 15767 : for( int j=0; j<6; j++ ) fd_secp256k1_fp_sqr( &t1, &t1 );
93 2254 : fd_secp256k1_fp_mul( &t1, &t1, &x2 );
94 2254 : fd_secp256k1_fp_sqr( &t1, &t1 );
95 2254 : fd_secp256k1_fp_sqr( r, &t1 );
96 :
97 2254 : fd_secp256k1_fp_sqr( &t1, r );
98 2254 : if( FD_UNLIKELY( !fd_secp256k1_fp_eq( &t1, a ) ) ) {
99 81 : return NULL;
100 81 : }
101 :
102 2173 : return r;
103 2254 : }
104 :
105 : /* Point */
106 :
107 : /* Sets a group element to the identity element in Jacobian coordinates */
108 : static inline void
109 6520 : fd_secp256k1_point_set_identity( fd_secp256k1_point_t *r ) {
110 6520 : fd_secp256k1_fp_set( r->x, fd_secp256k1_const_zero );
111 6520 : fd_secp256k1_fp_set( r->y, fd_secp256k1_const_one_mont );
112 6520 : fd_secp256k1_fp_set( r->z, fd_secp256k1_const_zero );
113 6520 : }
114 :
115 : /* Sets a group element to the base element in Jacobian coordinates */
116 : static inline void
117 2174 : fd_secp256k1_point_set_base( fd_secp256k1_point_t *r ) {
118 2174 : fd_secp256k1_fp_set( r->x, fd_secp256k1_const_base_x_mont );
119 2174 : fd_secp256k1_fp_set( r->y, fd_secp256k1_const_base_y_mont );
120 2174 : fd_secp256k1_fp_set( r->z, fd_secp256k1_const_one_mont );
121 2174 : }
122 :
123 : /* r = a */
124 : static inline void
125 : fd_secp256k1_point_set( fd_secp256k1_point_t * r,
126 4347 : fd_secp256k1_point_t const * a ) {
127 4347 : fd_secp256k1_fp_set( r->x, a->x );
128 4347 : fd_secp256k1_fp_set( r->y, a->y );
129 4347 : fd_secp256k1_fp_set( r->z, a->z );
130 4347 : }
131 :
132 : /* https://eprint.iacr.org/2015/1060.pdf, Algorithm 7 */
133 : static inline fd_secp256k1_point_t *
134 : fd_secp256k1_point_add( fd_secp256k1_point_t * r,
135 : fd_secp256k1_point_t const * a,
136 275060 : fd_secp256k1_point_t const * b ) {
137 275060 : fd_secp256k1_fp_t t0[ 1 ];
138 275060 : fd_secp256k1_fp_t t1[ 1 ];
139 275060 : fd_secp256k1_fp_t t2[ 1 ];
140 275060 : fd_secp256k1_fp_t t3[ 1 ];
141 275060 : fd_secp256k1_fp_t t4[ 1 ];
142 :
143 275060 : fd_secp256k1_fp_t X3[ 1 ];
144 275060 : fd_secp256k1_fp_t Y3[ 1 ];
145 275060 : fd_secp256k1_fp_t Z3[ 1 ];
146 :
147 : /* t0 = X1 * X2 */
148 275060 : fd_secp256k1_fp_mul( t0, a->x, b->x );
149 : /* t1 = Y1 * Y2 */
150 275060 : fd_secp256k1_fp_mul( t1, a->y, b->y );
151 : /* t2 = Z1 * Z2 */
152 275060 : fd_secp256k1_fp_mul( t2, a->z, b->z );
153 :
154 : /* t3 = (a.x + a.y) * (b.x + b.y) - (t0 + t1) */
155 275060 : fd_secp256k1_fp_add( t3, a->x, a->y );
156 275060 : fd_secp256k1_fp_add( t4, b->x, b->y );
157 275060 : fd_secp256k1_fp_mul( t3, t3, t4 );
158 275060 : fd_secp256k1_fp_add( t4, t0, t1 );
159 275060 : fd_secp256k1_fp_sub( t3, t3, t4 );
160 :
161 : /* t4 = (a.y + a.z) * (b.y + b.z) - (t1 + t2) */
162 275060 : fd_secp256k1_fp_add( t4, a->y, a->z );
163 275060 : fd_secp256k1_fp_add( X3, b->y, b->z );
164 275060 : fd_secp256k1_fp_mul( t4, t4, X3 );
165 275060 : fd_secp256k1_fp_add( X3, t1, t2 );
166 275060 : fd_secp256k1_fp_sub( t4, t4, X3 );
167 :
168 : /* Y3 = (a.x + a.z) * (b.x + b.z) - (t0 + t2) */
169 275060 : fd_secp256k1_fp_add( X3, a->x, a->z );
170 275060 : fd_secp256k1_fp_add( Y3, b->x, b->z );
171 275060 : fd_secp256k1_fp_mul( X3, X3, Y3 );
172 275060 : fd_secp256k1_fp_add( Y3, t0, t2 );
173 275060 : fd_secp256k1_fp_sub( Y3, X3, Y3 );
174 :
175 : /* t0 = 3 * t0 */
176 275060 : fd_secp256k1_fp_triple( t0, t0 );
177 :
178 : /* b3 = (2^2)^2 + 2^2 + 1 = 21 */
179 275060 : fd_secp256k1_fp_t t2_4[ 1 ];
180 275060 : fd_secp256k1_fp_t t5[ 1 ];
181 275060 : fd_secp256k1_fp_dbl( t2_4, t2 );
182 275060 : fd_secp256k1_fp_dbl( t2_4, t2_4 );
183 275060 : fd_secp256k1_fp_dbl( t5, t2_4 );
184 275060 : fd_secp256k1_fp_dbl( t5, t5 );
185 275060 : fd_secp256k1_fp_add( t5, t5, t2_4 );
186 275060 : fd_secp256k1_fp_add( t2, t5, t2 );
187 :
188 : /* Z3 = t1 * t2
189 : t1 = t1 - t2 */
190 275060 : fd_secp256k1_fp_add( Z3, t1, t2 );
191 275060 : fd_secp256k1_fp_sub( t1, t1, t2 );
192 :
193 275060 : fd_secp256k1_fp_t Y3_4[ 1 ];
194 275060 : fd_secp256k1_fp_dbl( Y3_4, Y3 );
195 275060 : fd_secp256k1_fp_dbl( Y3_4, Y3_4 );
196 275060 : fd_secp256k1_fp_dbl( t5, Y3_4 );
197 275060 : fd_secp256k1_fp_dbl( t5, t5 );
198 275060 : fd_secp256k1_fp_add( t5, t5, Y3_4 );
199 275060 : fd_secp256k1_fp_add( Y3, t5, Y3 );
200 :
201 275060 : fd_secp256k1_fp_mul( X3, t4, Y3 );
202 275060 : fd_secp256k1_fp_mul( t2, t3, t1 );
203 275060 : fd_secp256k1_fp_sub( r->x, t2, X3 );
204 275060 : fd_secp256k1_fp_mul( Y3, Y3, t0 );
205 275060 : fd_secp256k1_fp_mul( t1, t1, Z3 );
206 275060 : fd_secp256k1_fp_add( r->y, t1, Y3 );
207 275060 : fd_secp256k1_fp_mul( t0, t0, t3 );
208 275060 : fd_secp256k1_fp_mul( Z3, Z3, t4 );
209 275060 : fd_secp256k1_fp_add( r->z, Z3, t0 );
210 :
211 275060 : return r;
212 275060 : }
213 :
214 : /* https://eprint.iacr.org/2015/1060.pdf, Algorithm 9 */
215 : static inline fd_secp256k1_point_t *
216 : fd_secp256k1_point_dbl( fd_secp256k1_point_t * r,
217 568532 : fd_secp256k1_point_t const * a ) {
218 568532 : fd_secp256k1_fp_t t0[ 1 ];
219 568532 : fd_secp256k1_fp_t t1[ 1 ];
220 568532 : fd_secp256k1_fp_t t2[ 1 ];
221 :
222 568532 : fd_secp256k1_fp_t X3[ 1 ];
223 568532 : fd_secp256k1_fp_t Y3[ 1 ];
224 568532 : fd_secp256k1_fp_t Z3[ 1 ];
225 :
226 : /* t0 = Y * Y*/
227 568532 : fd_secp256k1_fp_sqr( t0, a->y );
228 : /* Z3 = 8 * t0 */
229 568532 : fd_secp256k1_fp_dbl( Z3, t0 );
230 568532 : fd_secp256k1_fp_dbl( Z3, Z3 );
231 568532 : fd_secp256k1_fp_dbl( Z3, Z3 );
232 :
233 : /* t1 = Y * Z */
234 568532 : fd_secp256k1_fp_mul( t1, a->y, a->z );
235 : /* t2 = Z * Z */
236 568532 : fd_secp256k1_fp_sqr( t2, a->z );
237 :
238 : /* b3 = (2^2)^2 + 2^2 + 1
239 : t2 = b3 * t2 */
240 568532 : fd_secp256k1_fp_t t2_4[1], t5[1];
241 568532 : fd_secp256k1_fp_dbl( t2_4, t2 );
242 568532 : fd_secp256k1_fp_dbl( t2_4, t2_4 );
243 568532 : fd_secp256k1_fp_dbl( t5, t2_4 );
244 568532 : fd_secp256k1_fp_dbl( t5, t5 );
245 568532 : fd_secp256k1_fp_add( t5, t5, t2_4 );
246 568532 : fd_secp256k1_fp_add( t2, t5, t2 );
247 :
248 : /* X3 = t2 * Z3 */
249 568532 : fd_secp256k1_fp_mul( X3, t2, Z3 );
250 : /* Y3 = t0 + t2 */
251 568532 : fd_secp256k1_fp_add( Y3, t0, t2 );
252 :
253 568532 : fd_secp256k1_fp_mul( r->z, t1, Z3 );
254 :
255 568532 : fd_secp256k1_fp_dbl( t1, t2 );
256 568532 : fd_secp256k1_fp_add( t2, t1, t2 );
257 568532 : fd_secp256k1_fp_sub( t0, t0, t2 );
258 568532 : fd_secp256k1_fp_mul( Y3, t0, Y3 );
259 : /* compute t1 first, as the next add may overwrite a->y */
260 568532 : fd_secp256k1_fp_mul( t1, a->x, a->y );
261 568532 : fd_secp256k1_fp_add( r->y, X3, Y3 );
262 :
263 568532 : fd_secp256k1_fp_mul( X3, t0, t1 );
264 568532 : fd_secp256k1_fp_dbl( r->x, X3 );
265 :
266 568532 : return r;
267 568532 : }
268 :
269 : /* r = -a */
270 : static inline fd_secp256k1_point_t *
271 : fd_secp256k1_point_neg( fd_secp256k1_point_t * r,
272 138941 : fd_secp256k1_point_t const * a ) {
273 138941 : fd_secp256k1_fp_set( r->x, a->x );
274 138941 : fd_secp256k1_fp_set( r->z, a->z );
275 138941 : fd_secp256k1_fp_negate( r->y, a->y );
276 138941 : return r;
277 138941 : }
278 :
279 : /* r = a - b */
280 : static inline fd_secp256k1_point_t *
281 : fd_secp256k1_point_sub( fd_secp256k1_point_t * r,
282 : fd_secp256k1_point_t const * a,
283 138934 : fd_secp256k1_point_t const * b ) {
284 138934 : fd_secp256k1_point_t tmp[ 1 ];
285 138934 : fd_secp256k1_point_neg( tmp, b );
286 138934 : return fd_secp256k1_point_add( r, a, tmp );
287 138934 : }
288 :
289 : /* Double base multiplication */
290 :
291 : static inline schar *
292 : fd_secp256k1_slide( schar r[ 2 * 32 + 1 ],
293 4342 : uchar const s[ 32 ] ) {
294 143286 : for( ulong i=0UL; i<32UL; i++ ) {
295 138944 : uchar x = s[i];
296 138944 : r[i * 2 + 0] = x & 0xF;
297 138944 : r[i * 2 + 1] = (x >> 4) & 0xF;
298 138944 : }
299 : /* Now, r[0..63] is between 0 and 15, r[63] is between 0 and 7 */
300 4342 : schar carry = 0;
301 282230 : for( ulong i=0UL; i<64UL; i++ ) {
302 277888 : r[i] = (schar)(r[i] + carry);
303 277888 : carry = (schar)(r[i] + 8) >> 4;
304 277888 : r[i] = (schar)(r[i] - carry * 16);
305 : /* r[i] MUST be between [-8, 8] */
306 277888 : }
307 4342 : r[64] = carry;
308 : /* carry MUST be between [-8, 8] */
309 4342 : return r;
310 4342 : }
311 :
312 : static inline fd_secp256k1_point_t *
313 : fd_secp256k1_precompute( fd_secp256k1_point_t r[ 9 ],
314 4347 : fd_secp256k1_point_t const * a ) {
315 4347 : fd_secp256k1_point_set_identity( &r[0] );
316 4347 : fd_secp256k1_point_set( &r[1], a );
317 34754 : for( ulong i=2UL; i<=8UL; i++ ) {
318 30407 : if( i%2UL ) {
319 13033 : fd_secp256k1_point_add( &r[i], &r[i - 1], a );
320 17374 : } else {
321 17374 : fd_secp256k1_point_dbl( &r[i], &r[i / 2] );
322 17374 : }
323 30407 : }
324 4347 : return r;
325 4347 : }
326 :
327 : /* Computes s1*G + s2*P2, where G is the base point */
328 : static inline fd_secp256k1_point_t *
329 : fd_secp256k1_double_base_mul( fd_secp256k1_point_t * r,
330 : fd_secp256k1_scalar_t const * s1,
331 : fd_secp256k1_point_t const * p2,
332 2174 : fd_secp256k1_scalar_t const * s2 ) {
333 2174 : fd_secp256k1_point_t base[ 1 ];
334 2174 : fd_secp256k1_point_set_base( base );
335 :
336 2174 : fd_secp256k1_point_t pc1[ 9 ];
337 2174 : fd_secp256k1_point_t pc2[ 9 ];
338 : /* TODO: Precompute the basepoint table in a generated table */
339 2174 : fd_secp256k1_precompute( pc1, base );
340 2174 : fd_secp256k1_precompute( pc2, p2 );
341 :
342 2174 : schar e1[ 2 * 32 + 1 ];
343 2174 : schar e2[ 2 * 32 + 1 ];
344 2174 : fd_secp256k1_slide( e1, s1->buf );
345 2174 : fd_secp256k1_slide( e2, s2->buf );
346 :
347 2174 : fd_secp256k1_point_set_identity( r );
348 140957 : for( int pos = 2 * 32; ; pos -= 1 ) {
349 140957 : schar slot1 = e1[pos];
350 140957 : if( slot1 > 0 ) {
351 62136 : fd_secp256k1_point_add( r, r, &pc1[(ulong)slot1] );
352 78821 : } else if( slot1 < 0 ) {
353 69485 : fd_secp256k1_point_sub( r, r, &pc1[(ulong)(-slot1)] );
354 69485 : }
355 :
356 140957 : schar slot2 = e2[pos];
357 140957 : if( slot2 > 0 ) {
358 61860 : fd_secp256k1_point_add( r, r, &pc2[(ulong)slot2] );
359 79097 : } else if( slot2 < 0 ) {
360 69613 : fd_secp256k1_point_sub( r, r, &pc2[(ulong)(-slot2)] );
361 69613 : }
362 :
363 140957 : if( pos == 0 ) break;
364 138783 : fd_secp256k1_point_dbl( r, r );
365 138783 : fd_secp256k1_point_dbl( r, r );
366 138783 : fd_secp256k1_point_dbl( r, r );
367 138783 : fd_secp256k1_point_dbl( r, r );
368 138783 : }
369 :
370 2174 : return r;
371 2174 : }
372 :
373 : static inline fd_secp256k1_point_t *
374 : fd_secp256k1_point_to_affine( fd_secp256k1_point_t * r,
375 2172 : fd_secp256k1_point_t const * a ) {
376 2172 : fd_secp256k1_fp_t z[1];
377 2172 : fd_secp256k1_fp_invert( z, a->z );
378 2172 : fd_secp256k1_fp_mul( r->x, a->x, z );
379 2172 : fd_secp256k1_fp_mul( r->y, a->y, z );
380 2172 : return r;
381 2172 : }
382 :
383 : static inline int
384 2174 : fd_secp256k1_point_is_identity( fd_secp256k1_point_t const *a ) {
385 2174 : int affine =
386 2174 : fd_secp256k1_fp_eq( a->x, fd_secp256k1_const_zero ) &
387 2174 : ( fd_secp256k1_fp_eq( a->y, fd_secp256k1_const_zero ) |
388 2174 : fd_secp256k1_fp_eq( a->y, fd_secp256k1_const_one_mont ) );
389 2174 : return fd_secp256k1_fp_eq( a->z, fd_secp256k1_const_zero ) | affine;
390 2174 : }
|
