File Coverage

blib/lib/Steemit/ECDSA.pm

Criterion	Covered	Total	%
statement	115	136	84.5
branch	16	34	47.0
condition	26	55	47.2
subroutine	16	17	94.1
pod	9	12	75.0
total	182	254	71.6

package Steemit::ECDSA;
use Modern::Perl;
use Math::EllipticCurve::Prime;
use Digest::SHA;
use Carp;

my $curve = Math::EllipticCurve::Prime->from_name('secp256k1');
$::testing_only::inject_k = undef;

# https://tools.ietf.org/html/rfc6979#section-3.2
sub deterministicGenerateK {
  my ( $hash, $d, $nonce)  = @_;

  $nonce //= 0;

  if ($nonce) {
    $hash = Digest::SHA::sha256( $hash.pack( "C",$nonce) );
  }

  # sanity check
  die " hash must be 256 bit but byte length is ".length($hash) unless length($hash) == 32;

  my $x = $d;
  # Step B
  my $v = pack "H*", 'F'x64;

  # Step C
  my $k = pack "H*", '0'x64;

  # Step D
  $k = Digest::SHA::hmac_sha256( $v.pack('C',0).$x->to_bytes.$hash, $k);

  # Step E
  $v = Digest::SHA::hmac_sha256($v, $k);

  # Step F
  $k = Digest::SHA::hmac_sha256($v.pack('C',1).$x->to_bytes.$hash ,$k);

  #// Step G
  $v = Digest::SHA::hmac_sha256($v,$k);

  #// Step H1/H2a, ignored as tlen === qlen (256 bit)
  #// Step H2b
  $v = Digest::SHA::hmac_sha256( $v,$k);

  my $T = Math::BigInt->from_bytes( $v );

  return($T,$v,$k)
}

sub ecdsa_sign {
  my( $message, $key ) = @_;
  my $n = $curve->n; my $nlen = length($n->to_bytes);
  my $sha256 = Digest::SHA::sha256( $message );
  my $z = Math::BigInt->from_bytes(substr($sha256,0,$nlen));
  my $N_OVER_TWO = $n->copy->brsft(1);

  my $is_canonical;
  my ($k, $r, $s, $i );
  my $nonce = 0;
  while( 1){

     ($k, $r, $s, $i ) = map {Math::BigInt->new($_) }(0,0,0);
     my ($k,$v,$k2) = deterministicGenerateK( substr($sha256,0,$nlen), $key, $nonce);

     # we need r and s to be in a valid form first
     until( $k > 0 and $k < $n and $r > 0 and $s > 0 and length($r->to_bytes) == 32 and length($s->to_bytes) == 32 and _are_rs_canonical($r,$s) ){

         $k2 = Digest::SHA::hmac_sha256( $v.pack('C',0), $k2 );
         $v  = Digest::SHA::hmac_sha256( $v, $k2 );
         $k  = $::testing_only::inject_k // Math::BigInt->from_bytes( $v );

         #$k = $::testing_only::inject_k // Math::BigInt->from_bin($random->string_from('01',$nlen-2)) until $k > 1 and $k < $n;
         my $point = $curve->g->multiply($k);
         $r = $point->x->bmod($n);
         $s = (($z + $key * $r) * $k->bmodinv($n))->bmod($n);
     }

     if( $s > $N_OVER_TWO ){
        $s = $n - $s;
     }

     $i = eval{ calcPubKeyRecoveryParam($message, $r, $s, get_public_key_point( $key ) ) };
     if( my $error = $@ and not $i ){
        die $error unless $error =~ /Unable to find valid recovery factor/;
        $nonce++;
        next;
     }
     return ( $r, $s, $i );
  }

  return ( $r, $s, $i );
}

sub _are_rs_canonical {
   my($r,$s) = @_;
   return is_signature_canonical_canonical( pack('C','0').$r->to_bytes.$s->to_bytes)
}

sub is_signature_canonical_canonical{
   my( $c ) = @_;
   #https://github.com/steemit/steem/blob/2945196ca5ead5049e78679d69affea98d97e27b/libraries/fc/src/crypto/elliptic_common.cpp#L171
   return !(unpack("xC",$c) & 0x80)
   && !( unpack("xC",$c) == 0 && !( unpack("x[2]C",$c) & 0x80))
   && !( unpack("x[33]C",$c) & 0x80)
   && !( unpack("x[33]C",$c) == 0 && !( unpack("x[34]C",$c) & 0x80));
   return 1
}

sub bytes_32_sha256 {
  my ( $message ) = @_;
  my $sha256 = Digest::SHA::sha256( $message );
  my $n = $curve->n; my $nlen = length($n->to_bytes);
  my $z = Math::BigInt->from_bytes(substr($sha256,0,$nlen));
  return $z;
}

sub ecdsa_verify {
   my ($message, $pubkey, $r, $s) = @_;
   my $n = $curve->n;
   return unless $r > 0 and $r < $n and $s > 0 and $s < $n;

   my $nlen  = length($n->to_bytes);
   my $sha256 = Digest::SHA::sha256( $message );
   my $z = Math::BigInt->from_bytes(substr($sha256,0,$nlen));

   my $w = $s->copy->bmodinv($n);
   my $u1 = ($w * $z)->bmod($n); my $u2 = ($w * $r)->bmod($n);
   my $x1 = $curve->g->multiply($u1)->add($pubkey->multiply($u2))->x->bmod($n);
   return $x1 == $r;
}


sub calcPubKeyRecoveryParam {
  my ( $message, $r, $s, $Q ) = @_;
  for ( my $i = 0; $i < 4; $i++ ){
     my $Qprime = recoverPubKey($message,$r,$s,$i);
     if( $Qprime->x == $Q->x and $Qprime->y == $Q->y ){
       return Math::BigInt->new($i);
     }
  }

  die ('Unable to find valid recovery factor')
}


sub recoverPubKey {
  my ( $message, $r, $s, $i ) = @_;

  $i //= 0;
  my $e = bytes_32_sha256($message );
  die "i must be 0 <= i < 4" unless $i >= 0 and $i < 4;

  my $n = $curve->n;
  my $G = $curve->g;

  die "invalid r" if $r < 0 or $r > $n;
  die "invalid s" if $s < 0 or $s > $n;

  my $isYOdd = ( $i == 1 or $i == 3 );

  my $isSecondKey = $i > 2;

  my $x = $isSecondKey ? ( $r + $n ) : $r;
  my $R = point_from_x( $r, $isYOdd );

  my $nR = $R->multiply( $n );
  die "nR is not a valid curve point " unless $nR->infinity;

  my $eNeg = $e->copy->bneg->bmod($n);

  my $rInv = $r->copy->bmodinv($n);

  my $Q = $R->multiply( $s )->badd( $G->multiply($eNeg) )->multiply( $rInv );

  return $Q;
}

sub get_compressed_public_key {
   my( $key ) = @_;

   my $Q = get_public_key_point( $key );
   my $buffer;

   if( $Q->y % 2 ){
      $buffer = pack 'C', 0x03;
   }else{
      $buffer = pack 'C', 0x02;
   }

   $buffer .= pack( 'H*', "0" x (( length($curve->p->to_bytes) - length($Q->x->to_bytes) ) * 2 ));
   $buffer .= $Q->x->to_bytes;

   return $buffer;
}

sub get_recovery_factor {
   my ( $x,$y ) = @_;
   my ($p, $a, $b) = ($curve->p, $curve->a, $curve->b);
   $x = $x->copy;
   $y = $y->copy;

   my $yr = ($x->bmodpow(3,$p)+$a*$x+$b)->bmodpow(($p+1)/4,$p);
   if( $y eq $yr ){
      return $yr%2;
   }
   $yr = $p - $y;
   if( $y eq $yr ){
      return ( $yr%2 + 1 ) % 2;
   }
   confess "unable to determine recovery factor";
}

sub point_from_x {
   my ( $x,$i ) = @_;
   my $y = recover_y( $x, $i );
   return Math::EllipticCurve::Prime::Point->new(
      x => $x,
      y => $y,
      curve => $curve
   );
}

sub recover_y {
   my ( $x,$i ) = @_;
   my ($p, $a, $b) = ($curve->p, $curve->a, $curve->b);
   $x = $x->copy;

   my $y = ($x->bmodpow(3,$p)+$a*$x+$b)->bmodpow(($p+1)/4,$p);

   $y = $p - $y if $i%2 ne $y%2;
   return $y;
}


sub get_public_key_point {
   my( $key ) = @_;

   die "key needs to be a Math::BigInt Object " unless( $key->isa('Math::BigInt') );

   my $public_key = $curve->g->multiply( $key );

   return $public_key;
}
1;


__END__