Line data    Source code

       1             : #include <stdint.h>
       2             : #include "../../third_party/s2n-bignum/include/s2n-bignum.h"
       3             : #include "../../util/sanitize/fd_msan.h"
       4             : 
       5             : /* On CPUs without ADX (mulx/adcx/adox), redirect the ADX-optimized
       6             :    s2n-bignum symbols to their _alt equivalents, which use only base
       7             :    x86-64 instructions and are functionally identical. */
       8             : #ifndef __ADX__
       9             : #define bignum_montmul_p256k1  bignum_montmul_p256k1_alt
      10             : #define bignum_montsqr_p256k1  bignum_montsqr_p256k1_alt
      11             : #define bignum_tomont_p256k1   bignum_tomont_p256k1_alt
      12             : #define bignum_triple_p256k1   bignum_triple_p256k1_alt
      13             : #endif
      14             : 
      15             : /* Scalars */
      16             : 
      17             : static inline int
      18        4916 : fd_secp256k1_scalar_is_zero( fd_secp256k1_scalar_t const *r ) {
      19        4916 :   return fd_uint256_eq( r, fd_secp256k1_const_zero );
      20        4916 : }
      21             : 
      22             : /* Returns the scalar in NON Montgomery form. */
      23             : static inline fd_secp256k1_scalar_t *
      24             : fd_secp256k1_scalar_frombytes( fd_secp256k1_scalar_t * r,
      25        4918 :                                uchar const             input[ 32 ] ) {
      26        4918 :   memcpy( r, input, 32 );
      27        4918 :   fd_uint256_bswap( r, r );
      28             : 
      29             :   /*
      30             :     The verifier SHALL check that 0 < r' < q and 0 < s' < q.
      31             :     The r' element is parsed as a scalar, and checked against r' < n.
      32             :     Later it is re-used as fp_t, however n < p, so we do not need to
      33             :     perform any additional checks after this.
      34             :   */
      35        4918 :   if( FD_UNLIKELY( fd_uint256_cmp( r, fd_secp256k1_const_n ) >= 0 ) ) {
      36           4 :     return NULL;
      37           4 :   }
      38        4914 :   if( FD_UNLIKELY( fd_secp256k1_scalar_is_zero( r ) ) ) {
      39           4 :     return NULL;
      40           4 :   }
      41        4910 :   return r;
      42        4914 : }
      43             : 
      44             : /* r = 1 / a
      45             :    Operates on scalars NOT in the montgomery domain.
      46             :    a MUST not be 0. */
      47             : fd_secp256k1_scalar_t *
      48             : fd_secp256k1_scalar_invert( fd_secp256k1_scalar_t *       r,
      49        2175 :                             fd_secp256k1_scalar_t const * a ) {
      50        2175 :   ulong t[ 12 ];
      51        2175 :   bignum_modinv( 4, r->limbs, (ulong *)a->limbs, (ulong *)fd_secp256k1_const_n[ 0 ].limbs, t );
      52        2175 :   fd_msan_unpoison( r->limbs, 32UL );
      53        2175 :   return r;
      54        2175 : }
      55             : 
      56             : /* None of the arguments may alias. */
      57             : static inline fd_secp256k1_scalar_t *
      58             : fd_secp256k1_scalar_mul( fd_secp256k1_scalar_t *       restrict r,
      59             :                          fd_secp256k1_scalar_t const * restrict a,
      60        4350 :                          fd_secp256k1_scalar_t const * restrict b ) {
      61        4350 :   bignum_montmul( 4, r->limbs, (ulong *)a->limbs, (ulong *)b->limbs, (ulong *)fd_secp256k1_const_n[0].limbs );
      62        4350 :   fd_msan_unpoison( r->limbs, 32UL );
      63        4350 :   return r;
      64        4350 : }
      65             : 
      66             : /* r = -a */
      67             : static inline fd_secp256k1_scalar_t *
      68             : fd_secp256k1_scalar_negate( fd_secp256k1_scalar_t *       r,
      69        2175 :                             fd_secp256k1_scalar_t const * a ) {
      70             :   /* We cannot use bignum_modsub() as it requires a < n /\ b < n.
      71             : 
      72             :      The best way to implement it using the current API is to use
      73             :      bignum_sub(n, a), getting a result bounded within [0, n+1). Then
      74             :      we perform a second reduction from [0, n+1) to [0, n) with
      75             :      bignum_mod_n256k1_4(). */
      76             : 
      77             :   /* t \in [0, n + 1). There is no carry-out, as a < n. */
      78        2175 :   ulong t[4];
      79        2175 :   bignum_sub( 4, t, 4, (ulong *)fd_secp256k1_const_n[ 0 ].limbs, 4, (ulong *)a->limbs );
      80        2175 :   fd_msan_unpoison( t, 32UL );
      81        2175 :   bignum_mod_n256k1_4( r->limbs, t );
      82        2175 :   fd_msan_unpoison( r->limbs, 32UL );
      83        2175 :   return r;
      84        2175 : }
      85             : 
      86             : static inline fd_secp256k1_scalar_t *
      87             : fd_secp256k1_scalar_tomont( fd_secp256k1_scalar_t *       r,
      88        6522 :                             fd_secp256k1_scalar_t const * a ) {
      89             :   /* bignum_montmul has an undocumented restriction
      90             :      that the input and outputs may not alias. */
      91        6522 :   ulong t[4];
      92        6522 :   memcpy( t, a->limbs, 32 );
      93        6522 :   bignum_montmul( 4, r->limbs, t, (ulong *)fd_secp256k1_const_scalar_rr_mont, (ulong *)fd_secp256k1_const_n[ 0 ].limbs );
      94        6522 :   fd_msan_unpoison( r->limbs, 32UL );
      95        6522 :   return r;
      96        6522 : }
      97             : 
      98             : static inline fd_secp256k1_scalar_t *
      99             : fd_secp256k1_scalar_demont( fd_secp256k1_scalar_t *       r,
     100        4349 :                             fd_secp256k1_scalar_t const * a ) {
     101        4349 :   bignum_demont( 4, r->limbs, (ulong *)a->limbs, (ulong *)fd_secp256k1_const_n[ 0 ].limbs );
     102        4349 :   fd_msan_unpoison( r->limbs, 32UL );
     103        4349 :   return r;
     104        4349 : }
     105             : 
     106             : /* r = a mod n, where a < 2^256 < 2n. NOT Montgomery. */
     107             : static inline fd_secp256k1_scalar_t *
     108             : fd_secp256k1_scalar_reduce( fd_secp256k1_scalar_t *       r,
     109        2174 :                             fd_secp256k1_scalar_t const * a ) {
     110        2174 :   bignum_mod_n256k1_4( r->limbs, (ulong *)a->limbs );
     111        2174 :   fd_msan_unpoison( r->limbs, 32UL );
     112        2174 :   return r;
     113        2174 : }
     114             : 
     115             : /* Field */
     116             : 
     117             : static inline fd_secp256k1_fp_t *
     118             : fd_secp256k1_fp_set( fd_secp256k1_fp_t *       r,
     119      321361 :                      fd_secp256k1_fp_t const * a ) {
     120      321361 :   r->limbs[ 0 ] = a->limbs[ 0 ];
     121      321361 :   r->limbs[ 1 ] = a->limbs[ 1 ];
     122      321361 :   r->limbs[ 2 ] = a->limbs[ 2 ];
     123      321361 :   r->limbs[ 3 ] = a->limbs[ 3 ];
     124      321361 :   return r;
     125      321361 : }
     126             : 
     127             : /* r = (a == b) */
     128             : static inline int
     129             : fd_secp256k1_fp_eq( fd_secp256k1_fp_t const * a,
     130       10951 :                     fd_secp256k1_fp_t const * b ) {
     131       10951 :   return fd_uint256_eq( a, b );
     132       10951 : }
     133             : 
     134             : /* r = a + b */
     135             : static inline fd_secp256k1_fp_t *
     136             : fd_secp256k1_fp_add( fd_secp256k1_fp_t *       r,
     137             :                      fd_secp256k1_fp_t const * a,
     138     6698020 :                      fd_secp256k1_fp_t const * b ) {
     139     6698020 :   bignum_add_p256k1( r->limbs, (ulong *)a->limbs, (ulong *)b->limbs );
     140     6698020 :   fd_msan_unpoison( r->limbs, 32UL );
     141     6698020 :   return r;
     142     6698020 : }
     143             : 
     144             : /* r = a - b */
     145             : static inline fd_secp256k1_fp_t *
     146             : fd_secp256k1_fp_sub( fd_secp256k1_fp_t *       r,
     147             :                      fd_secp256k1_fp_t const * a,
     148     1893508 :                      fd_secp256k1_fp_t const * b ) {
     149     1893508 :   bignum_sub_p256k1( r->limbs, (ulong *)a->limbs, (ulong *)b->limbs );
     150     1893508 :   fd_msan_unpoison( r->limbs, 32UL );
     151     1893508 :   return r;
     152     1893508 : }
     153             : 
     154             : /* r = 2 * a */
     155             : static inline fd_secp256k1_fp_t *
     156             : fd_secp256k1_fp_dbl( fd_secp256k1_fp_t *       r,
     157     6801434 :                      fd_secp256k1_fp_t const * a ) {
     158     6801434 :   bignum_double_p256k1( r->limbs, (ulong *)a->limbs );
     159     6801434 :   fd_msan_unpoison( r->limbs, 32UL );
     160     6801434 :   return r;
     161     6801434 : }
     162             : 
     163             : /* r = a * b */
     164             : static inline fd_secp256k1_fp_t *
     165             : fd_secp256k1_fp_mul( fd_secp256k1_fp_t *       r,
     166             :                      fd_secp256k1_fp_t const * a,
     167     6208439 :                      fd_secp256k1_fp_t const * b ) {
     168     6208439 :   bignum_montmul_p256k1( r->limbs, (ulong *)a->limbs, (ulong *)b->limbs );
     169     6208439 :   fd_msan_unpoison( r->limbs, 32UL );
     170     6208439 :   return r;
     171     6208439 : }
     172             : 
     173             : /* r = a^2 */
     174             : static inline fd_secp256k1_fp_t *
     175             : fd_secp256k1_fp_sqr( fd_secp256k1_fp_t *       r,
     176     1667731 :                      fd_secp256k1_fp_t const * a ) {
     177     1667731 :   bignum_montsqr_p256k1( r->limbs, (ulong *)a->limbs );
     178     1667731 :   fd_msan_unpoison( r->limbs, 32UL );
     179     1667731 :   return r;
     180     1667731 : }
     181             : 
     182             : /* r = -a */
     183             : static inline fd_secp256k1_fp_t *
     184             : fd_secp256k1_fp_negate( fd_secp256k1_fp_t *       r,
     185      140060 :                         fd_secp256k1_fp_t const * a ) {
     186      140060 :   bignum_neg_p256k1( r->limbs, (ulong *)a->limbs );
     187      140060 :   fd_msan_unpoison( r->limbs, 32UL );
     188      140060 :   return r;
     189      140060 : }
     190             : 
     191             : static inline int
     192        2175 : fd_secp256k1_fp_is_odd( fd_secp256k1_fp_t const *r ) {
     193        2175 :   fd_secp256k1_fp_t scratch[1];
     194        2175 :   bignum_demont_p256k1( scratch->limbs, (ulong *)r->limbs );
     195        2175 :   fd_msan_unpoison( scratch->limbs, 32UL );
     196        2175 :   return scratch->limbs[ 0 ] & 1;
     197        2175 : }
     198             : 
     199             : /* r = 1 / a
     200             :    a MUST not be 0. */
     201             : static inline fd_secp256k1_fp_t *
     202             : fd_secp256k1_fp_invert( fd_secp256k1_fp_t *       r,
     203        2173 :                         fd_secp256k1_fp_t const * a ) {
     204        2173 :   fd_secp256k1_fp_t ad[1];
     205        2173 :   bignum_demont_p256k1( ad->limbs, (ulong *)a->limbs );
     206        2173 :   fd_msan_unpoison( ad->limbs, 32UL );
     207        2173 :   ulong t[ 12 ];
     208        2173 :   bignum_modinv( 4, r->limbs, (ulong *)ad->limbs, (ulong *)fd_secp256k1_const_p[0].limbs, t );
     209        2173 :   fd_msan_unpoison( r->limbs, 32UL );
     210        2173 :   bignum_tomont_p256k1( r->limbs, (ulong *)r->limbs );
     211        2173 :   fd_msan_unpoison( r->limbs, 32UL );
     212        2173 :   return r;
     213        2173 : }
     214             : 
     215             : static inline uchar *
     216             : fd_secp256k1_fp_tobytes( uchar                    r[ 32 ],
     217        4346 :                          fd_secp256k1_fp_t const *a ) {
     218        4346 :   fd_secp256k1_fp_t swapped[1];
     219        4346 :   bignum_demont_p256k1( swapped->limbs, (ulong *)a->limbs );
     220        4346 :   fd_msan_unpoison( swapped->limbs, 32UL );
     221        4346 :   fd_uint256_bswap( swapped, swapped );
     222        4346 :   memcpy( r, swapped->buf, 32 );
     223        4346 :   return r;
     224        4346 : }
     225             : 
     226             : /* r = 3 * a */
     227             : static inline fd_secp256k1_fp_t *
     228             : fd_secp256k1_fp_triple( fd_secp256k1_fp_t *       r,
     229      274839 :                         fd_secp256k1_fp_t const * a ) {
     230      274839 :   bignum_triple_p256k1( r->limbs, (ulong *)a->limbs );
     231      274839 :   fd_msan_unpoison( r->limbs, 32UL );
     232      274839 :   return r;
     233      274839 : }
     234             : 
     235             : /* r = a * R, i.e. converts a plain residue into the Montgomery domain. */
     236             : static inline fd_secp256k1_fp_t *
     237             : fd_secp256k1_fp_tomont( fd_secp256k1_fp_t *       r,
     238        2455 :                         fd_secp256k1_fp_t const * a ) {
     239        2455 :   bignum_tomont_p256k1( r->limbs, (ulong *)a->limbs );
     240        2455 :   fd_msan_unpoison( r->limbs, 32UL );
     241        2455 :   return r;
     242        2455 : }