Line data Source code
1 : #include "./fd_bn254.h"
2 :
3 : /* G1 */
4 :
5 : static inline int
6 324921 : fd_bn254_g1_is_zero( fd_bn254_g1_t const * p ) {
7 324921 : return fd_bn254_fp_is_zero( &p->Z );
8 324921 : }
9 :
10 : static inline fd_bn254_g1_t *
11 : fd_bn254_g1_set( fd_bn254_g1_t * r,
12 3210 : fd_bn254_g1_t const * p ) {
13 3210 : fd_bn254_fp_set( &r->X, &p->X );
14 3210 : fd_bn254_fp_set( &r->Y, &p->Y );
15 3210 : fd_bn254_fp_set( &r->Z, &p->Z );
16 3210 : return r;
17 3210 : }
18 :
19 : static inline fd_bn254_g1_t *
20 51 : fd_bn254_g1_set_zero( fd_bn254_g1_t * r ) {
21 : // fd_bn254_fp_set_zero( &r->X );
22 : // fd_bn254_fp_set_zero( &r->Y );
23 51 : fd_bn254_fp_set_zero( &r->Z );
24 51 : return r;
25 51 : }
26 :
27 : static inline fd_bn254_g1_t *
28 : fd_bn254_g1_to_affine( fd_bn254_g1_t * r,
29 3162 : fd_bn254_g1_t const * p ) {
30 3162 : if( FD_UNLIKELY( fd_bn254_fp_is_zero( &p->Z ) || fd_bn254_fp_is_one( &p->Z ) ) ) {
31 60 : return fd_bn254_g1_set( r, p );
32 60 : }
33 :
34 3102 : fd_bn254_fp_t iz[1], iz2[1];
35 3102 : fd_bn254_fp_inv( iz, &p->Z );
36 3102 : fd_bn254_fp_sqr( iz2, iz );
37 :
38 : /* X / Z^2, Y / Z^3 */
39 3102 : fd_bn254_fp_mul( &r->X, &p->X, iz2 );
40 3102 : fd_bn254_fp_mul( &r->Y, &p->Y, iz2 );
41 3102 : fd_bn254_fp_mul( &r->Y, &r->Y, iz );
42 3102 : fd_bn254_fp_set_one( &r->Z );
43 3102 : return r;
44 3162 : }
45 :
46 : uchar *
47 : fd_bn254_g1_tobytes( uchar out[64],
48 : fd_bn254_g1_t const * p,
49 3180 : int big_endian ) {
50 3180 : if( FD_UNLIKELY( fd_bn254_g1_is_zero( p ) ) ) {
51 18 : fd_memset( out, 0, 64UL );
52 : /* no flags */
53 18 : return out;
54 18 : }
55 :
56 3162 : fd_bn254_g1_t r[1];
57 3162 : fd_bn254_g1_to_affine( r, p );
58 :
59 3162 : fd_bn254_fp_from_mont( &r->X, &r->X );
60 3162 : fd_bn254_fp_from_mont( &r->Y, &r->Y );
61 :
62 3162 : fd_bn254_fp_tobytes_nm( &out[ 0], &r->X, big_endian );
63 3162 : fd_bn254_fp_tobytes_nm( &out[32], &r->Y, big_endian );
64 : /* no flags */
65 3162 : return out;
66 3180 : }
67 :
68 : /* fd_bn254_g1_affine_add computes r = p + q.
69 : Both p, q are affine, i.e. Z==1. */
70 : fd_bn254_g1_t *
71 : fd_bn254_g1_affine_add( fd_bn254_g1_t * r,
72 : fd_bn254_g1_t const * p,
73 57 : fd_bn254_g1_t const * q ) {
74 : /* p==0, return q */
75 57 : if( FD_UNLIKELY( fd_bn254_g1_is_zero( p ) ) ) {
76 21 : return fd_bn254_g1_set( r, q );
77 21 : }
78 : /* q==0, return p */
79 36 : if( FD_UNLIKELY( fd_bn254_g1_is_zero( q ) ) ) {
80 9 : return fd_bn254_g1_set( r, p );
81 9 : }
82 :
83 27 : fd_bn254_fp_t lambda[1], x[1], y[1];
84 :
85 : /* same X, either the points are equal or opposite */
86 27 : if( fd_bn254_fp_eq( &p->X, &q->X ) ) {
87 6 : if( fd_bn254_fp_eq( &p->Y, &q->Y ) ) {
88 : /* p==q => point double: lambda = 3 * x1^2 / (2 * y1) */
89 6 : fd_bn254_fp_sqr( x, &p->X ); /* x = x1^2 */
90 6 : fd_bn254_fp_add( y, x, x ); /* y = 2 x1^2 */
91 6 : fd_bn254_fp_add( x, x, y ); /* x = 3 x1^2 */
92 6 : fd_bn254_fp_add( y, &p->Y, &p->Y );
93 6 : fd_bn254_fp_inv( lambda, y );
94 6 : fd_bn254_fp_mul( lambda, lambda, x );
95 6 : } else {
96 : /* p==-q => r=0 */
97 : /* COV: this may never happen with real data */
98 0 : return fd_bn254_g1_set_zero( r );
99 0 : }
100 21 : } else {
101 : /* point add: lambda = (y1 - y2) / (x1 - x2) */
102 21 : fd_bn254_fp_sub( x, &p->X, &q->X );
103 21 : fd_bn254_fp_sub( y, &p->Y, &q->Y );
104 21 : fd_bn254_fp_inv( lambda, x );
105 21 : fd_bn254_fp_mul( lambda, lambda, y );
106 21 : }
107 :
108 : /* x3 = lambda^2 - x1 - x2 */
109 27 : fd_bn254_fp_sqr( x, lambda );
110 27 : fd_bn254_fp_sub( x, x, &p->X );
111 27 : fd_bn254_fp_sub( x, x, &q->X );
112 :
113 : /* y3 = lambda * (x1 - x3) - y1 */
114 27 : fd_bn254_fp_sub( y, &p->X, x );
115 27 : fd_bn254_fp_mul( y, y, lambda );
116 27 : fd_bn254_fp_sub( y, y, &p->Y );
117 :
118 27 : fd_bn254_fp_set( &r->X, x );
119 27 : fd_bn254_fp_set( &r->Y, y );
120 27 : fd_bn254_fp_set_one( &r->Z );
121 27 : return r;
122 27 : }
123 :
124 : /* fd_bn254_g1_dbl computes r = 2p.
125 : https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l */
126 : fd_bn254_g1_t *
127 : fd_bn254_g1_dbl( fd_bn254_g1_t * r,
128 196968 : fd_bn254_g1_t const * p ) {
129 : /* p==0, return 0 */
130 196968 : if( FD_UNLIKELY( fd_bn254_g1_is_zero( p ) ) ) {
131 0 : return fd_bn254_g1_set_zero( r );
132 0 : }
133 :
134 196968 : fd_bn254_fp_t a[1], b[1], c[1];
135 196968 : fd_bn254_fp_t d[1], e[1], f[1];
136 :
137 : /* A = X1^2 */
138 196968 : fd_bn254_fp_sqr( a, &p->X );
139 : /* B = Y1^2 */
140 196968 : fd_bn254_fp_sqr( b, &p->Y );
141 : /* C = B^2 */
142 196968 : fd_bn254_fp_sqr( c, b );
143 : /* D = 2*((X1+B)^2-A-C)
144 : (X1+B)^2 = X1^2 + 2*X1*B + B^2
145 : D = 2*(X1^2 + 2*X1*B + B^2 - A - C)
146 : D = 2*(X1^2 + 2*X1*B + B^2 - X1^2 - B^2)
147 : ^ ^ ^ ^
148 : |---------------|-----| |
149 : |------------|
150 : These terms cancel each other out, and we're left with:
151 : D = 2*(2*X1*B) */
152 196968 : fd_bn254_fp_mul( d, &p->X, b );
153 196968 : fd_bn254_fp_add( d, d, d );
154 196968 : fd_bn254_fp_add( d, d, d );
155 : /* E = 3*A */
156 196968 : fd_bn254_fp_add( e, a, a );
157 196968 : fd_bn254_fp_add( e, a, e );
158 : /* F = E^2 */
159 196968 : fd_bn254_fp_sqr( f, e );
160 : /* X3 = F-2*D */
161 196968 : fd_bn254_fp_add( &r->X, d, d );
162 196968 : fd_bn254_fp_sub( &r->X, f, &r->X );
163 : /* Z3 = (Y1+Z1)^2-YY-ZZ
164 : note: compute Z3 before Y3 because it depends on p->Y,
165 : that might be overwritten if r==p. */
166 : /* Z3 = 2*Y1*Z1 */
167 196968 : fd_bn254_fp_mul( &r->Z, &p->Y, &p->Z );
168 196968 : fd_bn254_fp_add( &r->Z, &r->Z, &r->Z );
169 : /* Y3 = E*(D-X3)-8*C */
170 196968 : fd_bn254_fp_sub( &r->Y, d, &r->X );
171 196968 : fd_bn254_fp_mul( &r->Y, e, &r->Y );
172 196968 : fd_bn254_fp_add( c, c, c ); /* 2*c */
173 196968 : fd_bn254_fp_add( c, c, c ); /* 4*y */
174 196968 : fd_bn254_fp_add( c, c, c ); /* 8*y */
175 196968 : fd_bn254_fp_sub( &r->Y, &r->Y, c );
176 196968 : return r;
177 196968 : }
178 :
179 : /* fd_bn254_g1_add_mixed computes r = p + q, when q->Z==1.
180 : http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-madd-2007-bl */
181 : fd_bn254_g1_t *
182 : fd_bn254_g1_add_mixed( fd_bn254_g1_t * r,
183 : fd_bn254_g1_t const * p,
184 89595 : fd_bn254_g1_t const * q ) {
185 : /* p==0, return q */
186 89595 : if( FD_UNLIKELY( fd_bn254_g1_is_zero( p ) ) ) {
187 0 : return fd_bn254_g1_set( r, q );
188 0 : }
189 89595 : fd_bn254_fp_t zz[1], u2[1], s2[1];
190 89595 : fd_bn254_fp_t h[1], hh[1];
191 89595 : fd_bn254_fp_t i[1], j[1];
192 89595 : fd_bn254_fp_t rr[1], v[1];
193 : /* Z1Z1 = Z1^2 */
194 89595 : fd_bn254_fp_sqr( zz, &p->Z );
195 : /* U2 = X2*Z1Z1 */
196 89595 : fd_bn254_fp_mul( u2, &q->X, zz );
197 : /* S2 = Y2*Z1*Z1Z1 */
198 89595 : fd_bn254_fp_mul( s2, &q->Y, &p->Z );
199 89595 : fd_bn254_fp_mul( s2, s2, zz );
200 :
201 : /* if p==q, call fd_bn254_g1_dbl */
202 89595 : if( FD_UNLIKELY( fd_bn254_fp_eq( u2, &p->X ) && fd_bn254_fp_eq( s2, &p->Y ) ) ) {
203 : /* COV: this may never happen with real data */
204 0 : return fd_bn254_g1_dbl( r, p );
205 0 : }
206 :
207 : /* H = U2-X1 */
208 89595 : fd_bn254_fp_sub( h, u2, &p->X );
209 : /* HH = H^2 */
210 89595 : fd_bn254_fp_sqr( hh, h );
211 : /* I = 4*HH */
212 89595 : fd_bn254_fp_add( i, hh, hh );
213 89595 : fd_bn254_fp_add( i, i, i );
214 : /* J = H*I */
215 89595 : fd_bn254_fp_mul( j, h, i );
216 : /* r = 2*(S2-Y1) */
217 89595 : fd_bn254_fp_sub( rr, s2, &p->Y );
218 89595 : fd_bn254_fp_add( rr, rr, rr );
219 : /* V = X1*I */
220 89595 : fd_bn254_fp_mul( v, &p->X, i );
221 : /* X3 = r^2-J-2*V */
222 89595 : fd_bn254_fp_sqr( &r->X, rr );
223 89595 : fd_bn254_fp_sub( &r->X, &r->X, j );
224 89595 : fd_bn254_fp_sub( &r->X, &r->X, v );
225 89595 : fd_bn254_fp_sub( &r->X, &r->X, v );
226 : /* Y3 = r*(V-X3)-2*Y1*J
227 : note: i no longer used */
228 89595 : fd_bn254_fp_mul( i, &p->Y, j ); /* i = Y1*J */
229 89595 : fd_bn254_fp_add( i, i, i ); /* i = 2*Y1*J */
230 89595 : fd_bn254_fp_sub( &r->Y, v, &r->X );
231 89595 : fd_bn254_fp_mul( &r->Y, &r->Y, rr );
232 89595 : fd_bn254_fp_sub( &r->Y, &r->Y, i );
233 : /* Z3 = (Z1+H)^2-Z1Z1-HH */
234 89595 : fd_bn254_fp_add( &r->Z, &p->Z, h );
235 89595 : fd_bn254_fp_sqr( &r->Z, &r->Z );
236 89595 : fd_bn254_fp_sub( &r->Z, &r->Z, zz );
237 89595 : fd_bn254_fp_sub( &r->Z, &r->Z, hh );
238 89595 : return r;
239 89595 : }
240 :
241 : /* fd_bn254_g1_scalar_mul computes r = s * p.
242 : This assumes that p is affine, i.e. p->Z==1. */
243 : fd_bn254_g1_t *
244 : fd_bn254_g1_scalar_mul( fd_bn254_g1_t * r,
245 : fd_bn254_g1_t const * p,
246 3123 : fd_bn254_scalar_t const * s ) {
247 : /* TODO: wNAF, GLV */
248 3123 : int i = 255;
249 602523 : for( ; i>=0 && !fd_uint256_bit( s, i ); i-- ) ; /* do nothing, just i-- */
250 3123 : if( FD_UNLIKELY( i<0 ) ) {
251 3 : return fd_bn254_g1_set_zero( r );
252 3 : }
253 3120 : fd_bn254_g1_set( r, p );
254 200088 : for( i--; i>=0; i-- ) {
255 196968 : fd_bn254_g1_dbl( r, r );
256 196968 : if( fd_uint256_bit( s, i ) ) {
257 89595 : fd_bn254_g1_add_mixed( r, r, p );
258 89595 : }
259 196968 : }
260 3120 : return r;
261 3123 : }
262 :
263 : /* fd_bn254_g1_frombytes_internal extracts (x, y) and performs basic checks.
264 : This is used by fd_bn254_g1_compress() and fd_bn254_g1_frombytes_check_subgroup().
265 : https://github.com/arkworks-rs/algebra/blob/v0.4.2/ec/src/models/short_weierstrass/mod.rs#L173-L178 */
266 : static inline fd_bn254_g1_t *
267 : fd_bn254_g1_frombytes_internal( fd_bn254_g1_t * p,
268 : uchar const in[64],
269 34209 : int big_endian ) {
270 : /* Special case: all zeros => point at infinity */
271 34209 : const uchar zero[64] = { 0 };
272 34209 : if( FD_UNLIKELY( fd_memeq( in, zero, 64 ) ) ) {
273 48 : return fd_bn254_g1_set_zero( p );
274 48 : }
275 :
276 : /* Check x < p */
277 34161 : if( FD_UNLIKELY( !fd_bn254_fp_frombytes_nm( &p->X, &in[0], big_endian, NULL, NULL ) ) ) {
278 0 : return NULL;
279 0 : }
280 :
281 : /* Check flags and y < p */
282 34161 : int is_inf, is_neg;
283 34161 : if( FD_UNLIKELY( !fd_bn254_fp_frombytes_nm( &p->Y, &in[32], big_endian, &is_inf, &is_neg ) ) ) {
284 0 : return NULL;
285 0 : }
286 :
287 34161 : if( FD_UNLIKELY( is_inf ) ) {
288 0 : return fd_bn254_g1_set_zero( p );
289 0 : }
290 :
291 34161 : fd_bn254_fp_set_one( &p->Z );
292 34161 : return p;
293 34161 : }
294 :
295 : /* fd_bn254_g1_frombytes_check_subgroup performs frombytes AND checks subgroup membership. */
296 : static inline fd_bn254_g1_t *
297 : fd_bn254_g1_frombytes_check_subgroup( fd_bn254_g1_t * p,
298 : uchar const in[64],
299 4113 : int big_endian ) {
300 4113 : if( FD_UNLIKELY( !fd_bn254_g1_frombytes_internal( p, in, big_endian ) ) ) {
301 0 : return NULL;
302 0 : }
303 4113 : if( FD_UNLIKELY( fd_bn254_g1_is_zero( p ) ) ) {
304 45 : return p;
305 45 : }
306 :
307 4068 : fd_bn254_fp_to_mont( &p->X, &p->X );
308 4068 : fd_bn254_fp_to_mont( &p->Y, &p->Y );
309 4068 : fd_bn254_fp_set_one( &p->Z );
310 :
311 : /* Check that y^2 = x^3 + b */
312 4068 : fd_bn254_fp_t y2[1], x3b[1];
313 4068 : fd_bn254_fp_sqr( y2, &p->Y );
314 4068 : fd_bn254_fp_sqr( x3b, &p->X );
315 4068 : fd_bn254_fp_mul( x3b, x3b, &p->X );
316 4068 : fd_bn254_fp_add( x3b, x3b, fd_bn254_const_b_mont );
317 4068 : if( FD_UNLIKELY( !fd_bn254_fp_eq( y2, x3b ) ) ) {
318 0 : return NULL;
319 0 : }
320 :
321 : /* G1 has prime order, so we don't need to do any further checks. */
322 :
323 4068 : return p;
324 4068 : }
|
