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             : #define bignum_demont_p256     bignum_demont_p256_alt
       9             : #define bignum_mod_n256        bignum_mod_n256_alt
      10             : #define bignum_montmul_p256    bignum_montmul_p256_alt
      11             : #define bignum_montsqr_p256    bignum_montsqr_p256_alt
      12             : #define bignum_mul_4_8         bignum_mul_4_8_alt
      13             : #define bignum_tomont_p256     bignum_tomont_p256_alt
      14             : #define p256_montjdouble       p256_montjdouble_alt
      15             : #define p256_montjmixadd       p256_montjmixadd_alt
      16             : #define p256_montjscalarmul    p256_montjscalarmul_alt
      17             : #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       14886 : fd_secp256r1_scalar_is_zero( fd_secp256r1_scalar_t const * a ) {
      32       14886 :   return fd_uint256_eq( a, fd_secp256r1_const_zero );
      33       14886 : }
      34             : 
      35             : static inline fd_secp256r1_scalar_t *
      36             : fd_secp256r1_scalar_frombytes( fd_secp256r1_scalar_t * r,
      37       13093 :                                uchar const             in[ 32 ] ) {
      38       13093 :   memcpy( r->buf, in, 32 );
      39       13093 :   fd_uint256_bswap( r, r );
      40       13093 :   if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_n )<0 ) ) {
      41       12946 :     return r;
      42       12946 :   };
      43         147 :   return NULL;
      44       13093 : }
      45             : 
      46             : static inline fd_secp256r1_scalar_t *
      47             : fd_secp256r1_scalar_frombytes_positive( fd_secp256r1_scalar_t * r,
      48       12946 :                                         uchar const             in[ 32 ] ) {
      49       12946 :   memcpy( r->buf, in, 32 );
      50       12946 :   fd_uint256_bswap( r, r );
      51       12946 :   if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_n_m1_half )<=0 ) ) {
      52        7448 :     return r;
      53        7448 :   };
      54        5498 :   return NULL;
      55       12946 : }
      56             : 
      57             : static inline void
      58             : fd_secp256r1_scalar_from_digest( fd_secp256r1_scalar_t * r,
      59        7298 :                                  uchar const             in[ 32 ] ) {
      60        7298 :   memcpy( r->buf, in, 32 );
      61        7298 :   fd_uint256_bswap( r, r );
      62        7298 :   bignum_mod_n256_4( r->limbs, r->limbs );
      63        7298 : }
      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       14591 :                          fd_secp256r1_scalar_t const * b ) {
      69       14591 :   ulong t[ 8 ];
      70       14591 :   bignum_mul_4_8( t, (ulong *)a->limbs, (ulong *)b->limbs );
      71       14591 :   bignum_mod_n256( r->limbs, 8, t );
      72       14591 :   return r;
      73       14591 : }
      74             : 
      75             : static inline fd_secp256r1_scalar_t *
      76             : fd_secp256r1_scalar_inv( fd_secp256r1_scalar_t       * r,
      77        7300 :                          fd_secp256r1_scalar_t const * a ) {
      78        7300 :   ulong t[ 12 ];
      79        7300 :   bignum_modinv( 4, r->limbs, (ulong *)a->limbs, (ulong *)fd_secp256r1_const_n[0].limbs, t );
      80        7300 :   return r;
      81        7300 : }
      82             : 
      83             : /* Field */
      84             : 
      85             : static inline fd_secp256r1_fp_t *
      86             : fd_secp256r1_fp_set( fd_secp256r1_fp_t * r,
      87       14597 :                      fd_secp256r1_fp_t const * a ) {
      88       14597 :   r->limbs[0] = a->limbs[0];
      89       14597 :   r->limbs[1] = a->limbs[1];
      90       14597 :   r->limbs[2] = a->limbs[2];
      91       14597 :   r->limbs[3] = a->limbs[3];
      92       14597 :   return r;
      93       14597 : }
      94             : 
      95             : /* r = -a, Montgomery domain */
      96             : static inline fd_secp256r1_fp_t *
      97             : fd_secp256r1_fp_neg( fd_secp256r1_fp_t *       r,
      98           0 :                      fd_secp256r1_fp_t const * a ) {
      99           0 :   bignum_optneg_p256( r->limbs, 1UL, (ulong *)a->limbs );
     100           0 :   return r;
     101           0 : }
     102             : 
     103             : static inline fd_secp256r1_fp_t *
     104             : fd_secp256r1_fp_mul( fd_secp256r1_fp_t *       r,
     105             :                      fd_secp256r1_fp_t const * a,
     106           0 :                      fd_secp256r1_fp_t const * b ) {
     107           0 :   bignum_montmul_p256( r->limbs, a->limbs, b->limbs );
     108           0 :   return r;
     109           0 : }
     110             : 
     111             : static inline fd_secp256r1_fp_t *
     112             : fd_secp256r1_fp_sqr( fd_secp256r1_fp_t *       r,
     113           0 :                      fd_secp256r1_fp_t const * a ) {
     114           0 :   bignum_montsqr_p256( r->limbs, a->limbs );
     115           0 :   return r;
     116           0 : }
     117             : 
     118             : /* r = 1/a, Montgomery domain.  a MUST not be 0. */
     119             : static inline fd_secp256r1_fp_t *
     120             : fd_secp256r1_fp_inv( fd_secp256r1_fp_t *       r,
     121           0 :                      fd_secp256r1_fp_t const * a ) {
     122           0 :   bignum_montinv_p256( r->limbs, a->limbs );
     123           0 :   return r;
     124           0 : }
     125             : 
     126             : static inline fd_secp256r1_fp_t *
     127             : fd_secp256r1_fp_tomont( fd_secp256r1_fp_t *       r,
     128           0 :                         fd_secp256r1_fp_t const * a ) {
     129           0 :   bignum_tomont_p256( r->limbs, a->limbs );
     130           0 :   return r;
     131           0 : }
     132             : 
     133             : static inline fd_secp256r1_fp_t *
     134             : fd_secp256r1_fp_demont( fd_secp256r1_fp_t *       r,
     135           0 :                         fd_secp256r1_fp_t const * a ) {
     136           0 :   bignum_demont_p256( r->limbs, a->limbs );
     137           0 :   return r;
     138           0 : }
     139             : 
     140             : static inline fd_secp256r1_fp_t *
     141             : fd_secp256r1_fp_frombytes( fd_secp256r1_fp_t * r,
     142        7350 :                            uchar const             in[ 32 ] ) {
     143        7350 :   memcpy( r->buf, in, 32 );
     144        7350 :   fd_uint256_bswap( r, r );
     145        7357 :   if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_p )<0 ) ) {
     146        7357 :     return r;
     147 >1844*10^16 :   };
     148 >1844*10^16 :   return NULL;
     149        7350 : }
     150             : 
     151             : static inline fd_secp256r1_fp_t *
     152             : fd_secp256r1_fp_sqrt( fd_secp256r1_fp_t *       r,
     153        7365 :                       fd_secp256r1_fp_t const * a ) {
     154             :   /* https://github.com/golang/go/blob/master/src/crypto/internal/fips140/nistec/p256.go#L656 */
     155        7365 :   fd_secp256r1_fp_t _t0[1], _t1[1];
     156        7365 :   ulong * t0 = _t0->limbs;
     157        7365 :   ulong * t1 = _t1->limbs;
     158        7365 :   ulong * x = (ulong *)a->limbs;
     159             : 
     160        7365 :         bignum_montsqr_p256( t0, x );
     161        7365 :         bignum_montmul_p256( t0, t0, x );
     162       14736 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<2; i++ ) bignum_montsqr_p256( t1, t1 );
     163        7365 :         bignum_montmul_p256( t0, t0, t1);
     164       29489 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<4; i++ ) bignum_montsqr_p256( t1, t1 );
     165        7365 :         bignum_montmul_p256( t0, t0, t1);
     166       58869 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<8; i++ ) bignum_montsqr_p256( t1, t1 );
     167        7365 :         bignum_montmul_p256( t0, t0, t1);
     168      117590 :         bignum_montsqr_p256( t1, t0 ); for( int i=1; i<16; i++ ) bignum_montsqr_p256( t1, t1 );
     169        7365 :         bignum_montmul_p256( t0, t0, t1);
     170      241833 :         for( int i=0; i<32; i++ ) bignum_montsqr_p256( t0, t0 );
     171        7365 :         bignum_montmul_p256( t0, t0, x );
     172      707711 :         for( int i=0; i<96; i++ ) bignum_montsqr_p256( t0, t0 );
     173        7365 :         bignum_montmul_p256( t0, t0, x );
     174      693039 :         for( int i=0; i<94; i++ ) bignum_montsqr_p256( t0, t0 );
     175             : 
     176        7365 :   bignum_montsqr_p256( t1, t0 );
     177        7365 :   if( FD_UNLIKELY( !fd_uint256_eq( _t1, a ) ) ) {
     178          73 :     return NULL;
     179          73 :   }
     180             : 
     181        7292 :   return fd_secp256r1_fp_set( r, _t0 );
     182        7365 : }
     183             : 
     184             : /* Points */
     185             : 
     186             : static inline int
     187           0 : fd_secp256r1_point_is_inf( fd_secp256r1_point_t const * a ) {
     188           0 :   return fd_uint256_eq( a->z, fd_secp256r1_const_zero );
     189           0 : }
     190             : 
     191             : static inline void
     192           0 : fd_secp256r1_point_set_inf( fd_secp256r1_point_t * r ) {
     193           0 :   fd_secp256r1_fp_set( r->x, fd_secp256r1_const_zero );
     194           0 :   fd_secp256r1_fp_set( r->y, fd_secp256r1_const_one_mont );
     195           0 :   fd_secp256r1_fp_set( r->z, fd_secp256r1_const_zero );
     196           0 : }
     197             : 
     198             : /* Returns 1 if (x, y), Montgomery domain, satisfies y^2 = x^3 + ax + b. */
     199             : static inline int
     200             : fd_secp256r1_point_on_curve( fd_secp256r1_fp_t const * x,
     201           0 :                              fd_secp256r1_fp_t const * y ) {
     202           0 :   fd_secp256r1_fp_t lhs[1], rhs[1];
     203           0 :   bignum_montsqr_p256( lhs->limbs, y->limbs );
     204           0 :   bignum_montsqr_p256( rhs->limbs, x->limbs );
     205           0 :   bignum_add_p256    ( rhs->limbs, rhs->limbs, fd_secp256r1_const_a_mont[0].limbs );
     206           0 :   bignum_montmul_p256( rhs->limbs, rhs->limbs, x->limbs );
     207           0 :   bignum_add_p256    ( rhs->limbs, rhs->limbs, fd_secp256r1_const_b_mont[0].limbs );
     208           0 :   return fd_uint256_eq( lhs, rhs );
     209           0 : }
     210             : 
     211             : static inline int
     212           0 : fd_secp256r1_point_validate_uncompressed( uchar const in[ 65 ] ) {
     213           0 :   if( FD_UNLIKELY( in[ 0 ]!=0x04U ) ) return FD_SECP256R1_FAILURE;
     214             : 
     215           0 :   fd_secp256r1_fp_t x[1], y[1];
     216           0 :   if( FD_UNLIKELY( !fd_secp256r1_fp_frombytes( x, in+1  ) ) ) return FD_SECP256R1_FAILURE;
     217           0 :   if( FD_UNLIKELY( !fd_secp256r1_fp_frombytes( y, in+33 ) ) ) return FD_SECP256R1_FAILURE;
     218             : 
     219           0 :   bignum_tomont_p256( x->limbs, x->limbs );
     220           0 :   bignum_tomont_p256( y->limbs, y->limbs );
     221           0 :   return fd_secp256r1_point_on_curve( x, y );
     222           0 : }
     223             : 
     224             : static inline fd_secp256r1_point_t *
     225             : fd_secp256r1_point_frombytes( fd_secp256r1_point_t * r,
     226        7357 :                               uchar const            in[ 33 ] ) {
     227        7357 :   fd_secp256r1_fp_t y2[1], demont_y[1];
     228             : 
     229        7357 :   uchar sgn = in[0];
     230        7357 :   if( FD_UNLIKELY( sgn!=2U && sgn!=3U ) ) {
     231           5 :     return FD_SECP256R1_FAILURE;
     232           5 :   }
     233             : 
     234        7352 :   if( FD_UNLIKELY( !fd_secp256r1_fp_frombytes( r->x, in+1 ) ) ) {
     235           0 :     return FD_SECP256R1_FAILURE;
     236           0 :   }
     237             : 
     238        7352 :   bignum_tomont_p256( r->x->limbs, r->x->limbs );
     239             : 
     240             :   /* y^2 = x^3 + ax + b */
     241        7352 :   bignum_montsqr_p256( y2->limbs, r->x->limbs );
     242        7352 :   bignum_add_p256    ( y2->limbs, y2->limbs, (ulong *)fd_secp256r1_const_a_mont[0].limbs );
     243        7352 :   bignum_montmul_p256( y2->limbs, y2->limbs, r->x->limbs );
     244        7352 :   bignum_add_p256    ( y2->limbs, y2->limbs, (ulong *)fd_secp256r1_const_b_mont[0].limbs );
     245             : 
     246             :   /* y = sqrt(y^2) */
     247        7352 :   if( FD_UNLIKELY( !fd_secp256r1_fp_sqrt( r->y, y2 ) ) ) {
     248          73 :     return FD_SECP256R1_FAILURE;
     249          73 :   }
     250             : 
     251             :   /* choose y or -y */
     252        7279 :   bignum_demont_p256( demont_y->limbs, r->y->limbs );
     253        7279 :   ulong cond = (demont_y->limbs[0] % 2) != (sgn == 3U);
     254        7279 :   bignum_optneg_p256( r->y->limbs, cond, r->y->limbs );
     255             : 
     256        7279 :   fd_secp256r1_fp_set( r->z, fd_secp256r1_const_one_mont );
     257             : 
     258        7279 :   return r;
     259        7352 : }
     260             : 
     261             : static inline int
     262             : fd_secp256r1_point_eq_x( fd_secp256r1_point_t const *  p,
     263        7302 :                          fd_secp256r1_scalar_t const * r ) {
     264        7302 :   fd_secp256r1_fp_t affine_x[1];
     265        7302 :   fd_secp256r1_scalar_t * affine_x_mod_n = affine_x;
     266             : 
     267        7302 :   if( FD_UNLIKELY( fd_uint256_eq( p->z, fd_secp256r1_const_zero ) ) ) {
     268          22 :     return FD_SECP256R1_FAILURE;
     269          22 :   }
     270             : 
     271             :   /* x = demont(X / Z^2) mod n */
     272        7280 :   bignum_montinv_p256( affine_x->limbs, (ulong *)p->z->limbs );
     273        7280 :   bignum_montsqr_p256( affine_x->limbs, affine_x->limbs );
     274        7280 :   bignum_montmul_p256( affine_x->limbs, affine_x->limbs, (ulong *)p->x->limbs );
     275        7280 :   bignum_demont_p256( affine_x_mod_n->limbs, affine_x->limbs );
     276        7280 :   bignum_mod_n256_4 ( affine_x_mod_n->limbs, affine_x_mod_n->limbs );
     277             : 
     278        7280 :   if( FD_LIKELY( fd_uint256_eq( r, affine_x_mod_n ) ) ) {
     279        4645 :     return FD_SECP256R1_SUCCESS;
     280        4645 :   }
     281        2635 :   return FD_SECP256R1_FAILURE;
     282        7280 : }
     283             : 
     284             : /* Given the projective point `r` and the affine point `p`,
     285             :    returns 1 if they are equal and 0 otherwise.
     286             :    Assumes that `p` X and Y coordinates are in Montgomery domain. */
     287             : static inline int
     288             : fd_secp256r1_point_eq_mixed( fd_secp256r1_point_t const * a,
     289        7291 :                              ulong                const   b[ 8 ] ) {
     290        7291 :   fd_secp256r1_fp_t x[1], y[1];
     291        7291 :   fd_memcpy( x->limbs, b+0, sizeof(fd_secp256r1_fp_t) );
     292        7291 :   fd_memcpy( y->limbs, b+4, sizeof(fd_secp256r1_fp_t) );
     293             :   /* Indicates if the affine point is zero. */
     294        7291 :   int is_zero = fd_uint256_eq( x, fd_secp256r1_const_zero ) & fd_uint256_eq( y, fd_secp256r1_const_zero );
     295             : 
     296             :   /* Easy cases */
     297        7291 :   if( FD_UNLIKELY( fd_uint256_eq( a->z, fd_secp256r1_const_zero ) ) ) {
     298           0 :     return is_zero;
     299           0 :   }
     300        7291 :   if( FD_UNLIKELY( is_zero ) ) {
     301           0 :     return 0;
     302           0 :   }
     303             : 
     304        7291 :   fd_secp256r1_fp_t z1z1[1];
     305        7291 :   bignum_montsqr_p256( z1z1->limbs, (ulong *)a->z->limbs );
     306             : 
     307        7291 :   fd_secp256r1_fp_t temp[1];
     308        7291 :   bignum_montmul_p256( temp->limbs, (ulong *)x->limbs, z1z1->limbs );
     309             : 
     310        7291 :   if( FD_UNLIKELY( fd_uint256_eq( a->x, temp ) ) ) {
     311          35 :     bignum_montmul_p256( temp->limbs, z1z1->limbs,  (ulong *)a->z->limbs );
     312          35 :     bignum_montmul_p256( temp->limbs, temp->limbs, (ulong *)y->limbs );
     313          35 :     return fd_uint256_eq( a->y, temp );
     314        7256 :   } else {
     315        7256 :     return 0;
     316        7256 :   }
     317        7291 : }
     318             : 
     319             : /* Adds projective point `a` and affine-Montgomery point `b`, both
     320             :    in Montgomery domain. Handles identity elements and the equal-point
     321             :    (doubling) case. */
     322             : static inline void
     323             : fd_secp256r1_point_add_mixed( fd_secp256r1_point_t *       r,
     324             :                               fd_secp256r1_point_t const * a,
     325        7299 :                               ulong const                  b[ 8 ] ) {
     326        7299 :   int b_is_zero = fd_uint256_eq( (fd_uint256_t const *)(b+0), fd_secp256r1_const_zero ) &
     327        7299 :                   fd_uint256_eq( (fd_uint256_t const *)(b+4), fd_secp256r1_const_zero );
     328             : 
     329        7299 :   if( FD_UNLIKELY( b_is_zero ) ) {
     330             :     /* a + 0 = a */
     331           0 :     if( r != a ) fd_memcpy( r, a, sizeof(fd_secp256r1_point_t) );
     332           0 :     return;
     333           0 :   }
     334             : 
     335        7299 :   if( FD_UNLIKELY( fd_secp256r1_point_eq_mixed( a, b ) ) ) {
     336          13 :     p256_montjdouble( (ulong *)r, (ulong *)a );
     337        7286 :   } else {
     338             :     /* Also handles a == 0 and a == -b */
     339        7286 :     p256_montjmixadd( (ulong *)r, (ulong *)a, b );
     340        7286 :   }
     341        7299 : }
     342             : 
     343             : static inline void
     344             : fd_secp256r1_double_scalar_mul_base( fd_secp256r1_point_t *        r,
     345             :                                      fd_secp256r1_scalar_t const * u1,
     346             :                                      fd_secp256r1_point_t const *  a,
     347        7296 :                                      fd_secp256r1_scalar_t const * u2 ) {
     348             :   /* u1*G */
     349        7296 :   ulong rtmp[ 8 ];
     350        7296 :   p256_scalarmulbase( rtmp, (ulong *)u1->limbs, 6, (ulong *)fd_secp256r1_base_point_table );
     351        7296 :   bignum_tomont_p256( rtmp, rtmp );
     352        7296 :   bignum_tomont_p256( rtmp+4, rtmp+4 );
     353             : 
     354             :   /* u2*A */
     355        7296 :   p256_montjscalarmul( (ulong *)r, (ulong *)u2->limbs, (ulong *)a );
     356             : 
     357             :   /* u1*G + u2*A */
     358        7296 :   fd_secp256r1_point_add_mixed( r, r, rtmp );
     359        7296 : }
     360             : 
     361             : /* r = 2a.  Maps infinity to infinity.  r may alias a. */
     362             : static inline void
     363             : fd_secp256r1_point_double( fd_secp256r1_point_t *       r,
     364           0 :                            fd_secp256r1_point_t const * a ) {
     365           0 :   p256_montjdouble( (ulong *)r, (ulong const *)a );
     366           0 : }
     367             : 
     368             : /* r = s*a. s is a plain LE integer of 4 limbs, reduced mod n internally. */
     369             : static inline void
     370             : fd_secp256r1_point_scalarmul( fd_secp256r1_point_t *       r,
     371             :                               ulong const                  s[ 4 ],
     372           0 :                               fd_secp256r1_point_t const * a ) {
     373           0 :   p256_montjscalarmul( (ulong *)r, s, (ulong const *)a );
     374           0 : }
     375             : 
     376             : /* Converts the Jacobian point a to affine-Montgomery (x, y) laid out
     377             :    as 8 limbs, (0, 0) for infinity. */
     378             : static inline void
     379             : fd_secp256r1_point_toaffine_mont( ulong                        r[ 8 ],
     380           0 :                                   fd_secp256r1_point_t const * a ) {
     381           0 :   if( FD_UNLIKELY( fd_secp256r1_point_is_inf( a ) ) ) {
     382           0 :     memset( r, 0, 8*sizeof(ulong) );
     383           0 :     return;
     384           0 :   }
     385           0 :   ulong zinv[ 4 ], zinv2[ 4 ];
     386           0 :   bignum_montinv_p256( zinv, a->z->limbs );
     387           0 :   bignum_montsqr_p256( zinv2, zinv );
     388           0 :   bignum_montmul_p256( r,   a->x->limbs, zinv2 );
     389           0 :   bignum_montmul_p256( r+4, zinv2, zinv );
     390           0 :   bignum_montmul_p256( r+4, r+4, a->y->limbs );
     391           0 : }
     392             : 
     393             : /* r = a + b, Jacobian points. r may alias a. */
     394             : static inline void
     395             : fd_secp256r1_point_add( fd_secp256r1_point_t *       r,
     396             :                         fd_secp256r1_point_t const * a,
     397           0 :                         fd_secp256r1_point_t const * b ) {
     398           0 :   ulong baff[ 8 ];
     399           0 :   fd_secp256r1_point_toaffine_mont( baff, b );
     400           0 :   fd_secp256r1_point_add_mixed( r, a, baff );
     401           0 : }