Line data    Source code

       1             : #include "./fd_bn254.h"
       2             : #include "../fiat-crypto/bn254_64.c"
       3             : 
       4             : /* Fp = base field */
       5             : 
       6        2016 : #define FLAG_INF  ((uchar)(1 << 6))
       7        1938 : #define FLAG_NEG  ((uchar)(1 << 7))
       8        1589 : #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         264 : fd_bn254_fp_is_neg_nm( fd_bn254_fp_t * x ) {
      64         264 :   return fd_uint256_cmp( x, fd_bn254_const_p_minus_one_half ) > 0;
      65         264 : }
      66             : 
      67             : static inline fd_bn254_fp_t *
      68             : fd_bn254_fp_frombytes_nm( fd_bn254_fp_t * r,
      69             :                           uchar const     buf[32],
      70             :                           int             big_endian,
      71             :                           int *           is_inf,
      72        6014 :                           int *           is_neg ) {
      73             :   /* Flags (optional) */
      74        6014 :   if( is_inf != NULL /* && is_neg != NULL */ ) {
      75        1912 :     *is_inf = !!(buf[ big_endian ? 0 : 31 ] & FLAG_INF);
      76        1912 :     *is_neg = !!(buf[ big_endian ? 0 : 31 ] & FLAG_NEG);
      77             :     /* If both flags are set (bit 6, 7), return error.
      78             :        https://github.com/arkworks-rs/algebra/blob/v0.4.2/ec/src/models/short_weierstrass/serialization_flags.rs#L75 */
      79        1912 :     if( FD_UNLIKELY( *is_inf && *is_neg ) ) {
      80         326 :       return NULL;
      81         326 :     }
      82        1912 :   }
      83             : 
      84        5688 :   fd_memcpy( r, buf, 32 );
      85        5695 :   if( FD_BIG_ENDIAN_LIKELY( big_endian ) ) {
      86        5695 :     fd_uint256_bswap( r, r );
      87        5695 :   }
      88        5688 :   if( is_inf != NULL ) {
      89        1589 :     r->buf[ 31 ] &= FLAG_MASK;
      90        1589 :   }
      91             : 
      92             :   /* Field element */
      93        5688 :   if( FD_UNLIKELY( fd_uint256_cmp( r, fd_bn254_const_p ) >= 0 ) ) {
      94        1787 :     return NULL;
      95        1787 :   }
      96        3901 :   return r;
      97        5688 : }
      98             : 
      99             : static inline uchar *
     100             : fd_bn254_fp_tobytes_nm( uchar           buf[32],
     101             :                         fd_bn254_fp_t * a,
     102        1127 :                         int             big_endian ) {
     103        1127 :   if( FD_BIG_ENDIAN_LIKELY( big_endian ) ) {
     104        1127 :     fd_uint256_bswap( a, a );
     105        1127 :   }
     106        1127 :   fd_memcpy( buf, a, 32 );
     107        1127 :   return buf;
     108        1127 : }
     109             : 
     110             : static inline int
     111             : fd_bn254_fp_eq( fd_bn254_fp_t const * r,
     112       22356 :                 fd_bn254_fp_t const * a ) {
     113       22356 :   return fd_uint256_eq( r, a );
     114       22356 : }
     115             : 
     116             : static inline fd_bn254_fp_t *
     117             : fd_bn254_fp_from_mont( fd_bn254_fp_t * r,
     118         747 :                        fd_bn254_fp_t const * a ) {
     119         747 :   fiat_bn254_from_montgomery( r->limbs, a->limbs );
     120         747 :   return r;
     121         747 : }
     122             : 
     123             : static inline fd_bn254_fp_t *
     124             : fd_bn254_fp_to_mont( fd_bn254_fp_t * r,
     125        2298 :                      fd_bn254_fp_t const * a ) {
     126        2298 :   fiat_bn254_to_montgomery( r->limbs, a->limbs );
     127        2298 :   return r;
     128        2298 : }
     129             : 
     130             : static inline fd_bn254_fp_t *
     131             : fd_bn254_fp_neg_nm( fd_bn254_fp_t * r,
     132          75 :                     fd_bn254_fp_t const * a ) {
     133          75 :   if( FD_UNLIKELY( fd_bn254_fp_is_zero( a ) ) ) {
     134           2 :     return fd_bn254_fp_set_zero( r );
     135           2 :   }
     136             :   /* compute p-a */
     137         365 :   for( ulong i=0, cy=0; i<4; i++ ) {
     138         292 :     ulong p = fd_bn254_const_p->limbs[i];
     139         292 :     ulong b = a->limbs[i];
     140         292 :     b += cy;
     141         292 :     cy = (b < cy);
     142         292 :     cy += (p < b);
     143         292 :     r->limbs[i] = p - b;
     144         292 :   }
     145          73 :   return r;
     146          75 : }
     147             : 
     148             : static inline fd_bn254_fp_t *
     149             : fd_bn254_fp_set( fd_bn254_fp_t * r,
     150      298801 :                  fd_bn254_fp_t const * a ) {
     151      298801 :   r->limbs[0] = a->limbs[0];
     152      298801 :   r->limbs[1] = a->limbs[1];
     153      298801 :   r->limbs[2] = a->limbs[2];
     154      298801 :   r->limbs[3] = a->limbs[3];
     155      298801 :   return r;
     156      298801 : }
     157             : 
     158             : INLINE fd_bn254_fp_t *
     159             : fd_bn254_fp_add( fd_bn254_fp_t * r,
     160             :                  fd_bn254_fp_t const * a,
     161     2072163 :                  fd_bn254_fp_t const * b ) {
     162     2072163 :   fiat_bn254_add( r->limbs, a->limbs, b->limbs );
     163     2072163 :   return r;
     164     2072163 : }
     165             : 
     166             : INLINE fd_bn254_fp_t *
     167             : fd_bn254_fp_sub( fd_bn254_fp_t * r,
     168             :                  fd_bn254_fp_t const * a,
     169     1289817 :                  fd_bn254_fp_t const * b ) {
     170     1289817 :   fiat_bn254_sub( r->limbs, a->limbs, b->limbs );
     171     1289817 :   return r;
     172     1289817 : }
     173             : 
     174             : INLINE fd_bn254_fp_t *
     175             : fd_bn254_fp_neg( fd_bn254_fp_t * r,
     176       22481 :                  fd_bn254_fp_t const * a ) {
     177       22481 :   fiat_bn254_opp( r->limbs, a->limbs );
     178       22481 :   return r;
     179       22481 : }
     180             : 
     181             : static inline fd_bn254_fp_t *
     182             : fd_bn254_fp_halve( fd_bn254_fp_t * r,
     183       21212 :                    fd_bn254_fp_t const * a ) {
     184       21212 :   int is_odd = a->limbs[0] & 0x1;
     185       21212 :   fd_uint256_add( r, a, is_odd ? fd_bn254_const_p : fd_bn254_const_zero );
     186       21212 :   r->limbs[0] = (r->limbs[0] >> 1) | (r->limbs[1] << 63);
     187       21212 :   r->limbs[1] = (r->limbs[1] >> 1) | (r->limbs[2] << 63);
     188       21212 :   r->limbs[2] = (r->limbs[2] >> 1) | (r->limbs[3] << 63);
     189       21212 :   r->limbs[3] = (r->limbs[3] >> 1);
     190       21212 :   return r;
     191       21212 : }
     192             : 
     193             : FD_UINT256_FP_MUL_IMPL(fd_bn254_fp, fd_bn254_const_p, fd_bn254_const_p_inv)
     194             : 
     195             : static inline fd_bn254_fp_t *
     196             : fd_bn254_fp_sqr( fd_bn254_fp_t * r,
     197      335533 :                  fd_bn254_fp_t const * a ) {
     198      335533 :   return fd_bn254_fp_mul( r, a, a );
     199      335533 : }
     200             : 
     201             : fd_bn254_fp_t *
     202             : fd_bn254_fp_pow( fd_bn254_fp_t * restrict r,
     203             :                  fd_bn254_fp_t const *    a,
     204         753 :                  fd_uint256_t const *     b ) {
     205         753 :   fd_bn254_fp_set_one( r );
     206             : 
     207         753 :   int i = 255;
     208        2475 :   while( !fd_uint256_bit( b, i) ) i--;
     209      179689 :   for( ; i>=0; i--) {
     210      178936 :     fd_bn254_fp_sqr( r, r );
     211      178936 :     if( fd_uint256_bit( b, i ) ) {
     212       78622 :       fd_bn254_fp_mul( r, r, a );
     213       78622 :     }
     214      178936 :   }
     215         753 :   return r;
     216         753 : }
     217             : 
     218             : static inline fd_bn254_fp_t *
     219             : fd_bn254_fp_inv( fd_bn254_fp_t * r,
     220         644 :                   fd_bn254_fp_t const * a ) {
     221         644 :   fd_uint256_t p_minus_2[1];
     222         644 :   fd_bn254_fp_set( p_minus_2, fd_bn254_const_p );
     223         644 :   p_minus_2->limbs[0] = p_minus_2->limbs[0] - 2UL;
     224         644 :   return fd_bn254_fp_pow( r, a, p_minus_2 );
     225         644 : }
     226             : 
     227             : static inline fd_bn254_fp_t *
     228             : fd_bn254_fp_sqrt( fd_bn254_fp_t * r,
     229         108 :                   fd_bn254_fp_t const * a ) {
     230             :   /* Alg. 2, https://eprint.iacr.org/2012/685 */
     231             : 
     232         108 :   fd_bn254_fp_t a0[1], a1[1];
     233             : 
     234         108 :   fd_bn254_fp_pow( a1, a, fd_bn254_const_sqrt_exp );
     235             : 
     236         108 :   fd_bn254_fp_sqr( a0, a1 );
     237         108 :   fd_bn254_fp_mul( a0, a0, a );
     238         108 :   if( FD_UNLIKELY( fd_bn254_fp_eq( a0, fd_bn254_const_p_minus_one_mont ) ) ) {
     239           2 :     return NULL;
     240           2 :   }
     241             : 
     242         106 :   fd_bn254_fp_mul( r, a1, a );
     243         106 :   return r;
     244         108 : }