Line data Source code
1 : #include "./fd_bn254_field_inl.h"
2 : #include "./fd_bn254_glv.h"
3 :
4 : /* G1 */
5 :
6 : /* GLV consts (fd_bn254_glv.h), shared with fd_bn254_g2.c; the lattice
7 : constants are in fd_bn254_field.c. */
8 :
9 : /* beta in Montgomery form.
10 : 0x30644e72e131a0295e6dd9e7e0acccb0c28f069fbb966e3de4bd44e5607cfd48 */
11 : const fd_bn254_fp_t fd_bn254_const_beta_mont[1] = {{{
12 : 0x3350c88e13e80b9cUL, 0x7dce557cdb5e56b9UL, 0x6001b4b8b615564aUL, 0x2682e617020217e0UL
13 : }}};
14 :
15 : static inline fd_bn254_g1_t *
16 : fd_bn254_g1_set( fd_bn254_g1_t * r,
17 385 : fd_bn254_g1_t const * p ) {
18 385 : fd_bn254_fp_set( &r->X, &p->X );
19 385 : fd_bn254_fp_set( &r->Y, &p->Y );
20 385 : fd_bn254_fp_set( &r->Z, &p->Z );
21 385 : return r;
22 385 : }
23 :
24 : static inline fd_bn254_g1_t *
25 480 : fd_bn254_g1_set_zero( fd_bn254_g1_t * r ) {
26 : // fd_bn254_fp_set_zero( &r->X );
27 : // fd_bn254_fp_set_zero( &r->Y );
28 480 : fd_bn254_fp_set_zero( &r->Z );
29 480 : return r;
30 480 : }
31 :
32 : static inline fd_bn254_g1_t *
33 : fd_bn254_g1_to_affine( fd_bn254_g1_t * r,
34 315 : fd_bn254_g1_t const * p ) {
35 315 : if( FD_UNLIKELY( fd_bn254_fp_is_zero( &p->Z ) || fd_bn254_fp_is_one( &p->Z ) ) ) {
36 84 : return fd_bn254_g1_set( r, p );
37 84 : }
38 :
39 231 : fd_bn254_fp_t iz[1], iz2[1];
40 231 : fd_bn254_fp_inv( iz, &p->Z );
41 231 : fd_bn254_fp_sqr( iz2, iz );
42 :
43 : /* X / Z^2, Y / Z^3 */
44 231 : fd_bn254_fp_mul( &r->X, &p->X, iz2 );
45 231 : fd_bn254_fp_mul( &r->Y, &p->Y, iz2 );
46 231 : fd_bn254_fp_mul( &r->Y, &r->Y, iz );
47 231 : fd_bn254_fp_set_one( &r->Z );
48 231 : return r;
49 315 : }
50 :
51 : uchar *
52 : fd_bn254_g1_tobytes( uchar out[64],
53 : fd_bn254_g1_t const * p,
54 571 : int big_endian ) {
55 571 : if( FD_UNLIKELY( fd_bn254_g1_is_zero( p ) ) ) {
56 256 : fd_memset( out, 0, 64UL );
57 : /* no flags */
58 256 : return out;
59 256 : }
60 :
61 315 : fd_bn254_g1_t r[1];
62 315 : fd_bn254_g1_to_affine( r, p );
63 :
64 315 : fd_bn254_fp_from_mont( &r->X, &r->X );
65 315 : fd_bn254_fp_from_mont( &r->Y, &r->Y );
66 :
67 315 : fd_bn254_fp_tobytes_nm( &out[ 0], &r->X, big_endian );
68 315 : fd_bn254_fp_tobytes_nm( &out[32], &r->Y, big_endian );
69 : /* no flags */
70 315 : return out;
71 571 : }
72 :
73 : /* fd_bn254_g1_affine_add computes r = p + q.
74 : Both p, q are affine, i.e. Z==1. */
75 : fd_bn254_g1_t *
76 : fd_bn254_g1_affine_add( fd_bn254_g1_t * r,
77 : fd_bn254_g1_t const * p,
78 349 : fd_bn254_g1_t const * q ) {
79 : /* p==0, return q */
80 349 : if( FD_UNLIKELY( fd_bn254_g1_is_zero( p ) ) ) {
81 6 : return fd_bn254_g1_set( r, q );
82 6 : }
83 : /* q==0, return p */
84 343 : if( FD_UNLIKELY( fd_bn254_g1_is_zero( q ) ) ) {
85 3 : return fd_bn254_g1_set( r, p );
86 3 : }
87 :
88 340 : fd_bn254_fp_t lambda[1], x[1], y[1];
89 :
90 : /* same X, either the points are equal or opposite */
91 340 : if( fd_bn254_fp_eq( &p->X, &q->X ) ) {
92 1 : if( fd_bn254_fp_eq( &p->Y, &q->Y ) ) {
93 : /* p==q => point double: lambda = 3 * x1^2 / (2 * y1) */
94 1 : fd_bn254_fp_sqr( x, &p->X ); /* x = x1^2 */
95 1 : fd_bn254_fp_add( y, x, x ); /* y = 2 x1^2 */
96 1 : fd_bn254_fp_add( x, x, y ); /* x = 3 x1^2 */
97 1 : fd_bn254_fp_add( y, &p->Y, &p->Y );
98 1 : fd_bn254_fp_inv( lambda, y );
99 1 : fd_bn254_fp_mul( lambda, lambda, x );
100 1 : } else {
101 : /* p==-q => r=0 */
102 : /* COV: this may never happen with real data */
103 0 : return fd_bn254_g1_set_zero( r );
104 0 : }
105 339 : } else {
106 : /* point add: lambda = (y1 - y2) / (x1 - x2) */
107 339 : fd_bn254_fp_sub( x, &p->X, &q->X );
108 339 : fd_bn254_fp_sub( y, &p->Y, &q->Y );
109 339 : fd_bn254_fp_inv( lambda, x );
110 339 : fd_bn254_fp_mul( lambda, lambda, y );
111 339 : }
112 :
113 : /* x3 = lambda^2 - x1 - x2 */
114 340 : fd_bn254_fp_sqr( x, lambda );
115 340 : fd_bn254_fp_sub( x, x, &p->X );
116 340 : fd_bn254_fp_sub( x, x, &q->X );
117 :
118 : /* y3 = lambda * (x1 - x3) - y1 */
119 340 : fd_bn254_fp_sub( y, &p->X, x );
120 340 : fd_bn254_fp_mul( y, y, lambda );
121 340 : fd_bn254_fp_sub( y, y, &p->Y );
122 :
123 340 : fd_bn254_fp_set( &r->X, x );
124 340 : fd_bn254_fp_set( &r->Y, y );
125 340 : fd_bn254_fp_set_one( &r->Z );
126 340 : return r;
127 340 : }
128 :
129 : /* fd_bn254_g1_dbl computes r = 2p.
130 : https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l */
131 : fd_bn254_g1_t *
132 : fd_bn254_g1_dbl( fd_bn254_g1_t * r,
133 30288 : fd_bn254_g1_t const * p ) {
134 : /* p==0, return 0 */
135 30288 : if( FD_UNLIKELY( fd_bn254_g1_is_zero( p ) ) ) {
136 0 : return fd_bn254_g1_set_zero( r );
137 0 : }
138 :
139 30288 : fd_bn254_fp_t a[1], b[1], c[1];
140 30288 : fd_bn254_fp_t d[1], e[1], f[1];
141 :
142 : /* A = X1^2 */
143 30288 : fd_bn254_fp_sqr( a, &p->X );
144 : /* B = Y1^2 */
145 30288 : fd_bn254_fp_sqr( b, &p->Y );
146 : /* C = B^2 */
147 30288 : fd_bn254_fp_sqr( c, b );
148 : /* D = 2*((X1+B)^2-A-C)
149 : (X1+B)^2 = X1^2 + 2*X1*B + B^2
150 : D = 2*(X1^2 + 2*X1*B + B^2 - A - C)
151 : D = 2*(X1^2 + 2*X1*B + B^2 - X1^2 - B^2)
152 : ^ ^ ^ ^
153 : |---------------|-----| |
154 : |------------|
155 : These terms cancel each other out, and we're left with:
156 : D = 2*(2*X1*B) */
157 30288 : fd_bn254_fp_mul( d, &p->X, b );
158 30288 : fd_bn254_fp_add( d, d, d );
159 30288 : fd_bn254_fp_add( d, d, d );
160 : /* E = 3*A */
161 30288 : fd_bn254_fp_add( e, a, a );
162 30288 : fd_bn254_fp_add( e, a, e );
163 : /* F = E^2 */
164 30288 : fd_bn254_fp_sqr( f, e );
165 : /* X3 = F-2*D */
166 30288 : fd_bn254_fp_add( &r->X, d, d );
167 30288 : fd_bn254_fp_sub( &r->X, f, &r->X );
168 : /* Z3 = (Y1+Z1)^2-YY-ZZ
169 : note: compute Z3 before Y3 because it depends on p->Y,
170 : that might be overwritten if r==p. */
171 : /* Z3 = 2*Y1*Z1 */
172 30288 : fd_bn254_fp_mul( &r->Z, &p->Y, &p->Z );
173 30288 : fd_bn254_fp_add( &r->Z, &r->Z, &r->Z );
174 : /* Y3 = E*(D-X3)-8*C */
175 30288 : fd_bn254_fp_sub( &r->Y, d, &r->X );
176 30288 : fd_bn254_fp_mul( &r->Y, e, &r->Y );
177 30288 : fd_bn254_fp_add( c, c, c ); /* 2*c */
178 30288 : fd_bn254_fp_add( c, c, c ); /* 4*y */
179 30288 : fd_bn254_fp_add( c, c, c ); /* 8*y */
180 30288 : fd_bn254_fp_sub( &r->Y, &r->Y, c );
181 30288 : return r;
182 30288 : }
183 :
184 : /* fd_bn254_g1_add_mixed computes r = p + q, when q->Z==1.
185 : http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-madd-2007-bl */
186 : fd_bn254_g1_t *
187 : fd_bn254_g1_add_mixed( fd_bn254_g1_t * r,
188 : fd_bn254_g1_t const * p,
189 20695 : fd_bn254_g1_t const * q ) {
190 : /* p==0, return q */
191 20695 : if( FD_UNLIKELY( fd_bn254_g1_is_zero( p ) ) ) {
192 0 : return fd_bn254_g1_set( r, q );
193 0 : }
194 20695 : fd_bn254_fp_t zz[1], u2[1], s2[1];
195 20695 : fd_bn254_fp_t h[1], hh[1];
196 20695 : fd_bn254_fp_t i[1], j[1];
197 20695 : fd_bn254_fp_t rr[1], v[1];
198 : /* Z1Z1 = Z1^2 */
199 20695 : fd_bn254_fp_sqr( zz, &p->Z );
200 : /* U2 = X2*Z1Z1 */
201 20695 : fd_bn254_fp_mul( u2, &q->X, zz );
202 : /* S2 = Y2*Z1*Z1Z1 */
203 20695 : fd_bn254_fp_mul( s2, &q->Y, &p->Z );
204 20695 : fd_bn254_fp_mul( s2, s2, zz );
205 :
206 : /* if p==q, call fd_bn254_g1_dbl */
207 20695 : if( FD_UNLIKELY( fd_bn254_fp_eq( u2, &p->X ) && fd_bn254_fp_eq( s2, &p->Y ) ) ) {
208 : /* COV: this may never happen with real data */
209 0 : return fd_bn254_g1_dbl( r, p );
210 0 : }
211 :
212 : /* H = U2-X1 */
213 20695 : fd_bn254_fp_sub( h, u2, &p->X );
214 : /* HH = H^2 */
215 20695 : fd_bn254_fp_sqr( hh, h );
216 : /* I = 4*HH */
217 20695 : fd_bn254_fp_add( i, hh, hh );
218 20695 : fd_bn254_fp_add( i, i, i );
219 : /* J = H*I */
220 20695 : fd_bn254_fp_mul( j, h, i );
221 : /* r = 2*(S2-Y1) */
222 20695 : fd_bn254_fp_sub( rr, s2, &p->Y );
223 20695 : fd_bn254_fp_add( rr, rr, rr );
224 : /* V = X1*I */
225 20695 : fd_bn254_fp_mul( v, &p->X, i );
226 : /* X3 = r^2-J-2*V */
227 20695 : fd_bn254_fp_sqr( &r->X, rr );
228 20695 : fd_bn254_fp_sub( &r->X, &r->X, j );
229 20695 : fd_bn254_fp_sub( &r->X, &r->X, v );
230 20695 : fd_bn254_fp_sub( &r->X, &r->X, v );
231 : /* Y3 = r*(V-X3)-2*Y1*J
232 : note: i no longer used */
233 20695 : fd_bn254_fp_mul( i, &p->Y, j ); /* i = Y1*J */
234 20695 : fd_bn254_fp_add( i, i, i ); /* i = 2*Y1*J */
235 20695 : fd_bn254_fp_sub( &r->Y, v, &r->X );
236 20695 : fd_bn254_fp_mul( &r->Y, &r->Y, rr );
237 20695 : fd_bn254_fp_sub( &r->Y, &r->Y, i );
238 : /* Z3 = (Z1+H)^2-Z1Z1-HH */
239 20695 : fd_bn254_fp_add( &r->Z, &p->Z, h );
240 20695 : fd_bn254_fp_sqr( &r->Z, &r->Z );
241 20695 : fd_bn254_fp_sub( &r->Z, &r->Z, zz );
242 20695 : fd_bn254_fp_sub( &r->Z, &r->Z, hh );
243 20695 : return r;
244 20695 : }
245 :
246 : /* fd_bn254_g1_scalar_mul computes r = [s]P.
247 : p must be in affine form (p->Z == 1).
248 : The result is in projective coordinates. */
249 : fd_bn254_g1_t *
250 : fd_bn254_g1_scalar_mul( fd_bn254_g1_t * r,
251 : fd_bn254_g1_t const * p,
252 513 : fd_bn254_scalar_t const * s ) {
253 513 : if( FD_UNLIKELY( fd_uint256_is_zero( s ) || fd_bn254_g1_is_zero( p ) ) ) {
254 222 : return fd_bn254_g1_set_zero( r );
255 222 : }
256 291 : ulong b1[ 3 ];
257 291 : ulong b2[ 2 ];
258 291 : fd_bn254_glv_sxg3( b1, s, g1_const_g1 );
259 291 : fd_bn254_glv_sxg2( b2, s, g2_const );
260 :
261 : /* k1 = s - b1*N_A - b2*N_B (always non-negative for G1) */
262 291 : fd_uint256_t k1[1];
263 291 : {
264 291 : ulong p11[ 4 ];
265 : /* b2*nb will produce at most 3 limbs, but we want the 4th zeroed for the addition. */
266 291 : ulong p21[ 4 ] = {0};
267 291 : ulong t[ 4 ];
268 291 : fd_bn254_glv_mul3x2( p11, b1, na );
269 291 : fd_bn254_glv_mul2x1( p21, b2, nb );
270 291 : fd_bn254_glv_add4( t, p11, p21 );
271 291 : fd_bn254_glv_sub4( k1->limbs, s->limbs, t );
272 291 : }
273 :
274 : /* k2 = b1*N_B - b2*N_C (may be negative) */
275 291 : fd_uint256_t k2_abs[1];
276 291 : int k2_neg = 0;
277 291 : {
278 291 : ulong pos[ 4 ], neg[ 4 ];
279 291 : fd_bn254_glv_mul3x1( pos, b1, nb );
280 291 : fd_bn254_glv_mul2x2( neg, b2, nc );
281 291 : ulong borrow = fd_bn254_glv_sub4( k2_abs->limbs, pos, neg );
282 291 : if( borrow ) {
283 0 : k2_neg = 1;
284 0 : fd_bn254_glv_negate4( k2_abs->limbs );
285 0 : }
286 291 : }
287 :
288 : /* pt2 = phi(P) = (beta * P.x, P.y). If k2 < 0, negate pt2. */
289 291 : fd_bn254_g1_t pt2[1];
290 291 : fd_bn254_fp_mul ( &pt2->X, &p->X, fd_bn254_const_beta_mont );
291 291 : fd_bn254_fp_set ( &pt2->Y, &p->Y );
292 291 : fd_bn254_fp_set_one( &pt2->Z );
293 291 : if( k2_neg ) {
294 0 : fd_bn254_fp_neg( &pt2->Y, &pt2->Y );
295 0 : }
296 :
297 291 : fd_bn254_g1_t pt12[1];
298 291 : fd_bn254_g1_affine_add( pt12, p, pt2 );
299 :
300 : /* Shamir's trick: simultaneous double-and-add on k1, k2. */
301 291 : int i = 255;
302 42276 : for( ; i>=0; i-- ) {
303 42276 : int k1b = !!fd_uint256_bit( k1, i );
304 42276 : int k2b = !!fd_uint256_bit( k2_abs, i );
305 42276 : if( k1b || k2b ) {
306 292 : fd_bn254_g1_set( r, ( k1b && k2b ) ? pt12 : ( k1b ? p : pt2 ) );
307 292 : break;
308 292 : }
309 42276 : }
310 291 : if( FD_UNLIKELY( i<0 ) ) {
311 0 : return fd_bn254_g1_set_zero( r );
312 0 : }
313 30580 : for( i--; i >= 0; i-- ) {
314 30289 : fd_bn254_g1_dbl( r, r );
315 30289 : int k1b = !!fd_uint256_bit( k1, i );
316 30289 : int k2b = !!fd_uint256_bit( k2_abs, i );
317 30289 : if( k1b && k2b ) {
318 9192 : fd_bn254_g1_add_mixed( r, r, pt12 );
319 21097 : } else if( k1b ) {
320 5945 : fd_bn254_g1_add_mixed( r, r, p );
321 15152 : } else if( k2b ) {
322 6155 : fd_bn254_g1_add_mixed( r, r, pt2 );
323 6155 : }
324 30289 : }
325 :
326 291 : return r;
327 291 : }
328 :
329 : /* fd_bn254_g1_frombytes_internal extracts (x, y) and performs basic checks.
330 : This is used by fd_bn254_g1_compress() and fd_bn254_g1_frombytes_check_subgroup().
331 : https://github.com/arkworks-rs/algebra/blob/v0.4.2/ec/src/models/short_weierstrass/mod.rs#L173-L178 */
332 : fd_bn254_g1_t *
333 : fd_bn254_g1_frombytes_internal( fd_bn254_g1_t * p,
334 : uchar const in[64],
335 3126 : int big_endian ) {
336 : /* Special case: all zeros => point at infinity */
337 3126 : const uchar zero[64] = { 0 };
338 3126 : if( FD_UNLIKELY( fd_memeq( in, zero, 64 ) ) ) {
339 36 : return fd_bn254_g1_set_zero( p );
340 36 : }
341 :
342 : /* Check x < p */
343 3090 : if( FD_UNLIKELY( !fd_bn254_fp_frombytes_nm( &p->X, &in[0], big_endian, NULL, NULL ) ) ) {
344 1221 : return NULL;
345 1221 : }
346 :
347 : /* Check flags and y < p */
348 1869 : int is_inf, is_neg;
349 1869 : if( FD_UNLIKELY( !fd_bn254_fp_frombytes_nm( &p->Y, &in[32], big_endian, &is_inf, &is_neg ) ) ) {
350 367 : return NULL;
351 367 : }
352 :
353 1502 : if( FD_UNLIKELY( is_inf ) ) {
354 222 : return fd_bn254_g1_set_zero( p );
355 222 : }
356 :
357 1280 : fd_bn254_fp_set_one( &p->Z );
358 1280 : return p;
359 1502 : }
360 :
361 : /* fd_bn254_g1_frombytes_check_subgroup performs frombytes AND checks subgroup membership. */
362 : fd_bn254_g1_t *
363 : fd_bn254_g1_frombytes_check_subgroup( fd_bn254_g1_t * p,
364 : uchar const in[64],
365 2864 : int big_endian ) {
366 2864 : if( FD_UNLIKELY( !fd_bn254_g1_frombytes_internal( p, in, big_endian ) ) ) {
367 1425 : return NULL;
368 1425 : }
369 1439 : if( FD_UNLIKELY( fd_bn254_g1_is_zero( p ) ) ) {
370 235 : return p;
371 235 : }
372 :
373 1204 : fd_bn254_fp_to_mont( &p->X, &p->X );
374 1204 : fd_bn254_fp_to_mont( &p->Y, &p->Y );
375 1204 : fd_bn254_fp_set_one( &p->Z );
376 :
377 : /* Check that y^2 = x^3 + b */
378 1204 : fd_bn254_fp_t y2[1], x3b[1];
379 1204 : fd_bn254_fp_sqr( y2, &p->Y );
380 1204 : fd_bn254_fp_sqr( x3b, &p->X );
381 1204 : fd_bn254_fp_mul( x3b, x3b, &p->X );
382 1204 : fd_bn254_fp_add( x3b, x3b, fd_bn254_const_b_mont );
383 1204 : if( FD_UNLIKELY( !fd_bn254_fp_eq( y2, x3b ) ) ) {
384 123 : return NULL;
385 123 : }
386 :
387 : /* G1 has prime order, so we don't need to do any further checks. */
388 :
389 1081 : return p;
390 1204 : }
|
