Line data    Source code

       1             : #include <stdint.h>
       2             : #include "../../third_party/s2n-bignum/include/s2n-bignum.h"
       3             : 
       4             : /* On CPUs without ADX (mulx/adcx/adox), redirect the ADX-optimized
       5             :    s2n-bignum symbols to their _alt equivalents, which use only base
       6             :    x86-64 instructions and are functionally identical. */
       7             : #ifndef __ADX__
       8       46402 : #define bignum_demont_p256     bignum_demont_p256_alt
       9      206382 : #define bignum_mod_n256        bignum_mod_n256_alt
      10      354904 : #define bignum_montmul_p256    bignum_montmul_p256_alt
      11    11030564 : #define bignum_montsqr_p256    bignum_montsqr_p256_alt
      12      206382 : #define bignum_mul_4_8         bignum_mul_4_8_alt
      13       35210 : #define bignum_tomont_p256     bignum_tomont_p256_alt
      14           4 : #define p256_montjdouble       p256_montjdouble_alt
      15        3194 : #define p256_montjmixadd       p256_montjmixadd_alt
      16        3192 : #define p256_montjscalarmul    p256_montjscalarmul_alt
      17        3192 : #define p256_scalarmulbase     p256_scalarmulbase_alt
      18             : #endif
      19             : 
      20             : #include "fd_secp256r1_table.c"
      21             : 
      22             : /* p256_base_table_size is used for p256_scalarmulbase with a blocksize=6.
      23             :    B=2^(6-1)=32, there are 43 blocks i with 6*i<=256 (6*42=252<=256), and
      24             :    43 * 32 * 8 = 11008 entries.
      25             :    https://github.com/awslabs/s2n-bignum/blob/9061e8b76522beafa5ca020f3c8d99b23eba4fbc/x86/p256/p256_scalarmulbase.S#L14-L23 */
      26             : FD_STATIC_ASSERT( sizeof(fd_secp256r1_base_point_table)==(43UL*32UL*8UL)*sizeof(ulong), p256_base_table_size );
      27             : 
      28             : /* Scalars */
      29             : 
      30             : static inline int
      31        9576 : fd_secp256r1_scalar_is_zero( fd_secp256r1_scalar_t const * a ) {
      32        9576 :   return fd_uint256_eq( a, fd_secp256r1_const_zero );
      33        9576 : }
      34             : 
      35             : static inline fd_secp256r1_scalar_t *
      36             : fd_secp256r1_scalar_frombytes( fd_secp256r1_scalar_t * r,
      37     3006600 :                                uchar const             in[ 32 ] ) {
      38     3006600 :   memcpy( r->buf, in, 32 );
      39     3006600 :   fd_uint256_bswap( r, r );
      40     3006600 :   if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_n )<0 ) ) {
      41     3006597 :     return r;
      42     3006597 :   };
      43           3 :   return NULL;
      44     3006600 : }
      45             : 
      46             : static inline fd_secp256r1_scalar_t *
      47             : fd_secp256r1_scalar_frombytes_positive( fd_secp256r1_scalar_t * r,
      48     3003021 :                                         uchar const             in[ 32 ] ) {
      49     3003021 :   memcpy( r->buf, in, 32 );
      50     3003021 :   fd_uint256_bswap( r, r );
      51     3003021 :   if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_n_m1_half )<=0 ) ) {
      52     3003015 :     return r;
      53     3003015 :   };
      54           6 :   return NULL;
      55     3003021 : }
      56             : 
      57             : static inline void
      58             : fd_secp256r1_scalar_from_digest( fd_secp256r1_scalar_t * r,
      59        4785 :                                  uchar const             in[ 32 ] ) {
      60        4785 :   memcpy( r->buf, in, 32 );
      61        4785 :   fd_uint256_bswap( r, r );
      62        4785 :   bignum_mod_n256_4( r->limbs, r->limbs );
      63        4785 : }
      64             : 
      65             : static inline fd_secp256r1_scalar_t *
      66             : fd_secp256r1_scalar_mul( fd_secp256r1_scalar_t *       r,
      67             :                          fd_secp256r1_scalar_t const * a,
      68      309573 :                          fd_secp256r1_scalar_t const * b ) {
      69      309573 :   ulong t[ 8 ];
      70      309573 :   bignum_mul_4_8( t, (ulong *)a->limbs, (ulong *)b->limbs );
      71      309573 :   bignum_mod_n256( r->limbs, 8, t );
      72      309573 :   return r;
      73      309573 : }
      74             : 
      75             : static inline fd_secp256r1_scalar_t *
      76             : fd_secp256r1_scalar_inv( fd_secp256r1_scalar_t       * r,
      77       34788 :                          fd_secp256r1_scalar_t const * a ) {
      78       34788 :   ulong t[ 12 ];
      79       34788 :   bignum_modinv( 4, r->limbs, (ulong *)a->limbs, (ulong *)fd_secp256r1_const_n[0].limbs, t );
      80       34788 :   return r;
      81       34788 : }
      82             : 
      83             : /* Field */
      84             : 
      85             : static inline fd_secp256r1_fp_t *
      86             : fd_secp256r1_fp_set( fd_secp256r1_fp_t * r,
      87       99618 :                      fd_secp256r1_fp_t const * a ) {
      88       99618 :   r->limbs[0] = a->limbs[0];
      89       99618 :   r->limbs[1] = a->limbs[1];
      90       99618 :   r->limbs[2] = a->limbs[2];
      91       99618 :   r->limbs[3] = a->limbs[3];
      92       99618 :   return r;
      93       99618 : }
      94             : 
      95             : /* r = -a, Montgomery domain */
      96             : static inline fd_secp256r1_fp_t *
      97             : fd_secp256r1_fp_neg( fd_secp256r1_fp_t *       r,
      98           3 :                      fd_secp256r1_fp_t const * a ) {
      99           3 :   bignum_optneg_p256( r->limbs, 1UL, (ulong *)a->limbs );
     100           3 :   return r;
     101           3 : }
     102             : 
     103             : static inline fd_secp256r1_fp_t *
     104             : fd_secp256r1_fp_frombytes( fd_secp256r1_fp_t * r,
     105     3043263 :                            uchar const             in[ 32 ] ) {
     106     3043263 :   memcpy( r->buf, in, 32 );
     107     3043263 :   fd_uint256_bswap( r, r );
     108     3043263 :   if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_p )<0 ) ) {
     109     3043254 :     return r;
     110     3043254 :   };
     111           9 :   return NULL;
     112     3043263 : }
     113             : 
     114             : static inline fd_secp256r1_fp_t *
     115             : fd_secp256r1_fp_sqrt( fd_secp256r1_fp_t *       r,
     116       64815 :                       fd_secp256r1_fp_t const * a ) {
     117             :   /* https://github.com/golang/go/blob/master/src/crypto/internal/fips140/nistec/p256.go#L656 */
     118       64815 :   fd_secp256r1_fp_t _t0[1], _t1[1];
     119       64815 :   ulong * t0 = _t0->limbs;
     120       64815 :   ulong * t1 = _t1->limbs;
     121       64815 :   ulong * x = (ulong *)a->limbs;
     122             : 
     123       64815 :         bignum_montsqr_p256( t0, x );
     124       64815 :         bignum_montmul_p256( t0, t0, x );
     125      129630 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<2; i++ ) bignum_montsqr_p256( t1, t1 );
     126       64815 :         bignum_montmul_p256( t0, t0, t1);
     127      259260 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<4; i++ ) bignum_montsqr_p256( t1, t1 );
     128       64815 :         bignum_montmul_p256( t0, t0, t1);
     129      518520 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<8; i++ ) bignum_montsqr_p256( t1, t1 );
     130       64815 :         bignum_montmul_p256( t0, t0, t1);
     131     1037040 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<16; i++ ) bignum_montsqr_p256( t1, t1 );
     132       64815 :         bignum_montmul_p256( t0, t0, t1);
     133     2138895 :         for( int i=0; i<32; i++ ) bignum_montsqr_p256( t0, t0 );
     134       64815 :         bignum_montmul_p256( t0, t0, x );
     135     6287055 :         for( int i=0; i<96; i++ ) bignum_montsqr_p256( t0, t0 );
     136       64815 :         bignum_montmul_p256( t0, t0, x );
     137     6157425 :         for( int i=0; i<94; i++ ) bignum_montsqr_p256( t0, t0 );
     138             : 
     139       64815 :   bignum_montsqr_p256( t1, t0 );
     140       64815 :   if( FD_UNLIKELY( !fd_uint256_eq( _t1, a ) ) ) {
     141           6 :     return NULL;
     142           6 :   }
     143             : 
     144       64809 :   return fd_secp256r1_fp_set( r, _t0 );
     145       64815 : }
     146             : 
     147             : /* Points */
     148             : 
     149             : static inline int
     150        4224 : fd_secp256r1_point_validate_uncompressed( uchar const in[ 65 ] ) {
     151        4224 :   if( FD_UNLIKELY( in[ 0 ]!=0x04U ) ) return FD_SECP256R1_FAILURE;
     152             : 
     153        4221 :   fd_secp256r1_fp_t x[1], y[1], lhs[1], rhs[1];
     154        4221 :   if( FD_UNLIKELY( !fd_secp256r1_fp_frombytes( x, in+1  ) ) ) return FD_SECP256R1_FAILURE;
     155        4218 :   if( FD_UNLIKELY( !fd_secp256r1_fp_frombytes( y, in+33 ) ) ) return FD_SECP256R1_FAILURE;
     156             : 
     157        4215 :   bignum_tomont_p256( x->limbs, x->limbs );
     158        4215 :   bignum_tomont_p256( y->limbs, y->limbs );
     159             : 
     160             :   /* Validate y^2 = x^3 + ax + b. */
     161        4215 :   bignum_montsqr_p256( lhs->limbs, y->limbs );
     162        4215 :   bignum_montsqr_p256( rhs->limbs, x->limbs );
     163        4215 :   bignum_add_p256    ( rhs->limbs, rhs->limbs, (ulong *)fd_secp256r1_const_a_mont[0].limbs );
     164        4215 :   bignum_montmul_p256( rhs->limbs, rhs->limbs, x->limbs );
     165        4215 :   bignum_add_p256    ( rhs->limbs, rhs->limbs, (ulong *)fd_secp256r1_const_b_mont[0].limbs );
     166        4215 :   return fd_uint256_eq( lhs, rhs );
     167        4218 : }
     168             : 
     169             : static inline fd_secp256r1_point_t *
     170             : fd_secp256r1_point_frombytes( fd_secp256r1_point_t * r,
     171       34815 :                               uchar const            in[ 33 ] ) {
     172       34815 :   fd_secp256r1_fp_t y2[1], demont_y[1];
     173             : 
     174       34815 :   uchar sgn = in[0];
     175       34815 :   if( FD_UNLIKELY( sgn!=2U && sgn!=3U ) ) {
     176           3 :     return FD_SECP256R1_FAILURE;
     177           3 :   }
     178             : 
     179       34812 :   if( FD_UNLIKELY( !fd_secp256r1_fp_frombytes( r->x, in+1 ) ) ) {
     180           3 :     return FD_SECP256R1_FAILURE;
     181           3 :   }
     182             : 
     183       34809 :   bignum_tomont_p256( r->x->limbs, r->x->limbs );
     184             : 
     185             :   /* y^2 = x^3 + ax + b */
     186       34809 :   bignum_montsqr_p256( y2->limbs, r->x->limbs );
     187       34809 :   bignum_add_p256    ( y2->limbs, y2->limbs, (ulong *)fd_secp256r1_const_a_mont[0].limbs );
     188       34809 :   bignum_montmul_p256( y2->limbs, y2->limbs, r->x->limbs );
     189       34809 :   bignum_add_p256    ( y2->limbs, y2->limbs, (ulong *)fd_secp256r1_const_b_mont[0].limbs );
     190             : 
     191             :   /* y = sqrt(y^2) */
     192       34809 :   if( FD_UNLIKELY( !fd_secp256r1_fp_sqrt( r->y, y2 ) ) ) {
     193           3 :     return FD_SECP256R1_FAILURE;
     194           3 :   }
     195             : 
     196             :   /* choose y or -y */
     197       34806 :   bignum_demont_p256( demont_y->limbs, r->y->limbs );
     198       34806 :   ulong cond = (demont_y->limbs[0] % 2) != (sgn == 3U);
     199       34806 :   bignum_optneg_p256( r->y->limbs, cond, r->y->limbs );
     200             : 
     201       34806 :   fd_secp256r1_fp_set( r->z, fd_secp256r1_const_one_mont );
     202             : 
     203       34806 :   return r;
     204       34809 : }
     205             : 
     206             : static inline int
     207             : fd_secp256r1_point_eq_x( fd_secp256r1_point_t const *  p,
     208       34800 :                          fd_secp256r1_scalar_t const * r ) {
     209       34800 :   fd_secp256r1_fp_t affine_x[1];
     210       34800 :   fd_secp256r1_scalar_t * affine_x_mod_n = affine_x;
     211             : 
     212       34800 :   if( FD_UNLIKELY( fd_uint256_eq( p->z, fd_secp256r1_const_zero ) ) ) {
     213           3 :     return FD_SECP256R1_FAILURE;
     214           3 :   }
     215             : 
     216             :   /* x = demont(X / Z^2) mod n */
     217       34797 :   bignum_montinv_p256( affine_x->limbs, (ulong *)p->z->limbs );
     218       34797 :   bignum_montsqr_p256( affine_x->limbs, affine_x->limbs );
     219       34797 :   bignum_montmul_p256( affine_x->limbs, affine_x->limbs, (ulong *)p->x->limbs );
     220       34797 :   bignum_demont_p256( affine_x_mod_n->limbs, affine_x->limbs );
     221       34797 :   bignum_mod_n256_4 ( affine_x_mod_n->limbs, affine_x_mod_n->limbs );
     222             : 
     223       34797 :   if( FD_LIKELY( fd_uint256_eq( r, affine_x_mod_n ) ) ) {
     224       34788 :     return FD_SECP256R1_SUCCESS;
     225       34788 :   }
     226           9 :   return FD_SECP256R1_FAILURE;
     227       34797 : }
     228             : 
     229             : /* Given the projective point `r` and the affine point `p`,
     230             :    returns 1 if they are equal and 0 otherwise.
     231             :    Assumes that `p` X and Y coordinates are in Montgomery domain. */
     232             : static inline int
     233             : fd_secp256r1_point_eq_mixed( fd_secp256r1_point_t const * a,
     234        4806 :                              ulong                const   b[ 8 ] ) {
     235        4806 :   fd_secp256r1_fp_t x[1], y[1];
     236        4806 :   fd_memcpy( x->limbs, b+0, sizeof(fd_secp256r1_fp_t) );
     237        4806 :   fd_memcpy( y->limbs, b+4, sizeof(fd_secp256r1_fp_t) );
     238             :   /* Indicates if the affine point is zero. */
     239        4806 :   int is_zero = fd_uint256_eq( x, fd_secp256r1_const_zero ) & fd_uint256_eq( y, fd_secp256r1_const_zero );
     240             : 
     241             :   /* Easy cases */
     242        4806 :   if( FD_UNLIKELY( fd_uint256_eq( a->z, fd_secp256r1_const_zero ) ) ) {
     243           6 :     return is_zero;
     244           6 :   }
     245        4800 :   if( FD_UNLIKELY( is_zero ) ) {
     246           0 :     return 0;
     247           0 :   }
     248             : 
     249        4800 :   fd_secp256r1_fp_t z1z1[1];
     250        4800 :   bignum_montsqr_p256( z1z1->limbs, (ulong *)a->z->limbs );
     251             : 
     252        4800 :   fd_secp256r1_fp_t temp[1];
     253        4800 :   bignum_montmul_p256( temp->limbs, (ulong *)x->limbs, z1z1->limbs );
     254             : 
     255        4800 :   if( FD_UNLIKELY( fd_uint256_eq( a->x, temp ) ) ) {
     256          15 :     bignum_montmul_p256( temp->limbs, z1z1->limbs,  (ulong *)a->z->limbs );
     257          15 :     bignum_montmul_p256( temp->limbs, temp->limbs, (ulong *)y->limbs );
     258          15 :     return fd_uint256_eq( a->y, temp );
     259        4785 :   } else {
     260        4785 :     return 0;
     261        4785 :   }
     262        4800 : }
     263             : 
     264             : /* Adds projective point `a` and affine-Montgomery point `b`, both
     265             :    in Montgomery domain. Handles identity elements and the equal-point
     266             :    (doubling) case. */
     267             : static inline void
     268             : fd_secp256r1_point_add_mixed( fd_secp256r1_point_t *       r,
     269             :                               fd_secp256r1_point_t const * a,
     270        4803 :                               ulong                        b[ 8 ] ) {
     271        4803 :   int b_is_zero = fd_uint256_eq( (fd_uint256_t const *)(b+0), fd_secp256r1_const_zero ) &
     272        4803 :                   fd_uint256_eq( (fd_uint256_t const *)(b+4), fd_secp256r1_const_zero );
     273             : 
     274        4803 :   if( FD_UNLIKELY( b_is_zero ) ) {
     275             :     /* a + 0 = a */
     276           6 :     if( r != a ) fd_memcpy( r, a, sizeof(fd_secp256r1_point_t) );
     277           6 :     return;
     278           6 :   }
     279             : 
     280        4797 :   if( FD_UNLIKELY( fd_secp256r1_point_eq_mixed( a, b ) ) ) {
     281           6 :     p256_montjdouble( (ulong *)r, (ulong *)a );
     282        4791 :   } else {
     283             :     /* Also handles a == 0 and a == -b */
     284        4791 :     p256_montjmixadd( (ulong *)r, (ulong *)a, b );
     285        4791 :   }
     286        4797 : }
     287             : 
     288             : static inline void
     289             : fd_secp256r1_double_scalar_mul_base( fd_secp256r1_point_t *        r,
     290             :                                      fd_secp256r1_scalar_t const * u1,
     291             :                                      fd_secp256r1_point_t const *  a,
     292        4788 :                                      fd_secp256r1_scalar_t const * u2 ) {
     293             :   /* u1*G */
     294        4788 :   ulong rtmp[ 8 ];
     295        4788 :   p256_scalarmulbase( rtmp, (ulong *)u1->limbs, 6, (ulong *)fd_secp256r1_base_point_table );
     296        4788 :   bignum_tomont_p256( rtmp, rtmp );
     297        4788 :   bignum_tomont_p256( rtmp+4, rtmp+4 );
     298             : 
     299             :   /* u2*A */
     300        4788 :   p256_montjscalarmul( (ulong *)r, (ulong *)u2->limbs, (ulong *)a );
     301             : 
     302             :   /* u1*G + u2*A */
     303        4788 :   fd_secp256r1_point_add_mixed( r, r, rtmp );
     304        4788 : }