Line data    Source code

       1             : #include "./fd_bn254.h"
       2             : #include "../fiat-crypto/bn254_64.c"
       3             : 
       4             : /* Fp = base field */
       5             : 
       6      187875 : #define FLAG_INF  ((uchar)(1 << 6))
       7      127818 : #define FLAG_NEG  ((uchar)(1 << 7))
       8      160875 : #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       93168 : fd_bn254_fp_is_neg_nm( fd_bn254_fp_t * x ) {
      64       93168 :   return fd_uint256_cmp( x, fd_bn254_const_p_minus_one_half ) > 0;
      65       93168 : }
      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      287094 :                              int *           is_neg ) {
      72             :   /* Flags (optional) */
      73      287094 :   if( is_inf != NULL /* && is_neg != NULL */ ) {
      74      127791 :     *is_inf = !!(buf[0] & FLAG_INF);
      75      127791 :     *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      127791 :     if( FD_UNLIKELY( *is_inf && *is_neg ) ) {
      79           0 :       return NULL;
      80           0 :     }
      81      127791 :   }
      82             : 
      83      287094 :   fd_memcpy( r, buf, 32 );
      84      287094 :   fd_uint256_bswap( r, r );
      85      287094 :   if( is_inf != NULL ) {
      86      127791 :     r->buf[31] &= FLAG_MASK;
      87      127791 :   }
      88             : 
      89             :   /* Field element */
      90      287094 :   if( FD_UNLIKELY( fd_uint256_cmp( r, fd_bn254_const_p ) >= 0 ) ) {
      91           0 :     return NULL;
      92           0 :   }
      93      287094 :   return r;
      94      287094 : }
      95             : 
      96             : static inline uchar *
      97             : fd_bn254_fp_tobytes_be_nm( uchar           buf[32],
      98      102396 :                            fd_bn254_fp_t * a ) {
      99      102396 :   fd_uint256_bswap( a, a );
     100      102396 :   fd_memcpy( buf, a, 32 );
     101      102396 :   return buf;
     102      102396 : }
     103             : 
     104             : static inline int
     105             : fd_bn254_fp_eq( fd_bn254_fp_t const * r,
     106       99795 :                 fd_bn254_fp_t const * a ) {
     107       99795 :   return fd_uint256_eq( r, a );
     108       99795 : }
     109             : 
     110             : static inline fd_bn254_fp_t *
     111             : fd_bn254_fp_from_mont( fd_bn254_fp_t * r,
     112      102396 :                        fd_bn254_fp_t const * a ) {
     113      102396 :   fiat_bn254_from_montgomery( r->limbs, a->limbs );
     114      102396 :   return r;
     115      102396 : }
     116             : 
     117             : static inline fd_bn254_fp_t *
     118             : fd_bn254_fp_to_mont( fd_bn254_fp_t * r,
     119      106842 :                      fd_bn254_fp_t const * a ) {
     120      106842 :   fiat_bn254_to_montgomery( r->limbs, a->limbs );
     121      106842 :   return r;
     122      106842 : }
     123             : 
     124             : static inline fd_bn254_fp_t *
     125             : fd_bn254_fp_neg_nm( fd_bn254_fp_t * r,
     126          57 :                     fd_bn254_fp_t const * a ) {
     127          57 :   if( FD_UNLIKELY( fd_bn254_fp_is_zero( a ) ) ) {
     128           0 :     return fd_bn254_fp_set_zero( r );
     129           0 :   }
     130             :   /* compute p-a */
     131         285 :   for( ulong i=0, cy=0; i<4; i++ ) {
     132         228 :     ulong p = fd_bn254_const_p->limbs[i];
     133         228 :     ulong b = a->limbs[i];
     134         228 :     b += cy;
     135         228 :     cy = (b < cy);
     136         228 :     cy += (p < b);
     137         228 :     r->limbs[i] = p - b;
     138         228 :   }
     139          57 :   return r;
     140          57 : }
     141             : 
     142             : static inline fd_bn254_fp_t *
     143             : fd_bn254_fp_set( fd_bn254_fp_t * r,
     144     4712148 :                  fd_bn254_fp_t const * a ) {
     145     4712148 :   r->limbs[0] = a->limbs[0];
     146     4712148 :   r->limbs[1] = a->limbs[1];
     147     4712148 :   r->limbs[2] = a->limbs[2];
     148     4712148 :   r->limbs[3] = a->limbs[3];
     149     4712148 :   return r;
     150     4712148 : }
     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    45088884 :                  fd_bn254_fp_t const * b ) {
     156    45088884 :   fiat_bn254_add( r->limbs, a->limbs, b->limbs );
     157    45088884 :   return r;
     158    45088884 : }
     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    28336116 :                  fd_bn254_fp_t const * b ) {
     164    28336116 :   fiat_bn254_sub( r->limbs, a->limbs, b->limbs );
     165    28336116 :   return r;
     166    28336116 : }
     167             : 
     168             : static inline fd_bn254_fp_t *
     169             : fd_bn254_fp_neg( fd_bn254_fp_t * r,
     170      191202 :                  fd_bn254_fp_t const * a ) {
     171      191202 :   fiat_bn254_opp( r->limbs, a->limbs );
     172      191202 :   return r;
     173      191202 : }
     174             : 
     175             : static inline fd_bn254_fp_t *
     176             : fd_bn254_fp_halve( fd_bn254_fp_t * r,
     177      188160 :                    fd_bn254_fp_t const * a ) {
     178      188160 :   int is_odd = r->limbs[0] & 0x1;
     179      188160 :   fd_uint256_add( r, a, is_odd ? fd_bn254_const_p : fd_bn254_const_zero );
     180      188160 :   r->limbs[0] = (r->limbs[0] >> 1) | (r->limbs[1] << 63);
     181      188160 :   r->limbs[1] = (r->limbs[1] >> 1) | (r->limbs[2] << 63);
     182      188160 :   r->limbs[2] = (r->limbs[2] >> 1) | (r->limbs[3] << 63);
     183      188160 :   r->limbs[3] = (r->limbs[3] >> 1);
     184      188160 :   return r;
     185      188160 : }
     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    11497167 :                  fd_bn254_fp_t const * a ) {
     192    11497167 :   return fd_bn254_fp_mul( r, a, a );
     193    11497167 : }
     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       33795 :                  fd_uint256_t const *     b ) {
     199       33795 :   fd_bn254_fp_set_one( r );
     200             : 
     201       33795 :   int i = 255;
     202      161469 :   while( !fd_uint256_bit( b, i) ) i--;
     203     8557641 :   for( ; i>=0; i--) {
     204     8523846 :     fd_bn254_fp_sqr( r, r );
     205     8523846 :     if( fd_uint256_bit( b, i ) ) {
     206     3687408 :       fd_bn254_fp_mul( r, r, a );
     207     3687408 :     }
     208     8523846 :   }
     209       33795 :   return r;
     210       33795 : }
     211             : 
     212             : static inline fd_bn254_fp_t *
     213             : fd_bn254_fp_inv( fd_bn254_fp_t * r,
     214        3753 :                   fd_bn254_fp_t const * a ) {
     215        3753 :   fd_uint256_t p_minus_2[1];
     216        3753 :   fd_bn254_fp_set( p_minus_2, fd_bn254_const_p );
     217        3753 :   p_minus_2->limbs[0] = p_minus_2->limbs[0] - 2UL;
     218        3753 :   return fd_bn254_fp_pow( r, a, p_minus_2 );
     219        3753 : }
     220             : 
     221             : static inline fd_bn254_fp_t *
     222             : fd_bn254_fp_sqrt( fd_bn254_fp_t * r,
     223       30042 :                   fd_bn254_fp_t const * a ) {
     224             :   /* Alg. 2, https://eprint.iacr.org/2012/685 */
     225             : 
     226       30042 :   fd_bn254_fp_t a0[1], a1[1];
     227             : 
     228       30042 :   fd_bn254_fp_pow( a1, a, fd_bn254_const_sqrt_exp );
     229             : 
     230       30042 :   fd_bn254_fp_sqr( a0, a1 );
     231       30042 :   fd_bn254_fp_mul( a0, a0, a );
     232       30042 :   if( FD_UNLIKELY( fd_bn254_fp_eq( a0, fd_bn254_const_p_minus_one_mont ) ) ) {
     233           0 :     return NULL;
     234           0 :   }
     235             : 
     236       30042 :   fd_bn254_fp_mul( r, a1, a );
     237       30042 :   return r;
     238       30042 : }