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        4910 : fd_secp256k1_scalar_is_zero( fd_secp256k1_scalar_t const *r ) {
      19        4910 :   return fd_uint256_eq( r, fd_secp256k1_const_zero );
      20        4910 : }
      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        4916 :                                uchar const             input[ 32 ] ) {
      26        4916 :   memcpy( r, input, 32 );
      27        4916 :   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        4916 :   if( FD_UNLIKELY( fd_uint256_cmp( r, fd_secp256k1_const_n ) >= 0 ) ) {
      36           4 :     return NULL;
      37           4 :   }
      38        4912 :   if( FD_UNLIKELY( fd_secp256k1_scalar_is_zero( r ) ) ) {
      39           4 :     return NULL;
      40           4 :   }
      41        4908 :   return r;
      42        4912 : }
      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        2174 :                             fd_secp256k1_scalar_t const * a ) {
      50        2174 :   ulong t[ 12 ];
      51        2174 :   bignum_modinv( 4, r->limbs, (ulong *)a->limbs, (ulong *)fd_secp256k1_const_n[ 0 ].limbs, t );
      52        2174 :   fd_msan_unpoison( r->limbs, 32UL );
      53        2174 :   return r;
      54        2174 : }
      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        4347 :                          fd_secp256k1_scalar_t const * restrict b ) {
      61        4347 :   bignum_montmul( 4, r->limbs, (ulong *)a->limbs, (ulong *)b->limbs, (ulong *)fd_secp256k1_const_n[0].limbs );
      62        4347 :   fd_msan_unpoison( r->limbs, 32UL );
      63        4347 :   return r;
      64        4347 : }
      65             : 
      66             : /* r = -a */
      67             : static inline fd_secp256k1_scalar_t *
      68             : fd_secp256k1_scalar_negate( fd_secp256k1_scalar_t *       r,
      69        2173 :                             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        2173 :   ulong t[4];
      79        2173 :   bignum_sub( 4, t, 4, (ulong *)fd_secp256k1_const_n[ 0 ].limbs, 4, (ulong *)a->limbs );
      80        2173 :   fd_msan_unpoison( t, 32UL );
      81        2173 :   bignum_mod_n256k1_4( r->limbs, t );
      82        2173 :   fd_msan_unpoison( r->limbs, 32UL );
      83        2173 :   return r;
      84        2173 : }
      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        4347 :                             fd_secp256k1_scalar_t const * a ) {
     101        4347 :   bignum_demont( 4, r->limbs, (ulong *)a->limbs, (ulong *)fd_secp256k1_const_n[ 0 ].limbs );
     102        4347 :   fd_msan_unpoison( r->limbs, 32UL );
     103        4347 :   return r;
     104        4347 : }
     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      321144 :                      fd_secp256k1_fp_t const * a ) {
     120      321144 :   r->limbs[ 0 ] = a->limbs[ 0 ];
     121      321144 :   r->limbs[ 1 ] = a->limbs[ 1 ];
     122      321144 :   r->limbs[ 2 ] = a->limbs[ 2 ];
     123      321144 :   r->limbs[ 3 ] = a->limbs[ 3 ];
     124      321144 :   return r;
     125      321144 : }
     126             : 
     127             : /* r = (a == b) */
     128             : static inline int
     129             : fd_secp256k1_fp_eq( fd_secp256k1_fp_t const * a,
     130       10947 :                     fd_secp256k1_fp_t const * b ) {
     131       10947 :   return fd_uint256_eq( a, b );
     132       10947 : }
     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     6691676 :                      fd_secp256k1_fp_t const * b ) {
     139     6691676 :   bignum_add_p256k1( r->limbs, (ulong *)a->limbs, (ulong *)b->limbs );
     140     6691676 :   fd_msan_unpoison( r->limbs, 32UL );
     141     6691676 :   return r;
     142     6691676 : }
     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     1890742 :                      fd_secp256k1_fp_t const * b ) {
     149     1890742 :   bignum_sub_p256k1( r->limbs, (ulong *)a->limbs, (ulong *)b->limbs );
     150     1890742 :   fd_msan_unpoison( r->limbs, 32UL );
     151     1890742 :   return r;
     152     1890742 : }
     153             : 
     154             : /* r = 2 * a */
     155             : static inline fd_secp256k1_fp_t *
     156             : fd_secp256k1_fp_dbl( fd_secp256k1_fp_t *       r,
     157     6788231 :                      fd_secp256k1_fp_t const * a ) {
     158     6788231 :   bignum_double_p256k1( r->limbs, (ulong *)a->limbs );
     159     6788231 :   fd_msan_unpoison( r->limbs, 32UL );
     160     6788231 :   return r;
     161     6788231 : }
     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     6203006 :                      fd_secp256k1_fp_t const * b ) {
     168     6203006 :   bignum_montmul_p256k1( r->limbs, (ulong *)a->limbs, (ulong *)b->limbs );
     169     6203006 :   fd_msan_unpoison( r->limbs, 32UL );
     170     6203006 :   return r;
     171     6203006 : }
     172             : 
     173             : /* r = a^2 */
     174             : static inline fd_secp256k1_fp_t *
     175             : fd_secp256k1_fp_sqr( fd_secp256k1_fp_t *       r,
     176     1669874 :                      fd_secp256k1_fp_t const * a ) {
     177     1669874 :   bignum_montsqr_p256k1( r->limbs, (ulong *)a->limbs );
     178     1669874 :   fd_msan_unpoison( r->limbs, 32UL );
     179     1669874 :   return r;
     180     1669874 : }
     181             : 
     182             : /* r = -a */
     183             : static inline fd_secp256k1_fp_t *
     184             : fd_secp256k1_fp_negate( fd_secp256k1_fp_t *       r,
     185      139947 :                         fd_secp256k1_fp_t const * a ) {
     186      139947 :   bignum_neg_p256k1( r->limbs, (ulong *)a->limbs );
     187      139947 :   fd_msan_unpoison( r->limbs, 32UL );
     188      139947 :   return r;
     189      139947 : }
     190             : 
     191             : static inline int
     192        2174 : fd_secp256k1_fp_is_odd( fd_secp256k1_fp_t const *r ) {
     193        2174 :   fd_secp256k1_fp_t scratch[1];
     194        2174 :   bignum_demont_p256k1( scratch->limbs, (ulong *)r->limbs );
     195        2174 :   fd_msan_unpoison( scratch->limbs, 32UL );
     196        2174 :   return scratch->limbs[ 0 ] & 1;
     197        2174 : }
     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        2171 :                         fd_secp256k1_fp_t const * a ) {
     204        2171 :   fd_secp256k1_fp_t ad[1];
     205        2171 :   bignum_demont_p256k1( ad->limbs, (ulong *)a->limbs );
     206        2171 :   fd_msan_unpoison( ad->limbs, 32UL );
     207        2171 :   ulong t[ 12 ];
     208        2171 :   bignum_modinv( 4, r->limbs, (ulong *)ad->limbs, (ulong *)fd_secp256k1_const_p[0].limbs, t );
     209        2171 :   fd_msan_unpoison( r->limbs, 32UL );
     210        2171 :   bignum_tomont_p256k1( r->limbs, (ulong *)r->limbs );
     211        2171 :   fd_msan_unpoison( r->limbs, 32UL );
     212        2171 :   return r;
     213        2171 : }
     214             : 
     215             : static inline uchar *
     216             : fd_secp256k1_fp_tobytes( uchar                    r[ 32 ],
     217        4344 :                          fd_secp256k1_fp_t const *a ) {
     218        4344 :   fd_secp256k1_fp_t swapped[1];
     219        4344 :   bignum_demont_p256k1( swapped->limbs, (ulong *)a->limbs );
     220        4344 :   fd_msan_unpoison( swapped->limbs, 32UL );
     221        4344 :   fd_uint256_bswap( swapped, swapped );
     222        4344 :   memcpy( r, swapped->buf, 32 );
     223        4344 :   return r;
     224        4344 : }
     225             : 
     226             : /* r = 3 * a */
     227             : static inline fd_secp256k1_fp_t *
     228             : fd_secp256k1_fp_triple( fd_secp256k1_fp_t *       r,
     229      274538 :                         fd_secp256k1_fp_t const * a ) {
     230      274538 :   bignum_triple_p256k1( r->limbs, (ulong *)a->limbs );
     231      274538 :   fd_msan_unpoison( r->limbs, 32UL );
     232      274538 :   return r;
     233      274538 : }
     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        2452 :                         fd_secp256k1_fp_t const * a ) {
     239        2452 :   bignum_tomont_p256k1( r->limbs, (ulong *)a->limbs );
     240        2452 :   fd_msan_unpoison( r->limbs, 32UL );
     241        2452 :   return r;
     242        2452 : }