Line data    Source code

       1             : #include "./fd_bn254.h"
       2             : #include "../fiat-crypto/bn254_64.c"
       3             : 
       4             : /* Fp = base field */
       5             : 
       6        6018 : #define FLAG_INF  ((uchar)(1 << 6))
       7        5796 : #define FLAG_NEG  ((uchar)(1 << 7))
       8        5328 : #define FLAG_MASK 0x3F
       9             : 
      10             : /* const 0. */
      11             : const fd_bn254_fp_t fd_bn254_const_zero[1] = {{{
      12             :   0x0UL, 0x0UL, 0x0UL, 0x0UL,
      13             : }}};
      14             : 
      15             : /* const p, used to validate a field element. NOT Montgomery.
      16             :    0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47 */
      17             : const fd_bn254_fp_t fd_bn254_const_p[1] = {{{
      18             :   0x3c208c16d87cfd47, 0x97816a916871ca8d, 0xb85045b68181585d, 0x30644e72e131a029,
      19             : }}};
      20             : 
      21             : /* const 1/p for CIOS mul */
      22             : static const ulong fd_bn254_const_p_inv = 0x87D20782E4866389UL;
      23             : 
      24             : /* const 1. Montgomery.
      25             :    0x0e0a77c19a07df2f666ea36f7879462c0a78eb28f5c70b3dd35d438dc58f0d9d */
      26             : const fd_bn254_fp_t fd_bn254_const_one_mont[1] = {{{
      27             :   0xd35d438dc58f0d9d, 0x0a78eb28f5c70b3d, 0x666ea36f7879462c, 0x0e0a77c19a07df2f
      28             : }}};
      29             : 
      30             : /* const x, used by fd_bn254_g2_frombytes_check(). scalar (NOT Montgomery)
      31             :    0x44e992b44a6909f1 (64-bit) */
      32             : const fd_bn254_scalar_t fd_bn254_const_x[1] = {{{
      33             :   0x44e992b44a6909f1, 0x0, 0x0, 0x0,
      34             : }}};
      35             : 
      36             : /* const b=3, in curve equation y^2 = x^3 + b. Montgomery.
      37             :    0x2a1f6744ce179d8e334bea4e696bd2841f6ac17ae15521b97a17caa950ad28d7 */
      38             : const fd_bn254_fp_t fd_bn254_const_b_mont[1] = {{{
      39             :   0x7a17caa950ad28d7, 0x1f6ac17ae15521b9, 0x334bea4e696bd284, 0x2a1f6744ce179d8e
      40             :   // 0x3UL, 0x0UL, 0x0UL, 0x0UL,
      41             : }}};
      42             : 
      43             : /* const p-1, to check if sqrt exists. Montgomery.
      44             :    0x2259d6b14729c0fa51e1a247090812318d087f6872aabf4f68c3488912edefaa */
      45             : const fd_bn254_fp_t fd_bn254_const_p_minus_one_mont[1] = {{{
      46             :   0x68c3488912edefaa, 0x8d087f6872aabf4f, 0x51e1a24709081231, 0x2259d6b14729c0fa,
      47             : }}};
      48             : 
      49             : /* const (p-1)/2, used to check if an element is positive or negative,
      50             :    and to calculate sqrt() in Fp2. NOT Montgomery.
      51             :    0x183227397098d014dc2822db40c0ac2ecbc0b548b438e5469e10460b6c3e7ea3 */
      52             : const fd_bn254_fp_t fd_bn254_const_p_minus_one_half[1] = {{{
      53             :   0x9e10460b6c3e7ea3, 0xcbc0b548b438e546, 0xdc2822db40c0ac2e, 0x183227397098d014,
      54             : }}};
      55             : 
      56             : /* const (p-3)/4, used to calculate sqrt() in Fp and Fp2. bigint (NOT Montgomery)
      57             :    0x0c19139cb84c680a6e14116da060561765e05aa45a1c72a34f082305b61f3f51 */
      58             : const fd_uint256_t fd_bn254_const_sqrt_exp[1] = {{{
      59             :   0x4f082305b61f3f51, 0x65e05aa45a1c72a3, 0x6e14116da0605617, 0x0c19139cb84c680a,
      60             : }}};
      61             : 
      62             : static inline int
      63         789 : fd_bn254_fp_is_neg_nm( fd_bn254_fp_t * x ) {
      64         789 :   return fd_uint256_cmp( x, fd_bn254_const_p_minus_one_half ) > 0;
      65         789 : }
      66             : 
      67             : static inline fd_bn254_fp_t *
      68             : fd_bn254_fp_frombytes_be_nm( fd_bn254_fp_t * r,
      69             :                              uchar const     buf[32],
      70             :                              int *           is_inf,
      71       18117 :                              int *           is_neg ) {
      72             :   /* Flags (optional) */
      73       18117 :   if( is_inf != NULL /* && is_neg != NULL */ ) {
      74        5718 :     *is_inf = !!(buf[0] & FLAG_INF);
      75        5718 :     *is_neg = !!(buf[0] & FLAG_NEG);
      76             :     /* If both flags are set (bit 6, 7), return error.
      77             :        https://github.com/arkworks-rs/algebra/blob/v0.4.2/ec/src/models/short_weierstrass/serialization_flags.rs#L75 */
      78        5718 :     if( FD_UNLIKELY( *is_inf && *is_neg ) ) {
      79         981 :       return NULL;
      80         981 :     }
      81        5718 :   }
      82             : 
      83       17136 :   fd_memcpy( r, buf, 32 );
      84       17136 :   fd_uint256_bswap( r, r );
      85       17136 :   if( is_inf != NULL ) {
      86        4737 :     r->buf[31] &= FLAG_MASK;
      87        4737 :   }
      88             : 
      89             :   /* Field element */
      90       17136 :   if( FD_UNLIKELY( fd_uint256_cmp( r, fd_bn254_const_p ) >= 0 ) ) {
      91        5382 :     return NULL;
      92        5382 :   }
      93       11754 :   return r;
      94       17136 : }
      95             : 
      96             : static inline uchar *
      97             : fd_bn254_fp_tobytes_be_nm( uchar           buf[32],
      98        2217 :                            fd_bn254_fp_t * a ) {
      99        2217 :   fd_uint256_bswap( a, a );
     100        2217 :   fd_memcpy( buf, a, 32 );
     101        2217 :   return buf;
     102        2217 : }
     103             : 
     104             : static inline int
     105             : fd_bn254_fp_eq( fd_bn254_fp_t const * r,
     106      103584 :                 fd_bn254_fp_t const * a ) {
     107      103584 :   return fd_uint256_eq( r, a );
     108      103584 : }
     109             : 
     110             : static inline fd_bn254_fp_t *
     111             : fd_bn254_fp_from_mont( fd_bn254_fp_t * r,
     112        2217 :                        fd_bn254_fp_t const * a ) {
     113        2217 :   fiat_bn254_from_montgomery( r->limbs, a->limbs );
     114        2217 :   return r;
     115        2217 : }
     116             : 
     117             : static inline fd_bn254_fp_t *
     118             : fd_bn254_fp_to_mont( fd_bn254_fp_t * r,
     119        6831 :                      fd_bn254_fp_t const * a ) {
     120        6831 :   fiat_bn254_to_montgomery( r->limbs, a->limbs );
     121        6831 :   return r;
     122        6831 : }
     123             : 
     124             : static inline fd_bn254_fp_t *
     125             : fd_bn254_fp_neg_nm( fd_bn254_fp_t * r,
     126         219 :                     fd_bn254_fp_t const * a ) {
     127         219 :   if( FD_UNLIKELY( fd_bn254_fp_is_zero( a ) ) ) {
     128           6 :     return fd_bn254_fp_set_zero( r );
     129           6 :   }
     130             :   /* compute p-a */
     131        1065 :   for( ulong i=0, cy=0; i<4; i++ ) {
     132         852 :     ulong p = fd_bn254_const_p->limbs[i];
     133         852 :     ulong b = a->limbs[i];
     134         852 :     b += cy;
     135         852 :     cy = (b < cy);
     136         852 :     cy += (p < b);
     137         852 :     r->limbs[i] = p - b;
     138         852 :   }
     139         213 :   return r;
     140         219 : }
     141             : 
     142             : static inline fd_bn254_fp_t *
     143             : fd_bn254_fp_set( fd_bn254_fp_t * r,
     144     1940574 :                  fd_bn254_fp_t const * a ) {
     145     1940574 :   r->limbs[0] = a->limbs[0];
     146     1940574 :   r->limbs[1] = a->limbs[1];
     147     1940574 :   r->limbs[2] = a->limbs[2];
     148     1940574 :   r->limbs[3] = a->limbs[3];
     149     1940574 :   return r;
     150     1940574 : }
     151             : 
     152             : static inline fd_bn254_fp_t *
     153             : fd_bn254_fp_add( fd_bn254_fp_t * r,
     154             :                  fd_bn254_fp_t const * a,
     155    16783779 :                  fd_bn254_fp_t const * b ) {
     156    16783779 :   fiat_bn254_add( r->limbs, a->limbs, b->limbs );
     157    16783779 :   return r;
     158    16783779 : }
     159             : 
     160             : static inline fd_bn254_fp_t *
     161             : fd_bn254_fp_sub( fd_bn254_fp_t * r,
     162             :                  fd_bn254_fp_t const * a,
     163    10781037 :                  fd_bn254_fp_t const * b ) {
     164    10781037 :   fiat_bn254_sub( r->limbs, a->limbs, b->limbs );
     165    10781037 :   return r;
     166    10781037 : }
     167             : 
     168             : static inline fd_bn254_fp_t *
     169             : fd_bn254_fp_neg( fd_bn254_fp_t * r,
     170       67458 :                  fd_bn254_fp_t const * a ) {
     171       67458 :   fiat_bn254_opp( r->limbs, a->limbs );
     172       67458 :   return r;
     173       67458 : }
     174             : 
     175             : static inline fd_bn254_fp_t *
     176             : fd_bn254_fp_halve( fd_bn254_fp_t * r,
     177       64512 :                    fd_bn254_fp_t const * a ) {
     178       64512 :   int is_odd = r->limbs[0] & 0x1;
     179       64512 :   fd_uint256_add( r, a, is_odd ? fd_bn254_const_p : fd_bn254_const_zero );
     180       64512 :   r->limbs[0] = (r->limbs[0] >> 1) | (r->limbs[1] << 63);
     181       64512 :   r->limbs[1] = (r->limbs[1] >> 1) | (r->limbs[2] << 63);
     182       64512 :   r->limbs[2] = (r->limbs[2] >> 1) | (r->limbs[3] << 63);
     183       64512 :   r->limbs[3] = (r->limbs[3] >> 1);
     184       64512 :   return r;
     185       64512 : }
     186             : 
     187             : FD_UINT256_FP_MUL_IMPL(fd_bn254_fp, fd_bn254_const_p, fd_bn254_const_p_inv)
     188             : 
     189             : static inline fd_bn254_fp_t *
     190             : fd_bn254_fp_sqr( fd_bn254_fp_t * r,
     191     1763430 :                  fd_bn254_fp_t const * a ) {
     192     1763430 :   return fd_bn254_fp_mul( r, a, a );
     193     1763430 : }
     194             : 
     195             : fd_bn254_fp_t *
     196             : fd_bn254_fp_pow( fd_bn254_fp_t * restrict r,
     197             :                  fd_bn254_fp_t const *    a,
     198        1167 :                  fd_uint256_t const *     b ) {
     199        1167 :   fd_bn254_fp_set_one( r );
     200             : 
     201        1167 :   int i = 255;
     202        4155 :   while( !fd_uint256_bit( b, i) ) i--;
     203      296931 :   for( ; i>=0; i--) {
     204      295764 :     fd_bn254_fp_sqr( r, r );
     205      295764 :     if( fd_uint256_bit( b, i ) ) {
     206      128043 :       fd_bn254_fp_mul( r, r, a );
     207      128043 :     }
     208      295764 :   }
     209        1167 :   return r;
     210        1167 : }
     211             : 
     212             : static inline fd_bn254_fp_t *
     213             : fd_bn254_fp_inv( fd_bn254_fp_t * r,
     214         840 :                   fd_bn254_fp_t const * a ) {
     215         840 :   fd_uint256_t p_minus_2[1];
     216         840 :   fd_bn254_fp_set( p_minus_2, fd_bn254_const_p );
     217         840 :   p_minus_2->limbs[0] = p_minus_2->limbs[0] - 2UL;
     218         840 :   return fd_bn254_fp_pow( r, a, p_minus_2 );
     219         840 : }
     220             : 
     221             : static inline fd_bn254_fp_t *
     222             : fd_bn254_fp_sqrt( fd_bn254_fp_t * r,
     223         327 :                   fd_bn254_fp_t const * a ) {
     224             :   /* Alg. 2, https://eprint.iacr.org/2012/685 */
     225             : 
     226         327 :   fd_bn254_fp_t a0[1], a1[1];
     227             : 
     228         327 :   fd_bn254_fp_pow( a1, a, fd_bn254_const_sqrt_exp );
     229             : 
     230         327 :   fd_bn254_fp_sqr( a0, a1 );
     231         327 :   fd_bn254_fp_mul( a0, a0, a );
     232         327 :   if( FD_UNLIKELY( fd_bn254_fp_eq( a0, fd_bn254_const_p_minus_one_mont ) ) ) {
     233           6 :     return NULL;
     234           6 :   }
     235             : 
     236         321 :   fd_bn254_fp_mul( r, a1, a );
     237         321 :   return r;
     238         327 : }