Line data    Source code

       1             : #include "./fd_bn254_g2_inl.h"
       2             : #include "./fd_bn254_glv.h"
       3             : 
       4             : /* G2 scalar mul and deserialization. */
       5             : 
       6             : /* fd_bn254_g2_scalar_mul computes r = [s]P.
       7             :    p must be in affine form (p->Z == 1).
       8             :    The result is in projective coordinates over Fp2. */
       9             : fd_bn254_g2_t *
      10             : fd_bn254_g2_scalar_mul( fd_bn254_g2_t *           r,
      11             :                         fd_bn254_g2_t const *     p,
      12         487 :                         fd_bn254_scalar_t const * s ) {
      13         487 :   if( FD_UNLIKELY( fd_uint256_is_zero( s ) || fd_bn254_g2_is_zero( p ) ) ) {
      14           3 :     return fd_bn254_g2_set_zero( r );
      15           3 :   }
      16             : 
      17         484 :   ulong b1[ 3 ], b2[ 2 ];
      18         484 :   fd_bn254_glv_sxg3( b1, s, g1_const_g2 );
      19         484 :   fd_bn254_glv_sxg2( b2, s, g2_const );
      20             : 
      21             :   /* k1 = s - b1*N_C - b2*N_B (may be negative for G2) */
      22         484 :   fd_uint256_t k1_abs[1];
      23         484 :   int k1_neg = 0;
      24         484 :   {
      25         484 :     ulong p_nc[ 4 ];
      26             :     /* b2*nb will produce at most 3 limbs, so we want the 4th zeroed for the addition. */
      27         484 :     ulong p_nb[ 4 ] = {0};
      28         484 :     ulong    t[ 4 ];
      29         484 :     fd_bn254_glv_mul3x2( p_nc, b1, nc );
      30         484 :     fd_bn254_glv_mul2x1( p_nb, b2, nb );
      31         484 :     fd_bn254_glv_add4( t, p_nc, p_nb );
      32         484 :     ulong borrow = fd_bn254_glv_sub4( k1_abs->limbs, s->limbs, t );
      33         484 :     if( borrow ) {
      34           1 :       k1_neg = 1;
      35           1 :       fd_bn254_glv_negate4( k1_abs->limbs );
      36           1 :     }
      37         484 :   }
      38             : 
      39             :   /* k2 = b2*N_A - b1*N_B (usually negative for G2) */
      40         484 :   fd_uint256_t k2_abs[1];
      41         484 :   int k2_neg = 0;
      42         484 :   {
      43         484 :     ulong pos[ 4 ], neg[ 4 ];
      44         484 :     fd_bn254_glv_mul2x2( pos, b2, na );
      45         484 :     fd_bn254_glv_mul3x1( neg, b1, nb );
      46         484 :     ulong borrow = fd_bn254_glv_sub4( k2_abs->limbs, pos, neg );
      47         484 :     if( borrow ) {
      48          27 :       k2_neg = 1;
      49          27 :       fd_bn254_glv_negate4( k2_abs->limbs );
      50          27 :     }
      51         484 :   }
      52             : 
      53             :   /* pt1 = P, pt2 = phi(P) = (beta * P.x, P.y).
      54             :      If k1 < 0, negate pt1. If k2 < 0, negate pt2. */
      55         484 :   fd_bn254_g2_t pt1[1], pt2[1];
      56         484 :   fd_bn254_g2_set( pt1, p );
      57         484 :   fd_bn254_fp_mul( &pt2->X.el[0], &p->X.el[0], fd_bn254_const_beta_mont );
      58         484 :   fd_bn254_fp_mul( &pt2->X.el[1], &p->X.el[1], fd_bn254_const_beta_mont );
      59         484 :   fd_bn254_fp2_set( &pt2->Y, &p->Y );
      60         484 :   fd_bn254_fp2_set_one( &pt2->Z );
      61         484 :   if( k1_neg ) {
      62           1 :     fd_bn254_fp2_neg( &pt1->Y, &pt1->Y );
      63           1 :   }
      64         484 :   if( k2_neg ) {
      65          27 :     fd_bn254_fp2_neg( &pt2->Y, &pt2->Y );
      66          27 :   }
      67             : 
      68         484 :   fd_bn254_g2_t pt12[1];
      69         484 :   fd_bn254_g2_affine_add( pt12, pt1, pt2 );
      70             : 
      71             :   /* Shamir's trick: simultaneous double-and-add on k1, k2. */
      72         484 :   int i = 255;
      73       91988 :   for( ; i>=0; i-- ) {
      74       91988 :     int k1b = !!fd_uint256_bit( k1_abs, i );
      75       91988 :     int k2b = !!fd_uint256_bit( k2_abs, i );
      76       91988 :     if( k1b || k2b ) {
      77         484 :       fd_bn254_g2_set( r, ( k1b && k2b ) ? pt12 : ( k1b ? pt1 : pt2 ) );
      78         484 :       break;
      79         484 :     }
      80       91988 :   }
      81         484 :   if( FD_UNLIKELY( i<0 ) ) {
      82           0 :     return fd_bn254_g2_set_zero( r );
      83           0 :   }
      84       31541 :   for( i--; i >= 0; i-- ) {
      85       31057 :     fd_bn254_g2_dbl( r, r );
      86       31057 :     int k1b = !!fd_uint256_bit( k1_abs, i );
      87       31057 :     int k2b = !!fd_uint256_bit( k2_abs, i );
      88       31057 :     if( k1b && k2b ) {
      89         819 :       fd_bn254_g2_add_mixed( r, r, pt12 );
      90       30238 :     } else if( k1b ) {
      91       12993 :       fd_bn254_g2_add_mixed( r, r, pt1 );
      92       17245 :     } else if( k2b ) {
      93         879 :       fd_bn254_g2_add_mixed( r, r, pt2 );
      94         879 :     }
      95       31057 :   }
      96             : 
      97         484 :   return r;
      98         484 : }
      99             : 
     100             : /* fd_bn254_g2_frombytes_internal extracts (x, y) and performs basic checks.
     101             :    This is used by fd_bn254_g2_compress() and fd_bn254_g2_frombytes_check_subgroup(). */
     102             : fd_bn254_g2_t *
     103             : fd_bn254_g2_frombytes_internal( fd_bn254_g2_t * p,
     104             :                                 uchar const     in[128],
     105        1149 :                                 int             big_endian ) {
     106             :   /* Special case: all zeros => point at infinity */
     107        1149 :   const uchar zero[128] = { 0 };
     108        1149 :   if( FD_UNLIKELY( fd_memeq( in, zero, 128 ) ) ) {
     109          21 :     return fd_bn254_g2_set_zero( p );
     110          21 :   }
     111             : 
     112             :   /* Check x < p */
     113        1128 :   if( FD_UNLIKELY( !fd_bn254_fp2_frombytes_nm( &p->X, &in[0], big_endian, NULL, NULL ) ) ) {
     114         362 :     return NULL;
     115         362 :   }
     116             : 
     117             :   /* Check flags and y < p */
     118         766 :   int is_inf, is_neg;
     119         766 :   if( FD_UNLIKELY( !fd_bn254_fp2_frombytes_nm( &p->Y, &in[64], big_endian, &is_inf, &is_neg ) ) ) {
     120         162 :     return NULL;
     121         162 :   }
     122             : 
     123         604 :   if( FD_UNLIKELY( is_inf ) ) {
     124          24 :     return fd_bn254_g2_set_zero( p );
     125          24 :   }
     126             : 
     127         580 :   fd_bn254_fp2_set_one( &p->Z );
     128         580 :   return p;
     129         604 : }
     130             : 
     131             : /* fd_bn254_g2_frombytes_check_eq_only performs frombytes, checks the curve
     132             :    equation, but does NOT check subgroup membership. */
     133             : fd_bn254_g2_t *
     134             : fd_bn254_g2_frombytes_check_eq_only( fd_bn254_g2_t * p,
     135             :                                      uchar const     in[128],
     136         828 :                                      int             big_endian ) {
     137         828 :   if( FD_UNLIKELY( !fd_bn254_g2_frombytes_internal( p, in, big_endian ) ) ) {
     138         273 :     return NULL;
     139         273 :   }
     140         555 :   if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
     141          29 :     return p;
     142          29 :   }
     143             : 
     144         526 :   fd_bn254_fp2_to_mont( &p->X, &p->X );
     145         526 :   fd_bn254_fp2_to_mont( &p->Y, &p->Y );
     146         526 :   fd_bn254_fp2_set_one( &p->Z );
     147             : 
     148             :   /* Check that y^2 = x^3 + b */
     149         526 :   fd_bn254_fp2_t y2[1], x3b[1];
     150         526 :   fd_bn254_fp2_sqr( y2, &p->Y );
     151         526 :   fd_bn254_fp2_sqr( x3b, &p->X );
     152         526 :   fd_bn254_fp2_mul( x3b, x3b, &p->X );
     153         526 :   fd_bn254_fp2_add( x3b, x3b, fd_bn254_const_twist_b_mont );
     154         526 :   if( FD_UNLIKELY( !fd_bn254_fp2_eq( y2, x3b ) ) ) {
     155          16 :     return NULL;
     156          16 :   }
     157         510 :   return p;
     158         526 : }
     159             : 
     160             : /* fd_bn254_g2_frombytes_check_subgroup performs frombytes AND checks subgroup membership. */
     161             : fd_bn254_g2_t *
     162             : fd_bn254_g2_frombytes_check_subgroup( fd_bn254_g2_t * p,
     163             :                                       uchar const     in[128],
     164         737 :                                       int             big_endian ) {
     165         737 :   if( FD_UNLIKELY( fd_bn254_g2_frombytes_check_eq_only( p, in, big_endian )==NULL ) ) {
     166         257 :     return NULL;
     167         257 :   }
     168         480 :   if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
     169          25 :     return p;
     170          25 :   }
     171             : 
     172             :   /* G2 does NOT have prime order, so we have to check group membership. */
     173             : 
     174             :   /* We use the fast subgroup membership check, that requires a single 64-bit scalar mul.
     175             :      https://eprint.iacr.org/2022/348, Sec 3.1.
     176             :      [r]P == 0 <==> [x+1]P + ψ([x]P) + ψ²([x]P) = ψ³([2x]P)
     177             :      See also: https://github.com/Consensys/gnark-crypto/blob/v0.12.1/ecc/bn254/g2.go#L404
     178             : 
     179             :      For reference, the following also work:
     180             : 
     181             :      1) very slow: 256-bit scalar mul
     182             : 
     183             :      fd_bn254_g2_t r[1];
     184             :      fd_bn254_g2_scalar_mul( r, p, fd_bn254_const_r );
     185             :      if( !fd_bn254_g2_is_zero( r ) ) return NULL;
     186             : 
     187             :      2) slow: 128-bit scalar mul
     188             : 
     189             :      fd_bn254_g2_t a[1], b[1];
     190             :      const fd_bn254_scalar_t six_x_sqr[1] = {{{ 0xf83e9682e87cfd46, 0x6f4d8248eeb859fb, 0x0, 0x0, }}};
     191             :      fd_bn254_g2_scalar_mul( a, p, six_x_sqr );
     192             :      fd_bn254_g2_frob( b, p );
     193             :      if( !fd_bn254_g2_eq( a, b ) ) return NULL; */
     194             : 
     195         455 :   fd_bn254_g2_t xp[1], l[1], psi[1], r[1];
     196         455 :   fd_bn254_g2_scalar_mul( xp, p, fd_bn254_const_x ); /* 64-bit */
     197         455 :   fd_bn254_g2_add_mixed( l, xp, p );
     198             : 
     199             :   /* l will not be equal to psi unless p==0 */
     200         455 :   fd_bn254_g2_frob( psi, xp );
     201         455 :   fd_bn254_g2_add( l, l, psi );
     202             : 
     203         455 :   fd_bn254_g2_frob2( psi, xp ); /* faster than frob( psi, psi ) */
     204         455 :   fd_bn254_g2_add( l, l, psi );
     205             : 
     206         455 :   fd_bn254_g2_frob( psi, psi );
     207         455 :   fd_bn254_g2_dbl( r, psi );
     208         455 :   if( FD_UNLIKELY( !fd_bn254_g2_eq( l, r ) ) ) {
     209           8 :     return NULL;
     210           8 :   }
     211         447 :   return p;
     212         455 : }