Line data Source code
1 : #include "./fd_bn254.h"
2 :
3 : /* G2 */
4 :
5 : /* COV: unlike g1, g2 operations are not exposed to users.
6 : So many edge cases and checks for zero are never triggered, e.g. by syscall tests. */
7 :
8 : static inline int
9 428310 : fd_bn254_g2_is_zero( fd_bn254_g2_t const * p ) {
10 428310 : return fd_bn254_fp2_is_zero( &p->Z );
11 428310 : }
12 :
13 : static inline int
14 : fd_bn254_g2_eq( fd_bn254_g2_t const * p,
15 1206 : fd_bn254_g2_t const * q ) {
16 1206 : if( fd_bn254_g2_is_zero( p ) ) {
17 12 : return fd_bn254_g2_is_zero( q );
18 12 : }
19 1194 : if( fd_bn254_g2_is_zero( q ) ) {
20 0 : return 0;
21 0 : }
22 :
23 1194 : fd_bn254_fp2_t pz2[1], qz2[1];
24 1194 : fd_bn254_fp2_t l[1], r[1];
25 :
26 1194 : fd_bn254_fp2_sqr( pz2, &p->Z );
27 1194 : fd_bn254_fp2_sqr( qz2, &q->Z );
28 :
29 1194 : fd_bn254_fp2_mul( l, &p->X, qz2 );
30 1194 : fd_bn254_fp2_mul( r, &q->X, pz2 );
31 1194 : if( !fd_bn254_fp2_eq( l, r ) ) {
32 0 : return 0;
33 0 : }
34 :
35 1194 : fd_bn254_fp2_mul( l, &p->Y, qz2 );
36 1194 : fd_bn254_fp2_mul( l, l, &q->Z );
37 1194 : fd_bn254_fp2_mul( r, &q->Y, pz2 );
38 1194 : fd_bn254_fp2_mul( r, r, &p->Z );
39 1194 : return fd_bn254_fp2_eq( l, r );
40 1194 : }
41 :
42 : static inline fd_bn254_g2_t *
43 : fd_bn254_g2_set( fd_bn254_g2_t * r,
44 33972 : fd_bn254_g2_t const * p ) {
45 33972 : fd_bn254_fp2_set( &r->X, &p->X );
46 33972 : fd_bn254_fp2_set( &r->Y, &p->Y );
47 33972 : fd_bn254_fp2_set( &r->Z, &p->Z );
48 33972 : return r;
49 33972 : }
50 :
51 : static inline fd_bn254_g2_t *
52 : fd_bn254_g2_neg( fd_bn254_g2_t * r,
53 876 : fd_bn254_g2_t const * p ) {
54 876 : fd_bn254_fp2_set( &r->X, &p->X );
55 876 : fd_bn254_fp2_neg( &r->Y, &p->Y );
56 876 : fd_bn254_fp2_set( &r->Z, &p->Z );
57 876 : return r;
58 876 : }
59 :
60 : static inline fd_bn254_g2_t *
61 87 : fd_bn254_g2_set_zero( fd_bn254_g2_t * r ) {
62 : // fd_bn254_fp2_set_zero( &r->X );
63 : // fd_bn254_fp2_set_zero( &r->Y );
64 87 : fd_bn254_fp2_set_zero( &r->Z );
65 87 : return r;
66 87 : }
67 :
68 : static inline fd_bn254_g2_t *
69 : fd_bn254_g2_to_affine( fd_bn254_g2_t * r,
70 30336 : fd_bn254_g2_t const * p ) {
71 30336 : if( FD_UNLIKELY( fd_bn254_fp2_is_zero( &p->Z ) || fd_bn254_fp2_is_one( &p->Z ) ) ) {
72 30030 : return fd_bn254_g2_set( r, p );
73 30030 : }
74 :
75 306 : fd_bn254_fp2_t iz[1], iz2[1];
76 306 : fd_bn254_fp2_inv( iz, &p->Z );
77 306 : fd_bn254_fp2_sqr( iz2, iz );
78 :
79 : /* X / Z^2, Y / Z^3 */
80 306 : fd_bn254_fp2_mul( &r->X, &p->X, iz2 );
81 306 : fd_bn254_fp2_mul( &r->Y, &p->Y, iz2 );
82 306 : fd_bn254_fp2_mul( &r->Y, &r->Y, iz );
83 306 : fd_bn254_fp2_set_one( &r->Z );
84 306 : return r;
85 30336 : }
86 :
87 : uchar *
88 : fd_bn254_g2_tobytes( uchar out[128],
89 : fd_bn254_g2_t const * p,
90 30360 : int big_endian ) {
91 30360 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
92 24 : fd_memset( out, 0, 128UL );
93 : /* no flags */
94 24 : return out;
95 24 : }
96 :
97 30336 : fd_bn254_g2_t r[1];
98 30336 : fd_bn254_g2_to_affine( r, p );
99 :
100 30336 : fd_bn254_fp2_from_mont( &r->X, &r->X );
101 30336 : fd_bn254_fp2_from_mont( &r->Y, &r->Y );
102 :
103 30336 : fd_bn254_fp2_tobytes_nm( &out[ 0], &r->X, big_endian );
104 30336 : fd_bn254_fp2_tobytes_nm( &out[64], &r->Y, big_endian );
105 : /* no flags */
106 30336 : return out;
107 30360 : }
108 :
109 : static inline fd_bn254_g2_t *
110 : fd_bn254_g2_frob( fd_bn254_g2_t * r,
111 3288 : fd_bn254_g2_t const * p ) {
112 3288 : fd_bn254_fp2_conj( &r->X, &p->X );
113 3288 : fd_bn254_fp2_mul ( &r->X, &r->X, &fd_bn254_const_frob_gamma1_mont[1] );
114 3288 : fd_bn254_fp2_conj( &r->Y, &p->Y );
115 3288 : fd_bn254_fp2_mul ( &r->Y, &r->Y, &fd_bn254_const_frob_gamma1_mont[2] );
116 3288 : fd_bn254_fp2_conj( &r->Z, &p->Z );
117 3288 : return r;
118 3288 : }
119 :
120 : static inline fd_bn254_g2_t *
121 : fd_bn254_g2_frob2( fd_bn254_g2_t * r,
122 2082 : fd_bn254_g2_t const * p ) {
123 : /* X */
124 2082 : fd_bn254_fp_mul( &r->X.el[0], &p->X.el[0], &fd_bn254_const_frob_gamma2_mont[1] );
125 2082 : fd_bn254_fp_mul( &r->X.el[1], &p->X.el[1], &fd_bn254_const_frob_gamma2_mont[1] );
126 : /* Y */
127 2082 : fd_bn254_fp_mul( &r->Y.el[0], &p->Y.el[0], &fd_bn254_const_frob_gamma2_mont[2] );
128 2082 : fd_bn254_fp_mul( &r->Y.el[1], &p->Y.el[1], &fd_bn254_const_frob_gamma2_mont[2] );
129 : /* Z=1 */
130 2082 : fd_bn254_fp2_set( &r->Z, &p->Z );
131 2082 : return r;
132 2082 : }
133 :
134 : /* fd_bn254_g2_dbl computes r = 2p.
135 : https://hyperelliptic.org/efd/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l */
136 : fd_bn254_g2_t *
137 : fd_bn254_g2_dbl( fd_bn254_g2_t * r,
138 113790 : fd_bn254_g2_t const * p ) {
139 : /* p==0, return 0 */
140 113790 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
141 12 : return fd_bn254_g2_set_zero( r );
142 12 : }
143 :
144 113778 : fd_bn254_fp2_t a[1], b[1], c[1];
145 113778 : fd_bn254_fp2_t d[1], e[1], f[1];
146 :
147 : /* A = X1^2 */
148 113778 : fd_bn254_fp2_sqr( a, &p->X );
149 : /* B = Y1^2 */
150 113778 : fd_bn254_fp2_sqr( b, &p->Y );
151 : /* C = B^2 */
152 113778 : fd_bn254_fp2_sqr( c, b );
153 : /* D = 2*((X1+B)^2-A-C)
154 : (X1+B)^2 = X1^2 + 2*X1*B + B^2
155 : D = 2*(X1^2 + 2*X1*B + B^2 - A - C)
156 : D = 2*(X1^2 + 2*X1*B + B^2 - X1^2 - B^2)
157 : ^ ^ ^ ^
158 : |---------------|-----| |
159 : |------------|
160 : These terms cancel each other out, and we're left with:
161 : D = 2*(2*X1*B) */
162 113778 : fd_bn254_fp2_mul( d, &p->X, b );
163 113778 : fd_bn254_fp2_add( d, d, d );
164 113778 : fd_bn254_fp2_add( d, d, d );
165 : /* E = 3*A */
166 113778 : fd_bn254_fp2_add( e, a, a );
167 113778 : fd_bn254_fp2_add( e, a, e );
168 : /* F = E^2 */
169 113778 : fd_bn254_fp2_sqr( f, e );
170 : /* X3 = F-2*D */
171 113778 : fd_bn254_fp2_add( &r->X, d, d );
172 113778 : fd_bn254_fp2_sub( &r->X, f, &r->X );
173 : /* Z3 = (Y1+Z1)^2-YY-ZZ
174 : note: compute Z3 before Y3 because it depends on p->Y,
175 : that might be overwritten if r==p. */
176 : /* Z3 = 2*Y1*Z1 */
177 113778 : fd_bn254_fp2_mul( &r->Z, &p->Y, &p->Z );
178 113778 : fd_bn254_fp2_add( &r->Z, &r->Z, &r->Z );
179 : /* Y3 = E*(D-X3)-8*C */
180 113778 : fd_bn254_fp2_sub( &r->Y, d, &r->X );
181 113778 : fd_bn254_fp2_mul( &r->Y, e, &r->Y );
182 113778 : fd_bn254_fp2_add( c, c, c ); /* 2*c */
183 113778 : fd_bn254_fp2_add( c, c, c ); /* 4*y */
184 113778 : fd_bn254_fp2_add( c, c, c ); /* 8*y */
185 113778 : fd_bn254_fp2_sub( &r->Y, &r->Y, c );
186 113778 : return r;
187 113790 : }
188 :
189 : /* fd_bn254_g2_add_mixed computes r = p + q, when q->Z==1.
190 : http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-madd-2007-bl */
191 : fd_bn254_g2_t *
192 : fd_bn254_g2_add_mixed( fd_bn254_g2_t * r,
193 : fd_bn254_g2_t const * p,
194 60066 : fd_bn254_g2_t const * q ) {
195 : /* p==0, return q */
196 60066 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
197 12 : return fd_bn254_g2_set( r, q );
198 12 : }
199 : /* q==0, return p */
200 60054 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( q ) ) ) {
201 0 : return fd_bn254_g2_set( r, p );
202 0 : }
203 60054 : fd_bn254_fp2_t zz[1], u2[1], s2[1];
204 60054 : fd_bn254_fp2_t h[1], hh[1];
205 60054 : fd_bn254_fp2_t i[1], j[1];
206 60054 : fd_bn254_fp2_t rr[1], v[1];
207 : /* Z1Z1 = Z1^2 */
208 60054 : fd_bn254_fp2_sqr( zz, &p->Z );
209 : /* U2 = X2*Z1Z1 */
210 60054 : fd_bn254_fp2_mul( u2, &q->X, zz );
211 : /* S2 = Y2*Z1*Z1Z1 */
212 60054 : fd_bn254_fp2_mul( s2, &q->Y, &p->Z );
213 60054 : fd_bn254_fp2_mul( s2, s2, zz );
214 :
215 : /* if p==q, call fd_bn254_g2_dbl */
216 60054 : if( FD_UNLIKELY( fd_bn254_fp2_eq( u2, &p->X ) && fd_bn254_fp2_eq( s2, &p->Y ) ) ) {
217 0 : return fd_bn254_g2_dbl( r, p );
218 0 : }
219 :
220 : /* H = U2-X1 */
221 60054 : fd_bn254_fp2_sub( h, u2, &p->X );
222 : /* HH = H^2 */
223 60054 : fd_bn254_fp2_sqr( hh, h );
224 : /* I = 4*HH */
225 60054 : fd_bn254_fp2_add( i, hh, hh );
226 60054 : fd_bn254_fp2_add( i, i, i );
227 : /* J = H*I */
228 60054 : fd_bn254_fp2_mul( j, h, i );
229 : /* r = 2*(S2-Y1) */
230 60054 : fd_bn254_fp2_sub( rr, s2, &p->Y );
231 60054 : fd_bn254_fp2_add( rr, rr, rr );
232 : /* V = X1*I */
233 60054 : fd_bn254_fp2_mul( v, &p->X, i );
234 : /* X3 = r^2-J-2*V */
235 60054 : fd_bn254_fp2_sqr( &r->X, rr );
236 60054 : fd_bn254_fp2_sub( &r->X, &r->X, j );
237 60054 : fd_bn254_fp2_sub( &r->X, &r->X, v );
238 60054 : fd_bn254_fp2_sub( &r->X, &r->X, v );
239 : /* Y3 = r*(V-X3)-2*Y1*J
240 : note: i no longer used */
241 60054 : fd_bn254_fp2_mul( i, &p->Y, j ); /* i = Y1*J */
242 60054 : fd_bn254_fp2_add( i, i, i ); /* i = 2*Y1*J */
243 60054 : fd_bn254_fp2_sub( &r->Y, v, &r->X );
244 60054 : fd_bn254_fp2_mul( &r->Y, &r->Y, rr );
245 60054 : fd_bn254_fp2_sub( &r->Y, &r->Y, i );
246 : /* Z3 = (Z1+H)^2-Z1Z1-HH */
247 60054 : fd_bn254_fp2_add( &r->Z, &p->Z, h );
248 60054 : fd_bn254_fp2_sqr( &r->Z, &r->Z );
249 60054 : fd_bn254_fp2_sub( &r->Z, &r->Z, zz );
250 60054 : fd_bn254_fp2_sub( &r->Z, &r->Z, hh );
251 60054 : return r;
252 60054 : }
253 :
254 : /* fd_bn254_g2_add computes r = p + q.
255 : p MUST not be equal to q, unless p==0.
256 : http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-add-2007-bl */
257 : fd_bn254_g2_t *
258 : fd_bn254_g2_add( fd_bn254_g2_t * r,
259 : fd_bn254_g2_t const * p,
260 2412 : fd_bn254_g2_t const * q ) {
261 : /* p==0, return q */
262 2412 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
263 24 : return fd_bn254_g2_set( r, q );
264 24 : }
265 : /* q==0, return p */
266 2388 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( q ) ) ) {
267 0 : return fd_bn254_g2_set( r, p );
268 0 : }
269 2388 : fd_bn254_fp2_t zz1[1], zz2[1];
270 2388 : fd_bn254_fp2_t u1[1], s1[1];
271 2388 : fd_bn254_fp2_t u2[1], s2[1];
272 2388 : fd_bn254_fp2_t h[1];
273 2388 : fd_bn254_fp2_t i[1], j[1];
274 2388 : fd_bn254_fp2_t rr[1], v[1];
275 : /* Z1Z1 = Z1^2 */
276 2388 : fd_bn254_fp2_sqr( zz1, &p->Z );
277 : /* Z2Z2 = Z2^2 */
278 2388 : fd_bn254_fp2_sqr( zz2, &q->Z );
279 : /* U1 = X1*Z2Z2 */
280 2388 : fd_bn254_fp2_mul( u1, &p->X, zz2 );
281 : /* U2 = X2*Z1Z1 */
282 2388 : fd_bn254_fp2_mul( u2, &q->X, zz1 );
283 : /* S1 = Y1*Z2*Z2Z2 */
284 2388 : fd_bn254_fp2_mul( s1, &p->Y, &q->Z );
285 2388 : fd_bn254_fp2_mul( s1, s1, zz2 );
286 : /* S2 = Y2*Z1*Z1Z1 */
287 2388 : fd_bn254_fp2_mul( s2, &q->Y, &p->Z );
288 2388 : fd_bn254_fp2_mul( s2, s2, zz1 );
289 :
290 : /* if p==q, call fd_bn254_g2_dbl */
291 : // if( FD_UNLIKELY( fd_bn254_fp2_eq( u2, &p->X ) && fd_bn254_fp2_eq( s2, &p->Y ) ) ) {
292 : // return fd_bn254_g2_dbl( r, p );
293 : // }
294 :
295 : /* H = U2-U1 */
296 2388 : fd_bn254_fp2_sub( h, u2, u1 );
297 : /* HH = (2*H)^2 */
298 2388 : fd_bn254_fp2_add( i, h, h );
299 2388 : fd_bn254_fp2_sqr( i, i );
300 : /* J = H*I */
301 2388 : fd_bn254_fp2_mul( j, h, i );
302 : /* r = 2*(S2-S1) */
303 2388 : fd_bn254_fp2_sub( rr, s2, s1 );
304 2388 : fd_bn254_fp2_add( rr, rr, rr );
305 : /* V = U1*I */
306 2388 : fd_bn254_fp2_mul( v, u1, i );
307 : /* X3 = r^2-J-2*V */
308 2388 : fd_bn254_fp2_sqr( &r->X, rr );
309 2388 : fd_bn254_fp2_sub( &r->X, &r->X, j );
310 2388 : fd_bn254_fp2_sub( &r->X, &r->X, v );
311 2388 : fd_bn254_fp2_sub( &r->X, &r->X, v );
312 : /* Y3 = r*(V-X3)-2*S1*J
313 : note: i no longer used */
314 2388 : fd_bn254_fp2_mul( i, s1, j ); /* i = S1*J */
315 2388 : fd_bn254_fp2_add( i, i, i ); /* i = 2*S1*J */
316 2388 : fd_bn254_fp2_sub( &r->Y, v, &r->X );
317 2388 : fd_bn254_fp2_mul( &r->Y, &r->Y, rr );
318 2388 : fd_bn254_fp2_sub( &r->Y, &r->Y, i );
319 : /* Z3 = ((Z1+Z2)^2-Z1Z1-Z2Z2)*H */
320 2388 : fd_bn254_fp2_add( &r->Z, &p->Z, &q->Z );
321 2388 : fd_bn254_fp2_sqr( &r->Z, &r->Z );
322 2388 : fd_bn254_fp2_sub( &r->Z, &r->Z, zz1 );
323 2388 : fd_bn254_fp2_sub( &r->Z, &r->Z, zz2 );
324 2388 : fd_bn254_fp2_mul( &r->Z, &r->Z, h );
325 2388 : return r;
326 2388 : }
327 :
328 : /* fd_bn254_g2_affine_add computes r = p + q.
329 : Both p, q are affine, i.e. Z==1. */
330 : static fd_bn254_g2_t *
331 : fd_bn254_g2_affine_add( fd_bn254_g2_t * r,
332 : fd_bn254_g2_t const * p,
333 31536 : fd_bn254_g2_t const * q ) {
334 : /* p==0, return q */
335 31536 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
336 12 : return fd_bn254_g2_set( r, q );
337 12 : }
338 : /* q==0, return p */
339 31524 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( q ) ) ) {
340 6 : return fd_bn254_g2_set( r, p );
341 6 : }
342 :
343 31518 : fd_bn254_fp2_t lambda[1], x[1], y[1];
344 :
345 : /* same X, either the points are equal or opposite */
346 31518 : if( fd_bn254_fp2_eq( &p->X, &q->X ) ) {
347 6 : if( fd_bn254_fp2_eq( &p->Y, &q->Y ) ) {
348 : /* p==q => point double: lambda = 3 * x1^2 / (2 * y1) */
349 6 : fd_bn254_fp2_sqr( x, &p->X ); /* x = x1^2 */
350 6 : fd_bn254_fp2_add( y, x, x ); /* y = 2 x1^2 */
351 6 : fd_bn254_fp2_add( x, x, y ); /* x = 3 x1^2 */
352 6 : fd_bn254_fp2_add( y, &p->Y, &p->Y );
353 6 : fd_bn254_fp2_inv( lambda, y );
354 6 : fd_bn254_fp2_mul( lambda, lambda, x );
355 6 : } else {
356 : /* p==-q => r=0 */
357 0 : return fd_bn254_g2_set_zero( r );
358 0 : }
359 31512 : } else {
360 : /* point add: lambda = (y1 - y2) / (x1 - x2) */
361 31512 : fd_bn254_fp2_sub( x, &p->X, &q->X );
362 31512 : fd_bn254_fp2_sub( y, &p->Y, &q->Y );
363 31512 : fd_bn254_fp2_inv( lambda, x );
364 31512 : fd_bn254_fp2_mul( lambda, lambda, y );
365 31512 : }
366 :
367 : /* x3 = lambda^2 - x1 - x2 */
368 31518 : fd_bn254_fp2_sqr( x, lambda );
369 31518 : fd_bn254_fp2_sub( x, x, &p->X );
370 31518 : fd_bn254_fp2_sub( x, x, &q->X );
371 :
372 : /* y3 = lambda * (x1 - x3) - y1 */
373 31518 : fd_bn254_fp2_sub( y, &p->X, x );
374 31518 : fd_bn254_fp2_mul( y, y, lambda );
375 31518 : fd_bn254_fp2_sub( y, y, &p->Y );
376 :
377 31518 : fd_bn254_fp2_set( &r->X, x );
378 31518 : fd_bn254_fp2_set( &r->Y, y );
379 31518 : fd_bn254_fp2_set_one( &r->Z );
380 31518 : return r;
381 31518 : }
382 :
383 : /* fd_bn254_g2_scalar_mul computes r = [s]P.
384 : p must be in affine form (p->Z == 1).
385 : The result is in projective coordinates over Fp2. */
386 : fd_bn254_g2_t *
387 : fd_bn254_g2_scalar_mul( fd_bn254_g2_t * r,
388 : fd_bn254_g2_t const * p,
389 1536 : fd_bn254_scalar_t const * s ) {
390 1536 : if( FD_UNLIKELY( fd_uint256_is_zero( s ) || fd_bn254_g2_is_zero( p ) ) ) {
391 30 : return fd_bn254_g2_set_zero( r );
392 30 : }
393 :
394 1506 : const ulong g1_const[ 3 ] = { 0x7a7bd9d4391eb18eUL, 0x4ccef014a773d2cfUL, 0x0000000000000002UL };
395 1506 : ulong b1[ 3 ], b2[ 2 ];
396 1506 : fd_bn254_glv_sxg3( b1, s, g1_const );
397 1506 : fd_bn254_glv_sxg2( b2, s, g2_const );
398 :
399 : /* k1 = s - b1*N_C - b2*N_B (may be negative for G2) */
400 1506 : fd_uint256_t k1_abs[1];
401 1506 : int k1_neg = 0;
402 1506 : {
403 1506 : ulong p_nc[ 4 ];
404 : /* b2*nb will produce at most 3 limbs, so we want the 4th zeroed for the addition. */
405 1506 : ulong p_nb[ 4 ] = {0};
406 1506 : ulong t[ 4 ];
407 1506 : fd_bn254_glv_mul3x2( p_nc, b1, nc );
408 1506 : fd_bn254_glv_mul2x1( p_nb, b2, nb );
409 1506 : fd_bn254_glv_add4( t, p_nc, p_nb );
410 1506 : ulong borrow = fd_bn254_glv_sub4( k1_abs->limbs, s->limbs, t );
411 1506 : if( borrow ) {
412 0 : k1_neg = 1;
413 0 : fd_bn254_glv_negate4( k1_abs->limbs );
414 0 : }
415 1506 : }
416 :
417 : /* k2 = b2*N_A - b1*N_B (usually negative for G2) */
418 1506 : fd_uint256_t k2_abs[1];
419 1506 : int k2_neg = 0;
420 1506 : {
421 1506 : ulong pos[ 4 ], neg[ 4 ];
422 1506 : fd_bn254_glv_mul2x2( pos, b2, na );
423 1506 : fd_bn254_glv_mul3x1( neg, b1, nb );
424 1506 : ulong borrow = fd_bn254_glv_sub4( k2_abs->limbs, pos, neg );
425 1506 : if( borrow ) {
426 306 : k2_neg = 1;
427 306 : fd_bn254_glv_negate4( k2_abs->limbs );
428 306 : }
429 1506 : }
430 :
431 : /* pt1 = P, pt2 = phi(P) = (beta * P.x, P.y).
432 : If k1 < 0, negate pt1. If k2 < 0, negate pt2. */
433 1506 : fd_bn254_g2_t pt1[1], pt2[1];
434 1506 : fd_bn254_g2_set( pt1, p );
435 1506 : fd_bn254_fp_mul( &pt2->X.el[0], &p->X.el[0], fd_bn254_const_beta_mont );
436 1506 : fd_bn254_fp_mul( &pt2->X.el[1], &p->X.el[1], fd_bn254_const_beta_mont );
437 1506 : fd_bn254_fp2_set( &pt2->Y, &p->Y );
438 1506 : fd_bn254_fp2_set_one( &pt2->Z );
439 1506 : if( k1_neg ) {
440 0 : fd_bn254_fp2_neg( &pt1->Y, &pt1->Y );
441 0 : }
442 1506 : if( k2_neg ) {
443 306 : fd_bn254_fp2_neg( &pt2->Y, &pt2->Y );
444 306 : }
445 :
446 1506 : fd_bn254_g2_t pt12[1];
447 1506 : fd_bn254_g2_affine_add( pt12, pt1, pt2 );
448 :
449 : /* Shamir's trick: simultaneous double-and-add on k1, k2. */
450 1506 : int i = 255;
451 272952 : for( ; i>=0; i-- ) {
452 272952 : int k1b = !!fd_uint256_bit( k1_abs, i );
453 272952 : int k2b = !!fd_uint256_bit( k2_abs, i );
454 272952 : if( k1b || k2b ) {
455 1506 : fd_bn254_g2_set( r, ( k1b && k2b ) ? pt12 : ( k1b ? pt1 : pt2 ) );
456 1506 : break;
457 1506 : }
458 272952 : }
459 1506 : if( FD_UNLIKELY( i<0 ) ) {
460 0 : return fd_bn254_g2_set_zero( r );
461 0 : }
462 114090 : for( i--; i >= 0; i-- ) {
463 112584 : fd_bn254_g2_dbl( r, r );
464 112584 : int k1b = !!fd_uint256_bit( k1_abs, i );
465 112584 : int k2b = !!fd_uint256_bit( k2_abs, i );
466 112584 : if( k1b && k2b ) {
467 8874 : fd_bn254_g2_add_mixed( r, r, pt12 );
468 103710 : } else if( k1b ) {
469 41724 : fd_bn254_g2_add_mixed( r, r, pt1 );
470 61986 : } else if( k2b ) {
471 8262 : fd_bn254_g2_add_mixed( r, r, pt2 );
472 8262 : }
473 112584 : }
474 :
475 1506 : return r;
476 1506 : }
477 :
478 : /* fd_bn254_g2_frombytes_internal extracts (x, y) and performs basic checks.
479 : This is used by fd_bn254_g2_compress() and fd_bn254_g2_frombytes_check_subgroup(). */
480 : static inline fd_bn254_g2_t *
481 : fd_bn254_g2_frombytes_internal( fd_bn254_g2_t * p,
482 : uchar const in[128],
483 91368 : int big_endian ) {
484 : /* Special case: all zeros => point at infinity */
485 91368 : const uchar zero[128] = { 0 };
486 91368 : if( FD_UNLIKELY( fd_memeq( in, zero, 128 ) ) ) {
487 39 : return fd_bn254_g2_set_zero( p );
488 39 : }
489 :
490 : /* Check x < p */
491 91329 : if( FD_UNLIKELY( !fd_bn254_fp2_frombytes_nm( &p->X, &in[0], big_endian, NULL, NULL ) ) ) {
492 0 : return NULL;
493 0 : }
494 :
495 : /* Check flags and y < p */
496 91329 : int is_inf, is_neg;
497 91329 : if( FD_UNLIKELY( !fd_bn254_fp2_frombytes_nm( &p->Y, &in[64], big_endian, &is_inf, &is_neg ) ) ) {
498 0 : return NULL;
499 0 : }
500 :
501 91329 : if( FD_UNLIKELY( is_inf ) ) {
502 6 : return fd_bn254_g2_set_zero( p );
503 6 : }
504 :
505 91323 : fd_bn254_fp2_set_one( &p->Z );
506 91323 : return p;
507 91329 : }
508 :
509 : /* fd_bn254_g2_frombytes_check_eq_only performs frombytes, checks the curve
510 : equation, but does NOT check subgroup membership. */
511 : static inline fd_bn254_g2_t *
512 : fd_bn254_g2_frombytes_check_eq_only( fd_bn254_g2_t * p,
513 : uchar const in[128],
514 61266 : int big_endian ) {
515 61266 : if( FD_UNLIKELY( !fd_bn254_g2_frombytes_internal( p, in, big_endian ) ) ) {
516 0 : return NULL;
517 0 : }
518 61266 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
519 36 : return p;
520 36 : }
521 :
522 61230 : fd_bn254_fp2_to_mont( &p->X, &p->X );
523 61230 : fd_bn254_fp2_to_mont( &p->Y, &p->Y );
524 61230 : fd_bn254_fp2_set_one( &p->Z );
525 :
526 : /* Check that y^2 = x^3 + b */
527 61230 : fd_bn254_fp2_t y2[1], x3b[1];
528 61230 : fd_bn254_fp2_sqr( y2, &p->Y );
529 61230 : fd_bn254_fp2_sqr( x3b, &p->X );
530 61230 : fd_bn254_fp2_mul( x3b, x3b, &p->X );
531 61230 : fd_bn254_fp2_add( x3b, x3b, fd_bn254_const_twist_b_mont );
532 61230 : if( FD_UNLIKELY( !fd_bn254_fp2_eq( y2, x3b ) ) ) {
533 0 : return NULL;
534 0 : }
535 61230 : return p;
536 61230 : }
537 :
538 : /* fd_bn254_g2_frombytes_check_subgroup performs frombytes AND checks subgroup membership. */
539 : static inline fd_bn254_g2_t *
540 : fd_bn254_g2_frombytes_check_subgroup( fd_bn254_g2_t * p,
541 : uchar const in[128],
542 1206 : int big_endian ) {
543 1206 : if( FD_UNLIKELY( fd_bn254_g2_frombytes_check_eq_only( p, in, big_endian )==NULL ) ) {
544 0 : return NULL;
545 0 : }
546 :
547 : /* G2 does NOT have prime order, so we have to check group membership. */
548 :
549 : /* We use the fast subgroup membership check, that requires a single 64-bit scalar mul.
550 : https://eprint.iacr.org/2022/348, Sec 3.1.
551 : [r]P == 0 <==> [x+1]P + ψ([x]P) + ψ²([x]P) = ψ³([2x]P)
552 : See also: https://github.com/Consensys/gnark-crypto/blob/v0.12.1/ecc/bn254/g2.go#L404
553 :
554 : For reference, the followings also work:
555 :
556 : 1) very slow: 256-bit scalar mul
557 :
558 : fd_bn254_g2_t r[1];
559 : fd_bn254_g2_scalar_mul( r, p, fd_bn254_const_r );
560 : if( !fd_bn254_g2_is_zero( r ) ) return NULL;
561 :
562 : 2) slow: 128-bit scalar mul
563 :
564 : fd_bn254_g2_t a[1], b[1];
565 : const fd_bn254_scalar_t six_x_sqr[1] = {{{ 0xf83e9682e87cfd46, 0x6f4d8248eeb859fb, 0x0, 0x0, }}};
566 : fd_bn254_g2_scalar_mul( a, p, six_x_sqr );
567 : fd_bn254_g2_frob( b, p );
568 : if( !fd_bn254_g2_eq( a, b ) ) return NULL; */
569 :
570 1206 : fd_bn254_g2_t xp[1], l[1], psi[1], r[1];
571 1206 : fd_bn254_g2_scalar_mul( xp, p, fd_bn254_const_x ); /* 64-bit */
572 1206 : fd_bn254_g2_add_mixed( l, xp, p );
573 :
574 : /* l will not be equal to psi unless p==0 */
575 1206 : fd_bn254_g2_frob( psi, xp );
576 1206 : fd_bn254_g2_add( l, l, psi );
577 :
578 1206 : fd_bn254_g2_frob2( psi, xp ); /* faster than frob( psi, psi ) */
579 1206 : fd_bn254_g2_add( l, l, psi );
580 :
581 1206 : fd_bn254_g2_frob( psi, psi );
582 1206 : fd_bn254_g2_dbl( r, psi );
583 1206 : if( FD_UNLIKELY( !fd_bn254_g2_eq( l, r ) ) ) {
584 0 : return NULL;
585 0 : }
586 1206 : return p;
587 1206 : }
|
