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 60084 : fd_secp256k1_fp_t const * restrict a ) {
43 60084 : fd_secp256k1_fp_t x2;
44 60084 : fd_secp256k1_fp_t x3;
45 :
46 60084 : fd_secp256k1_fp_sqr( &x2, a );
47 60084 : fd_secp256k1_fp_mul( &x2, &x2, a );
48 :
49 60084 : fd_secp256k1_fp_sqr( &x3, &x2 );
50 60084 : fd_secp256k1_fp_mul( &x3, &x3, a );
51 :
52 60084 : fd_secp256k1_fp_t x6 = x3;
53 240336 : for( int j=0; j<3; j++ ) fd_secp256k1_fp_sqr( &x6, &x6 );
54 60084 : fd_secp256k1_fp_mul( &x6, &x6, &x3 );
55 :
56 60084 : fd_secp256k1_fp_t x9 = x6;
57 240336 : for( int j=0; j<3; j++ ) fd_secp256k1_fp_sqr( &x9, &x9 );
58 60084 : fd_secp256k1_fp_mul( &x9, &x9, &x3 );
59 :
60 60084 : fd_secp256k1_fp_t x11 = x9;
61 180252 : for( int j=0; j<2; j++ ) fd_secp256k1_fp_sqr( &x11, &x11 );
62 60084 : fd_secp256k1_fp_mul( &x11, &x11, &x2 );
63 :
64 60084 : fd_secp256k1_fp_t x22 = x11;
65 721008 : for( int j=0; j<11; j++ ) fd_secp256k1_fp_sqr( &x22, &x22 );
66 60084 : fd_secp256k1_fp_mul( &x22, &x22, &x11 );
67 :
68 60084 : fd_secp256k1_fp_t x44 = x22;
69 1381932 : for( int j=0; j<22; j++ ) fd_secp256k1_fp_sqr( &x44, &x44 );
70 60084 : fd_secp256k1_fp_mul( &x44, &x44, &x22 );
71 :
72 60084 : fd_secp256k1_fp_t x88 = x44;
73 2703780 : for( int j=0; j<44; j++ ) fd_secp256k1_fp_sqr( &x88, &x88 );
74 60084 : fd_secp256k1_fp_mul( &x88, &x88, &x44 );
75 :
76 60084 : fd_secp256k1_fp_t x176 = x88;
77 5347476 : for( int j=0; j<88; j++ ) fd_secp256k1_fp_sqr( &x176, &x176 );
78 60084 : fd_secp256k1_fp_mul( &x176, &x176, &x88 );
79 :
80 60084 : fd_secp256k1_fp_t x220 = x176;
81 2703780 : for( int j=0; j<44; j++ ) fd_secp256k1_fp_sqr( &x220, &x220 );
82 60084 : fd_secp256k1_fp_mul( &x220, &x220, &x44 );
83 :
84 60084 : fd_secp256k1_fp_t x223 = x220;
85 240336 : for( int j=0; j<3; j++ ) fd_secp256k1_fp_sqr( &x223, &x223 );
86 60084 : fd_secp256k1_fp_mul( &x223, &x223, &x3 );
87 :
88 60084 : fd_secp256k1_fp_t t1 = x223;
89 1442016 : for( int j=0; j<23; j++ ) fd_secp256k1_fp_sqr( &t1, &t1 );
90 60084 : fd_secp256k1_fp_mul( &t1, &t1, &x22 );
91 :
92 420588 : for( int j=0; j<6; j++ ) fd_secp256k1_fp_sqr( &t1, &t1 );
93 60084 : fd_secp256k1_fp_mul( &t1, &t1, &x2 );
94 60084 : fd_secp256k1_fp_sqr( &t1, &t1 );
95 60084 : fd_secp256k1_fp_sqr( r, &t1 );
96 :
97 60084 : fd_secp256k1_fp_sqr( &t1, r );
98 60084 : if( FD_UNLIKELY( !fd_secp256k1_fp_eq( &t1, a ) ) ) {
99 30024 : return NULL;
100 30024 : }
101 :
102 30060 : return r;
103 60084 : }
104 :
105 : /* Point */
106 :
107 : /* Sets a group element to the identity element in Jacobian coordinates */
108 : static inline void
109 90180 : fd_secp256k1_point_set_identity( fd_secp256k1_point_t *r ) {
110 90180 : fd_secp256k1_fp_set( r->x, fd_secp256k1_const_zero );
111 90180 : fd_secp256k1_fp_set( r->y, fd_secp256k1_const_one_mont );
112 90180 : fd_secp256k1_fp_set( r->z, fd_secp256k1_const_zero );
113 90180 : }
114 :
115 : /* Sets a group element to the base element in Jacobian coordinates */
116 : static inline void
117 30060 : fd_secp256k1_point_set_base( fd_secp256k1_point_t *r ) {
118 30060 : fd_secp256k1_fp_set( r->x, fd_secp256k1_const_base_x_mont );
119 30060 : fd_secp256k1_fp_set( r->y, fd_secp256k1_const_base_y_mont );
120 30060 : fd_secp256k1_fp_set( r->z, fd_secp256k1_const_one_mont );
121 30060 : }
122 :
123 : /* r = a */
124 : static inline void
125 : fd_secp256k1_point_set( fd_secp256k1_point_t * r,
126 60120 : fd_secp256k1_point_t const * a ) {
127 60120 : fd_secp256k1_fp_set( r->x, a->x );
128 60120 : fd_secp256k1_fp_set( r->y, a->y );
129 60120 : fd_secp256k1_fp_set( r->z, a->z );
130 60120 : }
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 3757323 : fd_secp256k1_point_t const * b ) {
137 3757323 : fd_secp256k1_fp_t t0[ 1 ];
138 3757323 : fd_secp256k1_fp_t t1[ 1 ];
139 3757323 : fd_secp256k1_fp_t t2[ 1 ];
140 3757323 : fd_secp256k1_fp_t t3[ 1 ];
141 3757323 : fd_secp256k1_fp_t t4[ 1 ];
142 :
143 3757323 : fd_secp256k1_fp_t X3[ 1 ];
144 3757323 : fd_secp256k1_fp_t Y3[ 1 ];
145 3757323 : fd_secp256k1_fp_t Z3[ 1 ];
146 :
147 : /* t0 = X1 * X2 */
148 3757323 : fd_secp256k1_fp_mul( t0, a->x, b->x );
149 : /* t1 = Y1 * Y2 */
150 3757323 : fd_secp256k1_fp_mul( t1, a->y, b->y );
151 : /* t2 = Z1 * Z2 */
152 3757323 : fd_secp256k1_fp_mul( t2, a->z, b->z );
153 :
154 : /* t3 = (a.x + a.y) * (b.x + b.y) - (t0 + t1) */
155 3757323 : fd_secp256k1_fp_add( t3, a->x, a->y );
156 3757323 : fd_secp256k1_fp_add( t4, b->x, b->y );
157 3757323 : fd_secp256k1_fp_mul( t3, t3, t4 );
158 3757323 : fd_secp256k1_fp_add( t4, t0, t1 );
159 3757323 : fd_secp256k1_fp_sub( t3, t3, t4 );
160 :
161 : /* t4 = (a.y + a.z) * (b.y + b.z) - (t1 + t2) */
162 3757323 : fd_secp256k1_fp_add( t4, a->y, a->z );
163 3757323 : fd_secp256k1_fp_add( X3, b->y, b->z );
164 3757323 : fd_secp256k1_fp_mul( t4, t4, X3 );
165 3757323 : fd_secp256k1_fp_add( X3, t1, t2 );
166 3757323 : fd_secp256k1_fp_sub( t4, t4, X3 );
167 :
168 : /* Y3 = (a.x + a.z) * (b.x + b.z) - (t0 + t2) */
169 3757323 : fd_secp256k1_fp_add( X3, a->x, a->z );
170 3757323 : fd_secp256k1_fp_add( Y3, b->x, b->z );
171 3757323 : fd_secp256k1_fp_mul( X3, X3, Y3 );
172 3757323 : fd_secp256k1_fp_add( Y3, t0, t2 );
173 3757323 : fd_secp256k1_fp_sub( Y3, X3, Y3 );
174 :
175 : /* t0 = 3 * t0 */
176 3757323 : fd_secp256k1_fp_triple( t0, t0 );
177 :
178 : /* b3 = (2^2)^2 + 2^2 + 1 = 21 */
179 3757323 : fd_secp256k1_fp_t t2_4[ 1 ];
180 3757323 : fd_secp256k1_fp_t t5[ 1 ];
181 3757323 : fd_secp256k1_fp_dbl( t2_4, t2 );
182 3757323 : fd_secp256k1_fp_dbl( t2_4, t2_4 );
183 3757323 : fd_secp256k1_fp_dbl( t5, t2_4 );
184 3757323 : fd_secp256k1_fp_dbl( t5, t5 );
185 3757323 : fd_secp256k1_fp_add( t5, t5, t2_4 );
186 3757323 : fd_secp256k1_fp_add( t2, t5, t2 );
187 :
188 : /* Z3 = t1 * t2
189 : t1 = t1 - t2 */
190 3757323 : fd_secp256k1_fp_add( Z3, t1, t2 );
191 3757323 : fd_secp256k1_fp_sub( t1, t1, t2 );
192 :
193 3757323 : fd_secp256k1_fp_t Y3_4[ 1 ];
194 3757323 : fd_secp256k1_fp_dbl( Y3_4, Y3 );
195 3757323 : fd_secp256k1_fp_dbl( Y3_4, Y3_4 );
196 3757323 : fd_secp256k1_fp_dbl( t5, Y3_4 );
197 3757323 : fd_secp256k1_fp_dbl( t5, t5 );
198 3757323 : fd_secp256k1_fp_add( t5, t5, Y3_4 );
199 3757323 : fd_secp256k1_fp_add( Y3, t5, Y3 );
200 :
201 3757323 : fd_secp256k1_fp_mul( X3, t4, Y3 );
202 3757323 : fd_secp256k1_fp_mul( t2, t3, t1 );
203 3757323 : fd_secp256k1_fp_sub( r->x, t2, X3 );
204 3757323 : fd_secp256k1_fp_mul( Y3, Y3, t0 );
205 3757323 : fd_secp256k1_fp_mul( t1, t1, Z3 );
206 3757323 : fd_secp256k1_fp_add( r->y, t1, Y3 );
207 3757323 : fd_secp256k1_fp_mul( t0, t0, t3 );
208 3757323 : fd_secp256k1_fp_mul( Z3, Z3, t4 );
209 3757323 : fd_secp256k1_fp_add( r->z, Z3, t0 );
210 :
211 3757323 : return r;
212 3757323 : }
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 7935840 : fd_secp256k1_point_t const * a ) {
218 7935840 : fd_secp256k1_fp_t t0[ 1 ];
219 7935840 : fd_secp256k1_fp_t t1[ 1 ];
220 7935840 : fd_secp256k1_fp_t t2[ 1 ];
221 :
222 7935840 : fd_secp256k1_fp_t X3[ 1 ];
223 7935840 : fd_secp256k1_fp_t Y3[ 1 ];
224 7935840 : fd_secp256k1_fp_t Z3[ 1 ];
225 :
226 : /* t0 = Y * Y*/
227 7935840 : fd_secp256k1_fp_sqr( t0, a->y );
228 : /* Z3 = 8 * t0 */
229 7935840 : fd_secp256k1_fp_dbl( Z3, t0 );
230 7935840 : fd_secp256k1_fp_dbl( Z3, Z3 );
231 7935840 : fd_secp256k1_fp_dbl( Z3, Z3 );
232 :
233 : /* t1 = Y * Z */
234 7935840 : fd_secp256k1_fp_mul( t1, a->y, a->z );
235 : /* t2 = Z * Z */
236 7935840 : fd_secp256k1_fp_sqr( t2, a->z );
237 :
238 : /* b3 = (2^2)^2 + 2^2 + 1
239 : t2 = b3 * t2 */
240 7935840 : fd_secp256k1_fp_t t2_4[1], t5[1];
241 7935840 : fd_secp256k1_fp_dbl( t2_4, t2 );
242 7935840 : fd_secp256k1_fp_dbl( t2_4, t2_4 );
243 7935840 : fd_secp256k1_fp_dbl( t5, t2_4 );
244 7935840 : fd_secp256k1_fp_dbl( t5, t5 );
245 7935840 : fd_secp256k1_fp_add( t5, t5, t2_4 );
246 7935840 : fd_secp256k1_fp_add( t2, t5, t2 );
247 :
248 : /* X3 = t2 * Z3 */
249 7935840 : fd_secp256k1_fp_mul( X3, t2, Z3 );
250 : /* Y3 = t0 + t2 */
251 7935840 : fd_secp256k1_fp_add( Y3, t0, t2 );
252 :
253 7935840 : fd_secp256k1_fp_mul( r->z, t1, Z3 );
254 :
255 7935840 : fd_secp256k1_fp_dbl( t1, t2 );
256 7935840 : fd_secp256k1_fp_add( t2, t1, t2 );
257 7935840 : fd_secp256k1_fp_sub( t0, t0, t2 );
258 7935840 : fd_secp256k1_fp_mul( Y3, t0, Y3 );
259 : /* compute t1 first, as the next add may overwrite a->y */
260 7935840 : fd_secp256k1_fp_mul( t1, a->x, a->y );
261 7935840 : fd_secp256k1_fp_add( r->y, X3, Y3 );
262 :
263 7935840 : fd_secp256k1_fp_mul( X3, t0, t1 );
264 7935840 : fd_secp256k1_fp_dbl( r->x, X3 );
265 :
266 7935840 : return r;
267 7935840 : }
268 :
269 : /* r = -a */
270 : static inline fd_secp256k1_point_t *
271 : fd_secp256k1_point_neg( fd_secp256k1_point_t * r,
272 2043384 : fd_secp256k1_point_t const * a ) {
273 2043384 : fd_secp256k1_fp_set( r->x, a->x );
274 2043384 : fd_secp256k1_fp_set( r->z, a->z );
275 2043384 : fd_secp256k1_fp_negate( r->y, a->y );
276 2043384 : return r;
277 2043384 : }
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 2043384 : fd_secp256k1_point_t const * b ) {
284 2043384 : fd_secp256k1_point_t tmp[ 1 ];
285 2043384 : fd_secp256k1_point_neg( tmp, b );
286 2043384 : return fd_secp256k1_point_add( r, a, tmp );
287 2043384 : }
288 :
289 : /* Double base multiplication */
290 :
291 : static inline schar *
292 : fd_secp256k1_slide( schar r[ 2 * 32 + 1 ],
293 60120 : uchar const s[ 32 ] ) {
294 1983960 : for( ulong i=0UL; i<32UL; i++ ) {
295 1923840 : uchar x = s[i];
296 1923840 : r[i * 2 + 0] = x & 0xF;
297 1923840 : r[i * 2 + 1] = (x >> 4) & 0xF;
298 1923840 : }
299 : /* Now, r[0..63] is between 0 and 15, r[63] is between 0 and 7 */
300 60120 : schar carry = 0;
301 3907800 : for( ulong i=0UL; i<64UL; i++ ) {
302 3847680 : r[i] = (schar)(r[i] + carry);
303 3847680 : carry = (schar)(r[i] + 8) >> 4;
304 3847680 : r[i] = (schar)(r[i] - carry * 16);
305 : /* r[i] MUST be between [-8, 8] */
306 3847680 : }
307 60120 : r[64] = carry;
308 : /* carry MUST be between [-8, 8] */
309 60120 : return r;
310 60120 : }
311 :
312 : static inline fd_secp256k1_point_t *
313 : fd_secp256k1_precompute( fd_secp256k1_point_t r[ 9 ],
314 60120 : fd_secp256k1_point_t const * a ) {
315 60120 : fd_secp256k1_point_set_identity( &r[0] );
316 60120 : fd_secp256k1_point_set( &r[1], a );
317 480960 : for( ulong i=2UL; i<=8UL; i++ ) {
318 420840 : if( i%2UL ) {
319 180360 : fd_secp256k1_point_add( &r[i], &r[i - 1], a );
320 240480 : } else {
321 240480 : fd_secp256k1_point_dbl( &r[i], &r[i / 2] );
322 240480 : }
323 420840 : }
324 60120 : return r;
325 60120 : }
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 30060 : fd_secp256k1_scalar_t const * s2 ) {
333 30060 : fd_secp256k1_point_t base[ 1 ];
334 30060 : fd_secp256k1_point_set_base( base );
335 :
336 30060 : fd_secp256k1_point_t pc1[ 9 ];
337 30060 : fd_secp256k1_point_t pc2[ 9 ];
338 : /* TODO: Precompute the basepoint table in a generated table */
339 30060 : fd_secp256k1_precompute( pc1, base );
340 30060 : fd_secp256k1_precompute( pc2, p2 );
341 :
342 30060 : schar e1[ 2 * 32 + 1 ];
343 30060 : schar e2[ 2 * 32 + 1 ];
344 30060 : fd_secp256k1_slide( e1, s1->buf );
345 30060 : fd_secp256k1_slide( e2, s2->buf );
346 :
347 30060 : fd_secp256k1_point_set_identity( r );
348 1953900 : for( int pos = 2 * 32; ; pos -= 1 ) {
349 1953900 : schar slot1 = e1[pos];
350 1953900 : if( slot1 > 0 ) {
351 781878 : fd_secp256k1_point_add( r, r, &pc1[(ulong)slot1] );
352 1172022 : } else if( slot1 < 0 ) {
353 961515 : fd_secp256k1_point_sub( r, r, &pc1[(ulong)(-slot1)] );
354 961515 : }
355 :
356 1953900 : schar slot2 = e2[pos];
357 1953900 : if( slot2 > 0 ) {
358 751701 : fd_secp256k1_point_add( r, r, &pc2[(ulong)slot2] );
359 1202199 : } else if( slot2 < 0 ) {
360 1081869 : fd_secp256k1_point_sub( r, r, &pc2[(ulong)(-slot2)] );
361 1081869 : }
362 :
363 1953900 : if( pos == 0 ) break;
364 1923840 : fd_secp256k1_point_dbl( r, r );
365 1923840 : fd_secp256k1_point_dbl( r, r );
366 1923840 : fd_secp256k1_point_dbl( r, r );
367 1923840 : fd_secp256k1_point_dbl( r, r );
368 1923840 : }
369 :
370 30060 : return r;
371 30060 : }
372 :
373 : static inline fd_secp256k1_point_t *
374 : fd_secp256k1_point_to_affine( fd_secp256k1_point_t * r,
375 30060 : fd_secp256k1_point_t const * a ) {
376 30060 : fd_secp256k1_fp_t z[1];
377 30060 : fd_secp256k1_fp_invert( z, a->z );
378 30060 : fd_secp256k1_fp_mul( r->x, a->x, z );
379 30060 : fd_secp256k1_fp_mul( r->y, a->y, z );
380 30060 : return r;
381 30060 : }
382 :
383 : static inline int
384 30060 : fd_secp256k1_point_is_identity( fd_secp256k1_point_t const *a ) {
385 30060 : int affine =
386 30060 : fd_secp256k1_fp_eq( a->x, fd_secp256k1_const_zero ) &
387 30060 : ( fd_secp256k1_fp_eq( a->y, fd_secp256k1_const_zero ) |
388 30060 : fd_secp256k1_fp_eq( a->y, fd_secp256k1_const_one_mont ) );
389 30060 : return fd_secp256k1_fp_eq( a->z, fd_secp256k1_const_zero ) | affine;
390 30060 : }
|
