Line data    Source code

       1             : #include "fd_secp256k1_private.h"
       2             : #include "../../util/sanitize/fd_msan.h"
       3             : 
       4             : 
       5             : /* Given the coordinate X and the odd-ness of the Y coordinate, recovers Y and
       6             :    returns the affine group element. Returns NULL if there is no valid pair. */
       7             : static inline fd_secp256k1_point_t *
       8       60084 : fd_secp256k1_recovery_y( fd_secp256k1_point_t *r, fd_secp256k1_fp_t const *x, int odd ) {
       9       60084 :   fd_secp256k1_fp_t x2[1], x3[1];
      10             : 
      11             :   /* x^3 + b */
      12       60084 :   fd_secp256k1_fp_sqr( x2, x );
      13       60084 :   fd_secp256k1_fp_mul( x3, x2, x );
      14       60084 :   fd_secp256k1_fp_add( x3, x3, fd_secp256k1_const_b_mont );
      15             : 
      16             :   /* y^2 = x^3 + b <=> y = sqrt(x^3 + b) */
      17       60084 :   if( FD_UNLIKELY( !fd_secp256k1_fp_sqrt( r->y, x3 ) ) ) {
      18       30024 :     return NULL;
      19       30024 :   }
      20             : 
      21       30060 :   if( fd_secp256k1_fp_is_odd( r->y ) != odd ) {
      22          30 :     fd_secp256k1_fp_negate( r->y, r->y );
      23          30 :   }
      24             : 
      25       30060 :   fd_secp256k1_fp_set( r->x, x );
      26       30060 :   fd_secp256k1_fp_set( r->z, fd_secp256k1_const_one_mont );
      27       30060 :   return r;
      28       60084 : }
      29             : 
      30             : uchar *
      31             : fd_secp256k1_recover( uchar        public_key[64],
      32             :                       uchar const  msg_hash[32],
      33             :                       uchar const  sig[64],
      34       60153 :                       int          recovery_id ) {
      35       60153 :   if( FD_UNLIKELY( !( recovery_id>=0 && recovery_id<=3 ) ) ) {
      36             :     /* COV: the callers do the same check */
      37          27 :     return NULL;
      38          27 :   }
      39             : 
      40       60126 :   fd_secp256k1_scalar_t s[1];
      41       60126 :   fd_secp256k1_scalar_t rs[1];
      42       60126 :   if( FD_UNLIKELY( !fd_secp256k1_scalar_frombytes( rs, &sig[  0 ] ) ) ) {
      43          21 :     return NULL;
      44          21 :   }
      45       60105 :   if( FD_UNLIKELY( !fd_secp256k1_scalar_frombytes(  s, &sig[ 32 ] ) ) ) {
      46          12 :     return NULL;
      47          12 :   }
      48             : 
      49       60093 :   fd_secp256k1_fp_t r[1];
      50       60093 :   bignum_tomont_p256k1( r->limbs, rs->limbs );
      51       60093 :   fd_msan_unpoison( r->limbs, 32UL );
      52             : 
      53       60093 :   if( recovery_id & 2 ) {
      54             :     /* If rs >= p - n, return NULL. Otherwise, add the n to r.
      55             :        https://github.com/bitcoin-core/secp256k1/blob/v0.7.1/src/modules/recovery/main_impl.h#L104-L109 */
      56          21 :     if( FD_UNLIKELY( fd_uint256_cmp( rs, fd_secp256k1_const_p_minus_n ) >= 0 ) ) {
      57           9 :       return NULL;
      58           9 :     }
      59             :     /* Note that *only* r is incremented, rs is left unchanged. */
      60          12 :     fd_secp256k1_fp_add( r, r, fd_secp256k1_const_n_mont );
      61          12 :   }
      62             : 
      63             :   /* Recover the full public key group element. */
      64       60084 :   fd_secp256k1_point_t a[1];
      65       60084 :   if( FD_UNLIKELY( !fd_secp256k1_recovery_y( a, r, recovery_id & 1 ) ) ) {
      66       30024 :     return NULL;
      67       30024 :   }
      68             : 
      69       30060 :   fd_uint256_t msg[1];
      70       30060 :   memcpy( msg, msg_hash, 32 );
      71       30060 :   fd_uint256_bswap( msg, msg );
      72             :   /* The message scalar is unconditionally reduced to the scalar field.
      73             :      https://github.com/bitcoin-core/secp256k1/blob/v0.7.1/src/scalar_4x64_impl.h#L151 */
      74       30060 :   bignum_mod_n256k1_4( msg->limbs, (ulong *)msg->limbs );
      75       30060 :   fd_msan_unpoison( msg->limbs, 32UL );
      76       30060 :   fd_secp256k1_scalar_tomont( msg, msg );
      77             : 
      78       30060 :   fd_secp256k1_scalar_t rn[1], u1[1], u2[1];
      79       30060 :   fd_secp256k1_point_t pubkey[1];
      80             : 
      81             :   /* We delay converting rs into montgomery domain since
      82             :      we may need to perform the comparison against p-n first. */
      83       30060 :   fd_secp256k1_scalar_tomont( s, s );
      84             : 
      85             :   /* Unfortunately s2n-bignum has no API for performing
      86             :      in-montgomery inversion, so we invert and then convert. */
      87       30060 :   fd_secp256k1_scalar_invert( rn, rs );
      88       30060 :   fd_secp256k1_scalar_tomont( rn, rn );
      89             : 
      90       30060 :   fd_secp256k1_scalar_mul   ( u1, rn, msg );
      91       30060 :   fd_secp256k1_scalar_negate( u1, u1      );
      92       30060 :   fd_secp256k1_scalar_mul   ( u2, rn, s   );
      93             : 
      94       30060 :   fd_secp256k1_scalar_demont( u2, u2 );
      95       30060 :   fd_secp256k1_scalar_demont( u1, u1 );
      96       30060 :   fd_secp256k1_double_base_mul( pubkey, u1, a, u2 );
      97             : 
      98             :   /* If the computed pubkey is the identity point, we return NULL
      99             :      https://github.com/bitcoin-core/secp256k1/blob/v0.7.1/src/modules/recovery/main_impl.h#L120 */
     100       30060 :   if( FD_UNLIKELY( fd_secp256k1_point_is_identity( pubkey ) ) ) {
     101           0 :     return NULL;
     102           0 :   }
     103             : 
     104             :   /* Serialize the public key into an uncompressed form.
     105             :      The output does not have the recovery_id. */
     106       30060 :   fd_secp256k1_point_to_affine( pubkey, pubkey );
     107       30060 :   fd_secp256k1_fp_tobytes( &public_key[  0 ], pubkey->x );
     108       30060 :   fd_secp256k1_fp_tobytes( &public_key[ 32 ], pubkey->y );
     109       30060 :   return public_key;
     110       30060 : }