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 33303 : fd_bn254_g2_is_zero( fd_bn254_g2_t const * p ) {
10 33303 : return fd_bn254_fp2_is_zero( &p->Z );
11 33303 : }
12 :
13 : static inline int
14 : fd_bn254_g2_eq( fd_bn254_g2_t const * p,
15 342 : fd_bn254_g2_t const * q ) {
16 342 : if( fd_bn254_g2_is_zero( p ) ) {
17 0 : return fd_bn254_g2_is_zero( q );
18 0 : }
19 342 : if( fd_bn254_g2_is_zero( q ) ) {
20 0 : return 0;
21 0 : }
22 :
23 342 : fd_bn254_fp2_t pz2[1], qz2[1];
24 342 : fd_bn254_fp2_t l[1], r[1];
25 :
26 342 : fd_bn254_fp2_sqr( pz2, &p->Z );
27 342 : fd_bn254_fp2_sqr( qz2, &q->Z );
28 :
29 342 : fd_bn254_fp2_mul( l, &p->X, qz2 );
30 342 : fd_bn254_fp2_mul( r, &q->X, pz2 );
31 342 : if( !fd_bn254_fp2_eq( l, r ) ) {
32 24 : return 0;
33 24 : }
34 :
35 318 : fd_bn254_fp2_mul( l, &p->Y, qz2 );
36 318 : fd_bn254_fp2_mul( l, l, &q->Z );
37 318 : fd_bn254_fp2_mul( r, &q->Y, pz2 );
38 318 : fd_bn254_fp2_mul( r, r, &p->Z );
39 318 : return fd_bn254_fp2_eq( l, r );
40 342 : }
41 :
42 : static inline fd_bn254_g2_t *
43 : fd_bn254_g2_set( fd_bn254_g2_t * r,
44 594 : fd_bn254_g2_t const * p ) {
45 594 : fd_bn254_fp2_set( &r->X, &p->X );
46 594 : fd_bn254_fp2_set( &r->Y, &p->Y );
47 594 : fd_bn254_fp2_set( &r->Z, &p->Z );
48 594 : return r;
49 594 : }
50 :
51 : static inline fd_bn254_g2_t *
52 : fd_bn254_g2_neg( fd_bn254_g2_t * r,
53 252 : fd_bn254_g2_t const * p ) {
54 252 : fd_bn254_fp2_set( &r->X, &p->X );
55 252 : fd_bn254_fp2_neg( &r->Y, &p->Y );
56 252 : fd_bn254_fp2_set( &r->Z, &p->Z );
57 252 : return r;
58 252 : }
59 :
60 : static inline fd_bn254_g2_t *
61 78 : 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 78 : fd_bn254_fp2_set_zero( &r->Z );
65 78 : return r;
66 78 : }
67 :
68 : static inline fd_bn254_g2_t *
69 : fd_bn254_g2_frob( fd_bn254_g2_t * r,
70 936 : fd_bn254_g2_t const * p ) {
71 936 : fd_bn254_fp2_conj( &r->X, &p->X );
72 936 : fd_bn254_fp2_mul ( &r->X, &r->X, &fd_bn254_const_frob_gamma1_mont[1] );
73 936 : fd_bn254_fp2_conj( &r->Y, &p->Y );
74 936 : fd_bn254_fp2_mul ( &r->Y, &r->Y, &fd_bn254_const_frob_gamma1_mont[2] );
75 936 : fd_bn254_fp2_conj( &r->Z, &p->Z );
76 936 : return r;
77 936 : }
78 :
79 : static inline fd_bn254_g2_t *
80 : fd_bn254_g2_frob2( fd_bn254_g2_t * r,
81 594 : fd_bn254_g2_t const * p ) {
82 : /* X */
83 594 : fd_bn254_fp_mul( &r->X.el[0], &p->X.el[0], &fd_bn254_const_frob_gamma2_mont[1] );
84 594 : fd_bn254_fp_mul( &r->X.el[1], &p->X.el[1], &fd_bn254_const_frob_gamma2_mont[1] );
85 : /* Y */
86 594 : fd_bn254_fp_mul( &r->Y.el[0], &p->Y.el[0], &fd_bn254_const_frob_gamma2_mont[2] );
87 594 : fd_bn254_fp_mul( &r->Y.el[1], &p->Y.el[1], &fd_bn254_const_frob_gamma2_mont[2] );
88 : /* Z=1 */
89 594 : fd_bn254_fp2_set( &r->Z, &p->Z );
90 594 : return r;
91 594 : }
92 :
93 : /* fd_bn254_g2_dbl computes r = 2p.
94 : https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2007-bl */
95 : fd_bn254_g2_t *
96 : fd_bn254_g2_dbl( fd_bn254_g2_t * r,
97 21546 : fd_bn254_g2_t const * p ) {
98 : /* p==0, return 0 */
99 21546 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
100 0 : return fd_bn254_g2_set_zero( r );
101 0 : }
102 :
103 21546 : fd_bn254_fp2_t xx[1], yy[1], zz[1];
104 21546 : fd_bn254_fp2_t y4[1], s[1], m[1];
105 : /* XX = X1^2 */
106 21546 : fd_bn254_fp2_sqr( xx, &p->X );
107 : /* YY = Y1^2 */
108 21546 : fd_bn254_fp2_sqr( yy, &p->Y );
109 : /* YYYY = YY^2 */
110 21546 : fd_bn254_fp2_sqr( y4, yy );
111 : /* ZZ = Z1^2 */
112 21546 : fd_bn254_fp2_sqr( zz, &p->Z );
113 : /* S = 2*((X1+YY)^2-XX-YYYY) */
114 21546 : fd_bn254_fp2_add( s, &p->X, yy );
115 21546 : fd_bn254_fp2_sqr( s, s );
116 21546 : fd_bn254_fp2_sub( s, s, xx );
117 21546 : fd_bn254_fp2_sub( s, s, y4 );
118 21546 : fd_bn254_fp2_add( s, s, s );
119 : /* M = 3*XX+a*ZZ^2, a=0 */
120 21546 : fd_bn254_fp2_add( m, xx, xx );
121 21546 : fd_bn254_fp2_add( m, m, xx );
122 : /* T = M^2-2*S
123 : X3 = T */
124 21546 : fd_bn254_fp2_sqr( &r->X, m );
125 21546 : fd_bn254_fp2_sub( &r->X, &r->X, s );
126 21546 : fd_bn254_fp2_sub( &r->X, &r->X, s );
127 : /* Z3 = (Y1+Z1)^2-YY-ZZ
128 : note: compute Z3 before Y3 because it depends on p->Y,
129 : that might be overwritten if r==p. */
130 21546 : fd_bn254_fp2_add( &r->Z, &p->Z, &p->Y );
131 21546 : fd_bn254_fp2_sqr( &r->Z, &r->Z );
132 21546 : fd_bn254_fp2_sub( &r->Z, &r->Z, yy );
133 21546 : fd_bn254_fp2_sub( &r->Z, &r->Z, zz );
134 : /* Y3 = M*(S-T)-8*YYYY */
135 21546 : fd_bn254_fp2_sub( &r->Y, s, &r->X );
136 21546 : fd_bn254_fp2_mul( &r->Y, &r->Y, m );
137 21546 : fd_bn254_fp2_add( y4, y4, y4 ); /* 2 y^4 */
138 21546 : fd_bn254_fp2_add( y4, y4, y4 ); /* 4 y^4 */
139 21546 : fd_bn254_fp2_add( y4, y4, y4 ); /* 8 y^4 */
140 21546 : fd_bn254_fp2_sub( &r->Y, &r->Y, y4 );
141 21546 : return r;
142 21546 : }
143 :
144 : /* fd_bn254_g2_add_mixed computes r = p + q, when q->Z==1.
145 : http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-madd-2007-bl */
146 : fd_bn254_g2_t *
147 : fd_bn254_g2_add_mixed( fd_bn254_g2_t * r,
148 : fd_bn254_g2_t const * p,
149 9576 : fd_bn254_g2_t const * q ) {
150 : /* p==0, return q */
151 9576 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
152 0 : return fd_bn254_g2_set( r, q );
153 0 : }
154 9576 : fd_bn254_fp2_t zz[1], u2[1], s2[1];
155 9576 : fd_bn254_fp2_t h[1], hh[1];
156 9576 : fd_bn254_fp2_t i[1], j[1];
157 9576 : fd_bn254_fp2_t rr[1], v[1];
158 : /* Z1Z1 = Z1^2 */
159 9576 : fd_bn254_fp2_sqr( zz, &p->Z );
160 : /* U2 = X2*Z1Z1 */
161 9576 : fd_bn254_fp2_mul( u2, &q->X, zz );
162 : /* S2 = Y2*Z1*Z1Z1 */
163 9576 : fd_bn254_fp2_mul( s2, &q->Y, &p->Z );
164 9576 : fd_bn254_fp2_mul( s2, s2, zz );
165 :
166 : /* if p==q, call fd_bn254_g2_dbl */
167 9576 : if( FD_UNLIKELY( fd_bn254_fp2_eq( u2, &p->X ) && fd_bn254_fp2_eq( s2, &p->Y ) ) ) {
168 0 : return fd_bn254_g2_dbl( r, p );
169 0 : }
170 :
171 : /* H = U2-X1 */
172 9576 : fd_bn254_fp2_sub( h, u2, &p->X );
173 : /* HH = H^2 */
174 9576 : fd_bn254_fp2_sqr( hh, h );
175 : /* I = 4*HH */
176 9576 : fd_bn254_fp2_add( i, hh, hh );
177 9576 : fd_bn254_fp2_add( i, i, i );
178 : /* J = H*I */
179 9576 : fd_bn254_fp2_mul( j, h, i );
180 : /* r = 2*(S2-Y1) */
181 9576 : fd_bn254_fp2_sub( rr, s2, &p->Y );
182 9576 : fd_bn254_fp2_add( rr, rr, rr );
183 : /* V = X1*I */
184 9576 : fd_bn254_fp2_mul( v, &p->X, i );
185 : /* X3 = r^2-J-2*V */
186 9576 : fd_bn254_fp2_sqr( &r->X, rr );
187 9576 : fd_bn254_fp2_sub( &r->X, &r->X, j );
188 9576 : fd_bn254_fp2_sub( &r->X, &r->X, v );
189 9576 : fd_bn254_fp2_sub( &r->X, &r->X, v );
190 : /* Y3 = r*(V-X3)-2*Y1*J
191 : note: i no longer used */
192 9576 : fd_bn254_fp2_mul( i, &p->Y, j ); /* i = Y1*J */
193 9576 : fd_bn254_fp2_add( i, i, i ); /* i = 2*Y1*J */
194 9576 : fd_bn254_fp2_sub( &r->Y, v, &r->X );
195 9576 : fd_bn254_fp2_mul( &r->Y, &r->Y, rr );
196 9576 : fd_bn254_fp2_sub( &r->Y, &r->Y, i );
197 : /* Z3 = (Z1+H)^2-Z1Z1-HH */
198 9576 : fd_bn254_fp2_add( &r->Z, &p->Z, h );
199 9576 : fd_bn254_fp2_sqr( &r->Z, &r->Z );
200 9576 : fd_bn254_fp2_sub( &r->Z, &r->Z, zz );
201 9576 : fd_bn254_fp2_sub( &r->Z, &r->Z, hh );
202 9576 : return r;
203 9576 : }
204 :
205 : /* fd_bn254_g2_add computes r = p + q.
206 : http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-add-2007-bl */
207 : fd_bn254_g2_t *
208 : fd_bn254_g2_add( fd_bn254_g2_t * r,
209 : fd_bn254_g2_t const * p,
210 684 : fd_bn254_g2_t const * q ) {
211 : /* p==0, return q */
212 684 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
213 0 : return fd_bn254_g2_set( r, q );
214 0 : }
215 684 : fd_bn254_fp2_t zz1[1], zz2[1];
216 684 : fd_bn254_fp2_t u1[1], s1[1];
217 684 : fd_bn254_fp2_t u2[1], s2[1];
218 684 : fd_bn254_fp2_t h[1];
219 684 : fd_bn254_fp2_t i[1], j[1];
220 684 : fd_bn254_fp2_t rr[1], v[1];
221 : /* Z1Z1 = Z1^2 */
222 684 : fd_bn254_fp2_sqr( zz1, &p->Z );
223 : /* Z2Z2 = Z2^2 */
224 684 : fd_bn254_fp2_sqr( zz2, &q->Z );
225 : /* U1 = X1*Z2Z2 */
226 684 : fd_bn254_fp2_mul( u1, &p->X, zz2 );
227 : /* U2 = X2*Z1Z1 */
228 684 : fd_bn254_fp2_mul( u2, &q->X, zz1 );
229 : /* S1 = Y1*Z2*Z2Z2 */
230 684 : fd_bn254_fp2_mul( s1, &p->Y, &q->Z );
231 684 : fd_bn254_fp2_mul( s1, s1, zz2 );
232 : /* S2 = Y2*Z1*Z1Z1 */
233 684 : fd_bn254_fp2_mul( s2, &q->Y, &p->Z );
234 684 : fd_bn254_fp2_mul( s2, s2, zz1 );
235 :
236 : /* if p==q, call fd_bn254_g2_dbl */
237 : // if( FD_UNLIKELY( fd_bn254_fp2_eq( u2, &p->X ) && fd_bn254_fp2_eq( s2, &p->Y ) ) ) {
238 : // return fd_bn254_g2_dbl( r, p );
239 : // }
240 :
241 : /* H = U2-U1 */
242 684 : fd_bn254_fp2_sub( h, u2, u1 );
243 : /* HH = (2*H)^2 */
244 684 : fd_bn254_fp2_add( i, h, h );
245 684 : fd_bn254_fp2_sqr( i, i );
246 : /* J = H*I */
247 684 : fd_bn254_fp2_mul( j, h, i );
248 : /* r = 2*(S2-S1) */
249 684 : fd_bn254_fp2_sub( rr, s2, s1 );
250 684 : fd_bn254_fp2_add( rr, rr, rr );
251 : /* V = U1*I */
252 684 : fd_bn254_fp2_mul( v, u1, i );
253 : /* X3 = r^2-J-2*V */
254 684 : fd_bn254_fp2_sqr( &r->X, rr );
255 684 : fd_bn254_fp2_sub( &r->X, &r->X, j );
256 684 : fd_bn254_fp2_sub( &r->X, &r->X, v );
257 684 : fd_bn254_fp2_sub( &r->X, &r->X, v );
258 : /* Y3 = r*(V-X3)-2*S1*J
259 : note: i no longer used */
260 684 : fd_bn254_fp2_mul( i, s1, j ); /* i = S1*J */
261 684 : fd_bn254_fp2_add( i, i, i ); /* i = 2*S1*J */
262 684 : fd_bn254_fp2_sub( &r->Y, v, &r->X );
263 684 : fd_bn254_fp2_mul( &r->Y, &r->Y, rr );
264 684 : fd_bn254_fp2_sub( &r->Y, &r->Y, i );
265 : /* Z3 = ((Z1+Z2)^2-Z1Z1-Z2Z2)*H */
266 684 : fd_bn254_fp2_add( &r->Z, &p->Z, &q->Z );
267 684 : fd_bn254_fp2_sqr( &r->Z, &r->Z );
268 684 : fd_bn254_fp2_sub( &r->Z, &r->Z, zz1 );
269 684 : fd_bn254_fp2_sub( &r->Z, &r->Z, zz2 );
270 684 : fd_bn254_fp2_mul( &r->Z, &r->Z, h );
271 684 : return r;
272 684 : }
273 :
274 : /* fd_bn254_g2_scalar_mul computes r = s * p.
275 : This assumes that p is affine, i.e. p->Z==1. */
276 : fd_bn254_g2_t *
277 : fd_bn254_g2_scalar_mul( fd_bn254_g2_t * r,
278 : fd_bn254_g2_t const * p,
279 342 : fd_bn254_scalar_t const * s ) {
280 : /* TODO: wNAF, GLV */
281 342 : int i = 255;
282 66348 : for( ; i>=0 && !fd_uint256_bit( s, i ); i-- ) ; /* do nothing, just i-- */
283 342 : if( FD_UNLIKELY( i<0 ) ) {
284 : /* COV: this only happens when the scalar is zero.
285 : Unlike g1, g2_scalar_mul is not exposed to users but only used internally,
286 : so scalar is never zero. */
287 0 : return fd_bn254_g2_set_zero( r );
288 0 : }
289 342 : fd_bn254_g2_set( r, p );
290 21546 : for( i--; i>=0; i-- ) {
291 21204 : fd_bn254_g2_dbl( r, r );
292 21204 : if( fd_uint256_bit( s, i ) ) {
293 9234 : fd_bn254_g2_add_mixed( r, r, p );
294 9234 : }
295 21204 : }
296 342 : return r;
297 342 : }
298 :
299 : /* fd_bn254_g2_frombytes_internal extracts (x, y) and performs basic checks.
300 : This is used by fd_bn254_g2_compress() and fd_bn254_g2_frombytes_check_subgroup(). */
301 : static inline fd_bn254_g2_t *
302 : fd_bn254_g2_frombytes_internal( fd_bn254_g2_t * p,
303 1863 : uchar const in[128] ) {
304 : /* Special case: all zeros => point at infinity */
305 1863 : const uchar zero[128] = { 0 };
306 1863 : if( FD_UNLIKELY( fd_memeq( in, zero, 128 ) ) ) {
307 6 : return fd_bn254_g2_set_zero( p );
308 6 : }
309 :
310 : /* Check x < p */
311 1857 : if( FD_UNLIKELY( !fd_bn254_fp2_frombytes_be_nm( &p->X, &in[0], NULL, NULL ) ) ) {
312 888 : return NULL;
313 888 : }
314 :
315 : /* Check flags and y < p */
316 969 : int is_inf, is_neg;
317 969 : if( FD_UNLIKELY( !fd_bn254_fp2_frombytes_be_nm( &p->Y, &in[64], &is_inf, &is_neg ) ) ) {
318 456 : return NULL;
319 456 : }
320 :
321 513 : if( FD_UNLIKELY( is_inf ) ) {
322 72 : return fd_bn254_g2_set_zero( p );
323 72 : }
324 :
325 441 : fd_bn254_fp2_set_one( &p->Z );
326 441 : return p;
327 513 : }
328 :
329 : /* fd_bn254_g2_frombytes_check_subgroup performs frombytes AND checks subgroup membership. */
330 : static inline fd_bn254_g2_t *
331 : fd_bn254_g2_frombytes_check_subgroup( fd_bn254_g2_t * p,
332 1077 : uchar const in[128] ) {
333 1077 : if( FD_UNLIKELY( !fd_bn254_g2_frombytes_internal( p, in ) ) ) {
334 672 : return NULL;
335 672 : }
336 405 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
337 39 : return p;
338 39 : }
339 :
340 366 : fd_bn254_fp2_to_mont( &p->X, &p->X );
341 366 : fd_bn254_fp2_to_mont( &p->Y, &p->Y );
342 366 : fd_bn254_fp2_set_one( &p->Z );
343 :
344 : /* Check that y^2 = x^3 + b */
345 366 : fd_bn254_fp2_t y2[1], x3b[1];
346 366 : fd_bn254_fp2_sqr( y2, &p->Y );
347 366 : fd_bn254_fp2_sqr( x3b, &p->X );
348 366 : fd_bn254_fp2_mul( x3b, x3b, &p->X );
349 366 : fd_bn254_fp2_add( x3b, x3b, fd_bn254_const_twist_b_mont );
350 366 : if( FD_UNLIKELY( !fd_bn254_fp2_eq( y2, x3b ) ) ) {
351 24 : return NULL;
352 24 : }
353 :
354 : /* G2 does NOT have prime order, so we have to check group membership. */
355 :
356 : /* We use the fast subgroup membership check, that requires a single 64-bit scalar mul.
357 : https://eprint.iacr.org/2022/348, Sec 3.1.
358 : [r]P == 0 <==> [x+1]P + ψ([x]P) + ψ²([x]P) = ψ³([2x]P)
359 : See also: https://github.com/Consensys/gnark-crypto/blob/v0.12.1/ecc/bn254/g2.go#L404
360 :
361 : For reference, the followings also work:
362 :
363 : 1) very slow: 256-bit scalar mul
364 :
365 : fd_bn254_g2_t r[1];
366 : fd_bn254_g2_scalar_mul( r, p, fd_bn254_const_r );
367 : if( !fd_bn254_g2_is_zero( r ) ) return NULL;
368 :
369 : 2) slow: 128-bit scalar mul
370 :
371 : fd_bn254_g2_t a[1], b[1];
372 : const fd_bn254_scalar_t six_x_sqr[1] = {{{ 0xf83e9682e87cfd46, 0x6f4d8248eeb859fb, 0x0, 0x0, }}};
373 : fd_bn254_g2_scalar_mul( a, p, six_x_sqr );
374 : fd_bn254_g2_frob( b, p );
375 : if( !fd_bn254_g2_eq( a, b ) ) return NULL; */
376 :
377 342 : fd_bn254_g2_t xp[1], l[1], psi[1], r[1];
378 342 : fd_bn254_g2_scalar_mul( xp, p, fd_bn254_const_x ); /* 64-bit */
379 342 : fd_bn254_g2_add_mixed( l, xp, p );
380 :
381 342 : fd_bn254_g2_frob( psi, xp );
382 342 : fd_bn254_g2_add( l, l, psi );
383 :
384 342 : fd_bn254_g2_frob2( psi, xp ); /* faster than frob( psi, psi ) */
385 342 : fd_bn254_g2_add( l, l, psi );
386 :
387 342 : fd_bn254_g2_frob( psi, psi );
388 342 : fd_bn254_g2_dbl( r, psi );
389 342 : if( FD_UNLIKELY( !fd_bn254_g2_eq( l, r ) ) ) {
390 24 : return NULL;
391 24 : }
392 :
393 318 : return p;
394 342 : }
|
