| 1 | package Crypt::Perl::ECDSA::EC::Point; | ||
| 2 | |||
| 3 | use strict; | ||
| 4 | use warnings; | ||
| 5 | |||
| 6 | use Crypt::Perl::BigInt (); | ||
| 7 | |||
| 8 | my ($bi1, $bi2, $bi3); | ||
| 9 | |||
| 10 | END { | ||
| 11 | undef $bi1, $bi2, $bi3; | ||
| 12 | } | ||
| 13 | |||
| 14 | sub new_infinity { | ||
| 15 | my ($class) = @_; | ||
| 16 | |||
| 17 | return $class->new( undef, undef ); | ||
| 18 | } | ||
| 19 | |||
| 20 | #$curve is ECCurve | ||
| 21 | #$x and $y are “ECFieldElement” | ||
| 22 | #$z isa bigint (?) | ||
| 23 | sub new { | ||
| 24 | my ($class, $curve, $x, $y, $z) = @_; | ||
| 25 | |||
| 26 | $bi1 ||= Crypt::Perl::BigInt->new(1); | ||
| 27 | $bi2 ||= Crypt::Perl::BigInt->new(2); | ||
| 28 | $bi3 ||= Crypt::Perl::BigInt->new(3); | ||
| 29 | |||
| 30 | my $self = { | ||
| 31 | curve => $curve, | ||
| 32 | x => $x, | ||
| 33 | y => $y, | ||
| 34 | z => $z || $bi1->copy(), | ||
| 35 | zinv => undef, | ||
| 36 | }; | ||
| 37 | |||
| 38 | return bless $self, $class; | ||
| 39 | } | ||
| 40 | |||
| 41 | sub is_infinity { | ||
| 42 | my ($self) = @_; | ||
| 43 | |||
| 44 | return 1 if !defined $self->{'x'} && !defined $self->{'y'}; | ||
| 45 | |||
| 46 | return( ($self->{'z'}->is_zero() && !$self->{'y'}->to_bigint()->is_zero()) || 0 ); | ||
| 47 | } | ||
| 48 | |||
| 49 | #returns ECFieldElement | ||
| 50 | sub get_x { | ||
| 51 | my ($self) = @_; | ||
| 52 | |||
| 53 | return $self->_get_x_or_y('x'); | ||
| 54 | } | ||
| 55 | |||
| 56 | #returns ECFieldElement | ||
| 57 | #Used in key generation (not signing … ?) | ||
| 58 | sub get_y { | ||
| 59 | my ($self) = @_; | ||
| 60 | |||
| 61 | return $self->_get_x_or_y('y'); | ||
| 62 | } | ||
| 63 | |||
| 64 | sub _get_x_or_y { | ||
| 65 | my ($self, $to_get) = @_; | ||
| 66 | |||
| 67 | if (!defined $self->{'zinv'}) { | ||
| 68 | $self->{'zinv'} = $self->{'z'}->copy()->bmodinv($self->{'curve'}{'q'}); | ||
| 69 | } | ||
| 70 | |||
| 71 | return $self->{'curve'}->from_bigint( | ||
| 72 | $self->{$to_get}->to_bigint()->copy()->bmul($self->{'zinv'})->bmod($self->{'curve'}{'q'}) | ||
| 73 | ); | ||
| 74 | } | ||
| 75 | |||
| 76 | sub negate { | ||
| 77 | my ($self) = @_; | ||
| 78 | |||
| 79 | my @args = @{$self}{qw( curve x y z )}; | ||
| 80 | $args[2] = $args[2]->negate(); | ||
| 81 | |||
| 82 | return (ref $self)->new(@args); | ||
| 83 | } | ||
| 84 | |||
| 85 | #Did the quadratic formula explode??? | ||
| 86 | sub twice { | ||
| 87 | my ($self) = @_; | ||
| 88 | |||
| 89 | return $self if $self->is_infinity(); | ||
| 90 | |||
| 91 | #if ($self->{'y'}->to_bigint()->signum() == 0) { | ||
| 92 | # return $self->{'curve'}->get_infinity(); | ||
| 93 | #} | ||
| 94 | |||
| 95 | my $x1 = $self->{'x'}->to_bigint(); | ||
| 96 | my $y1 = $self->{'y'}->to_bigint(); | ||
| 97 | |||
| 98 | my $y1z1 = $y1->copy()->bmul($self->{'z'}); | ||
| 99 | |||
| 100 | my $y1sqz1 = $y1z1->copy()->bmul($y1)->bmod($self->{'curve'}{'q'}); | ||
| 101 | |||
| 102 | my $a = $self->{'curve'}{'a'}; | ||
| 103 | |||
| 104 | # w = 3 * x1^2 + a * z1^2 | ||
| 105 | #var w = x1.square().multiply(THREE); | ||
| 106 | my $w = $x1->copy()->bpow($bi2)->bmul($bi3); | ||
| 107 | |||
| 108 | if (!$a->is_zero()) { | ||
| 109 | #$w += ($self->{'z'} ** 2) * $a; | ||
| 110 | $w->badd( $a->copy()->bmul( $self->{'z'} )->bmul($self->{'z'}) ); | ||
| 111 | } | ||
| 112 | |||
| 113 | $w->bmod($self->{'curve'}{'q'}); | ||
| 114 | |||
| 115 | # x3 = 2 * y1 * z1 * (w^2 - 8 * x1 * y1^2 * z1) | ||
| 116 | #var x3 = w.square().subtract(x1.shiftLeft(3).multiply(y1sqz1)).shiftLeft(1).multiply(y1z1).mod(this.curve.q); | ||
| 117 | |||
| 118 | my $x3 = $w->copy()->bmuladd( $w, $y1sqz1->copy()->bmul($x1)->blsft($bi3)->bneg() )->bmul($bi2)->bmul($y1z1); | ||
| 119 | #my $x3 = 2 * $y1z1 * (($w ** 2) - ($x1 << 3) * $y1sqz1); | ||
| 120 | #my $x3 = ($w ** 2) - (($x1 << 3) * $y1sqz1); | ||
| 121 | #$x3 = $x3 << 1; | ||
| 122 | #$x3 *= $y1z1; | ||
| 123 | |||
| 124 | # y3 = 4 * y1^2 * z1 * (3 * w * x1 - 2 * y1^2 * z1) - w^3 | ||
| 125 | #var y3 = w.multiply(THREE).multiply(x1).subtract(y1sqz1.shiftLeft(1)).shiftLeft(2).multiply(y1sqz1).subtract(w.square().multiply(w)).mod(this.curve.q); | ||
| 126 | #my $y3 = 4 * $y1sqz1 * (3 * $w * $x1 - 2 * $y1sqz1) - ($w ** 3); | ||
| 127 | |||
| 128 | my $y3 = $y1sqz1->copy()->blsft($bi2); | ||
| 129 | |||
| 130 | $y3->bmuladd( | ||
| 131 | |||
| 132 | #We don’t need y1sqz1 anymore | ||
| 133 | $w->copy()->bmul($bi3)->bmuladd($x1, $y1sqz1->blsft($bi1)->bneg()), | ||
| 134 | |||
| 135 | #Don’t need $w anymore | ||
| 136 | $w->bpow($bi3)->bneg(), | ||
| 137 | ); | ||
| 138 | |||
| 139 | #// z3 = 8 * (y1 * z1)^3 | ||
| 140 | #var z3 = y1z1.square().multiply(y1z1).shiftLeft(3).mod(this.curve.q); | ||
| 141 | #my $z3 = ($y1z1 ** 3) << 3; | ||
| 142 | my $z3 = $y1z1->bpow($bi3)->blsft($bi3); #don’t need y1z1 anymore | ||
| 143 | |||
| 144 | #In original JS logic | ||
| 145 | $_->bmod($self->{'curve'}{'q'}) for ($x3, $y3, $z3); | ||
| 146 | |||
| 147 | #return new ECPointFp(this.curve, this.curve.fromBigInteger(x3), this.curve.fromBigInteger(y3), z3); | ||
| 148 | return (ref $self)->new( | ||
| 149 | $self->{'curve'}, | ||
| 150 | $self->{'curve'}->from_bigint($x3), | ||
| 151 | $self->{'curve'}->from_bigint($y3), | ||
| 152 | $z3, | ||
| 153 | ); | ||
| 154 | } | ||
| 155 | |||
| 156 | #XXX clear | ||
| 157 | sub dump { | ||
| 158 | my ($self, $label) = @_; | ||
| 159 | |||
| 160 | printf "$label.x: %s\n", $self->{'x'}->to_bigint()->as_hex(); | ||
| 161 | printf "$label.y: %s\n", $self->{'y'}->to_bigint()->as_hex(); | ||
| 162 | printf "$label.z: %s\n", $self->{'z'}->as_hex(); | ||
| 163 | } | ||
| 164 | |||
| 165 | #yowza ... | ||
| 166 | sub multiply { | ||
| 167 | my ($self, $k) = @_; | ||
| 168 | #print "in mult\n"; | ||
| 169 | #$self->dump('self'); | ||
| 170 | |||
| 171 | if ($self->is_infinity()) { | ||
| 172 | return $self; | ||
| 173 | } | ||
| 174 | |||
| 175 | #TODO | ||
| 176 | #if ($k->signum() == 0) { | ||
| 177 | # return $self->{'curve'}->getInfinity(); #should this happen? | ||
| 178 | #} | ||
| 179 | |||
| 180 | #print "here2\n"; | ||
| 181 | my $e = $k; | ||
| 182 | my $h = $e->copy()->bmul($bi3); | ||
| 183 | #print "h: " . $h->as_hex() . $/; | ||
| 184 | |||
| 185 | my $neg = $self->negate(); | ||
| 186 | #$neg->dump('neg'); | ||
| 187 | my $R = $self; | ||
| 188 | |||
| 189 | #print "start loop: " . (_MBI_bit_length($h) - 2) . $/; | ||
| 190 | for my $i ( reverse( 1 .. ($h->bit_length() - 2) ) ) { | ||
| 191 | $R = $R->twice(); | ||
| 192 | #$R->dump("R, loop $i"); | ||
| 193 | |||
| 194 | my $hbit = $h->test_bit($i); | ||
| 195 | my $ebit = $e->test_bit($i); | ||
| 196 | #print "hbit [$hbit], ebit [$ebit]\n"; | ||
| 197 | |||
| 198 | if ($hbit != $ebit) { | ||
| 199 | $R = $R->add( $hbit ? $self : $neg ); | ||
| 200 | } | ||
| 201 | #$R->dump("R, end of loop"); | ||
| 202 | } | ||
| 203 | |||
| 204 | return $R; | ||
| 205 | } | ||
| 206 | |||
| 207 | #$b isa ECPoint | ||
| 208 | sub add { | ||
| 209 | my ($self, $b) = @_; | ||
| 210 | #$b->dump('$b'); | ||
| 211 | |||
| 212 | #if(this.isInfinity()) return b; | ||
| 213 | #if(b.isInfinity()) return this; | ||
| 214 | |||
| 215 | return $b if $self->is_infinity(); | ||
| 216 | return $self if $b->is_infinity(); | ||
| 217 | |||
| 218 | #// u = Y2 * Z1 - Y1 * Z2 | ||
| 219 | #var u = b.y.toBigInteger().multiply(this.z).subtract(this.y.toBigInteger().multiply(b.z)).mod(this.curve.q); | ||
| 220 | my $u = $b->{'y'}->to_bigint()->copy()->bmuladd( | ||
| 221 | $self->{'z'}, | ||
| 222 | $self->{'y'}->to_bigint()->copy()->bneg()->bmul($b->{'z'}), | ||
| 223 | ); | ||
| 224 | # $b->{'z'}; | ||
| 225 | |||
| 226 | #// v = X2 * Z1 - X1 * Z2 | ||
| 227 | #var v = b.x.toBigInteger().multiply(this.z).subtract(this.x.toBigInteger().multiply(b.z)).mod(this.curve.q); | ||
| 228 | my $v = $b->{'x'}->to_bigint()->copy()->bmuladd( | ||
| 229 | $self->{'z'}, | ||
| 230 | $self->{'x'}->to_bigint()->copy()->bneg()->bmul($b->{'z'}), | ||
| 231 | ); | ||
| 232 | |||
| 233 | |||
| 234 | $_->bmod($self->{'curve'}{'q'}) for ($u, $v); | ||
| 235 | #print "u: " . $u->as_hex() . $/; | ||
| 236 | #print "v: " . $v->as_hex() . $/; | ||
| 237 | #if(BigInteger.ZERO.equals(v)) { | ||
| 238 | # if(BigInteger.ZERO.equals(u)) { | ||
| 239 | # return this.twice(); // this == b, so double | ||
| 240 | # } | ||
| 241 | #return this.curve.getInfinity(); // this = -b, so infinity | ||
| 242 | #} | ||
| 243 | if ($v->is_zero()) { | ||
| 244 | if ($u->is_zero()) { | ||
| 245 | return $self->twice(); | ||
| 246 | } | ||
| 247 | |||
| 248 | return $self->{'curve'}->get_infinity(); | ||
| 249 | } | ||
| 250 | |||
| 251 | #var THREE = new BigInteger("3"); | ||
| 252 | #var x1 = this.x.toBigInteger(); | ||
| 253 | #var y1 = this.y.toBigInteger(); | ||
| 254 | #var x2 = b.x.toBigInteger(); | ||
| 255 | #var y2 = b.y.toBigInteger(); | ||
| 256 | my ($x1, $y1, $z1) = @{$self}{ qw( x y z ) }; | ||
| 257 | my ($x2, $y2, $z2) = @{$b}{ qw( x y z ) }; | ||
| 258 | |||
| 259 | $_ = $_->to_bigint() for ($x1, $y1, $x2, $y2); | ||
| 260 | |||
| 261 | #var v2 = v.square(); | ||
| 262 | #var v3 = v2.multiply(v); | ||
| 263 | #var x1v2 = x1.multiply(v2); | ||
| 264 | #var zu2 = u.square().multiply(this.z); | ||
| 265 | |||
| 266 | my $v2 = $v->copy()->bmul($v); | ||
| 267 | my $v3 = $v->copy()->bmul($v2); | ||
| 268 | |||
| 269 | my $x1v2 = $x1->copy()->bmul($v2); | ||
| 270 | my $zu2 = $u->copy()->bmul($u)->bmul($self->{'z'}); | ||
| 271 | #use Data::Dumper; | ||
| 272 | #print Dumper( map { $_->as_hex() } $u, $v, $x1, $y1, $z1, $x2, $y2, $z2, $v2, $v3, $x1v2, $zu2 ); | ||
| 273 | |||
| 274 | #// x3 = v * (z2 * (z1 * u^2 - 2 * x1 * v^2) - v^3) | ||
| 275 | #var x3 = zu2.subtract(x1v2.shiftLeft(1)).multiply(b.z).subtract(v3).multiply(v).mod(this.curve.q); | ||
| 276 | #my $x3 = $v * ($z2 * ($z1 * ($u ** 2) - 2 * $x1 * ($v ** 2)) - ($v ** 3)); | ||
| 277 | my $x3 = $u->copy()->bmul($u); | ||
| 278 | $x3->bmuladd( $z1, $x1->copy()->blsft($bi1)->bneg()->bmul($v)->bmul($v) ); | ||
| 279 | $x3->bmuladd( $z2, $v->copy()->bpow($bi3)->bneg() ); | ||
| 280 | $x3->bmul($v); | ||
| 281 | |||
| 282 | #// y3 = z2 * (3 * x1 * u * v^2 - y1 * v^3 - z1 * u^3) + u * v^3 | ||
| 283 | #var y3 = x1v2.multiply(THREE).multiply(u).subtract(y1.multiply(v3)).subtract(zu2.multiply(u)).multiply(b.z).add(u.multiply(v3)).mod(this.curve.q); | ||
| 284 | #my $y3 = $z2 * (3 * $x1 * $u * $v2 - $y1 * $v3 - $z1 * ($u ** 3)) + $u * $v3; | ||
| 285 | my $y3 = $u->copy()->bmul($bi3)->bmul($x1); | ||
| 286 | $y3->bmuladd($v2, $y1->bmul($v3)->bneg()); #no more y1 after this | ||
| 287 | $y3->bsub( $u->copy()->bpow($bi3)->bmul($z1) ); | ||
| 288 | |||
| 289 | $y3->bmuladd( $z2, $u->bmul($v3) ); #we don’t need $u anymore | ||
| 290 | |||
| 291 | #// z3 = v^3 * z1 * z2 | ||
| 292 | #var z3 = v3.multiply(this.z).multiply(b.z).mod(this.curve.q); | ||
| 293 | my $z3 = $v3->bmul($z1)->bmul($z2); | ||
| 294 | |||
| 295 | $_->bmod($self->{'curve'}{'q'}) for ($x3, $y3, $z3); | ||
| 296 | |||
| 297 | return (ref $self)->new( | ||
| 298 | $self->{'curve'}, | ||
| 299 | $self->{'curve'}->from_bigint($x3), | ||
| 300 | $self->{'curve'}->from_bigint($y3), | ||
| 301 | $z3, | ||
| 302 | ); | ||
| 303 | } | ||
| 304 | |||
| 305 | 1; |