Line data    Source code

       1             : #include <stdint.h>
       2             : #include <s2n-bignum.h>
       3             : 
       4             : #include "fd_secp256r1_table.c"
       5             : 
       6             : /* Scalars */
       7             : 
       8             : static inline int
       9        6024 : fd_secp256r1_scalar_is_zero( fd_secp256r1_scalar_t const * a ) {
      10        6024 :   return fd_uint256_eq( a, fd_secp256r1_const_zero );
      11        6024 : }
      12             : 
      13             : static inline fd_secp256r1_scalar_t *
      14             : fd_secp256r1_scalar_frombytes( fd_secp256r1_scalar_t * r,
      15     3003033 :                                uchar const             in[ 32 ] ) {
      16     3003033 :   memcpy( r->buf, in, 32 );
      17     3003033 :   fd_uint256_bswap( r, r );
      18     3003033 :   if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_n )<0 ) ) {
      19     3003033 :     return r;
      20     3003033 :   };
      21           0 :   return NULL;
      22     3003033 : }
      23             : 
      24             : static inline fd_secp256r1_scalar_t *
      25             : fd_secp256r1_scalar_frombytes_positive( fd_secp256r1_scalar_t * r,
      26     3003021 :                                         uchar const             in[ 32 ] ) {
      27     3003021 :   memcpy( r->buf, in, 32 );
      28     3003021 :   fd_uint256_bswap( r, r );
      29     3003021 :   if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_n_m1_half )<=0 ) ) {
      30     3003015 :     return r;
      31     3003015 :   };
      32           6 :   return NULL;
      33     3003021 : }
      34             : 
      35             : static inline void
      36             : fd_secp256r1_scalar_from_digest( fd_secp256r1_scalar_t * r,
      37        3012 :                                  uchar const             in[ 32 ] ) {
      38        3012 :   memcpy( r->buf, in, 32 );
      39        3012 :   fd_uint256_bswap( r, r );
      40        3012 :   bignum_mod_n256_4( r->limbs, r->limbs );
      41        3012 : }
      42             : 
      43             : static inline fd_secp256r1_scalar_t *
      44             : fd_secp256r1_scalar_mul( fd_secp256r1_scalar_t *       r, 
      45             :                          fd_secp256r1_scalar_t const * a,
      46      306027 :                          fd_secp256r1_scalar_t const * b ) {
      47      306027 :   ulong t[ 8 ];
      48      306027 :   bignum_mul_4_8( t, (ulong *)a->limbs, (ulong *)b->limbs );
      49      306027 :   bignum_mod_n256( r->limbs, 8, t );
      50      306027 :   return r;
      51      306027 : }
      52             : 
      53             : static inline fd_secp256r1_scalar_t *
      54             : fd_secp256r1_scalar_inv( fd_secp256r1_scalar_t       * r, 
      55       33015 :                          fd_secp256r1_scalar_t const * a ) {
      56       33015 :   ulong t[ 12 ];
      57       33015 :   bignum_modinv( 4, r->limbs, (ulong *)a->limbs, (ulong *)fd_secp256r1_const_n[0].limbs, t );
      58       33015 :   return r;
      59       33015 : }
      60             : 
      61             : /* Field */
      62             : 
      63             : static inline fd_secp256r1_fp_t *
      64             : fd_secp256r1_fp_set( fd_secp256r1_fp_t * r,
      65       96060 :                      fd_secp256r1_fp_t const * a ) {
      66       96060 :   r->limbs[0] = a->limbs[0];
      67       96060 :   r->limbs[1] = a->limbs[1];
      68       96060 :   r->limbs[2] = a->limbs[2];
      69       96060 :   r->limbs[3] = a->limbs[3];
      70       96060 :   return r;
      71       96060 : }
      72             : 
      73             : static inline fd_secp256r1_fp_t *
      74             : fd_secp256r1_fp_frombytes( fd_secp256r1_fp_t * r,
      75     3033045 :                            uchar const             in[ 32 ] ) {
      76     3033045 :   memcpy( r->buf, in, 32 );
      77     3033045 :   fd_uint256_bswap( r, r );
      78     3033045 :   if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_p )<0 ) ) {
      79     3033042 :     return r;
      80     3033042 :   };
      81           3 :   return NULL;
      82     3033045 : }
      83             : 
      84             : static inline fd_secp256r1_fp_t *
      85             : fd_secp256r1_fp_sqrt( fd_secp256r1_fp_t *       r,
      86       63036 :                       fd_secp256r1_fp_t const * a ) {
      87             :   /* https://github.com/golang/go/blob/master/src/crypto/internal/fips140/nistec/p256.go#L656 */
      88       63036 :   fd_secp256r1_fp_t _t0[1], _t1[1];
      89       63036 :   ulong * t0 = _t0->limbs;
      90       63036 :   ulong * t1 = _t1->limbs;
      91       63036 :   ulong * x = (ulong *)a->limbs;
      92             : 
      93       63036 :         bignum_montsqr_p256( t0, x );
      94       63036 :         bignum_montmul_p256( t0, t0, x );
      95      126072 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<2; i++ ) bignum_montsqr_p256( t1, t1 );
      96       63036 :         bignum_montmul_p256( t0, t0, t1);
      97      252144 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<4; i++ ) bignum_montsqr_p256( t1, t1 );
      98       63036 :         bignum_montmul_p256( t0, t0, t1);
      99      504288 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<8; i++ ) bignum_montsqr_p256( t1, t1 );
     100       63036 :         bignum_montmul_p256( t0, t0, t1);
     101     1008576 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<16; i++ ) bignum_montsqr_p256( t1, t1 );
     102       63036 :         bignum_montmul_p256( t0, t0, t1);
     103     2080188 :         for( int i=0; i<32; i++ ) bignum_montsqr_p256( t0, t0 );
     104       63036 :         bignum_montmul_p256( t0, t0, x );
     105     6114492 :         for( int i=0; i<96; i++ ) bignum_montsqr_p256( t0, t0 );
     106       63036 :         bignum_montmul_p256( t0, t0, x );
     107     5988420 :         for( int i=0; i<94; i++ ) bignum_montsqr_p256( t0, t0 );
     108             : 
     109       63036 :   bignum_montsqr_p256( t1, t0 );
     110       63036 :   if( FD_UNLIKELY( !fd_uint256_eq( _t1, a ) ) ) {
     111           6 :     return NULL;
     112           6 :   }
     113             : 
     114       63030 :   return fd_secp256r1_fp_set( r, _t0 );
     115       63036 : }
     116             : 
     117             : /* Points */
     118             : 
     119             : static inline fd_secp256r1_point_t *
     120             : fd_secp256r1_point_frombytes( fd_secp256r1_point_t * r,
     121       33036 :                               uchar const            in[ 33 ] ) {
     122       33036 :   fd_secp256r1_fp_t y2[1], demont_y[1];
     123             : 
     124       33036 :   uchar sgn = in[0];
     125       33036 :   if( FD_UNLIKELY( sgn!=2U && sgn!=3U ) ) {
     126           3 :     return FD_SECP256R1_FAILURE;
     127           3 :   }
     128             : 
     129       33033 :   if( FD_UNLIKELY( !fd_secp256r1_fp_frombytes( r->x, in+1 ) ) ) {
     130           3 :     return FD_SECP256R1_FAILURE;
     131           3 :   }
     132             : 
     133       33030 :   bignum_tomont_p256( r->x->limbs, r->x->limbs );
     134             :   
     135             :   /* y^2 = x^3 + ax + b */
     136       33030 :   bignum_montsqr_p256( y2->limbs, r->x->limbs );
     137       33030 :   bignum_add_p256    ( y2->limbs, y2->limbs, (ulong *)fd_secp256r1_const_a_mont[0].limbs );
     138       33030 :   bignum_montmul_p256( y2->limbs, y2->limbs, r->x->limbs );
     139       33030 :   bignum_add_p256    ( y2->limbs, y2->limbs, (ulong *)fd_secp256r1_const_b_mont[0].limbs );
     140             : 
     141             :   /* y = sqrt(y^2) */
     142       33030 :   if( FD_UNLIKELY( !fd_secp256r1_fp_sqrt( r->y, y2 ) ) ) {
     143           3 :     return FD_SECP256R1_FAILURE;
     144           3 :   }
     145             : 
     146             :   /* choose y or -y */
     147       33027 :   bignum_demont_p256( demont_y->limbs, r->y->limbs );
     148       33027 :   ulong cond = (demont_y->limbs[0] % 2) != (sgn == 3U);
     149       33027 :   bignum_optneg_p256( r->y->limbs, cond, r->y->limbs );
     150             : 
     151       33027 :   fd_secp256r1_fp_set( r->z, fd_secp256r1_const_one_mont );
     152             : 
     153       33027 :   return r;
     154       33030 : }
     155             : 
     156             : static inline int
     157             : fd_secp256r1_point_eq_x( fd_secp256r1_point_t const *  p,
     158       33021 :                          fd_secp256r1_scalar_t const * r ) {
     159       33021 :   fd_secp256r1_fp_t affine_x[1];
     160       33021 :   fd_secp256r1_scalar_t * affine_x_mod_n = affine_x;
     161             : 
     162       33021 :   if( FD_UNLIKELY( fd_uint256_eq( p->z, fd_secp256r1_const_zero ) ) ) {
     163           3 :     return FD_SECP256R1_FAILURE;
     164           3 :   }
     165             : 
     166             :   /* x = demont(X / Z^2) mod n */
     167       33018 :   bignum_montinv_p256( affine_x->limbs, (ulong *)p->z->limbs );
     168       33018 :   bignum_montsqr_p256( affine_x->limbs, affine_x->limbs );
     169       33018 :   bignum_montmul_p256( affine_x->limbs, affine_x->limbs, (ulong *)p->x->limbs );
     170       33018 :   bignum_demont_p256( affine_x_mod_n->limbs, affine_x->limbs );
     171       33018 :   bignum_mod_n256_4 ( affine_x_mod_n->limbs, affine_x_mod_n->limbs );
     172             : 
     173       33018 :   if( FD_LIKELY( fd_uint256_eq( r, affine_x_mod_n ) ) ) {
     174       33015 :     return FD_SECP256R1_SUCCESS;
     175       33015 :   }
     176           3 :   return FD_SECP256R1_FAILURE;
     177       33018 : }
     178             : 
     179             : static inline void
     180             : fd_secp256r1_double_scalar_mul_base( fd_secp256r1_point_t *        r,
     181             :                                      fd_secp256r1_scalar_t const * u1,
     182             :                                      fd_secp256r1_point_t const *  a,
     183        3012 :                                      fd_secp256r1_scalar_t const * u2 ) {
     184             :   /* u1*G + u2*A */
     185        3012 :   ulong rtmp[ 8 ];
     186        3012 :   p256_scalarmulbase( rtmp, (ulong *)u1->limbs, 6, (ulong *)fd_secp256r1_base_point_table );
     187        3012 :   bignum_tomont_p256( rtmp, rtmp );
     188        3012 :   bignum_tomont_p256( rtmp+4, rtmp+4 );
     189             : 
     190        3012 :   p256_montjscalarmul( (ulong *)r, (ulong *)u2->limbs, (ulong *)a );
     191             : 
     192        3012 :   p256_montjmixadd( (ulong *)r, (ulong *)r, rtmp );
     193        3012 : }