Line data Source code
1 : #include "./fd_bn254_g2_inl.h"
2 : #include "./fd_bn254_glv.h"
3 :
4 : /* G2 scalar mul and deserialization. */
5 :
6 : /* fd_bn254_g2_scalar_mul computes r = [s]P.
7 : p must be in affine form (p->Z == 1).
8 : The result is in projective coordinates over Fp2. */
9 : fd_bn254_g2_t *
10 : fd_bn254_g2_scalar_mul( fd_bn254_g2_t * r,
11 : fd_bn254_g2_t const * p,
12 1536 : fd_bn254_scalar_t const * s ) {
13 1536 : if( FD_UNLIKELY( fd_uint256_is_zero( s ) || fd_bn254_g2_is_zero( p ) ) ) {
14 30 : return fd_bn254_g2_set_zero( r );
15 30 : }
16 :
17 1506 : const ulong g1_const[ 3 ] = { 0x7a7bd9d4391eb18eUL, 0x4ccef014a773d2cfUL, 0x0000000000000002UL };
18 1506 : ulong b1[ 3 ], b2[ 2 ];
19 1506 : fd_bn254_glv_sxg3( b1, s, g1_const );
20 1506 : fd_bn254_glv_sxg2( b2, s, g2_const );
21 :
22 : /* k1 = s - b1*N_C - b2*N_B (may be negative for G2) */
23 1506 : fd_uint256_t k1_abs[1];
24 1506 : int k1_neg = 0;
25 1506 : {
26 1506 : ulong p_nc[ 4 ];
27 : /* b2*nb will produce at most 3 limbs, so we want the 4th zeroed for the addition. */
28 1506 : ulong p_nb[ 4 ] = {0};
29 1506 : ulong t[ 4 ];
30 1506 : fd_bn254_glv_mul3x2( p_nc, b1, nc );
31 1506 : fd_bn254_glv_mul2x1( p_nb, b2, nb );
32 1506 : fd_bn254_glv_add4( t, p_nc, p_nb );
33 1506 : ulong borrow = fd_bn254_glv_sub4( k1_abs->limbs, s->limbs, t );
34 1506 : if( borrow ) {
35 0 : k1_neg = 1;
36 0 : fd_bn254_glv_negate4( k1_abs->limbs );
37 0 : }
38 1506 : }
39 :
40 : /* k2 = b2*N_A - b1*N_B (usually negative for G2) */
41 1506 : fd_uint256_t k2_abs[1];
42 1506 : int k2_neg = 0;
43 1506 : {
44 1506 : ulong pos[ 4 ], neg[ 4 ];
45 1506 : fd_bn254_glv_mul2x2( pos, b2, na );
46 1506 : fd_bn254_glv_mul3x1( neg, b1, nb );
47 1506 : ulong borrow = fd_bn254_glv_sub4( k2_abs->limbs, pos, neg );
48 1506 : if( borrow ) {
49 306 : k2_neg = 1;
50 306 : fd_bn254_glv_negate4( k2_abs->limbs );
51 306 : }
52 1506 : }
53 :
54 : /* pt1 = P, pt2 = phi(P) = (beta * P.x, P.y).
55 : If k1 < 0, negate pt1. If k2 < 0, negate pt2. */
56 1506 : fd_bn254_g2_t pt1[1], pt2[1];
57 1506 : fd_bn254_g2_set( pt1, p );
58 1506 : fd_bn254_fp_mul( &pt2->X.el[0], &p->X.el[0], fd_bn254_const_beta_mont );
59 1506 : fd_bn254_fp_mul( &pt2->X.el[1], &p->X.el[1], fd_bn254_const_beta_mont );
60 1506 : fd_bn254_fp2_set( &pt2->Y, &p->Y );
61 1506 : fd_bn254_fp2_set_one( &pt2->Z );
62 1506 : if( k1_neg ) {
63 0 : fd_bn254_fp2_neg( &pt1->Y, &pt1->Y );
64 0 : }
65 1506 : if( k2_neg ) {
66 306 : fd_bn254_fp2_neg( &pt2->Y, &pt2->Y );
67 306 : }
68 :
69 1506 : fd_bn254_g2_t pt12[1];
70 1506 : fd_bn254_g2_affine_add( pt12, pt1, pt2 );
71 :
72 : /* Shamir's trick: simultaneous double-and-add on k1, k2. */
73 1506 : int i = 255;
74 272952 : for( ; i>=0; i-- ) {
75 272952 : int k1b = !!fd_uint256_bit( k1_abs, i );
76 272952 : int k2b = !!fd_uint256_bit( k2_abs, i );
77 272952 : if( k1b || k2b ) {
78 1506 : fd_bn254_g2_set( r, ( k1b && k2b ) ? pt12 : ( k1b ? pt1 : pt2 ) );
79 1506 : break;
80 1506 : }
81 272952 : }
82 1506 : if( FD_UNLIKELY( i<0 ) ) {
83 0 : return fd_bn254_g2_set_zero( r );
84 0 : }
85 114090 : for( i--; i >= 0; i-- ) {
86 112584 : fd_bn254_g2_dbl( r, r );
87 112584 : int k1b = !!fd_uint256_bit( k1_abs, i );
88 112584 : int k2b = !!fd_uint256_bit( k2_abs, i );
89 112584 : if( k1b && k2b ) {
90 8874 : fd_bn254_g2_add_mixed( r, r, pt12 );
91 103710 : } else if( k1b ) {
92 41724 : fd_bn254_g2_add_mixed( r, r, pt1 );
93 61986 : } else if( k2b ) {
94 8262 : fd_bn254_g2_add_mixed( r, r, pt2 );
95 8262 : }
96 112584 : }
97 :
98 1506 : return r;
99 1506 : }
100 :
101 : /* fd_bn254_g2_frombytes_internal extracts (x, y) and performs basic checks.
102 : This is used by fd_bn254_g2_compress() and fd_bn254_g2_frombytes_check_subgroup(). */
103 : fd_bn254_g2_t *
104 : fd_bn254_g2_frombytes_internal( fd_bn254_g2_t * p,
105 : uchar const in[128],
106 91368 : int big_endian ) {
107 : /* Special case: all zeros => point at infinity */
108 91368 : const uchar zero[128] = { 0 };
109 91368 : if( FD_UNLIKELY( fd_memeq( in, zero, 128 ) ) ) {
110 39 : return fd_bn254_g2_set_zero( p );
111 39 : }
112 :
113 : /* Check x < p */
114 91329 : if( FD_UNLIKELY( !fd_bn254_fp2_frombytes_nm( &p->X, &in[0], big_endian, NULL, NULL ) ) ) {
115 0 : return NULL;
116 0 : }
117 :
118 : /* Check flags and y < p */
119 91329 : int is_inf, is_neg;
120 91329 : if( FD_UNLIKELY( !fd_bn254_fp2_frombytes_nm( &p->Y, &in[64], big_endian, &is_inf, &is_neg ) ) ) {
121 0 : return NULL;
122 0 : }
123 :
124 91329 : if( FD_UNLIKELY( is_inf ) ) {
125 6 : return fd_bn254_g2_set_zero( p );
126 6 : }
127 :
128 91323 : fd_bn254_fp2_set_one( &p->Z );
129 91323 : return p;
130 91329 : }
131 :
132 : /* fd_bn254_g2_frombytes_check_eq_only performs frombytes, checks the curve
133 : equation, but does NOT check subgroup membership. */
134 : fd_bn254_g2_t *
135 : fd_bn254_g2_frombytes_check_eq_only( fd_bn254_g2_t * p,
136 : uchar const in[128],
137 61266 : int big_endian ) {
138 61266 : if( FD_UNLIKELY( !fd_bn254_g2_frombytes_internal( p, in, big_endian ) ) ) {
139 0 : return NULL;
140 0 : }
141 61266 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
142 36 : return p;
143 36 : }
144 :
145 61230 : fd_bn254_fp2_to_mont( &p->X, &p->X );
146 61230 : fd_bn254_fp2_to_mont( &p->Y, &p->Y );
147 61230 : fd_bn254_fp2_set_one( &p->Z );
148 :
149 : /* Check that y^2 = x^3 + b */
150 61230 : fd_bn254_fp2_t y2[1], x3b[1];
151 61230 : fd_bn254_fp2_sqr( y2, &p->Y );
152 61230 : fd_bn254_fp2_sqr( x3b, &p->X );
153 61230 : fd_bn254_fp2_mul( x3b, x3b, &p->X );
154 61230 : fd_bn254_fp2_add( x3b, x3b, fd_bn254_const_twist_b_mont );
155 61230 : if( FD_UNLIKELY( !fd_bn254_fp2_eq( y2, x3b ) ) ) {
156 0 : return NULL;
157 0 : }
158 61230 : return p;
159 61230 : }
160 :
161 : /* fd_bn254_g2_frombytes_check_subgroup performs frombytes AND checks subgroup membership. */
162 : fd_bn254_g2_t *
163 : fd_bn254_g2_frombytes_check_subgroup( fd_bn254_g2_t * p,
164 : uchar const in[128],
165 1206 : int big_endian ) {
166 1206 : if( FD_UNLIKELY( fd_bn254_g2_frombytes_check_eq_only( p, in, big_endian )==NULL ) ) {
167 0 : return NULL;
168 0 : }
169 :
170 : /* G2 does NOT have prime order, so we have to check group membership. */
171 :
172 : /* We use the fast subgroup membership check, that requires a single 64-bit scalar mul.
173 : https://eprint.iacr.org/2022/348, Sec 3.1.
174 : [r]P == 0 <==> [x+1]P + ψ([x]P) + ψ²([x]P) = ψ³([2x]P)
175 : See also: https://github.com/Consensys/gnark-crypto/blob/v0.12.1/ecc/bn254/g2.go#L404
176 :
177 : For reference, the following also work:
178 :
179 : 1) very slow: 256-bit scalar mul
180 :
181 : fd_bn254_g2_t r[1];
182 : fd_bn254_g2_scalar_mul( r, p, fd_bn254_const_r );
183 : if( !fd_bn254_g2_is_zero( r ) ) return NULL;
184 :
185 : 2) slow: 128-bit scalar mul
186 :
187 : fd_bn254_g2_t a[1], b[1];
188 : const fd_bn254_scalar_t six_x_sqr[1] = {{{ 0xf83e9682e87cfd46, 0x6f4d8248eeb859fb, 0x0, 0x0, }}};
189 : fd_bn254_g2_scalar_mul( a, p, six_x_sqr );
190 : fd_bn254_g2_frob( b, p );
191 : if( !fd_bn254_g2_eq( a, b ) ) return NULL; */
192 :
193 1206 : fd_bn254_g2_t xp[1], l[1], psi[1], r[1];
194 1206 : fd_bn254_g2_scalar_mul( xp, p, fd_bn254_const_x ); /* 64-bit */
195 1206 : fd_bn254_g2_add_mixed( l, xp, p );
196 :
197 : /* l will not be equal to psi unless p==0 */
198 1206 : fd_bn254_g2_frob( psi, xp );
199 1206 : fd_bn254_g2_add( l, l, psi );
200 :
201 1206 : fd_bn254_g2_frob2( psi, xp ); /* faster than frob( psi, psi ) */
202 1206 : fd_bn254_g2_add( l, l, psi );
203 :
204 1206 : fd_bn254_g2_frob( psi, psi );
205 1206 : fd_bn254_g2_dbl( r, psi );
206 1206 : if( FD_UNLIKELY( !fd_bn254_g2_eq( l, r ) ) ) {
207 0 : return NULL;
208 0 : }
209 1206 : return p;
210 1206 : }
|
