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 53 : fd_bn254_g2_t const * p ) {
11 53 : if( FD_UNLIKELY( fd_bn254_fp2_is_zero( &p->Z ) || fd_bn254_fp2_is_one( &p->Z ) ) ) {
12 26 : return fd_bn254_g2_set( r, p );
13 26 : }
14 :
15 27 : fd_bn254_fp2_t iz[1], iz2[1];
16 27 : fd_bn254_fp2_inv( iz, &p->Z );
17 27 : fd_bn254_fp2_sqr( iz2, iz );
18 :
19 : /* X / Z^2, Y / Z^3 */
20 27 : fd_bn254_fp2_mul( &r->X, &p->X, iz2 );
21 27 : fd_bn254_fp2_mul( &r->Y, &p->Y, iz2 );
22 27 : fd_bn254_fp2_mul( &r->Y, &r->Y, iz );
23 27 : fd_bn254_fp2_set_one( &r->Z );
24 27 : return r;
25 53 : }
26 :
27 : uchar *
28 : fd_bn254_g2_tobytes( uchar out[128],
29 : fd_bn254_g2_t const * p,
30 57 : int big_endian ) {
31 57 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
32 4 : fd_memset( out, 0, 128UL );
33 : /* no flags */
34 4 : return out;
35 4 : }
36 :
37 53 : fd_bn254_g2_t r[1];
38 53 : fd_bn254_g2_to_affine( r, p );
39 :
40 53 : fd_bn254_fp2_from_mont( &r->X, &r->X );
41 53 : fd_bn254_fp2_from_mont( &r->Y, &r->Y );
42 :
43 53 : fd_bn254_fp2_tobytes_nm( &out[ 0], &r->X, big_endian );
44 53 : fd_bn254_fp2_tobytes_nm( &out[64], &r->Y, big_endian );
45 : /* no flags */
46 53 : return out;
47 57 : }
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 31851 : fd_bn254_g2_t const * p ) {
54 : /* p==0, return 0 */
55 31851 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
56 25 : return fd_bn254_g2_set_zero( r );
57 25 : }
58 :
59 31826 : fd_bn254_fp2_t a[1], b[1], c[1];
60 31826 : fd_bn254_fp2_t d[1], e[1], f[1];
61 :
62 : /* A = X1^2 */
63 31826 : fd_bn254_fp2_sqr( a, &p->X );
64 : /* B = Y1^2 */
65 31826 : fd_bn254_fp2_sqr( b, &p->Y );
66 : /* C = B^2 */
67 31826 : 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 31826 : fd_bn254_fp2_mul( d, &p->X, b );
78 31826 : fd_bn254_fp2_add( d, d, d );
79 31826 : fd_bn254_fp2_add( d, d, d );
80 : /* E = 3*A */
81 31826 : fd_bn254_fp2_add( e, a, a );
82 31826 : fd_bn254_fp2_add( e, a, e );
83 : /* F = E^2 */
84 31826 : fd_bn254_fp2_sqr( f, e );
85 : /* X3 = F-2*D */
86 31826 : fd_bn254_fp2_add( &r->X, d, d );
87 31826 : 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 31826 : fd_bn254_fp2_mul( &r->Z, &p->Y, &p->Z );
93 31826 : fd_bn254_fp2_add( &r->Z, &r->Z, &r->Z );
94 : /* Y3 = E*(D-X3)-8*C */
95 31826 : fd_bn254_fp2_sub( &r->Y, d, &r->X );
96 31826 : fd_bn254_fp2_mul( &r->Y, e, &r->Y );
97 31826 : fd_bn254_fp2_add( c, c, c ); /* 2*c */
98 31826 : fd_bn254_fp2_add( c, c, c ); /* 4*y */
99 31826 : fd_bn254_fp2_add( c, c, c ); /* 8*y */
100 31826 : fd_bn254_fp2_sub( &r->Y, &r->Y, c );
101 31826 : return r;
102 31851 : }
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 15237 : fd_bn254_g2_t const * q ) {
110 : /* p==0, return q */
111 15237 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
112 25 : return fd_bn254_g2_set( r, q );
113 25 : }
114 : /* q==0, return p */
115 15212 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( q ) ) ) {
116 0 : return fd_bn254_g2_set( r, p );
117 0 : }
118 15212 : fd_bn254_fp2_t zz[1], u2[1], s2[1];
119 15212 : fd_bn254_fp2_t h[1], hh[1];
120 15212 : fd_bn254_fp2_t i[1], j[1];
121 15212 : fd_bn254_fp2_t rr[1], v[1];
122 : /* Z1Z1 = Z1^2 */
123 15212 : fd_bn254_fp2_sqr( zz, &p->Z );
124 : /* U2 = X2*Z1Z1 */
125 15212 : fd_bn254_fp2_mul( u2, &q->X, zz );
126 : /* S2 = Y2*Z1*Z1Z1 */
127 15212 : fd_bn254_fp2_mul( s2, &q->Y, &p->Z );
128 15212 : fd_bn254_fp2_mul( s2, s2, zz );
129 :
130 : /* if p==q, call fd_bn254_g2_dbl */
131 15212 : 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 15212 : fd_bn254_fp2_sub( h, u2, &p->X );
137 : /* HH = H^2 */
138 15212 : fd_bn254_fp2_sqr( hh, h );
139 : /* I = 4*HH */
140 15212 : fd_bn254_fp2_add( i, hh, hh );
141 15212 : fd_bn254_fp2_add( i, i, i );
142 : /* J = H*I */
143 15212 : fd_bn254_fp2_mul( j, h, i );
144 : /* r = 2*(S2-Y1) */
145 15212 : fd_bn254_fp2_sub( rr, s2, &p->Y );
146 15212 : fd_bn254_fp2_add( rr, rr, rr );
147 : /* V = X1*I */
148 15212 : fd_bn254_fp2_mul( v, &p->X, i );
149 : /* X3 = r^2-J-2*V */
150 15212 : fd_bn254_fp2_sqr( &r->X, rr );
151 15212 : fd_bn254_fp2_sub( &r->X, &r->X, j );
152 15212 : fd_bn254_fp2_sub( &r->X, &r->X, v );
153 15212 : fd_bn254_fp2_sub( &r->X, &r->X, v );
154 : /* Y3 = r*(V-X3)-2*Y1*J
155 : note: i no longer used */
156 15212 : fd_bn254_fp2_mul( i, &p->Y, j ); /* i = Y1*J */
157 15212 : fd_bn254_fp2_add( i, i, i ); /* i = 2*Y1*J */
158 15212 : fd_bn254_fp2_sub( &r->Y, v, &r->X );
159 15212 : fd_bn254_fp2_mul( &r->Y, &r->Y, rr );
160 15212 : fd_bn254_fp2_sub( &r->Y, &r->Y, i );
161 : /* Z3 = (Z1+H)^2-Z1Z1-HH */
162 15212 : fd_bn254_fp2_add( &r->Z, &p->Z, h );
163 15212 : fd_bn254_fp2_sqr( &r->Z, &r->Z );
164 15212 : fd_bn254_fp2_sub( &r->Z, &r->Z, zz );
165 15212 : fd_bn254_fp2_sub( &r->Z, &r->Z, hh );
166 15212 : return r;
167 15212 : }
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 964 : fd_bn254_g2_t const * q ) {
176 : /* p==0, return q */
177 964 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
178 50 : return fd_bn254_g2_set( r, q );
179 50 : }
180 : /* q==0, return p */
181 914 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( q ) ) ) {
182 0 : return fd_bn254_g2_set( r, p );
183 0 : }
184 914 : fd_bn254_fp2_t zz1[1], zz2[1];
185 914 : fd_bn254_fp2_t u1[1], s1[1];
186 914 : fd_bn254_fp2_t u2[1], s2[1];
187 914 : fd_bn254_fp2_t h[1];
188 914 : fd_bn254_fp2_t i[1], j[1];
189 914 : fd_bn254_fp2_t rr[1], v[1];
190 : /* Z1Z1 = Z1^2 */
191 914 : fd_bn254_fp2_sqr( zz1, &p->Z );
192 : /* Z2Z2 = Z2^2 */
193 914 : fd_bn254_fp2_sqr( zz2, &q->Z );
194 : /* U1 = X1*Z2Z2 */
195 914 : fd_bn254_fp2_mul( u1, &p->X, zz2 );
196 : /* U2 = X2*Z1Z1 */
197 914 : fd_bn254_fp2_mul( u2, &q->X, zz1 );
198 : /* S1 = Y1*Z2*Z2Z2 */
199 914 : fd_bn254_fp2_mul( s1, &p->Y, &q->Z );
200 914 : fd_bn254_fp2_mul( s1, s1, zz2 );
201 : /* S2 = Y2*Z1*Z1Z1 */
202 914 : fd_bn254_fp2_mul( s2, &q->Y, &p->Z );
203 914 : 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 914 : fd_bn254_fp2_sub( h, u2, u1 );
212 : /* HH = (2*H)^2 */
213 914 : fd_bn254_fp2_add( i, h, h );
214 914 : fd_bn254_fp2_sqr( i, i );
215 : /* J = H*I */
216 914 : fd_bn254_fp2_mul( j, h, i );
217 : /* r = 2*(S2-S1) */
218 914 : fd_bn254_fp2_sub( rr, s2, s1 );
219 914 : fd_bn254_fp2_add( rr, rr, rr );
220 : /* V = U1*I */
221 914 : fd_bn254_fp2_mul( v, u1, i );
222 : /* X3 = r^2-J-2*V */
223 914 : fd_bn254_fp2_sqr( &r->X, rr );
224 914 : fd_bn254_fp2_sub( &r->X, &r->X, j );
225 914 : fd_bn254_fp2_sub( &r->X, &r->X, v );
226 914 : fd_bn254_fp2_sub( &r->X, &r->X, v );
227 : /* Y3 = r*(V-X3)-2*S1*J
228 : note: i no longer used */
229 914 : fd_bn254_fp2_mul( i, s1, j ); /* i = S1*J */
230 914 : fd_bn254_fp2_add( i, i, i ); /* i = 2*S1*J */
231 914 : fd_bn254_fp2_sub( &r->Y, v, &r->X );
232 914 : fd_bn254_fp2_mul( &r->Y, &r->Y, rr );
233 914 : fd_bn254_fp2_sub( &r->Y, &r->Y, i );
234 : /* Z3 = ((Z1+Z2)^2-Z1Z1-Z2Z2)*H */
235 914 : fd_bn254_fp2_add( &r->Z, &p->Z, &q->Z );
236 914 : fd_bn254_fp2_sqr( &r->Z, &r->Z );
237 914 : fd_bn254_fp2_sub( &r->Z, &r->Z, zz1 );
238 914 : fd_bn254_fp2_sub( &r->Z, &r->Z, zz2 );
239 914 : fd_bn254_fp2_mul( &r->Z, &r->Z, h );
240 914 : return r;
241 914 : }
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 511 : fd_bn254_g2_t const * q ) {
249 : /* p==0, return q */
250 511 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
251 1 : return fd_bn254_g2_set( r, q );
252 1 : }
253 : /* q==0, return p */
254 510 : if( FD_UNLIKELY( fd_bn254_g2_is_zero( q ) ) ) {
255 1 : return fd_bn254_g2_set( r, p );
256 1 : }
257 :
258 509 : fd_bn254_fp2_t lambda[1], x[1], y[1];
259 :
260 : /* same X, either the points are equal or opposite */
261 509 : if( fd_bn254_fp2_eq( &p->X, &q->X ) ) {
262 0 : if( fd_bn254_fp2_eq( &p->Y, &q->Y ) ) {
263 : /* p==q => point double: lambda = 3 * x1^2 / (2 * y1) */
264 0 : fd_bn254_fp2_sqr( x, &p->X ); /* x = x1^2 */
265 0 : fd_bn254_fp2_add( y, x, x ); /* y = 2 x1^2 */
266 0 : fd_bn254_fp2_add( x, x, y ); /* x = 3 x1^2 */
267 0 : fd_bn254_fp2_add( y, &p->Y, &p->Y );
268 0 : fd_bn254_fp2_inv( lambda, y );
269 0 : fd_bn254_fp2_mul( lambda, lambda, x );
270 0 : } else {
271 : /* p==-q => r=0 */
272 0 : return fd_bn254_g2_set_zero( r );
273 0 : }
274 509 : } else {
275 : /* point add: lambda = (y1 - y2) / (x1 - x2) */
276 509 : fd_bn254_fp2_sub( x, &p->X, &q->X );
277 509 : fd_bn254_fp2_sub( y, &p->Y, &q->Y );
278 509 : fd_bn254_fp2_inv( lambda, x );
279 509 : fd_bn254_fp2_mul( lambda, lambda, y );
280 509 : }
281 :
282 : /* x3 = lambda^2 - x1 - x2 */
283 509 : fd_bn254_fp2_sqr( x, lambda );
284 509 : fd_bn254_fp2_sub( x, x, &p->X );
285 509 : fd_bn254_fp2_sub( x, x, &q->X );
286 :
287 : /* y3 = lambda * (x1 - x3) - y1 */
288 509 : fd_bn254_fp2_sub( y, &p->X, x );
289 509 : fd_bn254_fp2_mul( y, y, lambda );
290 509 : fd_bn254_fp2_sub( y, y, &p->Y );
291 :
292 509 : fd_bn254_fp2_set( &r->X, x );
293 509 : fd_bn254_fp2_set( &r->Y, y );
294 509 : fd_bn254_fp2_set_one( &r->Z );
295 509 : return r;
296 509 : }
|
