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