Line data Source code
1 : #include "./fd_bn254_g2_inl.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 fd_bn254_g2_t *
9 : fd_bn254_g2_to_affine( fd_bn254_g2_t * r,
10 30336 : fd_bn254_g2_t const * p ) {
11 30336 : if( FD_UNLIKELY( fd_bn254_fp2_is_zero( &p->Z ) || fd_bn254_fp2_is_one( &p->Z ) ) ) {
12 30030 : return fd_bn254_g2_set( r, p );
13 30030 : }
14 :
15 306 : fd_bn254_fp2_t iz[1], iz2[1];
16 306 : fd_bn254_fp2_inv( iz, &p->Z );
17 306 : fd_bn254_fp2_sqr( iz2, iz );
18 :
19 : /* X / Z^2, Y / Z^3 */
20 306 : fd_bn254_fp2_mul( &r->X, &p->X, iz2 );
21 306 : fd_bn254_fp2_mul( &r->Y, &p->Y, iz2 );
22 306 : fd_bn254_fp2_mul( &r->Y, &r->Y, iz );
23 306 : fd_bn254_fp2_set_one( &r->Z );
24 306 : return r;
25 30336 : }
26 :
27 : uchar *
28 : fd_bn254_g2_tobytes( uchar out[128],
29 : fd_bn254_g2_t const * p,
30 30360 : int big_endian ) {
31 30360 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
32 24 : fd_memset( out, 0, 128UL );
33 : /* no flags */
34 24 : return out;
35 24 : }
36 :
37 30336 : fd_bn254_g2_t r[1];
38 30336 : fd_bn254_g2_to_affine( r, p );
39 :
40 30336 : fd_bn254_fp2_from_mont( &r->X, &r->X );
41 30336 : fd_bn254_fp2_from_mont( &r->Y, &r->Y );
42 :
43 30336 : fd_bn254_fp2_tobytes_nm( &out[ 0], &r->X, big_endian );
44 30336 : fd_bn254_fp2_tobytes_nm( &out[64], &r->Y, big_endian );
45 : /* no flags */
46 30336 : return out;
47 30360 : }
48 :
49 : /* fd_bn254_g2_dbl computes r = 2p.
50 : https://hyperelliptic.org/efd/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l */
51 : fd_bn254_g2_t *
52 : fd_bn254_g2_dbl( fd_bn254_g2_t * r,
53 113790 : fd_bn254_g2_t const * p ) {
54 : /* p==0, return 0 */
55 113790 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
56 12 : return fd_bn254_g2_set_zero( r );
57 12 : }
58 :
59 113778 : fd_bn254_fp2_t a[1], b[1], c[1];
60 113778 : fd_bn254_fp2_t d[1], e[1], f[1];
61 :
62 : /* A = X1^2 */
63 113778 : fd_bn254_fp2_sqr( a, &p->X );
64 : /* B = Y1^2 */
65 113778 : fd_bn254_fp2_sqr( b, &p->Y );
66 : /* C = B^2 */
67 113778 : fd_bn254_fp2_sqr( c, b );
68 : /* D = 2*((X1+B)^2-A-C)
69 : (X1+B)^2 = X1^2 + 2*X1*B + B^2
70 : D = 2*(X1^2 + 2*X1*B + B^2 - A - C)
71 : D = 2*(X1^2 + 2*X1*B + B^2 - X1^2 - B^2)
72 : ^ ^ ^ ^
73 : |---------------|-----| |
74 : |------------|
75 : These terms cancel each other out, and we're left with:
76 : D = 2*(2*X1*B) */
77 113778 : fd_bn254_fp2_mul( d, &p->X, b );
78 113778 : fd_bn254_fp2_add( d, d, d );
79 113778 : fd_bn254_fp2_add( d, d, d );
80 : /* E = 3*A */
81 113778 : fd_bn254_fp2_add( e, a, a );
82 113778 : fd_bn254_fp2_add( e, a, e );
83 : /* F = E^2 */
84 113778 : fd_bn254_fp2_sqr( f, e );
85 : /* X3 = F-2*D */
86 113778 : fd_bn254_fp2_add( &r->X, d, d );
87 113778 : fd_bn254_fp2_sub( &r->X, f, &r->X );
88 : /* Z3 = (Y1+Z1)^2-YY-ZZ
89 : note: compute Z3 before Y3 because it depends on p->Y,
90 : that might be overwritten if r==p. */
91 : /* Z3 = 2*Y1*Z1 */
92 113778 : fd_bn254_fp2_mul( &r->Z, &p->Y, &p->Z );
93 113778 : fd_bn254_fp2_add( &r->Z, &r->Z, &r->Z );
94 : /* Y3 = E*(D-X3)-8*C */
95 113778 : fd_bn254_fp2_sub( &r->Y, d, &r->X );
96 113778 : fd_bn254_fp2_mul( &r->Y, e, &r->Y );
97 113778 : fd_bn254_fp2_add( c, c, c ); /* 2*c */
98 113778 : fd_bn254_fp2_add( c, c, c ); /* 4*y */
99 113778 : fd_bn254_fp2_add( c, c, c ); /* 8*y */
100 113778 : fd_bn254_fp2_sub( &r->Y, &r->Y, c );
101 113778 : return r;
102 113790 : }
103 :
104 : /* fd_bn254_g2_add_mixed computes r = p + q, when q->Z==1.
105 : http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-madd-2007-bl */
106 : fd_bn254_g2_t *
107 : fd_bn254_g2_add_mixed( fd_bn254_g2_t * r,
108 : fd_bn254_g2_t const * p,
109 60066 : fd_bn254_g2_t const * q ) {
110 : /* p==0, return q */
111 60066 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
112 12 : return fd_bn254_g2_set( r, q );
113 12 : }
114 : /* q==0, return p */
115 60054 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( q ) ) ) {
116 0 : return fd_bn254_g2_set( r, p );
117 0 : }
118 60054 : fd_bn254_fp2_t zz[1], u2[1], s2[1];
119 60054 : fd_bn254_fp2_t h[1], hh[1];
120 60054 : fd_bn254_fp2_t i[1], j[1];
121 60054 : fd_bn254_fp2_t rr[1], v[1];
122 : /* Z1Z1 = Z1^2 */
123 60054 : fd_bn254_fp2_sqr( zz, &p->Z );
124 : /* U2 = X2*Z1Z1 */
125 60054 : fd_bn254_fp2_mul( u2, &q->X, zz );
126 : /* S2 = Y2*Z1*Z1Z1 */
127 60054 : fd_bn254_fp2_mul( s2, &q->Y, &p->Z );
128 60054 : fd_bn254_fp2_mul( s2, s2, zz );
129 :
130 : /* if p==q, call fd_bn254_g2_dbl */
131 60054 : if( FD_UNLIKELY( fd_bn254_fp2_eq( u2, &p->X ) && fd_bn254_fp2_eq( s2, &p->Y ) ) ) {
132 0 : return fd_bn254_g2_dbl( r, p );
133 0 : }
134 :
135 : /* H = U2-X1 */
136 60054 : fd_bn254_fp2_sub( h, u2, &p->X );
137 : /* HH = H^2 */
138 60054 : fd_bn254_fp2_sqr( hh, h );
139 : /* I = 4*HH */
140 60054 : fd_bn254_fp2_add( i, hh, hh );
141 60054 : fd_bn254_fp2_add( i, i, i );
142 : /* J = H*I */
143 60054 : fd_bn254_fp2_mul( j, h, i );
144 : /* r = 2*(S2-Y1) */
145 60054 : fd_bn254_fp2_sub( rr, s2, &p->Y );
146 60054 : fd_bn254_fp2_add( rr, rr, rr );
147 : /* V = X1*I */
148 60054 : fd_bn254_fp2_mul( v, &p->X, i );
149 : /* X3 = r^2-J-2*V */
150 60054 : fd_bn254_fp2_sqr( &r->X, rr );
151 60054 : fd_bn254_fp2_sub( &r->X, &r->X, j );
152 60054 : fd_bn254_fp2_sub( &r->X, &r->X, v );
153 60054 : fd_bn254_fp2_sub( &r->X, &r->X, v );
154 : /* Y3 = r*(V-X3)-2*Y1*J
155 : note: i no longer used */
156 60054 : fd_bn254_fp2_mul( i, &p->Y, j ); /* i = Y1*J */
157 60054 : fd_bn254_fp2_add( i, i, i ); /* i = 2*Y1*J */
158 60054 : fd_bn254_fp2_sub( &r->Y, v, &r->X );
159 60054 : fd_bn254_fp2_mul( &r->Y, &r->Y, rr );
160 60054 : fd_bn254_fp2_sub( &r->Y, &r->Y, i );
161 : /* Z3 = (Z1+H)^2-Z1Z1-HH */
162 60054 : fd_bn254_fp2_add( &r->Z, &p->Z, h );
163 60054 : fd_bn254_fp2_sqr( &r->Z, &r->Z );
164 60054 : fd_bn254_fp2_sub( &r->Z, &r->Z, zz );
165 60054 : fd_bn254_fp2_sub( &r->Z, &r->Z, hh );
166 60054 : return r;
167 60054 : }
168 :
169 : /* fd_bn254_g2_add computes r = p + q.
170 : p MUST not be equal to q, unless p==0.
171 : http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-add-2007-bl */
172 : fd_bn254_g2_t *
173 : fd_bn254_g2_add( fd_bn254_g2_t * r,
174 : fd_bn254_g2_t const * p,
175 2412 : fd_bn254_g2_t const * q ) {
176 : /* p==0, return q */
177 2412 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
178 24 : return fd_bn254_g2_set( r, q );
179 24 : }
180 : /* q==0, return p */
181 2388 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( q ) ) ) {
182 0 : return fd_bn254_g2_set( r, p );
183 0 : }
184 2388 : fd_bn254_fp2_t zz1[1], zz2[1];
185 2388 : fd_bn254_fp2_t u1[1], s1[1];
186 2388 : fd_bn254_fp2_t u2[1], s2[1];
187 2388 : fd_bn254_fp2_t h[1];
188 2388 : fd_bn254_fp2_t i[1], j[1];
189 2388 : fd_bn254_fp2_t rr[1], v[1];
190 : /* Z1Z1 = Z1^2 */
191 2388 : fd_bn254_fp2_sqr( zz1, &p->Z );
192 : /* Z2Z2 = Z2^2 */
193 2388 : fd_bn254_fp2_sqr( zz2, &q->Z );
194 : /* U1 = X1*Z2Z2 */
195 2388 : fd_bn254_fp2_mul( u1, &p->X, zz2 );
196 : /* U2 = X2*Z1Z1 */
197 2388 : fd_bn254_fp2_mul( u2, &q->X, zz1 );
198 : /* S1 = Y1*Z2*Z2Z2 */
199 2388 : fd_bn254_fp2_mul( s1, &p->Y, &q->Z );
200 2388 : fd_bn254_fp2_mul( s1, s1, zz2 );
201 : /* S2 = Y2*Z1*Z1Z1 */
202 2388 : fd_bn254_fp2_mul( s2, &q->Y, &p->Z );
203 2388 : fd_bn254_fp2_mul( s2, s2, zz1 );
204 :
205 : /* if p==q, call fd_bn254_g2_dbl */
206 : // if( FD_UNLIKELY( fd_bn254_fp2_eq( u2, &p->X ) && fd_bn254_fp2_eq( s2, &p->Y ) ) ) {
207 : // return fd_bn254_g2_dbl( r, p );
208 : // }
209 :
210 : /* H = U2-U1 */
211 2388 : fd_bn254_fp2_sub( h, u2, u1 );
212 : /* HH = (2*H)^2 */
213 2388 : fd_bn254_fp2_add( i, h, h );
214 2388 : fd_bn254_fp2_sqr( i, i );
215 : /* J = H*I */
216 2388 : fd_bn254_fp2_mul( j, h, i );
217 : /* r = 2*(S2-S1) */
218 2388 : fd_bn254_fp2_sub( rr, s2, s1 );
219 2388 : fd_bn254_fp2_add( rr, rr, rr );
220 : /* V = U1*I */
221 2388 : fd_bn254_fp2_mul( v, u1, i );
222 : /* X3 = r^2-J-2*V */
223 2388 : fd_bn254_fp2_sqr( &r->X, rr );
224 2388 : fd_bn254_fp2_sub( &r->X, &r->X, j );
225 2388 : fd_bn254_fp2_sub( &r->X, &r->X, v );
226 2388 : fd_bn254_fp2_sub( &r->X, &r->X, v );
227 : /* Y3 = r*(V-X3)-2*S1*J
228 : note: i no longer used */
229 2388 : fd_bn254_fp2_mul( i, s1, j ); /* i = S1*J */
230 2388 : fd_bn254_fp2_add( i, i, i ); /* i = 2*S1*J */
231 2388 : fd_bn254_fp2_sub( &r->Y, v, &r->X );
232 2388 : fd_bn254_fp2_mul( &r->Y, &r->Y, rr );
233 2388 : fd_bn254_fp2_sub( &r->Y, &r->Y, i );
234 : /* Z3 = ((Z1+Z2)^2-Z1Z1-Z2Z2)*H */
235 2388 : fd_bn254_fp2_add( &r->Z, &p->Z, &q->Z );
236 2388 : fd_bn254_fp2_sqr( &r->Z, &r->Z );
237 2388 : fd_bn254_fp2_sub( &r->Z, &r->Z, zz1 );
238 2388 : fd_bn254_fp2_sub( &r->Z, &r->Z, zz2 );
239 2388 : fd_bn254_fp2_mul( &r->Z, &r->Z, h );
240 2388 : return r;
241 2388 : }
242 :
243 : /* fd_bn254_g2_affine_add computes r = p + q.
244 : Both p, q are affine, i.e. Z==1. */
245 : fd_bn254_g2_t *
246 : fd_bn254_g2_affine_add( fd_bn254_g2_t * r,
247 : fd_bn254_g2_t const * p,
248 31536 : fd_bn254_g2_t const * q ) {
249 : /* p==0, return q */
250 31536 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
251 12 : return fd_bn254_g2_set( r, q );
252 12 : }
253 : /* q==0, return p */
254 31524 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( q ) ) ) {
255 6 : return fd_bn254_g2_set( r, p );
256 6 : }
257 :
258 31518 : fd_bn254_fp2_t lambda[1], x[1], y[1];
259 :
260 : /* same X, either the points are equal or opposite */
261 31518 : if( fd_bn254_fp2_eq( &p->X, &q->X ) ) {
262 6 : if( fd_bn254_fp2_eq( &p->Y, &q->Y ) ) {
263 : /* p==q => point double: lambda = 3 * x1^2 / (2 * y1) */
264 6 : fd_bn254_fp2_sqr( x, &p->X ); /* x = x1^2 */
265 6 : fd_bn254_fp2_add( y, x, x ); /* y = 2 x1^2 */
266 6 : fd_bn254_fp2_add( x, x, y ); /* x = 3 x1^2 */
267 6 : fd_bn254_fp2_add( y, &p->Y, &p->Y );
268 6 : fd_bn254_fp2_inv( lambda, y );
269 6 : fd_bn254_fp2_mul( lambda, lambda, x );
270 6 : } else {
271 : /* p==-q => r=0 */
272 0 : return fd_bn254_g2_set_zero( r );
273 0 : }
274 31512 : } else {
275 : /* point add: lambda = (y1 - y2) / (x1 - x2) */
276 31512 : fd_bn254_fp2_sub( x, &p->X, &q->X );
277 31512 : fd_bn254_fp2_sub( y, &p->Y, &q->Y );
278 31512 : fd_bn254_fp2_inv( lambda, x );
279 31512 : fd_bn254_fp2_mul( lambda, lambda, y );
280 31512 : }
281 :
282 : /* x3 = lambda^2 - x1 - x2 */
283 31518 : fd_bn254_fp2_sqr( x, lambda );
284 31518 : fd_bn254_fp2_sub( x, x, &p->X );
285 31518 : fd_bn254_fp2_sub( x, x, &q->X );
286 :
287 : /* y3 = lambda * (x1 - x3) - y1 */
288 31518 : fd_bn254_fp2_sub( y, &p->X, x );
289 31518 : fd_bn254_fp2_mul( y, y, lambda );
290 31518 : fd_bn254_fp2_sub( y, y, &p->Y );
291 :
292 31518 : fd_bn254_fp2_set( &r->X, x );
293 31518 : fd_bn254_fp2_set( &r->Y, y );
294 31518 : fd_bn254_fp2_set_one( &r->Z );
295 31518 : return r;
296 31518 : }
|
