our $VERSION = '0.063';
use base Crypt::ECDSA::Curve;use Carp qw( carp croak );sub equation { 'y * y = x * x * x + a * x + b, mod p, with a = -3' }
sub is_on_curve {
my ( $self, $x, $y ) = @_;
$x = bint($x) unless ref $x;
$y = bint($y) unless ref $y;
my $mod = $self->{p};
$mod = bint($mod) unless ref $mod;
my $a = bint( $self->{a} );
my $a_neg = ( $a < 0 ) ? 1 : 0;
my $b = bint( $self->{b} );
my $b_neg = ( $b < 0 ) ? 1 : 0;
return Crypt::ECDSA::is_Fp_point_on_curve( $x->{value}, $y->{value},
$mod->{value}, $a->{value}, $a_neg, $b->{value}, $b_neg );
}
sub double_on_curve {
my ( $self, $x, $y, $order ) = @_;
my $p = bint( $self->{p} );
my $a = bint( $self->{a} );
my $a_neg = ( $a < 0 ) ? 1 : 0;
my $x_sum = bint($x)->bmod($p);
my $y_sum = bint($y)->bmod($p);
Crypt::ECDSA::double_Fp_point(
$x_sum->{value}, $y_sum->{value},
$p->{value}, $a->{value}, $a_neg
);
return $self->infinity if
$x_sum->is_nan or $y_sum->is_nan or
( $x_sum->is_zero and $y_sum->is_zero );
return Crypt::ECDSA::Point->new(
X => $x_sum,
Y => $y_sum,
order => $order,
curve => $self
);
}
sub add_on_curve {
my ( $self, $x1, $y1, $x2, $y2, $order ) = @_;
my $p = bint( $self->{p} );
my $a = bint( $self->{a} );
my $a_neg = ( $a < 0 ) ? 1 : 0;
my $x_sum = bint($x1)->bmod($p);
my $y_sum = bint($y1)->bmod($p);
my $x2_mod = $x2 % $p;
my $y2_mod = $y2 % $p;
Crypt::ECDSA::add_Fp_point(
$x_sum->{value}, $y_sum->{value},
$x2_mod->{value}, $y2_mod->{value},
$p->{value}, $a->{value}, $a_neg
);
return $self->infinity if
$x_sum->is_nan or $y_sum->is_nan or
( $x_sum->is_zero and $y_sum->is_zero );
return Crypt::ECDSA::Point->new(
X => $x_sum,
Y => $y_sum,
order => $order,
curve => $self
);
}
sub subtract_on_curve {
my ( $self, $x1, $y1, $x2, $y2, $order ) = @_;
return $self->add_on_curve( $self, $x1, $y1, $x2, ( -$y2 ) % $self->{p},
$order );
}
sub inverse_on_curve {
my ( $self, $x, $y, $order ) = @_;
my $p = bint( $self->{p} );
my $y_neg = bint($y);
$y_neg->bneg;
$y_neg->bmod($p);
return Crypt::ECDSA::Point->new(
X => bint($x),
Y => $y_neg,
order => $order,
curve => $self
);
}
sub multiply_on_curve {
my ( $self, $x, $y, $scalar, $order ) = @_;
my $p = bint( $self->{p} );
my $a = bint( $self->{a} );
my $a_neg = ( $a < 0 ) ? 1 : 0;
my $new_x = bint($x)->bmod($p);
my $new_y = bint($y)->bmod($p);
$scalar = bint($scalar);
$scalar->bmod($order) if $order;
croak("cannot multiply by a negative number") if $scalar < 0;
return $self->infinity unless $scalar;
if ( $scalar != 1 ) {
Crypt::ECDSA::multiply_Fp_point(
$new_x->{value}, $new_y->{value}, $scalar->{value},
$p->{value}, $a->{value}, $a_neg
);
}
return $self->infinity
if ( $new_x->is_nan or $new_y->is_nan
or ( $new_x->is_zero and $new_y->is_zero ) );
return Crypt::ECDSA::Point->new(
X => $new_x,
Y => $new_y,
order => $order,
curve => $self
);
}
sub is_weak_curve {
my ($self) = @_;
my $n = $self->{N};
my $r = $self->{prime_group_order};
my $b = 29;
if ( $n <= 142 ) { $b = 6 }
elsif ( $n <= 165 ) { $b = 7 }
elsif ( $n <= 186 ) { $b = 8 }
elsif ( $n <= 206 ) { $b = 9 }
elsif ( $n <= 226 ) { $b = 10 }
elsif ( $n <= 244 ) { $b = 11 }
elsif ( $n <= 262 ) { $b = 12 }
elsif ( $n <= 280 ) { $b = 13 }
elsif ( $n <= 297 ) { $b = 14 }
elsif ( $n <= 313 ) { $b = 15 }
elsif ( $n <= 330 ) { $b = 16 }
elsif ( $n <= 346 ) { $b = 17 }
elsif ( $n <= 361 ) { $b = 18 }
elsif ( $n <= 376 ) { $b = 19 }
elsif ( $n <= 391 ) { $b = 20 }
elsif ( $n <= 406 ) { $b = 21 }
elsif ( $n <= 420 ) { $b = 22 }
elsif ( $n <= 434 ) { $b = 23 }
elsif ( $n <= 448 ) { $b = 24 }
elsif ( $n <= 462 ) { $b = 25 }
elsif ( $n <= 475 ) { $b = 26 }
elsif ( $n <= 488 ) { $b = 27 }
elsif ( $n <= 501 ) { $b = 28 }
$n = bint($n);
my $test_val = bint(1);
my $q = 2**$n;
for my $i ( 1 .. $b ) {
$test_val *= $q;
$test_val %= $r;
return 1 if $test_val == 1;
}
return;
}
sub to_octet {
my ( $self, $x, $y, $compress ) = @_;
my $octet;
my $x_octet = pack 'H*', substr( $x->as_hex, 2 );
if ($compress) {
my $first_byte = $y % 2 ? "\x03" : "\x02";
return $first_byte . $x_octet;
}
else {
my $y_octet = pack 'H*', substr( $y->as_hex, 2 );
return "\x04" . $x_octet . $y_octet;
}
}
sub from_octet {
my ( $self, $octet ) = @_;
my $q_bytes = ceil( ( length( $self->{q}->as_bin ) - 2 ) / 8 );
my $oct_len = length $octet;
my $invalid_point = 1;
my $x = bint();
my $y = bint();
if ( $oct_len == $q_bytes + 1 ) { # compressed point
my $y_byte = substr( $octet, 0, 1 );
my $y_test;
$y_test = 0 if $y_byte eq "\x02";
$y_test = 1 if $y_byte eq "\x03";
my $x = hex_bint( unpack( 'H*', substr( $octet, 1 ) ) );
if ( $x >= 0 and $x < $self->{p} and defined $y_test ) {
my $alpha = bint();
$alpha =
( $x * $x * $x + $self->{a} * $x + $self->{b} ) % $self->{p};
$alpha->bsqrt();
if ( ( $alpha & 1 ) == $y_test ) {
$y = bint($alpha);
}
else {
$y = bint( $self->{p} - $alpha );
}
$invalid_point = 0 if $y >= 0 and $y < $self->{p};
}
}
elsif ( $oct_len == 2 * $q_bytes + 1 ) {
my $m_byte = substr $octet, 0, 1;
if ( $m_byte eq "\x04" ) {
my $x_bytes = substr $octet, 1, $q_bytes;
my $y_bytes = substr $octet, 1 + $q_bytes, $q_bytes;
$x = hex_bint( unpack( "H*", $x_bytes ) );
$y = hex_bint( unpack( "H*", $y_bytes ) );
$invalid_point = 0
if $y >= 0
and $y < $self->{p}
and $x >= 0
and $x < $self->{p}
and $self->is_on_curve( $x, $y );
}
}
if ($invalid_point) {
$x = 0;
$y = 0;
carp("invalid octet source bytes for this point type");
}
return ( $x, $y );
}
1;