Line data    Source code

       1             : #include "./fd_bn254.h"
       2             : #include "../fiat-crypto/bn254_64.c"
       3             : 
       4             : /* Fp = base field */
       5             : 
       6      158862 : #define FLAG_INF  ((uchar)(1 << 6))
       7      158736 : #define FLAG_NEG  ((uchar)(1 << 7))
       8       98670 : #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       93372 : fd_bn254_fp_is_neg_nm( fd_bn254_fp_t * x ) {
      64       93372 :   return fd_uint256_cmp( x, fd_bn254_const_p_minus_one_half ) > 0;
      65       93372 : }
      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      229893 :                           int *           is_neg ) {
      73             :   /* Flags (optional) */
      74      229893 :   if( is_inf != NULL /* && is_neg != NULL */ ) {
      75       98670 :     *is_inf = !!(buf[ big_endian ? 0 : 31 ] & FLAG_INF);
      76       98670 :     *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       98670 :     if( FD_UNLIKELY( *is_inf && *is_neg ) ) {
      80           0 :       return NULL;
      81           0 :     }
      82       98670 :   }
      83             : 
      84      229893 :   fd_memcpy( r, buf, 32 );
      85      229893 :   if( FD_BIG_ENDIAN_LIKELY( big_endian ) ) {
      86        1488 :     fd_uint256_bswap( r, r );
      87        1488 :   }
      88      229893 :   if( is_inf != NULL ) {
      89       98670 :     r->buf[ 31 ] &= FLAG_MASK;
      90       98670 :   }
      91             : 
      92             :   /* Field element */
      93      229893 :   if( FD_UNLIKELY( fd_uint256_cmp( r, fd_bn254_const_p ) >= 0 ) ) {
      94           0 :     return NULL;
      95           0 :   }
      96      229893 :   return r;
      97      229893 : }
      98             : 
      99             : static inline uchar *
     100             : fd_bn254_fp_tobytes_nm( uchar           buf[32],
     101             :                         fd_bn254_fp_t * a,
     102      170505 :                         int             big_endian ) {
     103      170505 :   if( FD_BIG_ENDIAN_LIKELY( big_endian ) ) {
     104         612 :     fd_uint256_bswap( a, a );
     105         612 :   }
     106      170505 :   fd_memcpy( buf, a, 32 );
     107      170505 :   return buf;
     108      170505 : }
     109             : 
     110             : static inline int
     111             : fd_bn254_fp_eq( fd_bn254_fp_t const * r,
     112      202125 :                 fd_bn254_fp_t const * a ) {
     113      202125 :   return fd_uint256_eq( r, a );
     114      202125 : }
     115             : 
     116             : static inline fd_bn254_fp_t *
     117             : fd_bn254_fp_from_mont( fd_bn254_fp_t * r,
     118       43947 :                        fd_bn254_fp_t const * a ) {
     119       43947 :   fiat_bn254_from_montgomery( r->limbs, a->limbs );
     120       43947 :   return r;
     121       43947 : }
     122             : 
     123             : static inline fd_bn254_fp_t *
     124             : fd_bn254_fp_to_mont( fd_bn254_fp_t * r,
     125       49335 :                      fd_bn254_fp_t const * a ) {
     126       49335 :   fiat_bn254_to_montgomery( r->limbs, a->limbs );
     127       49335 :   return r;
     128       49335 : }
     129             : 
     130             : static inline fd_bn254_fp_t *
     131             : fd_bn254_fp_neg_nm( fd_bn254_fp_t * r,
     132        6129 :                     fd_bn254_fp_t const * a ) {
     133        6129 :   if( FD_UNLIKELY( fd_bn254_fp_is_zero( a ) ) ) {
     134           0 :     return fd_bn254_fp_set_zero( r );
     135           0 :   }
     136             :   /* compute p-a */
     137       30645 :   for( ulong i=0, cy=0; i<4; i++ ) {
     138       24516 :     ulong p = fd_bn254_const_p->limbs[i];
     139       24516 :     ulong b = a->limbs[i];
     140       24516 :     b += cy;
     141       24516 :     cy = (b < cy);
     142       24516 :     cy += (p < b);
     143       24516 :     r->limbs[i] = p - b;
     144       24516 :   }
     145        6129 :   return r;
     146        6129 : }
     147             : 
     148             : static inline fd_bn254_fp_t *
     149             : fd_bn254_fp_set( fd_bn254_fp_t * r,
     150     5151687 :                  fd_bn254_fp_t const * a ) {
     151     5151687 :   r->limbs[0] = a->limbs[0];
     152     5151687 :   r->limbs[1] = a->limbs[1];
     153     5151687 :   r->limbs[2] = a->limbs[2];
     154     5151687 :   r->limbs[3] = a->limbs[3];
     155     5151687 :   return r;
     156     5151687 : }
     157             : 
     158             : static inline fd_bn254_fp_t *
     159             : fd_bn254_fp_add( fd_bn254_fp_t * r,
     160             :                  fd_bn254_fp_t const * a,
     161    53412705 :                  fd_bn254_fp_t const * b ) {
     162    53412705 :   fiat_bn254_add( r->limbs, a->limbs, b->limbs );
     163    53412705 :   return r;
     164    53412705 : }
     165             : 
     166             : static inline fd_bn254_fp_t *
     167             : fd_bn254_fp_sub( fd_bn254_fp_t * r,
     168             :                  fd_bn254_fp_t const * a,
     169    32999721 :                  fd_bn254_fp_t const * b ) {
     170    32999721 :   fiat_bn254_sub( r->limbs, a->limbs, b->limbs );
     171    32999721 :   return r;
     172    32999721 : }
     173             : 
     174             : static inline fd_bn254_fp_t *
     175             : fd_bn254_fp_neg( fd_bn254_fp_t * r,
     176      225789 :                  fd_bn254_fp_t const * a ) {
     177      225789 :   fiat_bn254_opp( r->limbs, a->limbs );
     178      225789 :   return r;
     179      225789 : }
     180             : 
     181             : static inline fd_bn254_fp_t *
     182             : fd_bn254_fp_halve( fd_bn254_fp_t * r,
     183      224256 :                    fd_bn254_fp_t const * a ) {
     184      224256 :   int is_odd = a->limbs[0] & 0x1;
     185      224256 :   fd_uint256_add( r, a, is_odd ? fd_bn254_const_p : fd_bn254_const_zero );
     186      224256 :   r->limbs[0] = (r->limbs[0] >> 1) | (r->limbs[1] << 63);
     187      224256 :   r->limbs[1] = (r->limbs[1] >> 1) | (r->limbs[2] << 63);
     188      224256 :   r->limbs[2] = (r->limbs[2] >> 1) | (r->limbs[3] << 63);
     189      224256 :   r->limbs[3] = (r->limbs[3] >> 1);
     190      224256 :   return r;
     191      224256 : }
     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     9853959 :                  fd_bn254_fp_t const * a ) {
     198     9853959 :   return fd_bn254_fp_mul( r, a, a );
     199     9853959 : }
     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       34230 :                  fd_uint256_t const *     b ) {
     205       34230 :   fd_bn254_fp_set_one( r );
     206             : 
     207       34230 :   int i = 255;
     208      162876 :   while( !fd_uint256_bit( b, i) ) i--;
     209     8668464 :   for( ; i>=0; i--) {
     210     8634234 :     fd_bn254_fp_sqr( r, r );
     211     8634234 :     if( fd_uint256_bit( b, i ) ) {
     212     3735207 :       fd_bn254_fp_mul( r, r, a );
     213     3735207 :     }
     214     8634234 :   }
     215       34230 :   return r;
     216       34230 : }
     217             : 
     218             : static inline fd_bn254_fp_t *
     219             : fd_bn254_fp_inv( fd_bn254_fp_t * r,
     220        4137 :                   fd_bn254_fp_t const * a ) {
     221        4137 :   fd_uint256_t p_minus_2[1];
     222        4137 :   fd_bn254_fp_set( p_minus_2, fd_bn254_const_p );
     223        4137 :   p_minus_2->limbs[0] = p_minus_2->limbs[0] - 2UL;
     224        4137 :   return fd_bn254_fp_pow( r, a, p_minus_2 );
     225        4137 : }
     226             : 
     227             : static inline fd_bn254_fp_t *
     228             : fd_bn254_fp_sqrt( fd_bn254_fp_t * r,
     229       30093 :                   fd_bn254_fp_t const * a ) {
     230             :   /* Alg. 2, https://eprint.iacr.org/2012/685 */
     231             : 
     232       30093 :   fd_bn254_fp_t a0[1], a1[1];
     233             : 
     234       30093 :   fd_bn254_fp_pow( a1, a, fd_bn254_const_sqrt_exp );
     235             : 
     236       30093 :   fd_bn254_fp_sqr( a0, a1 );
     237       30093 :   fd_bn254_fp_mul( a0, a0, a );
     238       30093 :   if( FD_UNLIKELY( fd_bn254_fp_eq( a0, fd_bn254_const_p_minus_one_mont ) ) ) {
     239           0 :     return NULL;
     240           0 :   }
     241             : 
     242       30093 :   fd_bn254_fp_mul( r, a1, a );
     243       30093 :   return r;
     244       30093 : }