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        7083 : fd_secp256r1_scalar_is_zero( fd_secp256r1_scalar_t const * a ) {
      10        7083 :   return fd_uint256_eq( a, fd_secp256r1_const_zero );
      11        7083 : }
      12             : 
      13             : static inline fd_secp256r1_scalar_t *
      14             : fd_secp256r1_scalar_frombytes( fd_secp256r1_scalar_t * r,
      15     3004053 :                                uchar const             in[ 32 ] ) {
      16     3004053 :   memcpy( r->buf, in, 32 );
      17     3004053 :   fd_uint256_bswap( r, r );
      18     3004053 :   if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_n )<0 ) ) {
      19     3003951 :     return r;
      20     3003951 :   };
      21         102 :   return NULL;
      22     3004053 : }
      23             : 
      24             : static inline fd_secp256r1_scalar_t *
      25             : fd_secp256r1_scalar_frombytes_positive( fd_secp256r1_scalar_t * r,
      26     3003939 :                                         uchar const             in[ 32 ] ) {
      27     3003939 :   memcpy( r->buf, in, 32 );
      28     3003939 :   fd_uint256_bswap( r, r );
      29     3003939 :   if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_n_m1_half )<=0 ) ) {
      30     3003549 :     return r;
      31     3003549 :   };
      32         390 :   return NULL;
      33     3003939 : }
      34             : 
      35             : static inline void
      36             : fd_secp256r1_scalar_from_digest( fd_secp256r1_scalar_t * r,
      37        3507 :                                  uchar const             in[ 32 ] ) {
      38        3507 :   memcpy( r->buf, in, 32 );
      39        3507 :   fd_uint256_bswap( r, r );
      40        3507 :   bignum_mod_n256_4( r->limbs, r->limbs );
      41        3507 : }
      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      307017 :                          fd_secp256r1_scalar_t const * b ) {
      47      307017 :   ulong t[ 8 ];
      48      307017 :   bignum_mul_4_8( t, (ulong *)a->limbs, (ulong *)b->limbs );
      49      307017 :   bignum_mod_n256( r->limbs, 8, t );
      50      307017 :   return r;
      51      307017 : }
      52             : 
      53             : static inline fd_secp256r1_scalar_t *
      54             : fd_secp256r1_scalar_inv( fd_secp256r1_scalar_t       * r, 
      55       33510 :                          fd_secp256r1_scalar_t const * a ) {
      56       33510 :   ulong t[ 12 ];
      57       33510 :   bignum_modinv( 4, r->limbs, (ulong *)a->limbs, (ulong *)fd_secp256r1_const_n[0].limbs, t );
      58       33510 :   return r;
      59       33510 : }
      60             : 
      61             : /* Field */
      62             : 
      63             : static inline fd_secp256r1_fp_t *
      64             : fd_secp256r1_fp_set( fd_secp256r1_fp_t * r,
      65       97050 :                      fd_secp256r1_fp_t const * a ) {
      66       97050 :   r->limbs[0] = a->limbs[0];
      67       97050 :   r->limbs[1] = a->limbs[1];
      68       97050 :   r->limbs[2] = a->limbs[2];
      69       97050 :   r->limbs[3] = a->limbs[3];
      70       97050 :   return r;
      71       97050 : }
      72             : 
      73             : static inline fd_secp256r1_fp_t *
      74             : fd_secp256r1_fp_frombytes( fd_secp256r1_fp_t * r,
      75     3033540 :                            uchar const             in[ 32 ] ) {
      76     3033540 :   memcpy( r->buf, in, 32 );
      77     3033540 :   fd_uint256_bswap( r, r );
      78     3033540 :   if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_p )<0 ) ) {
      79     3033537 :     return r;
      80     3033537 :   };
      81           3 :   return NULL;
      82     3033540 : }
      83             : 
      84             : static inline fd_secp256r1_fp_t *
      85             : fd_secp256r1_fp_sqrt( fd_secp256r1_fp_t *       r,
      86       63531 :                       fd_secp256r1_fp_t const * a ) {
      87             :   /* https://github.com/golang/go/blob/master/src/crypto/internal/fips140/nistec/p256.go#L656 */
      88       63531 :   fd_secp256r1_fp_t _t0[1], _t1[1];
      89       63531 :   ulong * t0 = _t0->limbs;
      90       63531 :   ulong * t1 = _t1->limbs;
      91       63531 :   ulong * x = (ulong *)a->limbs;
      92             : 
      93       63531 :         bignum_montsqr_p256( t0, x );
      94       63531 :         bignum_montmul_p256( t0, t0, x );
      95      127062 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<2; i++ ) bignum_montsqr_p256( t1, t1 );
      96       63531 :         bignum_montmul_p256( t0, t0, t1);
      97      254124 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<4; i++ ) bignum_montsqr_p256( t1, t1 );
      98       63531 :         bignum_montmul_p256( t0, t0, t1);
      99      508248 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<8; i++ ) bignum_montsqr_p256( t1, t1 );
     100       63531 :         bignum_montmul_p256( t0, t0, t1);
     101     1016496 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<16; i++ ) bignum_montsqr_p256( t1, t1 );
     102       63531 :         bignum_montmul_p256( t0, t0, t1);
     103     2096523 :         for( int i=0; i<32; i++ ) bignum_montsqr_p256( t0, t0 );
     104       63531 :         bignum_montmul_p256( t0, t0, x );
     105     6162507 :         for( int i=0; i<96; i++ ) bignum_montsqr_p256( t0, t0 );
     106       63531 :         bignum_montmul_p256( t0, t0, x );
     107     6035445 :         for( int i=0; i<94; i++ ) bignum_montsqr_p256( t0, t0 );
     108             : 
     109       63531 :   bignum_montsqr_p256( t1, t0 );
     110       63531 :   if( FD_UNLIKELY( !fd_uint256_eq( _t1, a ) ) ) {
     111           6 :     return NULL;
     112           6 :   }
     113             : 
     114       63525 :   return fd_secp256r1_fp_set( r, _t0 );
     115       63531 : }
     116             : 
     117             : /* Points */
     118             : 
     119             : static inline fd_secp256r1_point_t *
     120             : fd_secp256r1_point_frombytes( fd_secp256r1_point_t * r,
     121       33546 :                               uchar const            in[ 33 ] ) {
     122       33546 :   fd_secp256r1_fp_t y2[1], demont_y[1];
     123             : 
     124       33546 :   uchar sgn = in[0];
     125       33546 :   if( FD_UNLIKELY( sgn!=2U && sgn!=3U ) ) {
     126          18 :     return FD_SECP256R1_FAILURE;
     127          18 :   }
     128             : 
     129       33528 :   if( FD_UNLIKELY( !fd_secp256r1_fp_frombytes( r->x, in+1 ) ) ) {
     130           3 :     return FD_SECP256R1_FAILURE;
     131           3 :   }
     132             : 
     133       33525 :   bignum_tomont_p256( r->x->limbs, r->x->limbs );
     134             :   
     135             :   /* y^2 = x^3 + ax + b */
     136       33525 :   bignum_montsqr_p256( y2->limbs, r->x->limbs );
     137       33525 :   bignum_add_p256    ( y2->limbs, y2->limbs, (ulong *)fd_secp256r1_const_a_mont[0].limbs );
     138       33525 :   bignum_montmul_p256( y2->limbs, y2->limbs, r->x->limbs );
     139       33525 :   bignum_add_p256    ( y2->limbs, y2->limbs, (ulong *)fd_secp256r1_const_b_mont[0].limbs );
     140             : 
     141             :   /* y = sqrt(y^2) */
     142       33525 :   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       33522 :   bignum_demont_p256( demont_y->limbs, r->y->limbs );
     148       33522 :   ulong cond = (demont_y->limbs[0] % 2) != (sgn == 3U);
     149       33522 :   bignum_optneg_p256( r->y->limbs, cond, r->y->limbs );
     150             : 
     151       33522 :   fd_secp256r1_fp_set( r->z, fd_secp256r1_const_one_mont );
     152             : 
     153       33522 :   return r;
     154       33525 : }
     155             : 
     156             : static inline int
     157             : fd_secp256r1_point_eq_x( fd_secp256r1_point_t const *  p,
     158       33516 :                          fd_secp256r1_scalar_t const * r ) {
     159       33516 :   fd_secp256r1_fp_t affine_x[1];
     160       33516 :   fd_secp256r1_scalar_t * affine_x_mod_n = affine_x;
     161             : 
     162       33516 :   if( FD_UNLIKELY( fd_uint256_eq( p->z, fd_secp256r1_const_zero ) ) ) {
     163          39 :     return FD_SECP256R1_FAILURE;
     164          39 :   }
     165             : 
     166             :   /* x = demont(X / Z^2) mod n */
     167       33477 :   bignum_montinv_p256( affine_x->limbs, (ulong *)p->z->limbs );
     168       33477 :   bignum_montsqr_p256( affine_x->limbs, affine_x->limbs );
     169       33477 :   bignum_montmul_p256( affine_x->limbs, affine_x->limbs, (ulong *)p->x->limbs );
     170       33477 :   bignum_demont_p256( affine_x_mod_n->limbs, affine_x->limbs );
     171       33477 :   bignum_mod_n256_4 ( affine_x_mod_n->limbs, affine_x_mod_n->limbs );
     172             : 
     173       33477 :   if( FD_LIKELY( fd_uint256_eq( r, affine_x_mod_n ) ) ) {
     174       33435 :     return FD_SECP256R1_SUCCESS;
     175       33435 :   }
     176          42 :   return FD_SECP256R1_FAILURE;
     177       33477 : }
     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        3507 :                                      fd_secp256r1_scalar_t const * u2 ) {
     184             :   /* u1*G + u2*A */
     185        3507 :   ulong rtmp[ 8 ];
     186        3507 :   p256_scalarmulbase( rtmp, (ulong *)u1->limbs, 6, (ulong *)fd_secp256r1_base_point_table );
     187        3507 :   bignum_tomont_p256( rtmp, rtmp );
     188        3507 :   bignum_tomont_p256( rtmp+4, rtmp+4 );
     189             : 
     190        3507 :   p256_montjscalarmul( (ulong *)r, (ulong *)u2->limbs, (ulong *)a );
     191             : 
     192        3507 :   p256_montjmixadd( (ulong *)r, (ulong *)r, rtmp );
     193        3507 : }