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