Line data Source code
1 : #include <stdint.h>
2 : #include <s2n-bignum.h>
3 :
4 : /* On CPUs without ADX (mulx/adcx/adox), redirect the ADX-optimized
5 : s2n-bignum symbols to their _alt equivalents, which use only base
6 : x86-64 instructions and are functionally identical. */
7 : #ifndef __ADX__
8 62402808 : #define bignum_montmul_p256k1 bignum_montmul_p256k1_alt
9 20795400 : #define bignum_montsqr_p256k1 bignum_montsqr_p256k1_alt
10 60102 : #define bignum_tomont_p256k1 bignum_tomont_p256k1_alt
11 2504882 : #define bignum_triple_p256k1 bignum_triple_p256k1_alt
12 : #endif
13 :
14 : /* Scalars */
15 :
16 : static inline int
17 120213 : fd_secp256k1_scalar_is_zero( fd_secp256k1_scalar_t const *r ) {
18 120213 : return fd_uint256_eq( r, fd_secp256k1_const_zero );
19 120213 : }
20 :
21 : /* Returns the scalar in NON Montgomery form. */
22 : static inline fd_secp256k1_scalar_t *
23 : fd_secp256k1_scalar_frombytes( fd_secp256k1_scalar_t * r,
24 120231 : uchar const input[ 32 ] ) {
25 120231 : memcpy( r, input, 32 );
26 120231 : fd_uint256_bswap( r, r );
27 :
28 : /*
29 : The verifier SHALL check that 0 < r' < q and 0 < s' < q.
30 : The r' element is parsed as a scalar, and checked against r' < n.
31 : Later it is re-used as fp_t, however n < p, so we do not need to
32 : perform any additional checks after this.
33 : */
34 120231 : if( FD_UNLIKELY( fd_uint256_cmp( r, fd_secp256k1_const_n ) >= 0 ) ) {
35 18 : return NULL;
36 18 : }
37 120213 : if( FD_UNLIKELY( fd_secp256k1_scalar_is_zero( r ) ) ) {
38 15 : return NULL;
39 15 : }
40 120198 : return r;
41 120213 : }
42 :
43 : /* r = 1 / a
44 : Operates on scalars NOT in the montgomery domain.
45 : a MUST not be 0. */
46 : fd_secp256k1_scalar_t *
47 : fd_secp256k1_scalar_invert( fd_secp256k1_scalar_t * r,
48 30060 : fd_secp256k1_scalar_t const * a ) {
49 30060 : ulong t[ 12 ];
50 30060 : bignum_modinv( 4, r->limbs, (ulong *)a->limbs, (ulong *)fd_secp256k1_const_n[ 0 ].limbs, t );
51 30060 : return r;
52 30060 : }
53 :
54 : /* None of the arguments may alias. */
55 : static inline fd_secp256k1_scalar_t *
56 : fd_secp256k1_scalar_mul( fd_secp256k1_scalar_t * restrict r,
57 : fd_secp256k1_scalar_t const * restrict a,
58 60120 : fd_secp256k1_scalar_t const * restrict b ) {
59 60120 : bignum_montmul( 4, r->limbs, (ulong *)a->limbs, (ulong *)b->limbs, (ulong *)fd_secp256k1_const_n[0].limbs );
60 60120 : return r;
61 60120 : }
62 :
63 : /* r = -a */
64 : static inline fd_secp256k1_scalar_t *
65 : fd_secp256k1_scalar_negate( fd_secp256k1_scalar_t * r,
66 30060 : fd_secp256k1_scalar_t const * a ) {
67 : /* We cannot use bignum_modsub() as it requires a < n /\ b < n.
68 :
69 : The best way to implement it using the current API is to use
70 : bignum_sub(n, a), getting a result bounded within [0, n+1). Then
71 : we perform a second reduction from [0, n+1) to [0, n) with
72 : bignum_mod_n256k1_4(). */
73 :
74 : /* t \in [0, n + 1). There is no carry-out, as a < n. */
75 30060 : ulong t[4];
76 30060 : bignum_sub( 4, t, 4, (ulong *)fd_secp256k1_const_n[ 0 ].limbs, 4, (ulong *)a->limbs );
77 30060 : bignum_mod_n256k1_4( r->limbs, t );
78 30060 : return r;
79 30060 : }
80 :
81 : static inline fd_secp256k1_scalar_t *
82 : fd_secp256k1_scalar_tomont( fd_secp256k1_scalar_t * r,
83 90180 : fd_secp256k1_scalar_t const * a ) {
84 : /* bignum_montmul has an undocumented restriction
85 : that the input and outputs may not alias. */
86 90180 : ulong t[4];
87 90180 : memcpy( t, a->limbs, 32 );
88 90180 : bignum_montmul( 4, r->limbs, t, (ulong *)fd_secp256k1_const_scalar_rr_mont, (ulong *)fd_secp256k1_const_n[ 0 ].limbs );
89 90180 : return r;
90 90180 : }
91 :
92 : static inline fd_secp256k1_scalar_t *
93 : fd_secp256k1_scalar_demont( fd_secp256k1_scalar_t * r,
94 60120 : fd_secp256k1_scalar_t const * a ) {
95 60120 : bignum_demont( 4, r->limbs, (ulong *)a->limbs, (ulong *)fd_secp256k1_const_n[ 0 ].limbs );
96 60120 : return r;
97 60120 : }
98 :
99 : /* Field */
100 :
101 : static inline fd_secp256k1_fp_t *
102 : fd_secp256k1_fp_set( fd_secp256k1_fp_t * r,
103 4687968 : fd_secp256k1_fp_t const * a ) {
104 4687968 : r->limbs[ 0 ] = a->limbs[ 0 ];
105 4687968 : r->limbs[ 1 ] = a->limbs[ 1 ];
106 4687968 : r->limbs[ 2 ] = a->limbs[ 2 ];
107 4687968 : r->limbs[ 3 ] = a->limbs[ 3 ];
108 4687968 : return r;
109 4687968 : }
110 :
111 : /* r = (a == b) */
112 : static inline int
113 : fd_secp256k1_fp_eq( fd_secp256k1_fp_t const * a,
114 180324 : fd_secp256k1_fp_t const * b ) {
115 180324 : return fd_uint256_eq( a, b );
116 180324 : }
117 :
118 : /* r = a + b */
119 : static inline fd_secp256k1_fp_t *
120 : fd_secp256k1_fp_add( fd_secp256k1_fp_t * r,
121 : fd_secp256k1_fp_t const * a,
122 99856464 : fd_secp256k1_fp_t const * b ) {
123 99856464 : bignum_add_p256k1( r->limbs, (ulong *)a->limbs, (ulong *)b->limbs );
124 99856464 : return r;
125 99856464 : }
126 :
127 : /* r = a - b */
128 : static inline fd_secp256k1_fp_t *
129 : fd_secp256k1_fp_sub( fd_secp256k1_fp_t * r,
130 : fd_secp256k1_fp_t const * a,
131 26722455 : fd_secp256k1_fp_t const * b ) {
132 26722455 : bignum_sub_p256k1( r->limbs, (ulong *)a->limbs, (ulong *)b->limbs );
133 26722455 : return r;
134 26722455 : }
135 :
136 : /* r = 2 * a */
137 : static inline fd_secp256k1_fp_t *
138 : fd_secp256k1_fp_dbl( fd_secp256k1_fp_t * r,
139 101481144 : fd_secp256k1_fp_t const * a ) {
140 101481144 : bignum_double_p256k1( r->limbs, (ulong *)a->limbs );
141 101481144 : return r;
142 101481144 : }
143 :
144 : /* r = a * b */
145 : static inline fd_secp256k1_fp_t *
146 : fd_secp256k1_fp_mul( fd_secp256k1_fp_t * r,
147 : fd_secp256k1_fp_t const * a,
148 93604212 : fd_secp256k1_fp_t const * b ) {
149 93604212 : bignum_montmul_p256k1( r->limbs, (ulong *)a->limbs, (ulong *)b->limbs );
150 93604212 : return r;
151 93604212 : }
152 :
153 : /* r = a^2 */
154 : static inline fd_secp256k1_fp_t *
155 : fd_secp256k1_fp_sqr( fd_secp256k1_fp_t * r,
156 31193100 : fd_secp256k1_fp_t const * a ) {
157 31193100 : bignum_montsqr_p256k1( r->limbs, (ulong *)a->limbs );
158 31193100 : return r;
159 31193100 : }
160 :
161 : /* r = -a */
162 : static inline fd_secp256k1_fp_t *
163 : fd_secp256k1_fp_negate( fd_secp256k1_fp_t * r,
164 2043414 : fd_secp256k1_fp_t const * a ) {
165 2043414 : bignum_neg_p256k1( r->limbs, (ulong *)a->limbs );
166 2043414 : return r;
167 2043414 : }
168 :
169 : static inline int
170 30060 : fd_secp256k1_fp_is_odd( fd_secp256k1_fp_t const *r ) {
171 30060 : fd_secp256k1_fp_t scratch[1];
172 30060 : bignum_demont_p256k1( scratch->limbs, (ulong *)r->limbs );
173 30060 : return scratch->limbs[ 0 ] & 1;
174 30060 : }
175 :
176 : /* r = 1 / a
177 : a MUST not be 0. */
178 : static inline fd_secp256k1_fp_t *
179 : fd_secp256k1_fp_invert( fd_secp256k1_fp_t * r,
180 30060 : fd_secp256k1_fp_t const * a ) {
181 30060 : fd_secp256k1_fp_t ad[1];
182 30060 : bignum_demont_p256k1( ad->limbs, (ulong *)a->limbs );
183 30060 : ulong t[ 12 ];
184 30060 : bignum_modinv( 4, r->limbs, (ulong *)ad->limbs, (ulong *)fd_secp256k1_const_p[0].limbs, t );
185 30060 : bignum_tomont_p256k1( r->limbs, (ulong *)r->limbs );
186 30060 : return r;
187 30060 : }
188 :
189 : static inline uchar *
190 : fd_secp256k1_fp_tobytes( uchar r[ 32 ],
191 60120 : fd_secp256k1_fp_t const *a ) {
192 60120 : fd_secp256k1_fp_t swapped[1];
193 60120 : bignum_demont_p256k1( swapped->limbs, (ulong *)a->limbs );
194 60120 : fd_uint256_bswap( swapped, swapped );
195 60120 : memcpy( r, swapped->buf, 32 );
196 60120 : return r;
197 60120 : }
198 :
199 : /*
200 : Returns NULL if a is not a square.
201 : r may NOT alias a
202 :
203 : r = a^((p + 1) / 4) mod p
204 :
205 : We know that a^((p-1)/2) = 1 when a is a quadratic residue.
206 : So for a valid square, we can show that re-squaring recovers a with:
207 : (a^((p+1)/4))^2 = a^((p+1)/1)
208 : = a * a^((p-1)/2)
209 : = a (if a is a square)
210 :
211 : We use a more optimal addition-chain which takes advantage that quite
212 : a few of the powers consist of all 1s when in binary form. We build up:
213 : x2 = a^3
214 : x3 = a^7
215 : x6 = a^63
216 : x9 = a^511
217 : x11 = a^2047
218 : x22 = a^(2^22 − 1) # All of these are all 1s
219 : x44 = a^(2^44 − 1)
220 : x88 = a^(2^88 − 1)
221 : x176 = a^(2^176 − 1)
222 : x220 = a^(2^220 − 1)
223 : x223 = a^(2^223 − 1)
224 :
225 : These "all 1s" exponents are convenient because:
226 : (2^k - 1)*(2^m)+(2^m - 1) = 2^(k+m) - 1
227 : Allowing us to quickly build them.
228 :
229 : If a is NOT a square, then
230 : a^((p-1)/2) = -1
231 : and the result will fail the final verification.
232 : */
233 : static inline fd_secp256k1_fp_t *
234 : fd_secp256k1_fp_sqrt( fd_secp256k1_fp_t * restrict r,
235 60084 : fd_secp256k1_fp_t const * restrict a ) {
236 60084 : fd_secp256k1_fp_t x2;
237 60084 : fd_secp256k1_fp_t x3;
238 :
239 60084 : fd_secp256k1_fp_sqr( &x2, a );
240 60084 : fd_secp256k1_fp_mul( &x2, &x2, a );
241 :
242 60084 : fd_secp256k1_fp_sqr( &x3, &x2 );
243 60084 : fd_secp256k1_fp_mul( &x3, &x3, a );
244 :
245 60084 : fd_secp256k1_fp_t x6 = x3;
246 240336 : for( int j=0; j<3; j++ ) fd_secp256k1_fp_sqr( &x6, &x6 );
247 60084 : fd_secp256k1_fp_mul( &x6, &x6, &x3 );
248 :
249 60084 : fd_secp256k1_fp_t x9 = x6;
250 240336 : for( int j=0; j<3; j++ ) fd_secp256k1_fp_sqr( &x9, &x9 );
251 60084 : fd_secp256k1_fp_mul( &x9, &x9, &x3 );
252 :
253 60084 : fd_secp256k1_fp_t x11 = x9;
254 180252 : for( int j=0; j<2; j++ ) fd_secp256k1_fp_sqr( &x11, &x11 );
255 60084 : fd_secp256k1_fp_mul( &x11, &x11, &x2 );
256 :
257 60084 : fd_secp256k1_fp_t x22 = x11;
258 721008 : for( int j=0; j<11; j++ ) fd_secp256k1_fp_sqr( &x22, &x22 );
259 60084 : fd_secp256k1_fp_mul( &x22, &x22, &x11 );
260 :
261 60084 : fd_secp256k1_fp_t x44 = x22;
262 1381932 : for( int j=0; j<22; j++ ) fd_secp256k1_fp_sqr( &x44, &x44 );
263 60084 : fd_secp256k1_fp_mul( &x44, &x44, &x22 );
264 :
265 60084 : fd_secp256k1_fp_t x88 = x44;
266 2703780 : for( int j=0; j<44; j++ ) fd_secp256k1_fp_sqr( &x88, &x88 );
267 60084 : fd_secp256k1_fp_mul( &x88, &x88, &x44 );
268 :
269 60084 : fd_secp256k1_fp_t x176 = x88;
270 5347476 : for( int j=0; j<88; j++ ) fd_secp256k1_fp_sqr( &x176, &x176 );
271 60084 : fd_secp256k1_fp_mul( &x176, &x176, &x88 );
272 :
273 60084 : fd_secp256k1_fp_t x220 = x176;
274 2703780 : for( int j=0; j<44; j++ ) fd_secp256k1_fp_sqr( &x220, &x220 );
275 60084 : fd_secp256k1_fp_mul( &x220, &x220, &x44 );
276 :
277 60084 : fd_secp256k1_fp_t x223 = x220;
278 240336 : for( int j=0; j<3; j++ ) fd_secp256k1_fp_sqr( &x223, &x223 );
279 60084 : fd_secp256k1_fp_mul( &x223, &x223, &x3 );
280 :
281 60084 : fd_secp256k1_fp_t t1 = x223;
282 1442016 : for( int j=0; j<23; j++ ) fd_secp256k1_fp_sqr( &t1, &t1 );
283 60084 : fd_secp256k1_fp_mul( &t1, &t1, &x22 );
284 :
285 420588 : for( int j=0; j<6; j++ ) fd_secp256k1_fp_sqr( &t1, &t1 );
286 60084 : fd_secp256k1_fp_mul( &t1, &t1, &x2 );
287 60084 : fd_secp256k1_fp_sqr( &t1, &t1 );
288 60084 : fd_secp256k1_fp_sqr( r, &t1 );
289 :
290 60084 : fd_secp256k1_fp_sqr( &t1, r );
291 60084 : if( FD_UNLIKELY( !fd_secp256k1_fp_eq( &t1, a ) ) ) {
292 30024 : return NULL;
293 30024 : }
294 :
295 30060 : return r;
296 60084 : }
297 :
298 : /* Point */
299 :
300 : /* Sets a group element to the identity element in Jacobian coordinates */
301 : static inline void
302 90180 : fd_secp256k1_point_set_identity( fd_secp256k1_point_t *r ) {
303 90180 : fd_secp256k1_fp_set( r->x, fd_secp256k1_const_zero );
304 90180 : fd_secp256k1_fp_set( r->y, fd_secp256k1_const_one_mont );
305 90180 : fd_secp256k1_fp_set( r->z, fd_secp256k1_const_zero );
306 90180 : }
307 :
308 : /* Sets a group element to the base element in Jacobian coordinates */
309 : static inline void
310 30060 : fd_secp256k1_point_set_base( fd_secp256k1_point_t *r ) {
311 30060 : fd_secp256k1_fp_set( r->x, fd_secp256k1_const_base_x_mont );
312 30060 : fd_secp256k1_fp_set( r->y, fd_secp256k1_const_base_y_mont );
313 30060 : fd_secp256k1_fp_set( r->z, fd_secp256k1_const_one_mont );
314 30060 : }
315 :
316 : /* r = a */
317 : static inline void
318 : fd_secp256k1_point_set( fd_secp256k1_point_t * r,
319 60120 : fd_secp256k1_point_t const * a ) {
320 60120 : fd_secp256k1_fp_set( r->x, a->x );
321 60120 : fd_secp256k1_fp_set( r->y, a->y );
322 60120 : fd_secp256k1_fp_set( r->z, a->z );
323 60120 : }
324 :
325 : /* https://eprint.iacr.org/2015/1060.pdf, Algorithm 7 */
326 : static inline fd_secp256k1_point_t *
327 : fd_secp256k1_point_add( fd_secp256k1_point_t * r,
328 : fd_secp256k1_point_t const * a,
329 3757323 : fd_secp256k1_point_t const * b ) {
330 3757323 : fd_secp256k1_fp_t t0[ 1 ];
331 3757323 : fd_secp256k1_fp_t t1[ 1 ];
332 3757323 : fd_secp256k1_fp_t t2[ 1 ];
333 3757323 : fd_secp256k1_fp_t t3[ 1 ];
334 3757323 : fd_secp256k1_fp_t t4[ 1 ];
335 :
336 3757323 : fd_secp256k1_fp_t X3[ 1 ];
337 3757323 : fd_secp256k1_fp_t Y3[ 1 ];
338 3757323 : fd_secp256k1_fp_t Z3[ 1 ];
339 :
340 : /* t0 = X1 * X2 */
341 3757323 : fd_secp256k1_fp_mul( t0, a->x, b->x );
342 : /* t1 = Y1 * Y2 */
343 3757323 : fd_secp256k1_fp_mul( t1, a->y, b->y );
344 : /* t2 = Z1 * Z2 */
345 3757323 : fd_secp256k1_fp_mul( t2, a->z, b->z );
346 :
347 : /* t3 = (a.x + a.y) * (b.x + b.y) - (t0 + t1) */
348 3757323 : fd_secp256k1_fp_add( t3, a->x, a->y );
349 3757323 : fd_secp256k1_fp_add( t4, b->x, b->y );
350 3757323 : fd_secp256k1_fp_mul( t3, t3, t4 );
351 3757323 : fd_secp256k1_fp_add( t4, t0, t1 );
352 3757323 : fd_secp256k1_fp_sub( t3, t3, t4 );
353 :
354 : /* t4 = (a.y + a.z) * (b.y + b.z) - (t1 + t2) */
355 3757323 : fd_secp256k1_fp_add( t4, a->y, a->z );
356 3757323 : fd_secp256k1_fp_add( X3, b->y, b->z );
357 3757323 : fd_secp256k1_fp_mul( t4, t4, X3 );
358 3757323 : fd_secp256k1_fp_add( X3, t1, t2 );
359 3757323 : fd_secp256k1_fp_sub( t4, t4, X3 );
360 :
361 : /* Y3 = (a.x + a.z) * (b.x + b.z) - (t0 + t2) */
362 3757323 : fd_secp256k1_fp_add( X3, a->x, a->z );
363 3757323 : fd_secp256k1_fp_add( Y3, b->x, b->z );
364 3757323 : fd_secp256k1_fp_mul( X3, X3, Y3 );
365 3757323 : fd_secp256k1_fp_add( Y3, t0, t2 );
366 3757323 : fd_secp256k1_fp_sub( Y3, X3, Y3 );
367 :
368 : /* t0 = 3 * t0 */
369 3757323 : bignum_triple_p256k1( t0->limbs, (ulong *)t0->limbs );
370 :
371 : /* b3 = (2^2)^2 + 2^2 + 1 = 21 */
372 3757323 : fd_secp256k1_fp_t t2_4[ 1 ];
373 3757323 : fd_secp256k1_fp_t t5[ 1 ];
374 3757323 : fd_secp256k1_fp_dbl( t2_4, t2 );
375 3757323 : fd_secp256k1_fp_dbl( t2_4, t2_4 );
376 3757323 : fd_secp256k1_fp_dbl( t5, t2_4 );
377 3757323 : fd_secp256k1_fp_dbl( t5, t5 );
378 3757323 : fd_secp256k1_fp_add( t5, t5, t2_4 );
379 3757323 : fd_secp256k1_fp_add( t2, t5, t2 );
380 :
381 : /* Z3 = t1 * t2
382 : t1 = t1 - t2 */
383 3757323 : fd_secp256k1_fp_add( Z3, t1, t2 );
384 3757323 : fd_secp256k1_fp_sub( t1, t1, t2 );
385 :
386 3757323 : fd_secp256k1_fp_t Y3_4[ 1 ];
387 3757323 : fd_secp256k1_fp_dbl( Y3_4, Y3 );
388 3757323 : fd_secp256k1_fp_dbl( Y3_4, Y3_4 );
389 3757323 : fd_secp256k1_fp_dbl( t5, Y3_4 );
390 3757323 : fd_secp256k1_fp_dbl( t5, t5 );
391 3757323 : fd_secp256k1_fp_add( t5, t5, Y3_4 );
392 3757323 : fd_secp256k1_fp_add( Y3, t5, Y3 );
393 :
394 3757323 : fd_secp256k1_fp_mul( X3, t4, Y3 );
395 3757323 : fd_secp256k1_fp_mul( t2, t3, t1 );
396 3757323 : fd_secp256k1_fp_sub( r->x, t2, X3 );
397 3757323 : fd_secp256k1_fp_mul( Y3, Y3, t0 );
398 3757323 : fd_secp256k1_fp_mul( t1, t1, Z3 );
399 3757323 : fd_secp256k1_fp_add( r->y, t1, Y3 );
400 3757323 : fd_secp256k1_fp_mul( t0, t0, t3 );
401 3757323 : fd_secp256k1_fp_mul( Z3, Z3, t4 );
402 3757323 : fd_secp256k1_fp_add( r->z, Z3, t0 );
403 :
404 3757323 : return r;
405 3757323 : }
406 :
407 : /* https://eprint.iacr.org/2015/1060.pdf, Algorithm 9 */
408 : static inline fd_secp256k1_point_t *
409 : fd_secp256k1_point_dbl( fd_secp256k1_point_t * r,
410 7935840 : fd_secp256k1_point_t const * a ) {
411 7935840 : fd_secp256k1_fp_t t0[ 1 ];
412 7935840 : fd_secp256k1_fp_t t1[ 1 ];
413 7935840 : fd_secp256k1_fp_t t2[ 1 ];
414 :
415 7935840 : fd_secp256k1_fp_t X3[ 1 ];
416 7935840 : fd_secp256k1_fp_t Y3[ 1 ];
417 7935840 : fd_secp256k1_fp_t Z3[ 1 ];
418 :
419 : /* t0 = Y * Y*/
420 7935840 : fd_secp256k1_fp_sqr( t0, a->y );
421 : /* Z3 = 8 * t0 */
422 7935840 : fd_secp256k1_fp_dbl( Z3, t0 );
423 7935840 : fd_secp256k1_fp_dbl( Z3, Z3 );
424 7935840 : fd_secp256k1_fp_dbl( Z3, Z3 );
425 :
426 : /* t1 = Y * Z */
427 7935840 : fd_secp256k1_fp_mul( t1, a->y, a->z );
428 : /* t2 = Z * Z */
429 7935840 : fd_secp256k1_fp_sqr( t2, a->z );
430 :
431 : /* b3 = (2^2)^2 + 2^2 + 1
432 : t2 = b3 * t2 */
433 7935840 : fd_secp256k1_fp_t t2_4[1], t5[1];
434 7935840 : fd_secp256k1_fp_dbl( t2_4, t2 );
435 7935840 : fd_secp256k1_fp_dbl( t2_4, t2_4 );
436 7935840 : fd_secp256k1_fp_dbl( t5, t2_4 );
437 7935840 : fd_secp256k1_fp_dbl( t5, t5 );
438 7935840 : fd_secp256k1_fp_add( t5, t5, t2_4 );
439 7935840 : fd_secp256k1_fp_add( t2, t5, t2 );
440 :
441 : /* X3 = t2 * Z3 */
442 7935840 : fd_secp256k1_fp_mul( X3, t2, Z3 );
443 : /* Y3 = t0 + t2 */
444 7935840 : fd_secp256k1_fp_add( Y3, t0, t2 );
445 :
446 7935840 : fd_secp256k1_fp_mul( r->z, t1, Z3 );
447 :
448 7935840 : fd_secp256k1_fp_dbl( t1, t2 );
449 7935840 : fd_secp256k1_fp_add( t2, t1, t2 );
450 7935840 : fd_secp256k1_fp_sub( t0, t0, t2 );
451 7935840 : fd_secp256k1_fp_mul( Y3, t0, Y3 );
452 : /* compute t1 first, as the next add may overwrite a->y */
453 7935840 : fd_secp256k1_fp_mul( t1, a->x, a->y );
454 7935840 : fd_secp256k1_fp_add( r->y, X3, Y3 );
455 :
456 7935840 : fd_secp256k1_fp_mul( X3, t0, t1 );
457 7935840 : fd_secp256k1_fp_dbl( r->x, X3 );
458 :
459 7935840 : return r;
460 7935840 : }
461 :
462 : /* r = -a */
463 : static inline fd_secp256k1_point_t *
464 : fd_secp256k1_point_neg( fd_secp256k1_point_t * r,
465 2043384 : fd_secp256k1_point_t const * a ) {
466 2043384 : fd_secp256k1_fp_set( r->x, a->x );
467 2043384 : fd_secp256k1_fp_set( r->z, a->z );
468 2043384 : fd_secp256k1_fp_negate( r->y, a->y );
469 2043384 : return r;
470 2043384 : }
471 :
472 : /* r = a - b */
473 : static inline fd_secp256k1_point_t *
474 : fd_secp256k1_point_sub( fd_secp256k1_point_t * r,
475 : fd_secp256k1_point_t const * a,
476 2043384 : fd_secp256k1_point_t const * b ) {
477 2043384 : fd_secp256k1_point_t tmp[ 1 ];
478 2043384 : fd_secp256k1_point_neg( tmp, b );
479 2043384 : return fd_secp256k1_point_add( r, a, tmp );
480 2043384 : }
481 :
482 : /* Double base multiplication */
483 :
484 : static inline schar *
485 : fd_secp256k1_slide( schar r[ 2 * 32 + 1 ],
486 60120 : uchar const s[ 32 ] ) {
487 1983960 : for(int i = 0; i<32; i++) {
488 1923840 : uchar x = s[i];
489 1923840 : r[i * 2 + 0] = x & 0xF;
490 1923840 : r[i * 2 + 1] = (x >> 4) & 0xF;
491 1923840 : }
492 : /* Now, r[0..63] is between 0 and 15, r[63] is between 0 and 7 */
493 60120 : schar carry = 0;
494 3907800 : for(int i = 0; i<64; i++) {
495 3847680 : r[i] += carry;
496 3847680 : carry = (schar)(r[i] + 8) >> 4;
497 3847680 : r[i] -= (schar)(carry * 16);
498 : /* r[i] MUST be between [-8, 8] */
499 3847680 : }
500 60120 : r[64] = carry;
501 : /* carry MUST be between [-8, 8] */
502 60120 : return r;
503 60120 : }
504 :
505 : static inline fd_secp256k1_point_t *
506 : fd_secp256k1_precompute( fd_secp256k1_point_t r[ 9 ],
507 60120 : fd_secp256k1_point_t const * a ) {
508 60120 : fd_secp256k1_point_set_identity( &r[0] );
509 60120 : fd_secp256k1_point_set( &r[1], a );
510 480960 : for(int i = 2; i <= 8; i++) {
511 420840 : if(i % 2) {
512 180360 : fd_secp256k1_point_add( &r[i], &r[i - 1], a );
513 240480 : } else {
514 240480 : fd_secp256k1_point_dbl( &r[i], &r[i / 2] );
515 240480 : }
516 420840 : }
517 60120 : return r;
518 60120 : }
519 :
520 : /* Computes s1*G + s2*P2, where G is the base point */
521 : static inline fd_secp256k1_point_t *
522 : fd_secp256k1_double_base_mul( fd_secp256k1_point_t * r,
523 : fd_secp256k1_scalar_t const * s1,
524 : fd_secp256k1_point_t const * p2,
525 30060 : fd_secp256k1_scalar_t const * s2 ) {
526 30060 : fd_secp256k1_point_t base[ 1 ];
527 30060 : fd_secp256k1_point_set_base( base );
528 :
529 30060 : fd_secp256k1_point_t pc1[ 9 ];
530 30060 : fd_secp256k1_point_t pc2[ 9 ];
531 : /* TODO: Precompute the basepoint table in a generated table */
532 30060 : fd_secp256k1_precompute( pc1, base );
533 30060 : fd_secp256k1_precompute( pc2, p2 );
534 :
535 30060 : schar e1[ 2 * 32 + 1 ];
536 30060 : schar e2[ 2 * 32 + 1 ];
537 30060 : fd_secp256k1_slide( e1, s1->buf );
538 30060 : fd_secp256k1_slide( e2, s2->buf );
539 :
540 30060 : fd_secp256k1_point_set_identity( r );
541 1953900 : for( int pos = 2 * 32; ; pos -= 1 ) {
542 1953900 : schar slot1 = e1[pos];
543 1953900 : if( slot1 > 0 ) {
544 781878 : fd_secp256k1_point_add( r, r, &pc1[(ulong)slot1] );
545 1172022 : } else if( slot1 < 0 ) {
546 961515 : fd_secp256k1_point_sub( r, r, &pc1[(ulong)(-slot1)] );
547 961515 : }
548 :
549 1953900 : schar slot2 = e2[pos];
550 1953900 : if( slot2 > 0 ) {
551 751701 : fd_secp256k1_point_add( r, r, &pc2[(ulong)slot2] );
552 1202199 : } else if( slot2 < 0 ) {
553 1081869 : fd_secp256k1_point_sub( r, r, &pc2[(ulong)(-slot2)] );
554 1081869 : }
555 :
556 1953900 : if( pos == 0 ) break;
557 1923840 : fd_secp256k1_point_dbl( r, r );
558 1923840 : fd_secp256k1_point_dbl( r, r );
559 1923840 : fd_secp256k1_point_dbl( r, r );
560 1923840 : fd_secp256k1_point_dbl( r, r );
561 1923840 : }
562 :
563 30060 : return r;
564 30060 : }
565 :
566 : static inline fd_secp256k1_point_t *
567 : fd_secp256k1_point_to_affine( fd_secp256k1_point_t * r,
568 30060 : fd_secp256k1_point_t const * a ) {
569 30060 : fd_secp256k1_fp_t z[1];
570 30060 : fd_secp256k1_fp_invert( z, a->z );
571 30060 : fd_secp256k1_fp_mul( r->x, a->x, z );
572 30060 : fd_secp256k1_fp_mul( r->y, a->y, z );
573 30060 : return r;
574 30060 : }
575 :
576 : static inline int
577 30060 : fd_secp256k1_point_is_identity( fd_secp256k1_point_t const *a ) {
578 30060 : int affine =
579 30060 : fd_secp256k1_fp_eq( a->x, fd_secp256k1_const_zero ) &
580 30060 : ( fd_secp256k1_fp_eq( a->y, fd_secp256k1_const_zero ) |
581 30060 : fd_secp256k1_fp_eq( a->y, fd_secp256k1_const_one_mont ) );
582 30060 : return fd_secp256k1_fp_eq( a->z, fd_secp256k1_const_zero ) | affine;
583 30060 : }
|
