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