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     3003045 :                                uchar const             in[ 32 ] ) {
      16     3003045 :   memcpy( r->buf, in, 32 );
      17     3003045 :   fd_uint256_bswap( r, r );
      18     3003045 :   if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_n )<0 ) ) {
      19     3003045 :     return r;
      20     3003045 :   };
      21           0 :   return NULL;
      22     3003045 : }
      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       96072 :                      fd_secp256r1_fp_t const * a ) {
      66       96072 :   r->limbs[0] = a->limbs[0];
      67       96072 :   r->limbs[1] = a->limbs[1];
      68       96072 :   r->limbs[2] = a->limbs[2];
      69       96072 :   r->limbs[3] = a->limbs[3];
      70       96072 :   return r;
      71       96072 : }
      72             : 
      73             : static inline fd_secp256r1_fp_t *
      74             : fd_secp256r1_fp_frombytes( fd_secp256r1_fp_t * r,
      75     3033051 :                            uchar const             in[ 32 ] ) {
      76     3033051 :   memcpy( r->buf, in, 32 );
      77     3033051 :   fd_uint256_bswap( r, r );
      78     3033051 :   if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_p )<0 ) ) {
      79     3033048 :     return r;
      80     3033048 :   };
      81           3 :   return NULL;
      82     3033051 : }
      83             : 
      84             : static inline fd_secp256r1_fp_t *
      85             : fd_secp256r1_fp_sqrt( fd_secp256r1_fp_t *       r,
      86       63042 :                       fd_secp256r1_fp_t const * a ) {
      87             :   /* https://github.com/golang/go/blob/master/src/crypto/internal/fips140/nistec/p256.go#L656 */
      88       63042 :   fd_secp256r1_fp_t _t0[1], _t1[1];
      89       63042 :   ulong * t0 = _t0->limbs;
      90       63042 :   ulong * t1 = _t1->limbs;
      91       63042 :   ulong * x = (ulong *)a->limbs;
      92             : 
      93       63042 :         bignum_montsqr_p256( t0, x );
      94       63042 :         bignum_montmul_p256( t0, t0, x );
      95      126084 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<2; i++ ) bignum_montsqr_p256( t1, t1 );
      96       63042 :         bignum_montmul_p256( t0, t0, t1);
      97      252168 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<4; i++ ) bignum_montsqr_p256( t1, t1 );
      98       63042 :         bignum_montmul_p256( t0, t0, t1);
      99      504336 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<8; i++ ) bignum_montsqr_p256( t1, t1 );
     100       63042 :         bignum_montmul_p256( t0, t0, t1);
     101     1008672 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<16; i++ ) bignum_montsqr_p256( t1, t1 );
     102       63042 :         bignum_montmul_p256( t0, t0, t1);
     103     2080386 :         for( int i=0; i<32; i++ ) bignum_montsqr_p256( t0, t0 );
     104       63042 :         bignum_montmul_p256( t0, t0, x );
     105     6115074 :         for( int i=0; i<96; i++ ) bignum_montsqr_p256( t0, t0 );
     106       63042 :         bignum_montmul_p256( t0, t0, x );
     107     5988990 :         for( int i=0; i<94; i++ ) bignum_montsqr_p256( t0, t0 );
     108             : 
     109       63042 :   bignum_montsqr_p256( t1, t0 );
     110       63042 :   if( FD_UNLIKELY( !fd_uint256_eq( _t1, a ) ) ) {
     111           6 :     return NULL;
     112           6 :   }
     113             : 
     114       63036 :   return fd_secp256r1_fp_set( r, _t0 );
     115       63042 : }
     116             : 
     117             : /* Points */
     118             : 
     119             : static inline fd_secp256r1_point_t *
     120             : fd_secp256r1_point_frombytes( fd_secp256r1_point_t * r,
     121       33042 :                               uchar const            in[ 33 ] ) {
     122       33042 :   fd_secp256r1_fp_t y2[1], demont_y[1];
     123             : 
     124       33042 :   uchar sgn = in[0];
     125       33042 :   if( FD_UNLIKELY( sgn!=2U && sgn!=3U ) ) {
     126           3 :     return FD_SECP256R1_FAILURE;
     127           3 :   }
     128             : 
     129       33039 :   if( FD_UNLIKELY( !fd_secp256r1_fp_frombytes( r->x, in+1 ) ) ) {
     130           3 :     return FD_SECP256R1_FAILURE;
     131           3 :   }
     132             : 
     133       33036 :   bignum_tomont_p256( r->x->limbs, r->x->limbs );
     134             : 
     135             :   /* y^2 = x^3 + ax + b */
     136       33036 :   bignum_montsqr_p256( y2->limbs, r->x->limbs );
     137       33036 :   bignum_add_p256    ( y2->limbs, y2->limbs, (ulong *)fd_secp256r1_const_a_mont[0].limbs );
     138       33036 :   bignum_montmul_p256( y2->limbs, y2->limbs, r->x->limbs );
     139       33036 :   bignum_add_p256    ( y2->limbs, y2->limbs, (ulong *)fd_secp256r1_const_b_mont[0].limbs );
     140             : 
     141             :   /* y = sqrt(y^2) */
     142       33036 :   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       33033 :   bignum_demont_p256( demont_y->limbs, r->y->limbs );
     148       33033 :   ulong cond = (demont_y->limbs[0] % 2) != (sgn == 3U);
     149       33033 :   bignum_optneg_p256( r->y->limbs, cond, r->y->limbs );
     150             : 
     151       33033 :   fd_secp256r1_fp_set( r->z, fd_secp256r1_const_one_mont );
     152             : 
     153       33033 :   return r;
     154       33036 : }
     155             : 
     156             : static inline int
     157             : fd_secp256r1_point_eq_x( fd_secp256r1_point_t const *  p,
     158       33027 :                          fd_secp256r1_scalar_t const * r ) {
     159       33027 :   fd_secp256r1_fp_t affine_x[1];
     160       33027 :   fd_secp256r1_scalar_t * affine_x_mod_n = affine_x;
     161             : 
     162       33027 :   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       33024 :   bignum_montinv_p256( affine_x->limbs, (ulong *)p->z->limbs );
     168       33024 :   bignum_montsqr_p256( affine_x->limbs, affine_x->limbs );
     169       33024 :   bignum_montmul_p256( affine_x->limbs, affine_x->limbs, (ulong *)p->x->limbs );
     170       33024 :   bignum_demont_p256( affine_x_mod_n->limbs, affine_x->limbs );
     171       33024 :   bignum_mod_n256_4 ( affine_x_mod_n->limbs, affine_x_mod_n->limbs );
     172             : 
     173       33024 :   if( FD_LIKELY( fd_uint256_eq( r, affine_x_mod_n ) ) ) {
     174       33021 :     return FD_SECP256R1_SUCCESS;
     175       33021 :   }
     176           3 :   return FD_SECP256R1_FAILURE;
     177       33024 : }
     178             : 
     179             : /* Given the projective point `r` and the affine point `p`,
     180             :    returns 1 if they are equal and 0 otherwise.
     181             :    Assumes that `p` X and Y coordinates are in Montgomery domain. */
     182             : static inline int
     183             : fd_secp256r1_point_eq_mixed( fd_secp256r1_point_t const * a,
     184        3033 :                              ulong                const   b[ 8 ] ) {
     185        3033 :   fd_secp256r1_fp_t x[1], y[1];
     186        3033 :   fd_memcpy( x->limbs, b+0, sizeof(fd_secp256r1_fp_t) );
     187        3033 :   fd_memcpy( y->limbs, b+4, sizeof(fd_secp256r1_fp_t) );
     188             :   /* Indicates if the affine point is zero. */
     189        3033 :   int is_zero = fd_uint256_eq( x, fd_secp256r1_const_zero ) & fd_uint256_eq( y, fd_secp256r1_const_zero );
     190             : 
     191             :   /* Easy cases */
     192        3033 :   if( FD_UNLIKELY( fd_uint256_eq( a->z, fd_secp256r1_const_zero ) ) ) {
     193           6 :     return is_zero;
     194           6 :   }
     195        3027 :   if( FD_UNLIKELY( is_zero ) ) {
     196           0 :     return 0;
     197           0 :   }
     198             : 
     199        3027 :   fd_secp256r1_fp_t z1z1[1];
     200        3027 :   bignum_montsqr_p256( z1z1->limbs, (ulong *)a->z->limbs );
     201             : 
     202        3027 :   fd_secp256r1_fp_t temp[1];
     203        3027 :   bignum_montmul_p256( temp->limbs, (ulong *)x->limbs, z1z1->limbs );
     204             : 
     205        3027 :   if( FD_UNLIKELY( fd_uint256_eq( a->x, temp ) ) ) {
     206          15 :     bignum_montmul_p256( temp->limbs, z1z1->limbs,  (ulong *)a->z->limbs );
     207          15 :     bignum_montmul_p256( temp->limbs, temp->limbs, (ulong *)y->limbs );
     208          15 :     return fd_uint256_eq( a->y, temp );
     209        3012 :   } else {
     210        3012 :     return 0;
     211        3012 :   }
     212        3027 : }
     213             : 
     214             : /* Adds projective point `a` and affine-Montgomery point `b`, both
     215             :    in Montgomery domain. Handles identity elements and the equal-point
     216             :    (doubling) case. */
     217             : static inline void
     218             : fd_secp256r1_point_add_mixed( fd_secp256r1_point_t *       r,
     219             :                               fd_secp256r1_point_t const * a,
     220        3030 :                               ulong                        b[ 8 ] ) {
     221        3030 :   int b_is_zero = fd_uint256_eq( (fd_uint256_t const *)(b+0), fd_secp256r1_const_zero ) &
     222        3030 :                   fd_uint256_eq( (fd_uint256_t const *)(b+4), fd_secp256r1_const_zero );
     223             : 
     224        3030 :   if( FD_UNLIKELY( b_is_zero ) ) {
     225             :     /* a + 0 = a */
     226           6 :     if( r != a ) fd_memcpy( r, a, sizeof(fd_secp256r1_point_t) );
     227           6 :     return;
     228           6 :   }
     229             : 
     230        3024 :   if( FD_UNLIKELY( fd_secp256r1_point_eq_mixed( a, b ) ) ) {
     231           6 :     p256_montjdouble( (ulong *)r, (ulong *)a );
     232        3018 :   } else {
     233             :     /* Also handles a == 0 and a == -b */
     234        3018 :     p256_montjmixadd( (ulong *)r, (ulong *)a, b );
     235        3018 :   }
     236        3024 : }
     237             : 
     238             : static inline void
     239             : fd_secp256r1_double_scalar_mul_base( fd_secp256r1_point_t *        r,
     240             :                                      fd_secp256r1_scalar_t const * u1,
     241             :                                      fd_secp256r1_point_t const *  a,
     242        3015 :                                      fd_secp256r1_scalar_t const * u2 ) {
     243             :   /* u1*G */
     244        3015 :   ulong rtmp[ 8 ];
     245        3015 :   p256_scalarmulbase( rtmp, (ulong *)u1->limbs, 6, (ulong *)fd_secp256r1_base_point_table );
     246        3015 :   bignum_tomont_p256( rtmp, rtmp );
     247        3015 :   bignum_tomont_p256( rtmp+4, rtmp+4 );
     248             : 
     249             :   /* u2*A */
     250        3015 :   p256_montjscalarmul( (ulong *)r, (ulong *)u2->limbs, (ulong *)a );
     251             : 
     252             :   /* u1*G + u2*A */
     253        3015 :   fd_secp256r1_point_add_mixed( r, r, rtmp );
     254        3015 : }